リストのuniq

30分プログラム、その82。エロと風俗情報満載 どう抜く？よりアレイのuniq。

irb(main):001:0> xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
=> [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
irb(main):002:0> xs.uniq
=> [3, 1, 4, 5, 9, 2, 6, 8, 7]

例はRubyだけど、書くのはScheme。

(use srfi-1)
(define (uniq1 xs)
  (if (null? xs)
      ()
      (cons
       (car xs)
       (uniq (delete (car xs) (cdr xs))))))

(define (uniq2 xs) 
  (define (sub acc xs)
    (cond 
     ((null? xs) 
      (reverse acc))
     ((find (lambda(x) (eq? x (car xs))) acc)
      (sub acc (cdr xs)))
     (#t
      (sub (cons (car xs) acc)
	   (cdr xs)))))
  (sub '() xs))

(define (uniq3 xs)
  (let1 table (make-hash-table)
	(define (sub acc xs)
	  (cond 
	   ((null? xs) 
	    (reverse acc))
	   ((hash-table-get table (car xs) #f)
	    (sub acc (cdr xs)))
	   (else
	    (hash-table-put! table (car xs) #t)
	    (sub (cons (car xs) acc)
		 (cdr xs)))))
  (sub '() xs)))

uniq1,uniq2はO(n*n)、uniq3はO(n)だと思う。ハッシュの計算はO(1)と仮定してるけど。
実際に時間を図ってみる。

gosh> (time (uniq1 (iota 5000)))
;(time (uniq1 (iota 5000)))
; real   1.417
; user   1.150
; sys    0.010

gosh>(time (uniq2 (iota 5000)))
;(time (uniq2 (iota 5000)))
; real   3.853
; user   3.470
; sys    0.020

gosh> (time (uniq3 (iota 5000)))
;(time (uniq3 (iota 5000)))
; real   0.026
; user   0.010
; sys    0.000

• ハッシュ最高!破壊代入最高!!
• 意外とdeleteが早いんですね
• こういうクイズを解くときはネタ切れの証