☰

純粋関数型プログラミングの効率性 質問する

tag-icon • tag-icon algorithm functional-programming performance
純粋関数型プログラミングの効率性 質問する

命令型ではなく純粋に機能的にプログラミングする場合（つまり、副作用を許可する場合）に発生する可能性のある最悪の漸近的速度低下が何であるかを知っている人はいますか?

itowlson のコメントからの説明: 最もよく知られている非破壊アルゴリズムが、最もよく知られている破壊アルゴリズムよりも漸近的に劣る問題はありますか? もしそうなら、どの程度劣るのでしょうか?

ベストアンサー1

によるとピッペンジャー [1996]純粋に関数的な（そして厳密な評価セマンティクスを持ち、遅延評価ではない）Lispシステムとデータを変更できるLispシステムを比較すると、不純なLisp用に書かれたO(n)で実行されるアルゴリズムは、純粋なLispではO( nlogn )で実行されるアルゴリズムに変換できる（ベン・アムラムとガリル [1992]ピッペンガーは、それが最善の方法であるアルゴリズムがあることも明らかにしています。つまり、純粋システムでは Ω( n log n ) である問題が、不純システムでは O( n ) である問題もあるということです。

この論文にはいくつか注意すべき点があります。最も重要なのは、Haskell などの遅延関数型言語については触れられていないことです。バード、ジョーンズ、デ・ムーア [1997]Pippenger によって構築された問題が遅延関数型言語で O( n ) 時間で解決できることを実証していますが、遅延関数型言語が突然変異を伴う言語と同じ漸近実行時間ですべての問題を解決できるかどうかは実証していません (私の知る限り、誰も実証していません)。

Pippenger が構築した問題では、Ω( n log n ) は、この結果を達成するために特別に構築されており、必ずしも実用的な現実の問題を代表するものではありません。この問題には、予想外ではあるものの、証明が​​機能するために必要となるいくつかの制約があります。特に、この問題では、結果がオンラインで計算され、将来の入力にアクセスできないこと、入力が固定サイズのセットではなく、可能性のある原子の無制限のセットからの原子のシーケンスで構成されることが求められます。また、この論文では、線形実行時間の不純なアルゴリズムの結果 (下限) のみを確立しています。より長い実行時間を必要とする問題の場合、線形問題で見られる余分な O(log n ) 係数は、より長い実行時間のアルゴリズムに必要な追加の操作のプロセスで「吸収」できる可能性があります。これらの説明と未解決の問題は、ベン・アムラム [1996]。

実際には、多くのアルゴリズムは、変更可能なデータ構造を持つ言語と同じ効率で純粋関数型言語で実装できます。純粋関数型データ構造を効率的に実装するためのテクニックに関する優れた参考資料については、以下を参照してください。クリス・オカサキの「純粋関数型データ構造」[Okasaki 1998]（これは彼の論文の拡張版である[岡崎 1996]）。

純粋関数型データ構造にアルゴリズムを実装する必要がある人は、Okasaki を読むべきです。可変メモリをバランスのとれたバイナリ ツリーでシミュレートすると、操作ごとに最悪でも O(log n ) の速度低下が発生しますが、多くの場合、それよりも大幅に改善できます。Okasaki は、償却手法から償却作業を段階的に実行するリアルタイム手法まで、多くの便利な手法を説明しています。純粋関数型データ構造は、操作や分析が少し難しい場合がありますが、コンパイラの最適化、並列および分散コンピューティング、バージョン管理、元に戻す、ロールバックなどの機能の実装に役立つ参照透過性など、多くの利点があります。

また、これらすべては漸近的な実行時間についてのみ説明していることにも注意してください。純粋に機能的なデータ構造を実装するための多くの手法では、動作するために必要な追加の記録と、問題の言語の実装の詳細により、一定量の定数倍の速度低下が発生します。純粋に機能的なデータ構造の利点は、これらの定数倍の速度低下を上回る可能性があるため、通常は問題に基づいてトレードオフを行う必要があります。

参考文献

おすすめ記事