algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found
2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い 珠玉のプログラミング Jon Bentley / 小林健一郎訳 絶賛風邪こじらせ中につきコードと戯れることに。 新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。 最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。 ソートしたいものに適当に番号を振っておく 番号がついたバケツを用意する ソートしたいものの番号がついたバケツにそれを放り込む 必要があればバケツの中身を同じやり方でソートする 番号順にバケツの中身をぶち
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
単体マシン（x86/x64）における最速sort algorithmは何か？ - maropuのメモ墓場
今日はsortの日なのでしょうか・・・ twitterのタイムラインを眺めていると，tim-sortというalgorithmが話題のようです． quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort http://d.hatena.ne.jp/gfx/20111019/1318981818 単体マシン（x86/x64）における高速なsort algorithmの研究はIntelが近年行っていて，有名な実装だとbufferingを利用したradix-sort実装と，SIMDを利用したmerge-sort(bitonic-sort）実装があります． 1. radix-sort: Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort, SIGMOD'10, ht
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
ヒープソート - Wikipedia
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。 アルゴリズムは、以下のように2つの段階から構成される。 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。 ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。 計算量は O となる[2]。安定ソートではない[2]。 ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の並び順（配列）だけで表現できるという利点がある。ヒープソートを実装する際にはこの利点を生かし、元のデータ領域をそのままヒープ構造や整列済みリストに転用するインプレースなソートとして実装することが多い。 最初にN個のデータを含む配列が与えられるものとする。添字は1 〜
開発メモ: トップNソートの検討
上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー
N要素の分岐しない odd-even mergesort (GCC+Linux/x86_64用) - memologue
(こちらの記事の続き) (ジェネレータを生成) % g++ -O2 -Wall gen_sort.cpp -o gen_sort (8要素向けのソート関数を作成) % ./gen_sort 0 8 > oem_sort_8.s % gcc -c oem_sort8.s (ちゃんと作られたようだ) % nm oem_sort_8.o 0000000000000000 T odd_even_sort8 (テストコード書き) % cat > test.c #include <assert.h> void odd_even_sort8(unsigned int* d); int main() { int i; unsigned int s[] = {7,6,5,4,1,2,3,4}; odd_even_sort8(s); for(i = 0; i < 7; ++i) { assert(s[i] <
4要素の分岐しないソート (GCC用) - memologue
(こちらの記事の続き、おまけです) 「分岐しないソート」の、VC++向けのコードをGCC+Linux向けに修正してみました。 実はC言語によるソートである sort4l() のほうも相当速いので、私の手元の環境だと同じくらいの速度しか出なかった*1んですが、面白いのでオッケー。例えば {1,2,3,4} から生成される順列(24通り)を何百万回か食わすような処理を書いてみると Celeron 2.4GHz & Linux だとアセンブラ版が10%遅く、Athron64 3200+ & Linux/x86_64, gcc -m32 だとアセンブラ版が10%速く、ARM9 200MHz & Linux だと同じ速度でした。 まずx86向けから。 // for GCC + Linux/x86 void sort4(unsigned int *d) { __asm__ ( "mov (%0), %
分岐しないソート (のジェネレータ） - memologue
分岐しない4要素のソート、GCC/Linux/x86,x86_64,arm版 こちらに、「分岐しないソート」という記事があります。短いので読んでいただくほうがよいと思いますが、文章＆アセンブリ言語のコードの内容を要約すると、 4要素のソートは、頑張れば5回の比較と5回の交換でできるよ。さらに、交換を Pentium Pro で追加された命令であるCMOVcc(Conditional Move)で行うことにすれば、「cmp b, a して、 b < a のときだけ b と a をswap」という処理を分岐命令なしで行うことができるから速いよ。 となります。この、「4要素専用・VC++専用の分岐しないソート」を、いつものように(?) GCC向けに書き直してみました。こちら。 分岐しないN要素の odd-even mergesort、GCC/Linux/x86_64版 (x86_64のお勉強がて
再帰処理のクイックソート 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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
emit.jp