より速いスキーム機能？

Question

したがって、リスト内の最大要素を見つけるには、O（n）時間の複雑さが必要です（リストにn個の要素がある場合）。より速く見えるアルゴリズムを実装しようとしました。

(define (clever-max lst) 
    (define (odd-half a-list) 
    (cond ((null? a-list) (list)) 
      ((null? (cdr a-list)) 
      (cons (car a-list) (list))) 
      (else 
      (cons (car a-list) 
       (odd-half (cdr (cdr a-list))))))) 
    (define (even-half a-list) 
    (if (null? a-list) 
     (list) 
     (odd-half (cdr a-list)))) 
    (cond ((null? lst) (error "no elements in list!")) 
     ((null? (cdr lst)) (car lst)) 
     (else 
     (let ((l1 (even-half lst)) 
       (l2 (odd-half lst))) 
      (max (clever-max l1) (clever-max l2)))))) 

これは実際には高速ですか？あなたは漸近的な時間の複雑さは（締め固められた）とは何と言うでしょうか？

Answer 1

あなたが何も知らないデータのリストがあれば、各要素を調べることなく最大の要素を見つける方法がないので、チェックしないと、それを見逃す可能性があるので、O(n)時間です。だから、あなたのアルゴリズムはO(n)より速くはありません。基本的にはマージソートを実行しているので、実際はO(n log n)です。

は、ここで私はそれについて考え、私はおそらくちょうど事実としてこれを述べるよりも、もう少し何かを行う必要があります実現Selection problem

に、より多くのデータです。だから私はクイックスピードテストをコーディングしました。今では全面的な開示、私はSchemeのプログラマーではないので、これはCommon Lispにありますが、アルゴリズムを忠実に変換したと思います。本当にそれは漸近的な計算のためにかなり小さいので、あなたは、私が唯一、リストのサイズのために10000を使用していますなぜ

;; Direct "iteration" method -- theoretical O(n) 
(defun find-max-001 (list) 
    (labels ((fm (list cur) 
      (if (null list) cur 
       (let ((head (car list)) 
        (rest (cdr list))) 
       (fm rest (if (> head cur) head cur)))))) 
    (fm (cdr list) (car list)))) 

;; Your proposed method 
(defun find-max-002 (list) 
    (labels ((odd-half (list) 
      (cond ((null list) list) 
        ((null (cdr list)) (list (car list))) 
        (T (cons (car list) (odd-half (cddr list)))))) 
      (even-half (list) 
      (if (null list) list (odd-half (cdr list))))) 
    (cond ((null list) list) 
      ((null (cdr list)) (car list)) 
      (T (let ((l1 (even-half list)) 
        (l2 (odd-half list))) 
       (max (find-max-002 l1) (find-max-002 l2))))))) 

;; Simplistic speed test    
(let ((list (loop for x from 0 to 10000 collect (random 10000)))) 
    (progn 
    (print "Running find-max-001") 
    (time (find-max-001 list)) 
    (print "Running find-max-002") 
    (time (find-max-002 list)))) 

今、あなたはあなたの自己を尋ねることができます。真実は、最初の関数が末尾再帰であることをsbclが認識しているため、ループに抽象化しますが、2番目の関数ではないので、スタックを強制終了せずに得ることができるほど大きくなります。以下の結果から分かるように、これはポイントを説明するのに十分です。

"Running find-max-001" 
Evaluation took: 
    0.000 seconds of real time 
    0.000000 seconds of total run time (0.000000 user, 0.000000 system) 
    100.00% CPU 
    128,862 processor cycles 
    0 bytes consed 

"Running find-max-002" 
Evaluation took: 
    0.012 seconds of real time 
    0.012001 seconds of total run time (0.012001 user, 0.000000 system) 
    [ Run times consist of 0.008 seconds GC time, and 0.005 seconds non-GC time. ] 
    100.00% CPU 
    27,260,311 processor cycles 
    2,138,112 bytes consed 

このレベルでさえ、私たちは大規模な減速について話しています。一度メソッドを実行すると、アルゴリズムの評価が10kまで遅くなります。

(let ((x (loop for x from 0 to 1000000 collect (random 1000000)))) 
    (time (find-max-001 x))) 

Evaluation took: 
    0.007 seconds of real time 
    0.008000 seconds of total run time (0.008000 user, 0.000000 system) 
    114.29% CPU 
    16,817,949 processor cycles 
    0 bytes consed 

最終的な考えや結論

第2のアルゴリズムは本当に多くの時間がかかっている理由を尋ねたそうする必要がある次の質問です。 tail recursion eliminationについて詳しく説明することなく、実際に飛び出すいくつかのことがあります。

最初のものはconsです。はい、consはO(1)ですが、それでもシステムを通過する別の操作です。また、システムはメモリを割り当てて解放する必要があります（ガベージコレクタを起動する必要があります）。 2番目のことは本当に飛び出します。基本的にマージソートを実行しているのは、リストの下半分と上半分を取得するだけでなく、偶数ノードと奇数ノードを取得していることです（これはまた、リストを作成する時間）。ここではO(n log n)というアルゴリズムを使用しています（ソートには本当に良いマージソートです）が、余分なオーバーヘッドが多くなります。