algorithm - お気に入りのアルゴリズムとそれが教えてくれた教訓

Question

プログラミングや特定の言語機能について、最も多く学んだアルゴリズムは何ですか?

私たちは皆、進化のはしごを数段上ったプログラマーによって書かれたアルゴリズムを最終的に理解することに基づいて、将来のための重要な教訓を突然知った、ただ知っている、という瞬間を経験したことがあります。誰のアイデアとコードがあなたに魔法のような影響を与えましたか?

score 33 · Accepted Answer

一般的なアルゴリズム:

クイックソート (および平均的な複雑さの分析) は、入力をランダム化することが良いことであることを示しています!;
バランスの取れたツリー (たとえば、AVL ツリー)。検索と挿入のコストのバランスを取るための適切な方法です。
グラフのダイクストラおよびフォード-フルカーソンアルゴリズム (2 番目のアルゴリズムには多くのアプリケーションがあるという事実が気に入っています)。
圧縮アルゴリズムの LZ* ファミリー ( LZWなど)、データ圧縮は、私がそれを発見するまで (ずっと前に :) 魔法のように聞こえました);
FFT、ユビキタス（他の多くのアルゴリズムで再利用されます）;
シンプレックスアルゴリズムもユビキタスです。

数値関連:

2 つの整数の gcd を計算する Euclid のアルゴリズム。
整数の高速乗算 (例: Cooley-Tukey );
非常に強力なメタアルゴリズムであるルートを反転/検索するためのニュートン反復。

数論関連：

AGM関連のアルゴリズム (例): 円周率を計算するための非常にシンプルでエレガントなアルゴリズム (およびそれ以上のもの!) につながりますが、理論は非常に深遠です (ガウスは楕円関数とそこからモジュラー形式を導入したため、誕生したと言えます)代数幾何学へ...);
数体ふるい(整数因数分解用):非常に複雑ですが、非常に優れた理論的結果です (これは、PRIMES が P にあることを証明したAKSアルゴリズムにも当てはまります) 。

また、量子コンピューティング ( ShorアルゴリズムやDeutsch-Joszaアルゴリズムなど)の研究も楽しんでいました。

ご覧のとおり、私は数学指向のアルゴリズムに少し偏っています:)

score 19 · Accepted Answer

「反復することは人間であり、神を呪うこと」-1989年に大学で引用された。

PS参加への招待を待っている間にWoodgnomeによって投稿されました

score 12 · Accepted Answer

Floyd-Warshall全ペア最短経路アルゴリズム

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

クールな理由は次のとおりです。グラフ理論のコースで最短経路問題について最初に学ぶときは、おそらく、単一ソースの最短経路を解くダイクストラのアルゴリズムから始めます。最初はかなり複雑ですが、それを乗り越えて、完全に理解しました。

次に、先生は「今、同じ問題をすべてのソースで解決したい」と言います。「ああ、これはもっと難しい問題になるだろう！ダイクストラのアルゴリズムよりも少なくともN倍複雑になるだろう!!!」とあなたは思います。

それから先生はあなたにフロイド-ウォーシャルを与えます。そして、あなたの心は爆発します。次に、アルゴリズムがいかに美しく単純であるかを理解し始めます。これは、3つにネストされたループです。データ構造に単純な配列のみを使用します。

私にとって最も目を見張る部分は、次の認識です。問題Aの解決策があるとします。次に、問題Aを含むより大きな「超問題」Bがあります。問題Bの解決策は、実際には、問題A。

score 10 · Accepted Answer

ハフマン符号化は私のものです。私はもともと、テキストをエンコードするビット数を8からそれ以下に最小化することによって独自のダムバージョンを作成しましたが、周波数に応じてビット数を変えることは考えていませんでした。それから、雑誌の記事に記載されているハフマン符号化を見つけ、それは多くの新しい可能性を開きました。

score 10 · Accepted Answer

これは些細なことに聞こえるかもしれませんが、当時の私にとっては啓示でした。私は最初のプログラミングクラス (VB6) に参加していて、ちょうど教授が乱数について教えてくれたところで、彼は次の指示を出しました: 「仮想宝くじマシンを作成します。0 から 99 までの番号が付けられた 100 個のピンポン球でいっぱいのガラス球を想像してください。それらをランダムに選択し、それらがすべて選択されるまでその番号を表示し、重複はありません。」

他の誰もが次のようにプログラムを書きました: ボールを選び、その番号を「選択済みリスト」に入れ、別のボールを選びます。すでに選択されているかどうかを確認し、選択されている場合は別のボールを選び、そうでない場合はその番号を「選択済みリスト」に追加します....

もちろん、最終的には何百もの比較を行って、まだ選択されていないボールをいくつか見つけました。ボールを選んだ後、ボールを瓶に投げ込むようなものでした。私の啓示は、ピッキング後にボールを捨てることでした。

当たり前のことのように聞こえるかもしれませんが、これが私の頭の中で「プログラミングのスイッチ」が入った瞬間でした。これは、プログラミングが奇妙な外国語を学ぼうとする試みから、楽しいパズルを理解しようとする試みへと移行した瞬間でした。そして、プログラミングと楽しみの間に精神的なつながりができたら、本当に私を止めるものはありませんでした.

score 9 · Accepted Answer

クイックソート。それは、再帰が強力で有用である可能性があることを私に示しました。

score 7 · Accepted Answer

Bresenham の線画アルゴリズムは、私がリアルタイムグラフィックスレンダリングに興味を持つきっかけになりました。これは、3D モデルのレンダリングなどのために、三角形などの塗りつぶされたポリゴンをレンダリングするために使用できます。

score 6 · Accepted Answer

Recursive Descent Parsing - このような単純なコードで、一見複雑に見えることを実行できることに非常に感銘を受けたことを覚えています。

score 4 · Accepted Answer

Haskellのクイックソート：

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

当時、Haskellを書くことはできませんでしたが、このコードと、再帰とクイックソートアルゴリズムを理解しました。クリックするだけで、そこに...

score 3 · Accepted Answer

ミニマックスは、チェスプログラムは賢くないと教えてくれました。彼らはあなたができるよりも多くの動きを考えることができます。

score 3 · Accepted Answer

どういうわけか私はシュワルツ変換が好きです

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

ここで、foo（$ ）は、$ （リストの各項目を順番に）を取り、そのために比較される対応する値を生成する、計算集約型の式を表します。

score 3 · Accepted Answer

フィボナッチの反復アルゴリズム。私にとっては、最も洗練されたコード（この場合は再帰バージョン）が必ずしも最も効率的であるとは限らないという事実を突き止めたからです。

詳細に説明すると、「fib（10）= fib（9）+ fib（8）」アプローチは、fib（9）がfib（8）+ fib（7）に評価されることを意味します。したがって、fib（8）（したがって、fib7、fib6）の評価はすべて2回評価されます。

反復法（forloopのcurr = prev1 + prev2）は、この方法でツリー化されません。また、再帰スタックのnフレームではなく、一時変数が3つしかないため、多くのメモリを消費しません。

プログラミングをしているときは、シンプルでエレガントなコードを目指して努力する傾向がありますが、これは、これが優れたソフトウェアを作成するためのすべてではなく、最終的にはエンドユーザーがそうではないことを理解するのに役立ったアルゴリズムです。コードがどのように見えるかを気にします。

score 2 · Accepted Answer

これがアルゴリズムとして適格なのか、それとも単なる古典的なハックとして適格なのかはわかりません。どちらの場合でも、それは私が箱の外で考え始めるのを助けました。

中間変数を使用せずに2つの整数を交換します（C ++の場合）

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

score 2 · Accepted Answer

クイックソート：大学に入るまで、ブルートフォースバブルソートが最も効率的なソート方法であるかどうか疑問に思ったことはありませんでした。直感的にわかりやすいように見えました。しかし、クイックソートのような非自明な解決策にさらされることで、私は明白な解決策を通り越して、より良いものが利用可能かどうかを確認するようになりました。

score 2 · Accepted Answer

私にとっては、(1) 賢明に選択されたデータ構造 (およびそれに取り組んでいるアルゴリズム) がパフォーマンスにどれだけ影響を与えることができるか、(2) 古くてよく知られているデータ構造でも興味深いことが発見できることを示しているため、これは弱いヒープソートアルゴリズムです。もの。(weak-heapsort は、8 年後に証明された、すべてのヒープソートの中で最良のバリアントです。)

score 1 · Accepted Answer

フィボナッチの反復アルゴリズム。私にとっては、最も洗練されたコード（この場合は再帰バージョン）が必ずしも最も効率的であるとは限らないという事実を突き止めたからです。

反復法（forloopのcurr = prev1 + prev2）は、この方法でツリー化されません。また、再帰スタックのnフレームではなく、一時変数が3つしかないため、多くのメモリを消費しません。

フィボナッチには、固定されたステップ数で結果を直接計算できる閉形式のソリューションがあることをご存知ですか？つまり、（phi ^n-（1-phi）ⁿ）/ sqrt（5）です。これが整数を生成するはずだということは、常にいくらか注目に値することですが、実際にはそうです。

もちろん、ファイは黄金比です。（1 + sqrt（5））/2。

score 1 · Accepted Answer

これは遅いです:)

Duffs DeviceとXORスワップを理解することで、Cとコンピューターの両方について多くのことを学びました。

編集：

@ Jason Z、それは私のXORスワップです:)かっこいいですね。

score 1 · Accepted Answer

何らかの理由で、Bubble Sort は常に私にとって目立っていました。間抜けな名前があった/持っているという理由だけで、それがエレガントまたは良いからではありません.

score 1 · Accepted Answer

二分決定図は、正式にはアルゴリズムではなくデータ構造ですが、さまざまな種類の (ブール) 論理問題に対する洗練された最小限のソリューションにつながります。これらは、チップ設計のゲート数を最小限に抑えるために発明および開発されたものであり、シリコン革命の基礎の 1 つと見なすことができます。結果として得られるアルゴリズムは驚くほど単純です。

彼らが私に教えたこと：

問題を簡潔に表現することが重要です。小さいことは美しい
これを達成するために、再帰的に適用される制約/削減の小さなセットを使用できます
対称性の問題については、正準形式への変換を最初に検討する必要があります
すべての文学作品が読まれるわけではありません。Knuth は、BDD の発明/導入から数年後にその存在を知りました。（そしてそれらを調査するのにほぼ1年を費やしました）

score 1 · Accepted Answer

RSAはモジュラ演算の世界を教えてくれました。モジュラ演算を使用すると、驚くほど多くの興味深い問題を解決できます。

score 1 · Accepted Answer

好きなものはありません。美しいものはたくさんありますが、私がいつも興味をそそられるのは、ベイリー・ボーウェイン・プロフ (BBP) の公式です。前の数字についての知識なし。

score 1 · Accepted Answer

あまり教えてくれませんでしたが、Johnson-Trotter Algorithmは私の心を吹き飛ばすことに失敗しません。

score 0 · Accepted Answer

二重にリンクされたリストの1つの単語に2つのポインターを格納すると、Cで非常に悪いことができるという教訓が得られました（保守的なGCでは多くの問題が発生します）。

score 0 · Accepted Answer

@クリシュナクマール

ビット単位のソリューションは、再帰的なソリューションよりもさらに楽しいものです。

score 0 · Accepted Answer

二分探索は、最もシンプルで洗練されたアルゴリズムでなければなりません。そのため、データを並べ替える必要があります。このため、マージ並べ替えアルゴリズムも最もシンプルで洗練されています。

score 0 · Accepted Answer

私にとって、参照による呼び出しを示すためのKelly＆PohlのA Book on Cの単純な交換は、私が最初にそれを見たときに私をひっくり返しました。私はそれを見て、ポインターが所定の位置にスナップしました。逐語的。。。

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

score 0 · Accepted Answer

O(log N) でフィボナッチを計算するための行列演算の使用
大きな数の乗算にフーリエ変換を使用する

教訓は、非常に予想外の分野で解決策を見つけることができ、アルゴリズムと数学のさまざまな分野の間に非常に驚くべきつながりがあることです。

score 0 · Accepted Answer

ハノイの塔アルゴリズムは、最も美しいアルゴリズムの 1 つです。再帰を使用して、反復法よりもはるかに洗練された方法で問題を解決する方法を示しています。

あるいは、フィボナッチ数列の再帰アルゴリズムと数のべき乗の計算は、適切な値を提供するのではなく、再帰のために使用される再帰アルゴリズムの逆の状況を示しています。

score 0 · Accepted Answer

解決策について私が最も誇りに思っているのは、DisplayTag パッケージに非常によく似たものを作成したことです。コードの設計、保守性、再利用について多くのことを学びました。DisplayTagよりもかなり前に書いたもので、NDA契約に陥っていたので、オープンソースにすることはできませんでしたが、就職の面接では今でもそれについて噴出することができます.

score 0 · Accepted Answer

各数値を現在の素数のリストと比較し、見つからない場合は追加し、最後に素数のリストを返すことで、素数のリストを生成するアルゴリズム。いくつかの点で頭を悩ませていますが、その中でも特に、部分的に完成した出力を主要な検索基準として使用するというアイデアがあります。

score 0 · Accepted Answer

私のお気に入りではありませんが、素数性をテストするためのMiller Rabin Algorithmは、ほぼ常に正しいことで十分であることを示してくれました。(つまり、間違っている可能性があるという理由だけで、確率的アルゴリズムを信用しないでください。)

score 0 · Accepted Answer

マップ/リデュース。2 つの単純な概念を組み合わせると、大量のデータ処理タスクを簡単に並列化できます。

ああ...そして、それは超並列インデックス作成の基礎にすぎません:

http://labs.google.com/papers/mapreduce.html

algorithm - お気に入りのアルゴリズムとそれが教えてくれた教訓

33 に答える 33

Related

Reference