お気に入りのアルゴリズムとそれが教えてくれた教訓 [終了]

Question

プログラミングや特定の言語機能について最も勉強になったのはどのアルゴリズムですか?

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

Answer 1

「反復することは人間であり、再帰することは神である」 - 1989 年に大学で引用。

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

Answer 2

一般的なアルゴリズム:

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

数値関連:

• 2 つの整数の gcd を計算する Euclid のアルゴリズム:最初のアルゴリズムの 1 つは、シンプルかつエレガントで強力ですが、多くの一般化が行われています。
• 整数の高速乗算 (クーリー・テューキー 例えば）;
• ニュートン反復による根の反転/検索。これは非常に強力なメタアルゴリズムです。

数論関連:

• 株主総会関連アルゴリズム (例):この理論は非常に奥深いものですが、円周率 (そしてそれ以上のもの!) を計算するための非常にシンプルで洗練されたアルゴリズムにつながります (ガウスは楕円関数とそこからモジュラー形式を導入したため、それが代数幾何学を生み出したと言えます...)。
• の 数値フィールドふるい (整数因数分解の場合): とても 複雑ですが、非常に優れた理論的結果です (これは AKS PRIMES が P にあることを証明したアルゴリズム。

量子コンピューティングの勉強も楽しかったです（ショール そして ドイチュ・ヨザ アルゴリズムなど):これは、既成概念にとらわれずに考えることを教えてくれます。

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

Answer 3

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 倍複雑になるでしょう!!!".

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

---

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

Answer 4

クイックソート. 。再帰が強力で便利であることがわかりました。

Answer 5

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

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

もちろん、最後までに彼らは何百もの比較を行って、まだ選ばれていないいくつかのボールを見つけました。ボールを選んだ後、ボールを瓶に戻すようなものでした。私の啓示は、ピック後にボールを投げ捨てることでした。

気が遠くなるような当たり前のことのように聞こえるかもしれませんが、これが私の頭の中で「プログラミングのスイッチ」が入った瞬間でした。これは、プログラミングが、見知らぬ外国語を学ぼうとすることから、楽しいパズルを見つけ出そうとすることに変わった瞬間でした。そして、プログラミングと楽しみの間に精神的なつながりができてしまえば、もう私を止めることはできませんでした。

Answer 6

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

Answer 7

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

Answer 8

再帰降下解析 - 一見複雑に見えることを、このような単純なコードでどのように実行できるのか、非常に感銘を受けたのを覚えています。

Answer 9

Haskell でのクイックソート:

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

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

Answer 10

フィボナッチの反復アルゴリズム。私にとって、最もエレガントなコード (この場合は再帰バージョン) が必ずしも最も効率的であるわけではないという事実がはっきりしたからです。

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

反復メソッド (for ループ内の curr = prev1 + prev2) は、この方法ではツリーアウトされず、再帰スタック内の n フレームではなく 3 つの一時変数のみであるため、それほど多くのメモリを必要としません。

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

Answer 11

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

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

ここで foo($) は、$ を必要とする計算集約型の式を表します。 (リストの各項目を順番に) そして、その目的のために比較される対応する値を生成します。

Answer 12

ミニマックス チェスのプログラムは賢いわけではなく、人間よりも先の手を考えられるだけだということを教えてくれました。

Answer 13

これがアルゴリズムと言えるのか、それとも単なる古典的なハックなのかはわかりません。いずれの場合でも、これは私が既成概念にとらわれずに考えるようになったのです。

中間変数を使用せずに 2 つの整数を交換する (C++ の場合)

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

Answer 14

クイックソート:大学に入学するまで、私は総当たりバブル ソートが最も効率的な並べ替え方法であるかどうか疑問に思ったことはありませんでした。それは直感的に明らかであるように思えました。しかし、クイックソートのような明白ではないソリューションに触れたことで、明白なソリューションを無視して、より良いものが利用可能かどうかを確認する必要があることを学びました。

Answer 15

私にとって、これはウィークヒープソート アルゴリズムです。なぜなら、このアルゴリズムは、(1) 賢明に選択されたデータ構造 (およびその上で動作するアルゴリズム) がパフォーマンスにどれだけ影響を与えることができるか、(2) 古くてよく知られているデータ構造であっても魅力的なものが発見できることを示すからです。もの。(weak-heapsort はすべてのヒープ ソートの中で最も優れたバリアントです。 証明された 8年後。）

Answer 16

これは遅いです:)

理解することで、C とコンピューター全般について多くのことを学びました。 ダフスデバイス そして XOR スワップ

編集：

@ジェイソン・Z, 、それが私の XOR スワップです:) 素晴らしいですね。

Answer 17

どういうわけか、バブルソートは常に私にとって印象的でした。単に間抜けな名前が付いているからといって、エレガントだからとか優れているからというわけではないと思います。

Answer 18

私は持っていない お気に入り -- 美しいものはたくさんあるので、選ぶのが大変ですが、私がいつも興味をそそられるのは、 ベイリー・ボーワイン・プルーフ (BBP) の式, を使用すると、前の桁に関する知識がなくても、円周率の任意の桁を計算できます。

Answer 19

RSA 私にモジュラー算術の世界を紹介してくれました。 解決する ある 驚くべき 番号 の 面白い 問題!

Answer 20

あまり教えてもらえなかったのですが、 ジョンソン・トロッターアルゴリズム いつも私の心を驚かせます。

Answer 21

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

彼らが私に教えてくれたこと:

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

Answer 22

私にとっては、ケリーとポールの単純な交換です C に関する本 参照渡しのデモを最初に見たときはびっくりしました。それを見ると、ポインタが所定の位置に収まりました。逐語的に。。。

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

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

Answer 23

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

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

Answer 24

フィボナッチの反復アルゴリズム。私にとって、最もエレガントなコード (この場合は再帰バージョン) が必ずしも最も効率的であるわけではないという事実がはっきりしたからです。

反復メソッド (for ループ内の curr = prev1 + prev2) は、この方法ではツリーアウトされず、再帰スタック内の n フレームではなく 3 つの一時変数のみであるため、それほど多くのメモリを必要としません。

フィボナッチには、固定ステップ数で結果を直接計算できる閉じた形式の解があることはご存知ですか?すなわち、(ファイⁿ - (1 - ファイ)ⁿ) / sqrt(5)。これで整数が得られるということは、いくぶん驚くべきことだといつも思いますが、実際にそうなります。

もちろんファイは黄金比です。(1 + sqrt(5)) / 2.

Answer 25

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

Answer 26

二重リンクリストの 1 つのワードに 2 つのポインタを格納するということは、実際に C では非常に悪いことができるという教訓を私に与えてくれました (保守的な GC では多くの問題が発生するでしょう)。

Answer 27

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

Answer 28

マップ/リデュース。2 つの単純な概念を組み合わせることで、データ処理タスクの負荷を並列化しやすくします。

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

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

Answer 29

私のお気に入りではありませんが、 ミラーラビンアルゴリズム 素数性をテストした結果、ほぼ常に正しいということは、ほぼ常に十分に良いことであることがわかりました。(すなわち、確率的アルゴリズムが間違っている可能性があるからといって、そのアルゴリズムを信用しないでください。)

Answer 30

@クリシュナ・クマール

ビットごとの解決策は、再帰的解決策よりもさらに楽しいです。