4chan BBS - Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
多倍長整数演算の速度比較 - まめめも
ruby 、perl 、python の多倍長整数演算の速度を適当に比較してみました。フィボナッチ数の計算速度比較以上にどーでもいい比較です。 前置き 使用した処理系のバージョンはそれぞれ以下のとおりです。 ruby 1.9.0 (2008-01-16 revision 0) perl v5.10.0 python 3.0a2 perl は多倍長整数を扱う方法が何個かあるようなので、標準装備らしい bigint と、別途 CPAN でインストールしないといけない Math::BitInt::GMP (GMP の binding) の 2 種類を試しました。python の psyco はなんか動かなくて面倒だったので試してません。この比較にはあまり影響しないような気がしてます。僕は Perl と Python は素人なので、もっと速くて美しい書き方・やり方があったら教えてください。 実験
カラツバ法 - Wikipedia
カラツバ法（カラツバほう）とは、主に多倍長乗算の乗算アルゴリズム（英語版）において、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba（Карацуба Анатолий Алексеевич）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算はだったが、Karatsuba法の再帰的適用により、（≒1.585）まで計算コストが抑えられる。 単純な例として、被乗数と乗数の積を求める()。 まず、被乗数と乗数をそれぞれ上位・下位の2つに分割する。 分割の基数を（例えば3桁ずつに分割するなら）とすると、 この乗算をKaratsuba以
The Sorting Algorithm Demo
Sorting Algorithms The animations on this page illustrate a number of different sequential and parallel sorting algorithms. The relative execution times of the animations give a very rough idea of the relative speeds of the algorithms. Each algorithm is finished when its colored lines disappear. Speed and Efficiency Analysis. Bubble Sort is a sequential algorithm, with an average case time of O(n2
Duff's device - Wikipedia
Duff's Device（ダフスデバイス）とは、C言語での可変長の連続的コピーをループ展開により最適化実装するときに直面する端数の問題を解決するための手法である。 C言語のswitch-case文が持つフォールスルーを利用して、アセンブリ言語で行われる技巧をC言語で実現している。1983年11月、ルーカスフィルムで働いていたトム・ダフが発見した。 背景問題[編集] ループ展開は、ループのための分岐回数を減らす技法である。指定されるループ回数が不明な場合、ループ展開すると回数が合わない場合が出てくるので、ループの途中にジャンプすることで調整する。例えば、8回ぶんのループを展開した場合、指定されたループ回数が8で割り切れないなら、その回数を8で割った剰余のぶんだけ処理を実行する位置にジャンプさせる。 ダフはそのような最適化を検討していてCでの技法を発見した。 本来のバージョン[編集] 連続コ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The Improved Sorting Algorithm Demo