1

したがって、リスト内の最大要素を見つけるには、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))))))

これは実際に高速ですか？漸近的な時間の複雑さは (タイト バウンド) であると思いますか?

4

1 に答える 1

13

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

選択の問題に関する詳細なデータは次のとおりです

私はそれについて考え、おそらくこれを事実として述べる以上のことをするべきだと気づきました。だから私はクイックスピードテストをコーディングしました。完全に開示しましたが、私はSchemeプログラマーではないので、これはCommon Lispにありますが、アルゴリズムを忠実に変換したと思います。

;; 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))))

ここで、リストサイズに10000しか使用していない理由を自問しているかもしれません。これは、漸近計算では実際にはかなり小さいためです。真実は、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になると、各アイテムを直接チェックするまでに約100万アイテムに増加します。

 (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番目のアルゴリズムが実際にそれほど長くかかっている理由です。末尾再帰の除去について詳しく説明しなくても、実際に飛び出すことがいくつかあります。

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

于 2012-02-15T08:13:46.260 に答える