5

特定の「因数分解可能な」プロパティを持つ数値を計算する次の Clojure コードがあります。（コードが正確に何をするかは二次的なものです）。

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (factor-9 (quot n 10))))))

現在、私は TCO に夢中になっており、recurキーワードを使用して明示的に指示された場合にのみ、Clojure が末尾再帰を提供できることに気付きました。だから私はそれを行うためにコードを書き直しました（唯一の違いはrecurでfactor-9を置き換えます）：

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (recur (quot n 10))))))

私の知る限り、TCO には 2 つのメリットがあります。最初のものは、非末尾再帰呼び出しほどスタックを使用しないため、より大きな再帰でスタックを吹き飛ばさないことです。2つ目は、ループに変換できるため、結果として高速になると思います。

さて、私は非常に大まかなベンチマークを作成しましたが、2 つの実装の間に違いは見られませんでした。私の 2 番目の仮定は間違っていますか、それとも JVM (自動 TCO を持たない) で実行し、recurそれを達成するためのトリックを使用することに関係がありますか?

ありがとうございました。

4

4 に答える 4

6

recurを使用すると処理速度が向上しますが、再帰呼び出しでは（実際には）約3ナノ秒しかかかりません。物事がそのように小さくなると、残りのテストのノイズに隠れることがあります。パフォーマンスの違いを説明できる4つのテスト（以下のリンク）を作成しました。

また、ベンチマークの際には、クリテリウムのようなものを使用することをお勧めします。（Stack Overflowでは、評判がないため、複数のリンクを投稿することはできません。そのため、グーグルで検索する必要があります。おそらく「clojure基準」です）

フォーマットの理由から、私はテストと結果をこの要点に入れました。

簡単に比較すると、再帰テストが1の場合、ループテストは約0.45、TCOテストは約0.87であり、再帰テストとTCOテストの絶対差は約3nsです。

もちろん、ベンチマークに関するすべての警告が適用されます。

于 2011-01-09T22:51:33.570 に答える
2

コードを最適化するときは、潜在的または実際のボトルネックから始めて、最初に最適化することをお勧めします。

この特定のコードが CPU 時間のほとんどを消費しているように私には思えます。

 (map (fn [x] ,(Integer. (apply str x))) (permutations digits))

そして、それは TCO にまったく依存せず、同じ方法で実行されます。したがって、この特定の例の末尾呼び出しにより、すべてのスタックを使い果たすことはありませんが、パフォーマンスを向上させるには、これを最適化してみてください。

于 2011-01-09T13:17:25.777 に答える
1

clojure には TCO がないことを念のために言っておきます。

于 2011-01-09T19:54:54.730 に答える
-1

factor-9 (quot n 10)anを評価した後、関数が戻る前にandanを評価する必要があります。orしたがって、末尾再帰ではありません。

于 2011-01-09T13:17:09.110 に答える