cpp sort
1.16.0 — Taxonomics
使用されているアプリケーションやコンピューターに関係なく、そのうちの 1 つまたは 2 つの並べ替え方法だけが他のすべての並べ替え方法を支配できれば素晴らしいでしょう。しかし実際には、それぞれの方法には独自の利点があります。 [...] したがって、アルゴリズムが最適であることが判明するいくつかのアプリケーションがあるため、ほぼすべてのアルゴリズムは覚えておく価値があることがわかります。 — Donald Knuth、コンピュータ プログラミングの芸術、第 3 巻
cpp-sort は、汎用の C++14 ヘッダーのみの並べ替えライブラリです。これは、1 つの主要な汎用並べ替えインターフェイスを中心に展開し、並べ替えアルゴリズムを選択および/または設計するためのいくつかの小さなツールを提供します。基本的な並べ替え機能の使用は十分に簡単です。
# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >
int main ()
{
std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
cppsort::smooth_sort (arr);
// prints 2 3 5 8 9
for ( int val: arr) {
std::cout << val << ' ' ;
}
}cpp-sort は、並べ替え関連の機能の完全なセットを提供します。ライブラリの主な構成要素は次のとおりです。
以下は、ライブラリで何ができるかのより完全な例です。
# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >
int main ()
{
struct wrapper { int value; };
std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
// When used, this sorter will use a pattern-defeating quicksort
// to sort random-access collections, and a mergesort otherwise
cppsort::hybrid_adapter<
cppsort::pdq_sorter,
cppsort::merge_sorter
> sorter;
// Sort li and vec in reverse order using their value member
sorter (li, std::greater<>{}, &wrapper::value);
sorter (vec, std::greater<>{}, &wrapper::value);
assert ( std::equal (
li. begin (), li. end (),
vec. begin (), vec. end (),
[]( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
));
}追加の機能なしで並べ替え関数が使用されている場合でも、いくつかの興味深い保証が提供されます (アイデアは Ranges TS から取得されることがよくあります)。
iter_swapとiter_moveを使用してプロキシ反復子を正しく処理します。operator()の関数ポインターに変換できます。利用可能なすべてのツールの詳細を読み、ウィキでcpp-sort の使用と拡張に関するいくつかのチュートリアルを見つけることができます。
次のグラフは、ベンチマーク ディレクトリにあるスクリプトを使用して生成されました。これは、 heap_sortが調整されずに 100 万個の要素をソートするのに必要な時間を示し、その後、 drop_merge_adapterまたはsplit_adapterで調整された場合に必要な時間を示しています。
上で見られるように、いずれかのアダプターでheap_sortラップすると、非侵入的な方法で反転の数に適応できるようになります。適応させるために使用されるアルゴリズムにはさまざまな長所と短所があり、どちらを使用するかはあなた次第です。
このベンチマークは主に、ライブラリが提供する可能性を示すために存在します。このようなコメント付きベンチマークは、専用の Wiki ページでさらに見つけることができます。
cpp-sort にはC++14 のサポートが必要で、次のコンパイラで動作する必要があります。
/permissive-のみ)。いくつかの機能は利用できません。上記のコンパイラは CI パイプラインで使用されるものであり、ライブラリはこれらのコンパイラの最新バージョンでも定期的にテストされます。中間の他のコンパイラ バージョンはすべてテストされていませんが、同様に動作するはずです。そうでない場合は、遠慮なく問題を開いてください。
ライブラリの機能は、使用される C++ バージョンと有効なコンパイラ拡張機能によって異なる場合があります。これらの変更は wiki に文書化されています。
メイン リポジトリには、CMake やコナンなどの標準ツールの追加サポートが含まれています。詳細については wiki を参照してください。
新しい車を手に入れました。あとはまとめるだけです。少しずつ盗む方が簡単です。 — ジャロッド・キンツ、3.33 ドル
ライブラリの一部は独自の研究であり、その他の部分は標準のソート アルゴリズムのカスタムでかなり単純な実装に対応していますが、 cpp-sort はオープンソース プロジェクトからの大量のコードとアイデアも再利用しており、多くの場合、シームレスに統合するために変更されています。図書館。このライブラリの作成に使用される外部リソースのリストは次のとおりです。さまざまなライセンスに互換性があることを願っています。そうでない場合は、私にご連絡ください (または問題を送信してください)。それに対して何ができるかを確認させていただきます。
insertion_sorterとpdq_sorterで使用されるアルゴリズムの一部は、Orson Peters のパターンを無効にするクイックソートから来ています。ベンチマークの一部もそこから取得されています。
tim_sorterで使用されるアルゴリズムは、Goro Fuji (gfx) による Timsort の実装から来ています。
spread_sorterで使用される 3 つのアルゴリズムは、Steven Ross Boost.Sort モジュールからのものです。
d_ary_spread_sorterで使用されるアルゴリズムは、Tim Blechmann の Boost.Heap モジュールからのものです。
spin_sorterで使用されるアルゴリズムは、Boost.Sort に実装された同名のアルゴリズムに由来しています。フランシスコ・ホセ・タピア著。
utility::as_function 、 utility::static_const 、およびいくつかの投影強化ヘルパー アルゴリズムは、Eric Niebler の Range v3 ライブラリから提供されています。プロキシ イテレータ、カスタマイズ ポイント、プロジェクションなどのいくつかのアイデア、および他のいくつかのユーティリティ関数も、そのライブラリ、または関連記事や標準 C++ 提案から得られます。
ska_sorterで使用されるアルゴリズムは、Malte Skarupke による独自の ska_sort アルゴリズムの実装から来ています。
drop_merge_sorterで使用されるアルゴリズムは、Emil Ernerfeldt のドロップマージ ソートを Adrian Wielgosik C++ で再実装したものです。
多くの拡張標準アルゴリズムは libc++ の対応するアルゴリズムから直接適応されており、プロジェクションとプロキシ反復子の両方を処理できるように拡張されています。
ライブラリは、前方イテレータと連携するinplace_merge関数を内部で使用します。その実装では、Dudziński と Dydek が提案し、Alexander Stepanov と Paul McJones が著書『Elements of Programming』で実装したマージ アルゴリズムを使用します。
ランダム アクセス イテレータのinplace_mergeオーバーロードは、アウトオブプレース マージを実行するのに十分なメモリがない場合に、Pok-Son Kim と Arne Kutzner が「対称比較による安定した最小ストレージ マージ」で提案したSymmergeアルゴリズムを使用します。
smooth_sorterで使用されるダイクストラのスムーズソートの実装は、Keith Schwarz のアルゴリズムの実装から直接適応されました。
wiki_sorterで使用されるアルゴリズムは、BonzaiThePenguin の WikiSort から採用されています。
grail_sorterで使用されるアルゴリズムは、Mrrl の GrailSort から採用されています。
indirect_adapterで前方反復子または双方向反復子とともに使用されるアルゴリズムは、Matthew Bentley の indiesort をわずかに修正したバージョンです。
一部のアルゴリズムで使用されるnth_elementのランダム アクセス オーバーロードの実装は、Danila Kutenin の miniselect ライブラリから来ており、Andrei Alexandrescu のAdaptiveQuickselectアルゴリズムを使用しています。
sorting_network_sorterによって使用される並べ替えネットワークはすべて、Bert Dobbelaere によって管理されているこのリストから取得されます。このページには、リストされているすべての分類ネットワークの情報源への参照が含まれています。
sorting_network_sorterで使用される最適化の一部は、StackOverflow でのこのディスカッションに基づいており、記事「Appiling Sorting Networks to Synthesize Optimized Sorting Libraries」の記事によって裏付けられています。
このテスト スイートは、もともと次の場所にあった乱数アルゴリズムを再実装します。
ソート ネットワークの描画に使用される LaTeX スクリプトは、kaayy のsortingnetwork.texの修正バージョンで、0 ベースでネットワークを上から下に描画するようにわずかに調整されています。
プロジェクトに埋め込まれた CMake ツールには、RWTH-HPC/CMake-codecov および Crascit/DownloadProject のスクリプトが含まれています。
ベンチマークの一部では、Thøger Rivera-Thorsen が開発した色盲に優しいパレットを使用しています。
