algorithm - 命令型アルゴリズムよりも高速な関数型アルゴリズムはありますか?

Question

命令型よりも高速な関数型のアルゴリズム (またはそのようなアルゴリズムの引数) を探しています。

私が関数型コードを好むのは、それが命令的なペンダントよりも表現力豊かで読みやすいからです。しかし、この表現力によって実行時のオーバーヘッドが発生する可能性があることも知っています。常に末尾再帰などの手法が原因であるとは限りませんが、多くの場合、処理が遅くなります。

最近の PC は非常に高速であり、開発時間はランタイムよりもコストがかかるため、プログラミング中は機能コードのランタイムコストについては考えません。さらに、私にとって読みやすさはパフォーマンスよりも重要です。それにもかかわらず、私のプログラムは十分に高速なので、命令的な方法で問題を解決する必要はめったにありません。

実際には命令型スタイル (ソートアルゴリズムなど) で実装する必要があるアルゴリズムがいくつかあります。そうしないと、ほとんどの場合、遅すぎるか、大量のメモリが必要になります。対照的に、関数型言語で記述されたパーサーのようなプログラム全体のパターンマッチングなどの手法により、コンパイラがコードを最適化する可能性があるため、命令型言語で記述されたパーサーよりもはるかに高速になる場合があります。

しかし、関数型スタイルでより高速なアルゴリズムはありますか、またはそのようなアルゴリズムの引数を設定する可能性はありますか?

score 14 · Accepted Answer

簡単な推論。用語を保証するものではありませんが、理にかなっているようです。

実行される関数プログラムは、機械語命令のセットに変換する必要があります。
すべてのマシン (私が聞いたことがあります) は不可欠です。
したがって、すべての関数型プログラムには、それに相当する命令型プログラム (大まかに言えば、アセンブラー言語で) があります。

したがって、「機能するコンピュータ」が完成するまでは、おそらく「表現力」に満足する必要があります。

score 5 · Accepted Answer

簡単な答え：

副作用がないために簡単に並列化できるものは、マルチコアプロセッサ上で高速になります。

たとえば、QuickSort は、不変のコレクションで使用すると非常にうまくスケールアップします: http://en.wikipedia.org/wiki/Quicksort#Parallelization

他のすべてが等しい場合、1 つが不変データに対して純粋な関数を使用し、2 つ目がインプレースミューテーションに依存していることを除いて、同等であると合理的に説明できる 2 つのアルゴリズムがある場合、最初のアルゴリズムは複数のコアに簡単にスケールアップします。 .

GPU で実行するコードをコンパイルする scalaCL プラグインのように、プログラミング言語がこの最適化を実行できる場合もあります。（SIMD命令がこれを「機能的な」プロセッサにするかどうか疑問に思っています）

したがって、並列ハードウェアが与えられた場合、最初のアルゴリズムのパフォーマンスが向上し、コアが多いほど、差が大きくなります。

score 3 · Accepted Answer

FWIW関数型プログラミングの恩恵を受ける純粋に関数型のデータ構造があります。

Chris Okasaki によるPurely Functional Data Structuresに関する素晴らしい本もあり、関数型言語の観点からデータ構造を提示しています。

もう 1 つの興味深い記事Announce Intel Concurrent Collections for Haskell 0.1では、並列プログラミングについて次のように述べられています。

さて、CnC のステップの概念が純関数であるということが起こります。ステップは、その入力を読み取り、タグとアイテムを出力として生成するだけです。この設計は、決定論的並列処理と呼ばれるとらえどころのない素晴らしい場所に CnC をもたらすために選択されました。この決定は、言語の好みとは何の関係もありませんでした。(実際、主要な CnC 実装は C++ と Java 用です。)

それでも、Haskell と CnC はなんと素晴らしい組み合わせでしょう! Haskell は、(1) ステップが純粋であることを強制し、(2) ステップとグラフ実行の両方が純粋であるという事実を直接認識 (および活用!) できる唯一の主要な言語です。

それに加えて、Haskell は驚くほど拡張性が高いため、CnC の「ライブラリ」はほとんどドメイン固有の言語のように感じることができます。

パフォーマンスについては触れていません。実装の詳細とパフォーマンスについては今後の投稿で説明する予定ですが、Haskell の「純粋さ」は並列プログラミングにうまく適合します。

score 1 · Accepted Answer

すべてのプログラムは機械語に帰結すると主張する人もいるかもしれません。

したがって、(命令型プログラムの) マシンコードを逆アセンブルし、アセンブラを微調整すると、より高速なプログラムになる可能性があります。または、特定の CPU 機能を利用する「アセンブラーアルゴリズム」を考え出すこともできます。そのため、命令型言語バージョンよりも実際に高速です。

この状況は、どこでもアセンブラを使用する必要があるという結論につながりますか? いいえ、命令型言語を使用することにしました。扱いにくいからです。本当に必要なので、アセンブラでピースを書きます。

理想的には、FP アルゴリズムはコーディングが面倒ではないため、FP アルゴリズムも使用し、本当に必要な場合は命令型コードを使用する必要があります。

score 0 · Accepted Answer

ええと、同じアルゴリズムの別の実装よりも高速な関数型プログラミング言語のアルゴリズムの実装があるかどうかを尋ねるつもりだったと思いますが、命令型言語です。「より速い」とは、信頼できると見なされる測定に従って、一部の入力で実行時間またはメモリフットプリントの点でパフォーマンスが向上することを意味します。

私はこの可能性を排除しません。:)

score 0 · Accepted Answer

Yasir Arsanukaevの答えを詳しく説明すると、純粋に機能的なデータ構造は、構造の一部を共有しているため、状況によっては変更可能なデータ構造よりも高速になる可能性があります。したがって、配列全体またはリスト全体を命令型言語でコピーする必要がある場所では、データ構造のごく一部しか変更 (およびコピー) できないため、コピーの一部で済みます。関数型言語のリストはこのようなものです。何も変更できないため、複数のリストが同じテールを共有できます。(これは命令型言語で行うことができますが、通常はそうではありません。命令型パラダイム内では、人々は通常、不変データについて話すことに慣れていないためです。)

また、関数型言語 (特にデフォルトで遅延する Haskell) での遅延評価も、コードの結果が実際に使用されない場合にコードの実行を排除できるため、非常に有利です。(ただし、このコードを命令型言語で最初から実行しないように注意する必要があります。)

algorithm - 命令型アルゴリズムよりも高速な関数型アルゴリズムはありますか?

6 に答える 6

Related

Reference