forked from fjtapia/sort_parallel
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathREADME.html
More file actions
112 lines (90 loc) · 5.33 KB
/
README.html
File metadata and controls
112 lines (90 loc) · 5.33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
<h1><a href="https://github.com/fjtapia/sort_parallel">sort::parallel</a> </h1>
<ul>
<li><p>In this <strong>parallel library</strong>, you can find stable and not stable sort algorithms, in a <strong>single thread and parallel version</strong>,
with similar performance than the provided by other libraries as TBB, Cilk, OpenMP or IPP. </p></li>
<li><p>The intention is to create algorithms <strong>only with the utilities provided by C++11</strong>, without any other library.
Any C++11 compliant compiler can compile and run these algorithms.</p></li>
<li><p>These algorithms are <strong>generic</strong>, can sort any kind of object using a comparison object, in contrast with the
<strong>specialized</strong> algorithms, as spreadsort, which only sort integers, strings and float values in a single
thread version, but with a speed greater than the generic sort algorithms.</p></li>
<li><p>The algorithms are <strong>exception safe</strong>, it means, the exceptions generated by the algorithms guarantee the integrity
of the objects to sort, but not they relative order.
If the exception is generate inside the objects (in the move or in the copy constructor..) the results can be unpredictable.</p></li>
</ul>
<h2>Algorithms</h2>
<ol>
<li><p><strong>introsort</strong></p>
<ul>
<li><em>Parallel :</em> no</li>
<li><em>Stable :</em> no<br></li>
<li><em>Additional Memory :</em> Log(N)<br></li>
<li><em>Best case :</em> N Log(N)<br></li>
<li><em>Average case :</em> N Log(N) </li>
<li><em>Worst case :</em> N Log(N) </li>
</ul></li>
<li><p><strong>parallel_introsort</strong></p>
<ul>
<li><em>Parallel :</em> yes</li>
<li><em>Stable :</em> no<br></li>
<li><em>Additional Memory :</em> Log(N)<br></li>
<li><em>Best case :</em> N Log(N)<br></li>
<li><em>Average case :</em> N Log(N) </li>
<li><em>Worst case :</em> N Log(N) </li>
</ul></li>
<li><p><strong>smart_</strong><strong>merge_sort</strong> </p>
<ul>
<li><em>Parallel :</em> no</li>
<li><em>Stable :</em> yes<br></li>
<li><em>Additional Memory :</em> N / 2 </li>
<li><em>Best case :</em> N Log(N)<br></li>
<li><em>Average case :</em> N Log(N) </li>
<li><em>Worst case :</em> N Log(N) </li>
</ul></li>
<li><p><strong>parallel_</strong><strong>stable_sort</strong></p>
<ul>
<li><em>Parallel :</em> yes</li>
<li><em>Stable :</em> yes<br></li>
<li><em>Additional Memory :</em> N / 2 </li>
<li><em>Best case :</em> N Log(N)<br></li>
<li><em>Average case :</em> N Log(N) </li>
<li><em>Worst case :</em> N Log(N) </li>
</ul></li>
<li><p><strong>sample_sort</strong></p>
<ul>
<li><em>Parallel :</em> yes</li>
<li><em>Stable :</em> yes<br></li>
<li><em>Additional Memory :</em> N<br></li>
<li><em>Best case :</em> N Log(N)<br></li>
<li><em>Average case :</em> N Log(N) </li>
<li><em>Worst case :</em> N Log(N)</li>
</ul></li>
</ol>
<h2>Benchmarks</h2>
<p>The speed of the algorithm over a machine depend, mainly of the algorithm, but also of the processor (speed, number of HW threads), memory and cache memory.</p>
<p>In the folder benchmarks, you have an easy and fast benchmark, for to check the speed of the algorithms on your computer.</p>
<p>There are versions for several compilers. In the folder you can find a README.txt with instructions about how to run the benchmarks.</p>
<p>The compilation need about 2 mins and the running about 5 mins, depending of your computer.</p>
<ul>
<li><em>GCC</em> :GCC compiler over a Linux x64</li>
<li><em>CLANG</em> : CLANG compiler over a Linux x64</li>
<li><em>VC++</em> : Visual C++ over a Windows</li>
</ul>
<h2>Author and Copyright </h2>
<p>This library had been created for to be integrated in the <a href="http://www.boost.org">Boost</a> Library, inside
the <a href="http://www.boost.org/doc/libs/release/libs/sort">boost::sort library</a>, with the spreadsort algorithms designed and implemented by Steven Ross.<br>
It is pending of the final approval, due this, can suffer some changes until the final version and definitive approval in the Boost Library.<br>
You can find in <a href="https://github.com/fjtapia/sort_parallel">https://github.com/fjtapia/sort_parallel</a> </p>
<p>Copyright 2015 <a href="mail:fjtapia@gmail.com">Francisco Tapia <em>(fjtapia@gmail.com)</em> </a>.
Distributed under the <a href="http://www.boost.org/LICENSE_1_0.txt">Boost Software License, Version 1.0. </a> <em>(See http://www.boost.org/LICENSE<em>1</em>0.txt)</em></p>
<p>The <a href="http://www.boost.org">Boost</a> Library<br>
<strong>"...one of the most highly regarded and expertly designed C++ library projects in the world."</strong> <em>Herb Sutter and Andrei Alexandrescu, C++ Coding Standards.</em> </p>
<h2>Installation</h2>
<ul>
<li>This library is include only. </li>
<li>Don't need to link with any static or dynamic library.<br></li>
<li>Don't have any dependence of any other Boost or external libraries.<br></li>
<li>For to use, only need a to include the files of the boost/sort/parallel folder, any more. </li>
<li>This library had been compiled successfully with the next compilers : GCC 4.7, GCC 4.8, GCC 4.9 , CLANG 3.6, Visual C++ 2013 Update 4, Visual C++ 2015</li>
</ul>
<hr>
<p><em>Copyright 2015 <a href="mail:fjtapia@gmail.com">Francisco Tapia (fjtapia@gmail.com) </a></em></p>