3

私は Lisp ファミリーの言語のトレーニングを受けており、現在は自分のために Haskell を少し学んでいます。Lisp では、関数型スタイルは問題ありませんが、適切なパフォーマンスを得るために命令型スタイルが必要な場合がいくつかあります。

  • 追加

    最初の引数をコピーする必要があるため、追加は低速です (場合によっては、削除に成功したバージョンの 100 倍の速度になります)。解決策は、追加する代わりに、最初のリストの最後のポインターを 2 番目のリストの先頭に移動することです。もちろん、これは破壊的な操作です。

  • 選別

    クイックソートの機能的なバージョンは、多くの中間リストを作成します。これは、可能な限り高速にするというアルゴリズムの目的を何らかの形で無効にします。AFAIR、一般的なlispでは、ソートは機能バージョンを持たない唯一の破壊的な関数です。

  • 長さ

    リストの長さを取得するにはリスト全体を調べなければならないため、これは Lisp ではコストのかかる操作です。これはそうである必要はありません.afaik clojureはリストの長さを対数時間で計算します. 解決策は、多くの場合、命令型ループでオンザフライで長さを計算することです。

私の質問は、haskell でこれらの問題にどのように対処するかです。

4

2 に答える 2

3

append普遍的なものではありません。両端キューへの追加は、コンス リストへの追加とは異なります。破壊的な追加は、コピーオン追加とは異なります。基準に応じて、遅さ、スレッド セーフ、またはシンプルさを最適化することができ、「問題」の定義が変わります。

delnan と Thomas DuBuisson が言及しているように、適切なデータ型を選択すれば、Haskell にはこれらすべてのオプションがあります。

したがって、最適化したい特定のアルゴリズムがある場合は、それを高速な非破壊バージョンに変換する方法、通常は乗算的なlog(n)スローダウンで破壊をシミュレートするオプション、または参照透過的に実行するオプションのいずれかが存在する可能性があります。相加的な一定の減速での破壊。

この変換の問題の良い例については、persistent union-find または Functional Graph Library のアルゴリズムを見てください。

于 2013-08-04T21:17:33.347 に答える