C++开源:TastyLib-一个数据结构和算法库(面试常见算法与数据结构的实现)
JefZnn
8年前
<h2>TastyLib</h2> <p>TastyLib is a c++ library of data structures and algorithms.</p> <p>It is also a <strong>header-only</strong> library, which means that you could just copy the include/tastylib directory to your project's include path and use it without caring about the issues related to link libraries.</p> <h2>Build Status</h2> <table> <thead> <tr> <th>Linux</th> <th>Windows</th> <th>Coverage</th> </tr> </thead> <tbody> <tr> <td> </td> <td> </td> <td> </td> </tr> </tbody> </table> <h2>Outline</h2> <p>Contents below show the data structures and algorithms available in this project. Just click the links at the name column to see the details of their usages and benchmarks. All benchmarks are run with the -O2 compiler flag under the Release version.</p> <h3>Data Structures</h3> <table> <thead> <tr> <th>Name</th> <th>Source</th> <th>Benchmarked</th> <th>Note</th> <th>Reference</th> </tr> </thead> <tbody> <tr> <td>DoublyLinkedList</td> <td><a href="/misc/goto?guid=4959735613019223617" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735613116965603" rel="nofollow,noindex">DoublyLinkedList.h</a></td> <td>Yes</td> <td>A linked data structure that consists of a set of sequentially linked records. It also supports merge sort.</td> <td><a href="/misc/goto?guid=4959735613206003864" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>BinaryHeap</td> <td><a href="/misc/goto?guid=4959735613285464045" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735613368713963" rel="nofollow,noindex">BinaryHeap.h</a></td> <td>Yes</td> <td>A heap data structure taking the form of a complete binary tree. A common way of implementing <a href="/misc/goto?guid=4959735613454153981" rel="nofollow,noindex">priority queue</a> .</td> <td><a href="/misc/goto?guid=4959735613540681829" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>HashTable</td> <td><a href="/misc/goto?guid=4959735613618647073" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735613702748848" rel="nofollow,noindex">HashTable.h</a></td> <td>No</td> <td>A data structure that stores unique elements in no particular order, and which allows for fast retrieval of individual elements based on their values. Similar to <a href="/misc/goto?guid=4959735613785800046" rel="nofollow,noindex">std::unordered_set</a> .</td> <td><a href="/misc/goto?guid=4959642961809881708" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>AVLTree</td> <td><a href="/misc/goto?guid=4959735613899810537" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735613984005694" rel="nofollow,noindex">AVLTree.h</a></td> <td>Yes</td> <td>A self-balancing binary search tree.</td> <td><a href="/misc/goto?guid=4959668749431269298" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>Graph</td> <td><a href="/misc/goto?guid=4959735614092767388" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735614179875080" rel="nofollow,noindex">Graph.h</a></td> <td>No</td> <td>A data structure to implement the directed/undirected graph concepts from mathematics. It stores a graph in an adjacency list or matrix.</td> <td><a href="/misc/goto?guid=4959735614261329042" rel="nofollow,noindex">Wikipedia</a></td> </tr> </tbody> </table> <h3>Algorithms</h3> <table> <thead> <tr> <th>Name</th> <th>Source</th> <th>Benchmarked</th> <th>Note</th> <th>Reference</th> </tr> </thead> <tbody> <tr> <td>MD5</td> <td><a href="/misc/goto?guid=4959735614340430515" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735614425981197" rel="nofollow,noindex">MD5.h</a></td> <td>Yes</td> <td>A widely used hash function producing a 128-bit hash value.</td> <td><a href="/misc/goto?guid=4959735614511314689" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>NPuzzle</td> <td><a href="/misc/goto?guid=4959735614594363134" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735614677548993" rel="nofollow,noindex">NPuzzle.h</a></td> <td>Yes</td> <td>A classic searching problem solved with <a href="/misc/goto?guid=4959735614762047495" rel="nofollow,noindex">A* search</a> . A <a href="/misc/goto?guid=4959735614848022365" rel="nofollow,noindex">GUI demo</a> has been provided.</td> <td><a href="/misc/goto?guid=4959735614932505665" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>Sort</td> <td><a href="/misc/goto?guid=4959735615017093795" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735615091700846" rel="nofollow,noindex">Sort.h</a></td> <td>Yes</td> <td>Including <a href="/misc/goto?guid=4959735615185725505" rel="nofollow,noindex">insertion sort</a> , <a href="/misc/goto?guid=4959735615263062331" rel="nofollow,noindex">selection sort</a> , <a href="/misc/goto?guid=4959735615346033270" rel="nofollow,noindex">heapsort</a> , <a href="/misc/goto?guid=4959643045803814134" rel="nofollow,noindex">quicksort</a> , <a href="/misc/goto?guid=4959735615454963302" rel="nofollow,noindex">quickselect</a> . For <a href="/misc/goto?guid=4959735615545633884" rel="nofollow,noindex">merge sort</a> , please refer toDoublyLinkedList.sort().</td> <td><a href="/misc/goto?guid=4959735615624069278" rel="nofollow,noindex">Wikipedia</a></td> </tr> <tr> <td>Dijkstra</td> <td><a href="/misc/goto?guid=4959735615712350203" rel="nofollow,noindex">Unit test</a><br> <a href="/misc/goto?guid=4959735615798017854" rel="nofollow,noindex">Dijkstra.h</a></td> <td>No</td> <td>An algorithm to find the shortest paths between vertices in a graph.</td> <td><a href="/misc/goto?guid=4959735615879299741" rel="nofollow,noindex">Wikipedia</a></td> </tr> </tbody> </table> <h2>Installation</h2> <ol> <li> <p>Install <a href="/misc/goto?guid=4958978886605118454" rel="nofollow,noindex">CMake</a> .</p> </li> <li> <p>Generate build files using the commands below:</p> <ul> <li> <p>Build benchmarks only</p> <pre> $ mkdir build $ cd build $ cmake ..</pre> </li> <li> <p>Build benchmarks and unit tests</p> <pre> $ mkdir build $ cd build $ git submodule init $ git submodule update $ cmake -DTASTYLIB_BUILD_TEST=ON ..</pre> </li> </ul> </li> <li> <p>Build files will be generated in the build directory based on your operating system. Use them to build this project:</p> <table> <thead> <tr> <th>Linux</th> <th>OS X</th> <th>Windows</th> </tr> </thead> <tbody> <tr> <td>Makefile</td> <td>Makefile</td> <td>Visual Studio Project</td> </tr> </tbody> </table> </li> <li> <p>All executables(benchmarks and unit tests) will be generated in the bin directory. To run all unit tests together, use command below:</p> <pre> $ ctest --verbose</pre> </li> </ol> <h2>Details</h2> <h3>DoublyLinkedList</h3> <p>Usage</p> <pre> #include "tastylib/DoublyLinkedList.h" using namespace tastylib; int main() { DoublyLinkedList<int> list; auto isEmpty = list.isEmpty(); // isEmpty == true list.insertBack(1); // List content: 1 list.insertFront(2); // List content: 2 1 list.insert(1, 3); // List content: 2 3 1 list.insert(3, 4); // List content: 2 3 1 4 list.sort(); // List content: 1 2 3 4 auto p1 = list.find(3); // p1 == 2 list.remove(p1); // List content: 1 2 4 list.removeFront(); // List content: 2 4 list.removeBack(); // List content: 2 auto p2 = list.find(3); // p2 == -1 auto size = list.getSize(); // size == 1 return 0; }</pre> <p>Benchmark</p> <p>Cost in theory</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> </tr> </thead> <tbody> <tr> <td><a href="/misc/goto?guid=4959735615985964958" rel="nofollow,noindex">insertFront()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616067229185" rel="nofollow,noindex">removeFront()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616156985959" rel="nofollow,noindex">insertBack()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616238162306" rel="nofollow,noindex">removeBack()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616321666689" rel="nofollow,noindex">insert()</a></td> <td>O(n)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616404315705" rel="nofollow,noindex">remove()</a></td> <td>O(n)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616492490123" rel="nofollow,noindex">find()</a></td> <td>O(n)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616570200114" rel="nofollow,noindex">sort()</a> (merge sort)</td> <td>O(nlogn)</td> </tr> </tbody> </table> <p>Cost in practice</p> <p>Source: <a href="/misc/goto?guid=4959735616656274064" rel="nofollow,noindex">benchmark_DoublyLinkedList.cpp</a></p> <p>The program compares the time cost of DoublyLinkedList with std::list . When benchmarking find() and sort() , the size of the list is <strong>100,000</strong> and <strong>5,000,000</strong> , respectively. Here are the results under different environments:</p> <p>Ubuntu 16.04 64-bit / g++ 5.4</p> <table> <thead> <tr> <th>Operation</th> <th>std::list</th> <th>DoublyLinkedList</th> </tr> </thead> <tbody> <tr> <td>insertFront()</td> <td>29 ns</td> <td>36 ns</td> </tr> <tr> <td>removeFront()</td> <td>15 ns</td> <td>12 ns</td> </tr> <tr> <td>insertBack()</td> <td>31 ns</td> <td>28 ns</td> </tr> <tr> <td>removeBack()</td> <td>14 ns</td> <td>12 ns</td> </tr> <tr> <td>find()</td> <td>165 µs</td> <td>230 µs</td> </tr> <tr> <td>sort()</td> <td>3432 ms</td> <td><strong>3011 ms</strong></td> </tr> </tbody> </table> <p>Windows 10 64-bit / Visual Studio 14 2015</p> <table> <thead> <tr> <th>Operation</th> <th>std::list</th> <th>DoublyLinkedList</th> </tr> </thead> <tbody> <tr> <td>insertFront()</td> <td>57 ns</td> <td>46 ns</td> </tr> <tr> <td>removeFront()</td> <td>42 ns</td> <td>49 ns</td> </tr> <tr> <td>insertBack()</td> <td>55 ns</td> <td>48 ns</td> </tr> <tr> <td>removeBack()</td> <td>48 ns</td> <td>51 ns</td> </tr> <tr> <td>find()</td> <td>112 µs</td> <td>114 µs</td> </tr> <tr> <td>sort()</td> <td>3534 ms</td> <td><strong>3138 ms</strong></td> </tr> </tbody> </table> <p>OS X 10.11.3 / AppleClang 7.3.0</p> <table> <thead> <tr> <th>Operation</th> <th>std::list</th> <th>DoublyLinkedList</th> </tr> </thead> <tbody> <tr> <td>insertFront()</td> <td>65 ns</td> <td>66 ns</td> </tr> <tr> <td>removeFront()</td> <td>70 ns</td> <td>82 ns</td> </tr> <tr> <td>insertBack()</td> <td>69 ns</td> <td>68 ns</td> </tr> <tr> <td>removeBack()</td> <td>73 ns</td> <td>79 ns</td> </tr> <tr> <td>find()</td> <td>10 ns*</td> <td>9 ns*</td> </tr> <tr> <td>sort()</td> <td>3717 ms</td> <td>3729 ms</td> </tr> </tbody> </table> <p>(Items marked with * may be unreliable.)</p> <h3>BinaryHeap</h3> <p>Usage</p> <pre> #include "tastylib/BinaryHeap.h" using namespace tastylib; int main() { BinaryHeap<int> heap; // Create a min-root heap auto isEmpty = heap.isEmpty(); // isEmpty == true heap.push(50); heap.push(20); heap.push(30); auto size1 = heap.getSize(); // size1 == 3 auto val1 = heap.top(); // val1 == 20 heap.pop(); auto val2 = heap.top(); // val2 == 30 heap.pop(); auto val3 = heap.top(); // val3 == 50 heap.pop(); auto size2 = heap.getSize(); // size2 == 0 return 0; }</pre> <p>Benchmark</p> <p>Cost in theory</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> </tr> </thead> <tbody> <tr> <td><a href="/misc/goto?guid=4959735616740370319" rel="nofollow,noindex">push()</a></td> <td>O(nlogn)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616826808084" rel="nofollow,noindex">top()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735616908381527" rel="nofollow,noindex">pop()</a></td> <td>O(nlogn)</td> </tr> </tbody> </table> <p>Cost in practice</p> <p>Source: <a href="/misc/goto?guid=4959735616996016085" rel="nofollow,noindex">benchmark_BinaryHeap.cpp</a></p> <p>The program compares the time cost of BinaryHeap with std::priority_queue . It calculates the average time cost of each operation. Here are the results under different environments:</p> <p>Ubuntu 16.04 64-bit / g++ 5.4</p> <table> <thead> <tr> <th>Operation</th> <th>std::priority_queue</th> <th>BinaryHeap</th> </tr> </thead> <tbody> <tr> <td>push()</td> <td>17 ns</td> <td>16 ns</td> </tr> <tr> <td>pop()</td> <td>294 ns</td> <td>293 ns</td> </tr> </tbody> </table> <p>Windows 10 64-bit / Visual Studio 14 2015</p> <table> <thead> <tr> <th>Operation</th> <th>std::priority_queue</th> <th>BinaryHeap</th> </tr> </thead> <tbody> <tr> <td>push()</td> <td>23 ns</td> <td>22 ns</td> </tr> <tr> <td>pop()</td> <td>498 ns</td> <td><strong>254 ns</strong></td> </tr> </tbody> </table> <h3>HashTable</h3> <p>Usage</p> <pre> #include "tastylib/HashTable.h" #include <string> using namespace tastylib; int main() { HashTable<std::string> table; auto isEmpty = table.isEmpty(); // isEmpty == true table.insert("Alice"); table.insert("Darth"); auto size1 = table.getSize(); // size1 == 2 auto hasAlice = table.has("Alice"); // hasAlice == true auto hasDarth = table.has("Darth"); // hasDarth == true table.remove("Darth"); hasAlice = table.has("Alice"); // hasAlice == true hasDarth = table.has("Darth"); // hasDarth == false auto size2 = table.getSize(); // size2 == 1 return 0; }</pre> <p>Benchmark</p> <p>Cost in theory</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> </tr> </thead> <tbody> <tr> <td><a href="/misc/goto?guid=4959735617079743105" rel="nofollow,noindex">insert()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735617163941054" rel="nofollow,noindex">has()/find()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735617248634737" rel="nofollow,noindex">remove()</a></td> <td>O(1)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735617329061518" rel="nofollow,noindex">rehash()</a></td> <td>O(n)</td> </tr> </tbody> </table> <p>Cost in practice</p> <p>Note that there are many different ways to implement the hash table. The C++ standard library implements the std::unordered_set as a <strong>dynamic</strong> hash table, which means that its bucket amount changes dynamically when performing insert() and remove()/erase() operations(i.e., using <a href="/misc/goto?guid=4959735617413888963" rel="nofollow,noindex">extendible hashing</a> or <a href="/misc/goto?guid=4959735617492746184" rel="nofollow,noindex">linear hashing</a> ). While in TastyLib, for simplicity, the hash table is <strong>static</strong> so its bucket amount is fixed after initialized. Since different implementations have different pros and cons, it's hard to give a convincing benchmark result.</p> <h3>AVLTree</h3> <p>Usage</p> <pre> #include "tastylib/AVLTree.h" #include <string> using namespace tastylib; int main() { AVLTree<int> tree; auto isEmpty = tree.isEmpty(); // isEmpty == true tree.insert(1); tree.insert(2); tree.insert(3); tree.insert(3); std::string str1 = tree.preorder(); // str1 == "{2, 1, 3, 3}" std::string str2 = tree.inorder(); // str2 == "{1, 2, 3, 3}" std::string str3 = tree.postorder(); // str3 == "{1, 3, 3, 2}" auto size1 = tree.getSize(); // size1 == 4 auto found1 = tree.has(3); // found1 == true tree.remove(3); std::string str4 = tree.preorder(); // str4 == "{2, 1}" auto size2 = tree.getSize(); // size2 == 2 auto found2 = tree.has(3); // found2 == false return 0; }</pre> <p>Benchmark</p> <p>Cost in theory</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> </tr> </thead> <tbody> <tr> <td><a href="/misc/goto?guid=4959735617582558044" rel="nofollow,noindex">find()</a></td> <td>O(logn)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735617668733355" rel="nofollow,noindex">insert()</a></td> <td>O(logn)</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735617750790272" rel="nofollow,noindex">remove()</a></td> <td>O(logn)</td> </tr> </tbody> </table> <p>Cost in practice</p> <p>Source: <a href="/misc/goto?guid=4959735617830750382" rel="nofollow,noindex">benchmark_AVLTree.cpp</a></p> <p>The program compares the time cost of AVLTree with std::multiset . It calculates the average time cost of each operation. Note that the std::multiset is implemented as a <a href="/misc/goto?guid=4959735617918583300" rel="nofollow,noindex">red-black tree</a> , which is faster than the AVL tree when performing insert() and remove() operations(but slower when performing find() ). Here are the results under different environments:</p> <p>Ubuntu 16.04 64-bit / g++ 5.4</p> <table> <thead> <tr> <th>Operation</th> <th>std::multiset</th> <th>AVLTree</th> </tr> </thead> <tbody> <tr> <td>find()</td> <td>1245 ns</td> <td>1056 ns</td> </tr> <tr> <td>insert()</td> <td>1241 ns</td> <td>1447 ns</td> </tr> <tr> <td>remove()</td> <td>1289 ns</td> <td>1728 ns</td> </tr> </tbody> </table> <p>Windows 10 64-bit / Visual Studio 14 2015</p> <table> <thead> <tr> <th>Operation</th> <th>std::multiset</th> <th>AVLTree</th> </tr> </thead> <tbody> <tr> <td>find()</td> <td>1597 ns</td> <td>168 ns*</td> </tr> <tr> <td>insert()</td> <td>1570 ns</td> <td>1260 ns</td> </tr> <tr> <td>remove()</td> <td>233 ns</td> <td>436 ns</td> </tr> </tbody> </table> <p>(Items marked with * may be unreliable.)</p> <h3>Graph</h3> <p>Usage</p> <pre> #include "tastylib/Graph.h" #include <string> using namespace tastylib; int main() { // Create a graph that has three vertices. // Each vertex stores a string object. Graph<std::string> graph(3); // Modify the string object in each vertex graph[0] = "I am vertex 0."; graph[1] = "I am vertex 1."; graph[2] = "I am vertex 2."; // Add edges graph.setWeight(0, 1, 10); graph.setWeight(0, 2, 20); graph.setWeight(1, 2, 30); // Get edge weights auto w0 = graph.getWeight(0, 1); // w0 == 10 auto w1 = graph.getWeight(0, 2); // w1 == 20 auto w2 = graph.getWeight(1, 2); // w2 == 30 // Get adjacent vertices auto n0 = graph.getNeighbors(0); // n0 == [1, 2] auto n1 = graph.getNeighbors(1); // n1 == [2] auto n2 = graph.getNeighbors(2); // n2 == [] return 0; }</pre> <h3>MD5</h3> <p>Usage</p> <pre> #include "tastylib/MD5.h" using namespace tastylib; int main() { // hashedMsg == "2dabbfd553b67530e4892eb9481121fa", // which is the MD5 value of the message "TastyLib" std::string hashedMsg = MD5<>::getInstance()->hash("TastyLib"); return 0; }</pre> <p>Benchmark</p> <p>Source: <a href="/misc/goto?guid=4959735617996095051" rel="nofollow,noindex">benchmark_MD5.cpp</a></p> <p>The program uses the MD5 algorithm to hash a fixed message of 200 MB for several times and calculates the average time cost. Here are the results:</p> <table> <thead> <tr> <th>Environment</th> <th>Average Time</th> </tr> </thead> <tbody> <tr> <td>Ubuntu 16.04 64-bit / g++ 5.4</td> <td>899 ms</td> </tr> <tr> <td>Windows 10 64-bit / Visual Studio 14 2015</td> <td>1229 ms</td> </tr> </tbody> </table> <h3>NPuzzle</h3> <p>Usage</p> <pre> #include "tastylib/NPuzzle.h" using namespace tastylib; int main() { // The beginning node and the ending node of a 3*3 puzzle problem. // Number '0' indicates the empty grid and number '1-8' denote other eight grids. PuzzleNode<> beg({0, 2, 3, 1, 4, 5, 6, 7, 8}, 3, 3); PuzzleNode<> end({1, 2, 3, 4, 0, 5, 6, 7, 8}, 3, 3); // Solve the problem NPuzzle<> puzzle(beg, end); puzzle.solve(); // List 'path' stores the move directions from the beginning node // to the ending node. Its contents must be [DOWN, RIGHT]. std::list<Direction> path = puzzle.getPath(); return 0; }</pre> <p>Benchmark</p> <p>Source: <a href="/misc/goto?guid=4959735618082720871" rel="nofollow,noindex">benchmark_NPuzzle.cpp</a></p> <p>The program solves 3*3 , 4*4 , 5*5 and 6*6 puzzle problems respectively and generates the information of overheads. Here are the outputs of the benchmark under different environments:</p> <p>Ubuntu 16.04 64-bit / g++ 5.4</p> <pre> Benchmark of NPuzzle running... Benchmarking 3*3 puzzle... Beg: {0, 6, 4, 3, 8, 2, 7, 5, 1} End: {6, 5, 7, 3, 1, 2, 8, 4, 0} Searching... Searched nodes: 161 Time cost: 1 ms Efficiency: 102.092581 node/ms Path length: 52 Solution check: pass Benchmark of 3*3 puzzle finished. Benchmarking 4*4 puzzle... Beg: {3, 0, 2, 13, 9, 1, 5, 6, 14, 11, 4, 10, 12, 7, 15, 8} End: {4, 2, 9, 3, 13, 0, 5, 6, 15, 12, 11, 14, 8, 10, 1, 7} Searching... Searched nodes: 1330 Time cost: 13 ms Efficiency: 98.089830 node/ms Path length: 117 Solution check: pass Benchmark of 4*4 puzzle finished. Benchmarking 5*5 puzzle... Beg: {6, 16, 17, 0, 8, 3, 2, 11, 5, 9, 4, 21, 13, 23, 18, 15, 7, 1, 20, 14, 22, 12, 10, 19, 24} End: {12, 10, 19, 22, 2, 5, 0, 20, 3, 4, 21, 6, 18, 13, 24, 11, 1, 8, 9, 7, 15, 14, 17, 16, 23} Searching... Searched nodes: 3676 Time cost: 43 ms Efficiency: 84.968680 node/ms Path length: 275 Solution check: pass Benchmark of 5*5 puzzle finished. Benchmarking 6*6 puzzle... Beg: {15, 3, 1, 4, 5, 13, 18, 2, 14, 0, 9, 10, 8, 27, 20, 24, 23, 16, 26, 30, 6, 34, 25, 21, 31, 28, 11, 12, 7, 29, 32, 19, 35, 17, 22, 33} End: {13, 6, 9, 2, 27, 16, 11, 14, 12, 15, 21, 17, 7, 20, 32, 4, 5, 3, 10, 18, 8, 19, 29, 23, 1, 26, 25, 24, 34, 33, 31, 35, 30, 0, 22, 28} Searching... Searched nodes: 69271 Time cost: 1088 ms Efficiency: 63.638602 node/ms Path length: 450 Solution check: pass Benchmark of 6*6 puzzle finished. Benchmark of NPuzzle finished.</pre> <h3>Sort</h3> <p>Usage</p> <pre> #include "tastylib/Sort.h" using namespace tastylib; int main() { const unsigned n = 5; int arr[n] = {5, 4, 3, 2, 1}; { // Sort. // Aftering running each of the function below, // the array's content will be: [1, 2, 3, 4, 5] insertionSort(arr, n); selectionSort(arr, n); heapSort(arr, n); quickSort(arr, 0, n - 1); } { // Find the kth smallest element. // After running the function below, the kth // smallest element will be stored at arr[k]. int k = 1; // Find the second smallest element quickSelect(arr, 0, n - 1, k); } return 0; }</pre> <p>Benchmark</p> <p>Cost in theory</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> <th>Stable</th> </tr> </thead> <tbody> <tr> <td><a href="/misc/goto?guid=4959735618165103520" rel="nofollow,noindex">insertionSort()</a></td> <td>O(n^2)</td> <td>Yes</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735618249823201" rel="nofollow,noindex">selectionSort()</a></td> <td>O(n^2)</td> <td>No</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735618336305603" rel="nofollow,noindex">heapSort()</a></td> <td>O(nlogn)</td> <td>No</td> </tr> <tr> <td>mergeSort()</td> <td>O(nlogn)</td> <td>Yes</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735618420073392" rel="nofollow,noindex">quickSort()</a></td> <td>O(nlogn)</td> <td>No</td> </tr> <tr> <td><a href="/misc/goto?guid=4959735618505400737" rel="nofollow,noindex">quickSelect()</a></td> <td>O(n)</td> <td>-</td> </tr> </tbody> </table> <p>Cost in practice</p> <p>Source: <a href="/misc/goto?guid=4959735618588076061" rel="nofollow,noindex">benchmark_Sort.cpp</a></p> <p>The program calculates the average time cost to sort or find the kth element in an array of 100000 elements. Here are the results under different environments:</p> <p>Ubuntu 16.04 64-bit / g++ 5.4</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> </tr> </thead> <tbody> <tr> <td>std::sort()</td> <td>6.41 ms</td> </tr> <tr> <td>insertionSort()</td> <td>1691.64 ms</td> </tr> <tr> <td>selectionSort()</td> <td>12220.25 ms</td> </tr> <tr> <td>heapSort()</td> <td>10.61 ms</td> </tr> <tr> <td>quickSort()</td> <td>7.07 ms</td> </tr> <tr> <td>std::nth_element()</td> <td>0.79 ms</td> </tr> <tr> <td>quickSelect()</td> <td>0.86 ms</td> </tr> </tbody> </table> <p>Windows 10 64-bit / Visual Studio 14 2015</p> <table> <thead> <tr> <th>Operation</th> <th>Time</th> </tr> </thead> <tbody> <tr> <td>std::sort()</td> <td>8.34 ms</td> </tr> <tr> <td>insertionSort()</td> <td>1559.92 ms</td> </tr> <tr> <td>selectionSort()</td> <td>4355.90 ms</td> </tr> <tr> <td>heapSort()</td> <td>11.56 ms</td> </tr> <tr> <td>quickSort()</td> <td>6.79 ms</td> </tr> <tr> <td>std::nth_element()</td> <td>1.08 ms</td> </tr> <tr> <td>quickSelect()</td> <td>0.88 ms</td> </tr> </tbody> </table> <h3>Dijkstra</h3> <p>Usage</p> <pre> #include "tastylib/Dijkstra.h" #include <string> using namespace tastylib; int main() { DijkGraph<string> graph(3); // Create a graph that has three vertices graph[0].val = "Alice"; // Vertex 0 denotes Alice's home graph[1].val = "Darth"; // Vertex 1 denotes Darth's home graph[2].val = "Bob"; // Vertex 2 denotes Bob' home graph.setWeight(0, 1, 5); // Distance from Alice's home to Darth's is 5 graph.setWeight(0, 2, 20); // Distance from Alice's home to Bob's is 20 graph.setWeight(1, 2, 5); // Distance from Darth's home to Bob's is 5 // Run Dijkstra's algorithm to compute the // shortest path from Alice's home to others'. dijkstra(graph, 0); // Now I know the minimum distance from Alice's home to Bob's home, which is 10. auto distToBob = graph[2].dist; // distToBob == 10 // I also know the minimum path to Bob's home is "0->1->2", namely "Alice->Darth->Bob". auto prev1 = graph[2].prev; // prev1 == 1 auto prev2 = graph[prev1].prev; // prev2 == 0 return 0; }</pre> <h2>License</h2> <p>See the <a href="/misc/goto?guid=4959735618668581834" rel="nofollow,noindex">LICENSE</a> file for license rights and limitations.</p> <p> </p> <p>来自：https://github.com/stevennL/TastyLib</p> <p> </p>