6

「Clojure プログラミング」(98 ページ) のヘッド保持に関する段落を読んで、例で何が起こっているのか理解できませんでしたsplit-with。repl を試してみましたが、もっと混乱しました。

(time (let [r (range 1e7) 
            a (take-while #(< % 12) r)
            b (drop-while #(< % 12) r)]
        [(count a) (count b)]))
"Elapsed time: 1910.401711 msecs"
[12 9999988]

(time (let [r (range 1e7) 
            a (take-while #(< % 12) r)
            b (drop-while #(< % 12) r)]
        [(count b) (count a)]))
"Elapsed time: 3580.473787 msecs"
[9999988 12]

(time (let [r (range 1e7) 
            a (take-while #(< % 12) r)
            b (drop-while #(< % 12) r)]
        [(count b)]))
"Elapsed time: 3516.70982 msecs"
[9999988]

最後の例からわかるように、 を計算しないaと、時間がかかります。ここで何かを見逃したと思いますが、何ですか？

4

5 に答える 5

1

count関数は、ベクトルとリストを含むCountedコレクションのO(1) です。

一方、シーケンスはカウントされないため、countO(n) になります。ここで重要な部分は、関数take-whileとdrop-while戻りシーケンスです。彼らが怠け者でもあるという事実は、ここでは大きな要因ではありません。

于 2012-11-08T16:26:20.093 に答える
1

カウントは O(1) です。そのため、測定値はそれに依存しません。

于 2012-11-08T09:22:43.563 に答える
1

time aa ベンチマークを使用する場合は、テストを何度も実行して正確な結果を得る

user> (defn example2 [] (let [r (range 1e7)                                             
              a (take-while #(< % 12) r)                                     
              b (drop-while #(< % 12) r)]                        
             [(count a) (count b)]))
#'user/example2

user> (dorun (take 1000 (repeatedly example2)))
nil

user> (time (example2))
"Elapsed time: 614.4 msecs"
[12 9999988]

hotspot コンパイラは生成されたクラスをまだ完全に最適化していないため、実行時の差異が原因だと思います。1 番目と 2 番目の例を数回実行したところ、相対的な結果が混在していました。

例 1 を 2 回実行します。

autotestbed.core> (time (let [r (range 1e7)                                                                
                                        a (take-while #(< % 12) r)                                     
                                                    b (drop-while #(< % 12) r)]                        
                              [(count a) (count b)]))
"Elapsed time: 929.681423 msecs"                                                                           
[12 9999988]
autotestbed.core> (time (let [r (range 1e7)                                                                
                                        a (take-while #(< % 12) r)                                     
                                                    b (drop-while #(< % 12) r)]                        
                              [(count a) (count b)]))
"Elapsed time: 887.81269 msecs"                                                                            
[12 9999988]

次に、例 2 を数回実行します。

core> (time (let [r (range 1e7)                                                                
                  a (take-while #(< % 12) r)                                     
                  b (drop-while #(< % 12) r)]                        
             [(count a) (count b)]))
"Elapsed time: 3838.751561 msecs"                                                                          
[12 9999988]
core> (time (let [r (range 1e7)                                                                
                  a (take-while #(< % 12) r)                                     
                  b (drop-while #(< % 12) r)]                        
             [(count a) (count b)]))
"Elapsed time: 970.397078 msecs"                                                                           
[12 9999988]

場合によっては、2 番目の例も同様に高速です

于 2012-11-08T18:34:52.083 に答える
0

letこの値を使用しなくてもフォームでのバインディングが実行されます。

(let [x (println "Side effect")] 1)

上記のコードは「Side effect」を出力し、1 を返します。

あなたの 3 つの例はすべて、let 形式で同じバインディングを使用したため、ここでは違いがわかりません。ちなみに、私のマシンでは、すべてのスニペットにほぼ同じ時間がかかりました。

このようなことを試したときの本当の違い：

(time (let [r (range 2e7) 
        a (take 100 r)
        b (drop 100 r)]
    [(count a)]))
"Elapsed time: 0.128304 msecs"
[100]

(time (let [r (range 2e7) 
        a (take 100 r)
        b (drop 100 r)]
    [(count b)]))
"Elapsed time: 3807.591342 msecs"
[19999900]

bとaは遅延シーケンスであるため、時間内にcount動作しO(n)ます。しかし、最初の例では b のカウントを計算しないので、ほとんどすぐに機能します。

于 2012-11-08T10:55:26.870 に答える