[B! sort] izariuo440のブックマーク

C++の関数オブジェクトが関数よりどれだけ速いか - でも今日はSRMあるから

C++では関数オブジェクトのほうが関数より速い。呼び出しの時間に差がある様子。数回呼ぶだけなら誤差だが呼ぶ回数が増えるとその速度は有利。ソート std::sortの比較関数に関数や関数オブジェクトを与える。関数 bool cmp(int x, int y) { return x < y; } 関数オブジェクト struct cmp_c { bool operator()(int x, int y) { return x < y; } } cmp; ファンクタとかファンクショノイドとか呼ばれる。cmpは上の関数のcmpと同じように呼ぶことができる。ラムダ式 auto cmp = [](int x, int y) -> bool { return x < y; }; C++11の記法。関数オブジェクトが作られる。 cmpの型はfunction< bool(int,int) >かと思われ

izariuo440 2015/08/08

std:sort はテンプレートなので最適化で比較関数がインライン展開されたりして関数呼び出しのオーバーヘッドが無くなる分速くなるはず。

c++
sort

リンク

めもニャンだむ:[Delphi] ビットマップの色を数える（４）

izariuo440 2012/03/20

imaging
sort

リンク

高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development

先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解

izariuo440 2012/03/13

sort

リンク

Optimized QuickSort — C Implementation (Non-Recursive)

Optimized QuickSort — C Implementation (Non-Recursive) August 2005, July 2007 NOTE 2010.02.25: I’ve received a few e-mails over the past few years telling me that my implementation of QuickSort may not be an improvement over the popular, recursive implementation. When I have time, I plan to perform my own comprehensive speed tests. Until then, don’t take the below information as gospel! Perform