[解決済み】純粋な関数型プログラミングの効率性

質問

命令的にではなく、純粋に機能的にプログラミングした場合に起こりうる最悪の漸近的な速度低下をご存知の方はいらっしゃいますか？

itowlson氏のコメントによる明確化 : 最善の非破壊アルゴリズムが最良の破壊アルゴリズムよりも漸近的に悪くなるような問題はありますか？

どのように解決するのですか？

によると ピッペンジャー［1996］ 純粋に関数的なLispシステム（遅延ではなく、厳密な評価セマンティクスを持つ）とデータを変異させることができるシステムを比較すると、不純なLisp用に書かれたアルゴリズムでO( n で実行される純粋なLispのアルゴリズムに翻訳することができる。 n ログ n )時間(work based on the work by ベンアムラムとガリル [1992]年 ポインタだけを使ったランダムアクセスメモリのシミュレーションについて)。Pippengerはまた、それが最善の方法であるアルゴリズムが存在することを立証しています。 n )である不純物系で、Ω( n ログ n )を純粋なシステムで実現する。

この論文については、いくつかの注意点があります。最も重要なのは、Haskellのような怠惰な関数型言語を扱っていないことである。 バード、ジョーンズ、デ・ムーア [1997］ は、ピペンガーが構築した問題が、遅延型関数型言語において、O( n しかし、遅延型関数型言語が突然変異を含む言語と同じ漸近的実行時間ですべての問題を解くことができるかどうかについては立証していません（私の知る限りでは、誰も立証していません）。

ピッペンジャーの作った問題では、Ω( n ログ n )は、この結果を得るために特別に構成されたものであり、必ずしも現実の問題を代表するものではありません。特に、この問題では、将来の入力にアクセスすることなくオンラインで結果を計算する必要があり、入力は固定サイズの集合ではなく、無限の可能性を持つアトムの集合からのアトムの列で構成される必要があるなど、少し意外な制限もありますが、証明が機能するためには必要です。また、この論文では、線形実行時間の不純物アルゴリズムに対する結果（下界）を確立しているだけで、より大きな実行時間を必要とする問題では、余分なO(log n 線形問題で見られる要素は、より大きな実行時間を持つアルゴリズムに必要な余分な操作の過程で吸収できる可能性がある。これらの解明と未解決の問題については、以下のサイトで簡単に検討されています。 ベンアムラム［1996］ .

実際には、多くのアルゴリズムは、純粋な関数型言語でも、ミュータブルなデータ構造を持つ言語と同じ効率で実装することができます。純粋に関数的なデータ構造を効率的に実装するために使うテクニックに関する良い参考文献として クリス岡崎のquot;純粋に関数的なデータ構造" [岡崎1998]を参照してください。 (これは彼の論文 [岡崎1996］ ).

純粋に機能的なデータ構造でアルゴリズムを実装する必要がある人は、岡崎を読むとよいでしょう。あなたは常に最悪の場合、O(log) n しかし、多くの場合、それよりもかなり良い結果を得ることができます。岡崎は、償却された技術から、償却された仕事を段階的に行うリアルタイム技術まで、多くの有用な技術を説明しています。純粋に関数的なデータ構造は、作業や分析が少し難しいかもしれませんが、参照透過性のように、コンパイラの最適化や並列・分散計算、バージョン管理、アンドゥ、ロールバックなどの機能の実装に役立つ多くの利点を提供します。

また、ここでは漸近的な実行時間のみを論じていることに注意してください。純粋に関数的なデータ構造を実装するための多くの技術は、それらが動作するために必要な余分な簿記や、問題の言語の実装の詳細のために、ある程度の定数ファクタの速度低下を与えます。純粋に関数的なデータ構造の利点は、これらの定数要因の速度低下を上回ることがあるので、一般に、問題の問題点に基づいてトレードオフを行う必要があります。

参考文献

• Ben-Amram, Amir and Galil, Zvi 1992. ポインタとアドレスの違いについて ACM誌, 39(3), pp.617-648, 1992年7月
• Ben-Amram, Amir 1996. "ピッペンジャーの純粋なLispと不純なLispの比較に関するメモ" 未発表原稿、DIKU、コペンハーゲン大学、デンマーク
• Bird, Richard, Jones, Geraint, and De Moor, Oege 1997. "More haste, less speed: Lazy versus Eager evaluation" Journal of Functional Programming 7, 5 pp. 541-547, September 1997
• 岡崎クリス 1996． 純粋な関数型データ構造 博士論文、カーネギーメロン大学
• 岡崎クリス 1998． 純粋な関数型データ構造 ケンブリッジ大学出版局、ケンブリッジ、イギリス
• Pippenger, Nicholas 1996. 純粋なLispと不純なLispの違い。 ACM Symposium on Principles of Programming Languages, ページ104-109, 1996年1月