dedup.rkt

#lang racket/base

(require file/sha1
         racket/list
         racket/random)

(define N 1000000)
(define symbol-length 5)

(define (random-string n)
  (let* ([ half-n       (ceiling (/ n 2))                ]
         [ random-bytes (crypto-random-bytes half-n)     ]
         [ str          (bytes->hex-string random-bytes) ])
    (if (even? n)
        str
        (substring str 0 n))))

(define (random-symbols n)
  (let loop ([ n n ][ result '() ])
    (if (< n 1)
        result
        (loop (sub1 n) (cons (string->symbol (random-string symbol-length)) result)))))

(define (sort-and-dedup-1 lst)
  (remove-duplicates (sort lst symbol<?) eq?))

(define (sort-and-dedup-2 lst)
  (let loop ([ lst (sort lst symbol<?) ][ result '() ][ prev #f ])
    (if (null? lst)
        (reverse result)
        (let ([ s (car lst) ])
          (if (eq? s prev)
              (loop (cdr lst) result prev)
              (loop (cdr lst) (cons s result) s))))))

(define (sort-and-dedup-3 lst)
  (let loop ([ lst (sort lst symbol<?) ][ result '() ][ prev #f ])
    (if (null? lst)
        result
        (let ([ s (car lst) ])
          (if (eq? s prev)
              (loop (cdr lst) result prev)
              (loop (cdr lst) (cons s result) s))))))

(define (sort-and-dedup-4 lst)
  (define (dedup lst prev)
    (if (null? lst)
        '()
        (let ([ s (car lst) ])
          (if (eq? s prev)
              (dedup (cdr lst) prev)
              (cons s (dedup (cdr lst) s))))))

  (dedup (sort lst symbol<?) #f))

(define (sort-and-dedup-5 lst)
  (sort (remove-duplicates lst eq?) symbol<?))

(let ([ lst (random-symbols N) ])
  (time (sort-and-dedup-1 lst)
        (void))
  (time (sort-and-dedup-2 lst)
        (void))
  (time (sort-and-dedup-3 lst)
        (void))
  (time (sort-and-dedup-4 lst)
        (void))
  (time (sort-and-dedup-5 lst)
        (void))
  )