[B! algorithm][javascript] nsyeeのブックマーク

JavaScriptでダイクストラ法 | @blog.justoneplanet.info

優先度つきキューを使用したダイクストラ法をJavaScriptで実装した。 ■実装 /** * Vertex * @param int value */ var Vertex = function(value){ var self = this; self.value = value; self.state = 0; self.dist = Number.POSITIVE_INFINITY;// もしくは十分に大きい値とか self.neighbor = []; self.appendNeighbor = function(){ for(var i = 0; i < arguments.length; i++){ self.neighbor.push(arguments[i]); } } } // set up a graph var s = new Vertex(0); var v1 =

nsyee 2011/01/13

リンク

Internet Explorerよりも速くソートできたよ

Internet Explorerよりも速くソートできたよ：コーディングに役立つ！アルゴリズムの基本（5）（1/4 ページ）プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）第4回「Internet Explorerよりも速くソートできるかな」では、選択ソート、バブルソート、シェルソート、クイックソートを実装して、IE組み込みのソート機能よりも速くソートできるかを試しました。残念ながら、いまのところ組み込みのソートよりも速くソートできていません。しかし徐々に差は縮まっています。ソートのアルゴリズムは、まだまだたくさんの種類があります。代表的なものだけでもまだいくつか残っていますので、今回はこれらを実装して、IE組み込みのソート機能と速度を比較してみましょう。だん

nsyee 2009/07/13

リンク

バケットソート(Bucket sort)で高速化 | 空中制作 (kuuchuuSeisaku)

nsyee 2009/07/13

リンク

JavaScript sort benchmark

これは何？3000件ぐらいの配列をJavaScriptでソートする際の高速化するための実験。要素は複数のプロパティを持つハッシュで、数値だったり文字列だったり。特定キーの数値比較が主。 sort_key: benchmark loop: benchmark: convert to object convert to object2 convert to object3 normal sort bucket sort quick sort marge sort marge sort2 object hack sort custom object sort count toString count cmp qsort count cmp msort count cmp count log Clear 説明 convert to object: ハッシュの配列を特定クラスのオブジェクトの配列に変

nsyee 2009/07/13

リンク

東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo

ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogle MapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。使ったのは東京メトロ＋都営＋山手線駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に

nsyee 2008/11/12

リンク

重み付きシャッフルの回答案 - snippets from shinichitomita’s journal

前回の続き。問題：配列の中のある要素aに対してWaの重みが付いている。このとき、要素aが要素bより先に来る確率がWa/(Wa+Wb)となるようにシャッフルするにはどうすればよいか？ # 2007年08月28日 brazil brazil 1, TEMP, JAVASCRIPT, PROGRAMMING 最後の方法じゃだめなんだ...、ランダムはてなブックマーク - 重み付けシャッフル、再び - snippets from shinichitomita’s journal ランダムにそのまま重みを掛けた値でのソートだとだめなのは、絵を描いてみるとわかりそう。 PaとPbがそれぞれaおよびbの方が大きくなるエリアだけど、面積比はあきらかにWa:Wbじゃない。まあその後色々考えて、多分これならそれっぽくシャッフルされるかな、というのを思いついたのだけど、どんなもんか。 var arr =