『わかりやすいパターン認識』の2章で説明されているパーセプトロンをPythonで実装しました。説明はここでは省きます。 #!/usr/bin/env python2.7 from matplotlib import pyplot from matplotlib.path import Path import matplotlib.patches as patches fi…

最近、courseraでアルゴリズムを勉強していました。そのときやった練習問題の1つのタイプに「xxxソートで4回スワップした結果を書きなさい」というものがあって、これがなかなか勉強になりました。イメージができれば、コーディングはだいたいできるので、こ…

*この文章はCodeIQの「ハサミを使うタイミング」に答えた人にしか伝わらないと思います。まだ挑戦されていない方はgihyo.co.jpのこのページを読んで挑戦してみてください。ハサミを使うタイミング(CodeIQ)について、フィードバックを受けてから考えたことに…

tsort(トポロジカルソート)は主に依存関係の解決に利用されるようです。この処理の前には、あの処理をやっておくというように指示すると、tsortはその条件に合うようにソートします。次のコードはRailsの初期化処理とほぼ同じ実装で、:afterまたは:beforeで…

バイナリサーチを例に、再帰からループへの変換をしてみます。バイナリサーチは、(a[0] vより小さければ、firstから今調べたところまでにvは無いことが分かります。なので、次回firstはnext+1にして、調べる領域を縮めることができます。逆の場合も同様です…

数学ガール-乱択アルゴリズム-の9章にある3-SATを解く乱択アルゴリズムをPythonで実装してみました。p336の強正美優問題は正しく計算できるところまで確認しました(テストではupdateとbf_three_satを使ってます)。ラウンドあたりの成功率が妥当かどうか調べ…

リニアサーチは配列arrayからある値valueのある位置(インデックス)の最小値を返します。もしarrayの中にvalueが無ければNoneを返します。このときのloop不変式としては、loopをlower [ループ前] array[lower:upper+1]=array[0:len(array)+1]=arrayなので、成…

SQLiteのソースコードリーディングしているのですが、ぼくはソート・アルゴリズムについてあまり勉強したことがないので、アルゴリズムのところでいちいち躓いています。SQLiteで使われているアルゴリズムは本にも載っているような古典アルゴリズムがほとん…

アルゴリズムの名前が分からないのですが、途中でマージは使われているのでマージソートの一種でしょうか。ぼくが見ているSQLiteのままのコード(pcache.cの457行目-のpcacheMergeDirtyListがmergeに、pcacheSortDirtyListがsortに対応します)だと一緒にする…

"ORDER BY"のときにSQLite中で動いているsort関数について調べているのですが、前回のは少しinputと結果が違っているようで、実はこんなのだと今のところ思っています。やっていることはcountの大きさのトーナメントを用意して、inputの配列の0-(count-1)成…

SQLiteの中のソート関数(ORDER BYを書いたときに内部で動く関数)を読んでいたら、複数のソートされた配列をマージしていたので、それをpythonに焼き直してみました。アルゴリズムとしては、各配列の第0要素をエントリして、一番小さな数を決めるのにトーナメ…