帮酷LOGO
  • 显示原文与译文双语对照的内容
Additional sorting algorithms for C++14

  • 源代碼名稱:cpp-sort
  • 源代碼網址:http://www.github.com/Morwenn/cpp-sort
  • cpp-sort源代碼文檔
  • cpp-sort源代碼下載
  • Git URL:
    git://www.github.com/Morwenn/cpp-sort.git
  • Git Clone代碼到本地:
    git clone http://www.github.com/Morwenn/cpp-sort
  • Subversion代碼到本地:
    $ svn co --depth empty http://www.github.com/Morwenn/cpp-sort
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
  • Latest ReleaseBuild StatusLicenseCode Coverage

    如果只有一或者兩種排序方法能夠支配所有其他的,不管應用程序或者使用的電腦是什麼,它都很好。 但事實上,每種方法都有自己獨特的優點。 因此,我們發現幾乎所有的演算法都值得記住,因為有些應用程序是最好的,它們是最好的。 ,電腦編程藝術,卷 3

    cpp排序是一個通用的C++14頭排序庫。 它圍繞一個主要的通用排序介面,提供了幾個小工具來挑選和/或者設計排序演算法。 使用它的基本排序功能應該足夠簡單:

    #include<array>#include<iostream>#include<cpp-sort/sort.h>intmain()
    {
     std::array<int, 5u> arr = { 5, 8, 3, 2, 9 };
     cppsort::sort(arr);
     // prints 2 3 5 8 9for (int val: arr) {
     std::cout <<val <<'';
     }
    }
    主要功能&附加功能

    排序實際上提供了一組完整的排序相關特性。 以下是庫的主要構造塊:

    下面是一個更完整的示例,說明如何使用該庫:

    #include<algorithm>#include<cassert>#include<forward_list>#include<functional>#include<iterator>#include<vector>#include<cpp-sort/adapters.h>#include<cpp-sort/sorters.h>intmain()
    {
     structwrapper { 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 otherwiseusing sorter = cppsort::hybrid_adapter<
     cppsort::pdq_sorter,
     cppsort::merge_sorter
    > ;
     sorter sort;
     // Sort li and vec in reverse order using their value membersort(li, std::greater<>{}, &wrapper::value);
     sort(vec, std::greater<>{}, &wrapper::value);
     assert(std::equal(
     std::begin(li), std::end(li),
     std::begin(vec), std::end(vec),
     [](auto& lhs, auto& rhs) { return lhs.value == rhs.value; }
     ));
    }

    即使沒有額外功能使用排序函數,它們仍然提供了一些有趣的保證( 從範圍TS的想法。):

    • 它們同時提供一個迭代器和一個範圍介面
    • 如果可能,他們接受定製的比較器參數
    • 其中大多數都接受投影參數
    • 它們使用 iter_swapiter_move 正確處理代理迭代器
    • 當迭代器不提供日誌增量或者 post-decrementation時,它們也工作
    • 要排序的集合的值類型不必是默認構造函數
    • 要排序的集合的值類型不必是 copyable ( 只可以移動)
    • 可以將無狀態排序器轉換為每個重載的operator()的函數指針
    • 排序器是函數對象:它們可以直接作為"重載集"傳遞給其他函數

    你可以閱讀更多關於可用工具的信息,並在中找到關於使用和擴展cpp排序的一些教程。

    基準測試

    下面的圖已經生成,並在benchmark目錄中找到了一個腳本。 它顯示了排序演算法所需的時間,將一百萬個已經拖動的std::array<int, N>的大小分為 0到 15. 比較了排序小數組時通常使用的排序器:

    small shuffled int arrays

    這些結果是用 MINGW G++ 6.1.0生成的,編譯器選項 -std=c++1z -O2 -march=native 。 這個基準測試只是一個例子,讓這個簡介看起來不錯。 你可以在專用wiki頁面中找到更多的註釋基準。

    命令行編譯器支持

    當前的cpp排序需要C++14支持,並且只使用g++5和 clang++3 。8 或者更高版本的這些編譯器。 到目前為止,構建矩陣+ 主測試提供以下支持:

    • 在Linux上使用g++5和 clang++3 。8
    • 使用 Xcode 8在OSX上工作
    • 使用 MinGW-w64 g++5在 Windows 上工作
    • 同時使用libstdc++和 libc+ +
    • 在Linux和OSX上通過Valgrind檢查,每個經過測試的編譯器
    • 通過 G++ 和 clang+ + 在Linux上傳遞未定義的殺毒檢查
    • 通過 clang+ + 在Linux上檢查地址消毒器

    上次嘗試它時,MSVC 2017無法使用。 C++14分支的未來開發將嘗試保持與上面列出的編譯器版本兼容。 上面沒有列出一些消毒測試,不是因為它們觸發錯誤,而是因為我不能讓它們正確構建。

    儲存庫還包含實驗性的C++17分支需要最新版本的G++ 和 clang++,而且可能需要更多的最新版本,直到兩個編譯器的C++17支持足夠穩定。 值得注意的是,當新語言和標準庫功能取代了一些實用程序頭時,針對C++14分支編寫的代碼不能被保證使用;這些更改會被記錄在文件頭上。 C++17分支具有比C++14分支更多的特性,並且將在某個時間點有一些重要特性,例如正確處理執行策略,以實現並行排序演算法。 在後來的某些時候,C++17分支可以能成為主分支,C++14分支只接收 Bug 修復和小更新。

    長期目標是使庫隨著 C++ 標準進化,C++14和C++17分支之間的差異也將在未來的分支之間存在。 一些諸如概念和標準範圍之類的特性可能會塑造圖書館的未來。

    謝謝

    我買了輛新車。 我只需要把它放在一起。 他們容易被撕成碎片。 - Jarod Kintz,$3.33

    library是一些標準排序演算法,而其他一些則與開放源代碼項目的實現相對應,通常是經過修改的,以集成到庫中的代碼。 下面是用於創建這裡庫的外部資源的列表。 我希望許多不同的許可證兼容。 如果不是這種情況,請聯繫我( 或者提交一個問題),我們將看到什麼可以做的事情,對它:

    • insertion_sorterpdq_sorter 使用的一些演算法來自Orson的模式失敗快速排序。 基準測試的某些部分也來自於那裡。

    • tim_sorter 使用的演算法來自實現的Goro ( gfx )的Timsort

    • spread_sorter 使用的三種演算法來自 Steven Ross Boost.Sort MODULE 。

    • utility::as_function 和幾個投影增強的helper 演算法來自的niebler範圍v3庫中的Eric 。 代理迭代器。定製點和投影等幾個想法也來自於該庫或者相關文章和標準 C++ 建議。

    • ska_sorter 使用的演算法來自於實現的Malte of他自己的ska_sort 演算法。

    • drop_merge_sorter 使用的演算法來自 Wielgosik C++ reimplementation ( ernerfeldt drop-merge-sort )的Emil

    • 許多增強標準演算法直接從它們在 libc++ 中的對應項修改,增強了處理投射和代理迭代器的。

    • 庫內部使用了一個 inplace_merge 函數,它可以與前向迭代器一起工作。 它的實現採用由Dudziński和Dydek提出的合併演算法,並由Alexander和 Paul McJones在他們的圖書編程語言編程元素Elements中實現。

    • 本文採用 smooth_sorter 演算法直接從演算法的實現中直接調整了dijkstra所使用的dijkstra 。

    • block_sorter 所使用的演算法已經從 bonzaithepenguin WikiSort的

    • grail_sorter 使用的演算法已經從 mrrl GrailSort的中修改,因此名稱是。

    • sorting_network_sorter 使用的演算法 0到 16已經用 perl Algorithm::Networksort MODULE 生成。

    • sorting_network_sorter 和 18使用的演算法 17對稱和進化found網路排序優化( 感測器) published使用對稱和進化搜索,以最小化排序網路,通過Valsalam和 Miikkulainen 。

    • sorting_network_sorter,20,21,24,和 28使用的演算法已經被發現並建議由Bert的SorterHunter項目 。 你可以以在他的網站上找到最多最多 32個輸入網路的已經知排序網路的完整列表。

    • sorting_network_sorter 使用的一些優化來自討論討論 StackOverflow,並通過文章 來支持Optimized優化的排序庫

    • 用於繪製排序網路的LaTeX 腳本是 sortingnetwork.tex的版本,稍微適合於 0-based,並從上到下繪製網路。




    Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语