Hatena::ブログ(Diary)

分室の分室 このページをアンテナに追加

2014-03-24 Mon

【443】(uniq)

 今回は Scheme オンリーのネタ。データ探索の勉強をするなら uniq も必要かと。昨年、ソートせずに uniq するやつを作った。

2013-06-13 Thu【405】Script-Fu で uniq
http://d.hatena.ne.jp/foussin/20130613

 これは sort せずに uniq するやつで、総当たり戦方式の二重ループだった。総当たり戦といっても比較対象のリストは次第に短くなってくるので(cdr のお陰でね)、そんなに酷いコードではなかったと思う。ついでなので、引数を受け取る形に修正してみた。↓

; sort を使わず いきなり unique (全データを比較)
(define (unique ls)
  ; next-loop の戻り値は (n) or () (マッチしなければ (n) を返す)
  (define (next-loop n ls)
    (cond
      ((null? ls) (list n))
      ((= n (car ls)) '())
      (else (next-loop n (cdr ls)))
      ))
  (let loop ((n (car ls)) (ls (cdr ls)) (a '()))
    (if (null? ls)
      (append a (list n)) ; 最後の n は必ず追加
      (loop (car ls) (cdr ls) (append a (next-loop n ls)))
      )))

実行例:

gosh> (load "./func.scm")
#t
gosh> (unique '(9 5 3 4 6 8 9 0 3 2))
(5 4 6 8 9 0 3 2)
gosh>

 ただし、実行例を見れば分かるとおり重複データは最後にマッチした要素が生き残る仕様になっている。今のところ、重複指定された引数をユニークにするために使っているだけだったかな。他にどんな使い方があるのかは、自分でもよく分からない。データ探索の勉強用のサンプルデータとしては使えるだろうけど…。


 通常の uniq はソート済みのデータ群に対して適用される。データがソート済みなら 1個のループでいい(隣接データを比較するだけ)。だが、ソートの実行コスト分も加えて考えると、効率の良し悪しはソーティング効率の良し悪しで決まってくる。で、sort と uniq を別々に実行する場合、uniq のためのループが余計に必要になるのは仕方がないね……

; sort 済みデータを uniq (隣接データを比較)
(define (uniq ls)
  (let ((n1 (car ls)) (ls (cdr ls)))
    (let loop ((n1 n1) (n2 (car ls)) (ls (cdr ls)) (a '()))
      (if (null? ls)
        (append a
          (if (= n1 n2) (list n1) (list n1 n2)))
        (if (= n1 n2)
          (loop n2 (car ls) (cdr ls) a)
          (loop n2 (car ls) (cdr ls) (append a (list n1)))
          )))))

実行例:

gosh> (unique '(9 5 3 4 6 8 9 0 3 2 1 7 3 1 1 2 5 15))
(4 6 8 9 0 7 3 1 2 5 15)                    ; sort せずにユニークにする
gosh> (uniq '(9 5 3 4 6 8 9 0 3 2 1 7 3 1 1 2 5 15))
(9 5 3 4 6 8 9 0 3 2 1 7 3 1 2 5 15)        ; 隣接重複データだけ消す
gosh> (uniq (sort '(9 5 3 4 6 8 9 0 3 2 1 7 3 1 1 2 5 15)))
(0 1 2 3 4 5 6 7 8 9 15)                    ; sort すればユニークになる
gosh> (uniq (sort '(9 5 3 4 6 8 9 0 3 2 1 7 3 1 1 2 5 15 15)))
(0 1 2 3 4 5 6 7 8 9 15)
gosh> (uniq (sort '(9 5 3 4 6 8 9 0 3 2 1 7 3 1 1 2 5 15 15 15)))
(0 1 2 3 4 5 6 7 8 9 15)


 今やってるのは、あとで色々と実験をするための下準備。で、下準備は、もうしばらく続く。。。