ソートキラー改 - d.y.d.
01:19 13/07/06 ソートキラー改 ここまでのあらすじ： → ソートの実装を渡すと、 自動でその実装の苦手な入力を作ってくれる ソートキラーを作りました。 → でも遅い。元々のソート処理が O(f(n)) として O(n2 f(n)) 時間かかる。 → あっ O(n3 + f(n)) になった！ …という最後のステップを、コードは書いたのだけど説明どこにも書いてなかったのでメモ書きです。 本当にメモ書きであんまりわかりやすく書いてないので、気になる人だけ読んで下さい。 あと、特にたいしたことではないのでアルゴリズム得意な人には自明だと思われます。 説明 古いバージョンも新しいバージョンも、やっていることの流れは、こうです。 要素xは要素yより {小さい,大きい,わからない} の3状態を記録した n×n の表を準備。 初期値は "わからない"。 ソート関数に「xはyより小さいですか
ソート - Wikipedia
ソート (英: sort) は、データの集合を一定の規則に従って並べること[1]。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される[1]。 主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。 対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。 効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
wonderfl build flash online | 面白法人カヤック
wonderflは、サイト上でFlashをつくることのできるサービス。 通常Flashをつくるためには、Flash IDEやFlex、FlashDevelop等といったツールを使って、コードを書き、コンパイルする必要がありますが、wonderflでは、サイトにあるフォームにActionscript3のコードを書けば、サーバサイドでコンパイルを行えます。 つまり、ブラウザさえあれば、Flashをつくれます。コンパイル結果はサイト上に表示され、作成されたFlash（swf）はページ上に自動的に表示されるので、完成したFlashをリアルタイムに見ながらコードを書くことができます。 ※APIとして、はてな OpenIDを使用してネットにさえつながれば、誰もがFlashクリエイターになれます。世界中のFlashクリエイターがユーザーになるwonderflは、 文字通り、世界のFlash図鑑となってい
Internet Explorerよりも速くソートできたよ
Internet Explorerよりも速くソートできたよ：コーディングに役立つ！ アルゴリズムの基本（5）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 第4回「Internet Explorerよりも速くソートできるかな」では、選択ソート、バブルソート、シェルソート、クイックソートを実装して、IE組み込みのソート機能よりも速くソートできるかを試しました。残念ながら、いまのところ組み込みのソートよりも速くソートできていません。しかし徐々に差は縮まっています。 ソートのアルゴリズムは、まだまだたくさんの種類があります。代表的なものだけでもまだいくつか残っていますので、今回はこれらを実装して、IE組み込みのソート機能と速度を比較してみましょう。だん
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: ハッシュの配列を特定クラスのオブジェクトの配列に変
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
バケットソート(Bucket sort)で高速化 | 空中制作 (kuuchuuSeisaku)
