14

私はGHC7.4を使用して次の関数をコンパイルしています。

nodups' :: [Int] -> Bool
nodups' = ok empty
  where ok _ [] = True
        ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns
        member n word = testBit word n
        insert n word = setBit word n
        empty = 0 :: Int

この関数は、小さな整数のリストから重複する要素を探します。セットseenは、ビットベクトルとしての小さな整数のセットの表現です。プロファイラー（で実行）は、関数が全体の割り当ての22％を占めるとghc -prof -auto-all主張しています。okで出力を見ると、-ddump-simplなぜこのコードが割り当てられているのか理解できません。確認しましたが、私が知る限り、への呼び出しにサンクを割り当てていませんinsert。

コードの割り当て部分を特定するには、何を確認する必要がありますか？

4

1 に答える 1

1

一般的

私は関数型言語の単純な (科学的な) 実装を知っています。私の記憶が正しければ、Haskell で使用できるG-Machineがあります。

これは、(私の記憶が正しければ) プログラムの状態が「ツリー」のように表されることを意味します。ノードは (ここでは簡単にするために) コードで使用する関数です。リーフはそれに対する引数になります。次に、「G-Maschine」は「スパイン」(ノードの左側のチェーン) に沿って検索し、利用可能な「関数」(「スーパーコンビネーター」?) のセットを検索して、適用できるパターン マッチを探します。定義の左側から問題一致が認識された場合は、定義の右側に置き換えられます。

これは、次のような単純な行でも

ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns

あるいは

(n:ns) = ns

コンピューターのメモリ内で何かを実行している、つまりパターンに一致している

       ...
     ...
    (:)
   /   \
  n     ns

そしてそれを

       ...
     ...
    ns

最終結果は入力より少ないメモリを消費する可能性がありますが、これは動的なステップであるため、どこかで実行する必要があります。これが何度も (「タイト ループ」で) 繰り返されると、G マシンが動作しているという理由だけで、CPU がビジー状態になり、メモリもビジー状態になります。(私が言ったように、G-Machine の概念がここに当てはまるかどうかはわかりませんが、似たようなものだと思います)。

具体的な推測

    member n word = testBit word n
    insert n word = setBit word n

それに加えて、私はいくつかの疑いを持っています。testBitリストのインデックス操作のようにsetBit見えます。もしそうなら、それはいくつかの作業が必要になる可能性があります。それらが適切な配列であれば、問題ありません。それらが一種のマップまたはセットである場合...まあ...コストのかかるハッシュが含まれる可能性がありますか? それとも、多くの (コストのかかる?) 比較操作を使用するバランスの取れたツリーを介して実装されますか?

于 2012-12-18T09:45:49.123 に答える