Animated Sorting Algorithms
Discussion These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates. Show that there is no best sorting algorithm. Show the advantages and disadvantages of each algorithm. Show that worse-case asymptotic behavior is not the deciding factor in choosing an algorithm. Show that the initial condition (inp
集合知と多量情報の可視化アルゴリズム本 Programming Collective Intelligence | fladdict
先日購入したBen FryのVisualizing Dataとあわせて買ってみた、Programming Collective Intelligence: Building Smart Web 2.0 Applications という本もかなりよさげ。 端的にいうとWEB2.0コンテンツ用に特化した、統計解析の理論とアルゴリズムの解説本。 いわゆる「これを買った人はこれを買ってます」を筆頭に、市場予測やスパム抽出、特徴データのグルーピングなど、集合知を抽出するアルゴリズムが大集合してる感じです。各アルゴリズムの原理の説明から、シンプルな自力実装までが書いてある感じっぽい。こういう系は数式だけあって理解不能か、動作がライブラリに隠蔽されてて理解不能で手が出せなかったけど、この本あれば大分理解できそう。以下、乗ってる内容メモ。 ・Amazon的なリコメンドのしくみ ・データのグループ化(クラス
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
再帰処理のクイックソート vs 非再帰処理のクイックソート
なるエラーでプログラムが続行できなくなる不具合に悩みました。そこで、今まで記述したことのない非再帰処理のクイックソートに書き直すことになりました。 僕の本業は VBA でないので、これ以上詳しい Excel VBA のソートのお話しは以下のサイトをご覧下さい。 さて、以下の説明は VBA に実装する前に作成した Perl 版クイックソートに説明を切り替えます。 まずは単純に再帰処理のクイックソートを実装してみる sub qsort_normal() { my $array = shift; my $left = shift; my $right = shift; my ($i, $j, $pivot, $tmp); if ($left < $right) { $i = $left; $j = $right; $pivot = $array->[($left+$right)/2]; whil
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
線形合同法 - Wikipedia
線形合同法（せんけいごうどうほう、英: Linear congruential generators, LCGs）とは、擬似乱数列の生成式の一つ。 漸化式 によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。 上の式で、が、乱数の種であり、これに数を代入すると、が得られる。さらにを生成する場合には、を使う。以後、同様に行う。 例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種=8とすると、（上の式においてはXn+1を左辺に置いたが、今回は便宜上、右辺に置く） 次に乱数を生成する際は前回生成された乱数（今回は3）を使って、 以下、同じように、 となる。 生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。 BとMが互いに素である。 A-1が、Mの持つ全ての素因
JavaScript でソートアルゴリズムを可視化 - bkブログ
JavaScript でソートアルゴリズムを可視化 JavaScript でソートアルゴリズムを可視化するプログラムを書いてみました。元ネタは Jon Bentley による ソートアルゴリズムを可視化する Java アプレットです。 アルゴリズム 要素数 動作確認は Firefox 2, IE 7, Opera 9 で行いました。要素数は最大で200まで選べますが、かなり重くなるので遅いマシンで実行すると危険です。 English version is also available. ソースコード: sort-animation.js 解説 X軸が配列の添え字、Y軸が配列の要素の値を示しています。最初に要素がランダムに並んでいる配列 (値に重複なし) を作って、それを各種のソートアルゴリズムでソートする様子をアニメーションで表示します。 ただし、要素のあらゆる変更に対して毎回表示を更新し
OBB vs AABB - Radium Software Development
This domain may be for sale!
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
きまぐれ日記: ソートの平均要素移動距離
配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば，サイズ n の配列の場合平均移動距離は n/3 になるらしい． サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので，直感的に考えると n/2 のような気がする．しかし，真ん中の要素は両側に移動するので，その距離は小さくなる．平均移動距離は n/2 より小さい値になるはずだ. 頭で考えるより手を動かしたほうが楽なので，モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし，ソート済みの配列と比較して各要素の平均移動距離を求める．これを 1000 回繰り返し平均値を計算する. #include <iostream> #include <vector> #include <cmath> #include <algorithm> static
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
データ構造とアルゴリズム - 自習用デモプログラムおよびソースコード集 (Java)
Amazon.co.jp: The art of computer programming: 日本語版 (volume 3) (ASCII Addison Wesley Programming Se): ドナルド・E. クヌース (著), 誠,有澤 (翻訳), 英一,和田 (翻訳), Knuth,Donald E. (原名): 本
MIT OpenCourseWare OCW Home
http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf