source: trip-planner-front/node_modules/timsort/README.md@ 1ad8e64

Last change on this file since 1ad8e64 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 7.9 KB
Line 
1# Node-TimSort: Fast Sorting for Node.js
2
3[![Build Status](https://travis-ci.org/mziccard/node-timsort.svg?branch=master)](https://travis-ci.org/mziccard/node-timsort)
4[![npm version](https://badge.fury.io/js/timsort.svg)](https://www.npmjs.com/package/timsort)
5
6An adaptive and **stable** sort algorithm based on merging that requires fewer than nlog(n)
7comparisons when run on partially sorted arrays. The algorithm uses O(n) memory and still runs in O(nlogn)
8(worst case) on random arrays.
9This implementation is based on the original
10[TimSort](http://svn.python.org/projects/python/trunk/Objects/listsort.txt) developed
11by Tim Peters for Python's lists (code [here](http://svn.python.org/projects/python/trunk/Objects/listobject.c)).
12TimSort has been also adopted in Java starting from version 7.
13
14## Acknowledgments
15
16- @novacrazy: ported the module to ES6/ES7 and made it available via bower
17- @kasperisager: implemented faster lexicographic comparison of small integers
18
19## Usage
20
21Install the package with npm:
22```
23npm install --save timsort
24```
25And use it:
26```javascript
27var TimSort = require('timsort');
28
29var arr = [...];
30TimSort.sort(arr);
31```
32You can also install it with bower:
33```
34bower install timsort
35```
36As `array.sort()` by default the `timsort` module sorts according to
37lexicographical order.
38You can also provide your own compare function (to sort any object) as:
39```javascript
40function numberCompare(a,b) {
41 return a-b;
42}
43
44var arr = [...];
45var TimSort = require('timsort');
46TimSort.sort(arr, numberCompare);
47```
48You can also sort only a specific subrange of the array:
49```javascript
50TimSort.sort(arr, 5, 10);
51TimSort.sort(arr, numberCompare, 5, 10);
52```
53
54## Performance
55
56A benchmark is provided in `benchmark/index.js`. It compares the `timsort` module against
57the default `array.sort` method in the numerical sorting of different types of integer array
58(as described [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt)):
59
60- *Random array*
61- *Descending array*
62- *Ascending array*
63- *Ascending array with 3 random exchanges*
64- *Ascending array with 10 random numbers in the end*
65- *Array of equal elements*
66- *Random Array with many duplicates*
67- *Random Array with some duplicates*
68
69For any of the array types the sorting is repeated several times and for
70different array sizes, average execution time is then printed.
71I run the benchmark on Node v6.3.1 (both pre-compiled and compiled from source,
72results are very similar), obtaining the following values:
73
74<table>
75 <tr>
76 <th></th><th></th>
77 <th colspan="2">Execution Time (ns)</th>
78 <th rowspan="2">Speedup</th>
79 </tr>
80 <tr>
81 <th>Array Type</th>
82 <th>Length</th>
83 <th>TimSort.sort</th>
84 <th>array.sort</th>
85 </tr>
86<tbody>
87 <tr>
88 <td rowspan="4">Random</td><td>10</td><td>404</td><td>1583</td><td>3.91</td>
89 </tr>
90 <tr>
91 <td>100</td><td>7147</td><td>4442</td><td>0.62</td>
92 </tr>
93 <tr>
94 <td>1000</td><td>96395</td><td>59979</td><td>0.62</td>
95 </tr>
96 <tr>
97 <td>10000</td><td>1341044</td><td>6098065</td><td>4.55</td>
98 </tr>
99 <tr>
100 <td rowspan="4">Descending</td><td>10</td><td>180</td><td>1881</td><td>10.41</td>
101 </tr>
102 <tr>
103 <td>100</td><td>682</td><td>19210</td><td>28.14</td>
104</tr>
105 <tr>
106 <td>1000</td><td>3809</td><td>185185</td><td>48.61</td>
107 </tr>
108 <tr>
109 <td>10000</td><td>35878</td><td>5392428</td><td>150.30</td>
110 </tr>
111 <tr>
112 <td rowspan="4">Ascending</td><td>10</td><td>173</td><td>816</td><td>4.69</td>
113 </tr>
114 <tr>
115 <td>100</td><td>578</td><td>18147</td><td>31.34</td>
116 </tr>
117 <tr>
118 <td>1000</td><td>2551</td><td>331993</td><td>130.12</td>
119 </tr>
120 <tr>
121 <td>10000</td><td>22098</td><td>5382446</td><td>243.57</td>
122 </tr>
123 <tr>
124 <td rowspan="4">Ascending + 3 Rand Exc</td><td>10</td><td>232</td><td>927</td><td>3.99</td>
125 </tr>
126 <tr>
127 <td>100</td><td>1059</td><td>15792</td><td>14.90</td>
128 </tr>
129 <tr>
130 <td>1000</td><td>3525</td><td>300708</td><td>85.29</td>
131 </tr>
132 <tr>
133 <td>10000</td><td>27455</td><td>4781370</td><td>174.15</td>
134 </tr>
135 <tr>
136 <td rowspan="4">Ascending + 10 Rand End</td><td>10</td><td>378</td><td>1425</td><td>3.77</td>
137 </tr>
138 <tr>
139 <td>100</td><td>1707</td><td>23346</td><td>13.67</td>
140 </tr>
141 <tr>
142 <td>1000</td><td>5818</td><td>334744</td><td>57.53</td>
143 </tr>
144 <tr>
145 <td>10000</td><td>38034</td><td>4985473</td><td>131.08</td>
146 </tr>
147 <tr>
148 <td rowspan="4">Equal Elements</td><td>10</td><td>164</td><td>766</td><td>4.68</td>
149 </tr>
150 <tr>
151 <td>100</td><td>520</td><td>3188</td><td>6.12</td>
152 </tr>
153 <tr>
154 <td>1000</td><td>2340</td><td>27971</td><td>11.95</td>
155 </tr>
156 <tr>
157 <td>10000</td><td>17011</td><td>281672</td><td>16.56</td>
158 </tr>
159 <tr>
160 <td rowspan="4">Many Repetitions</td><td>10</td><td>396</td><td>1482</td><td>3.74</td>
161 </tr>
162 <tr>
163 <td>100</td><td>7282</td><td>25267</td><td>3.47</td>
164 </tr>
165 <tr>
166 <td>1000</td><td>105528</td><td>420120</td><td>3.98</td>
167 </tr>
168 <tr>
169 <td>10000</td><td>1396120</td><td>5787399</td><td>4.15</td>
170 </tr>
171 <tr>
172 <td rowspan="4">Some Repetitions</td><td>10</td><td>390</td><td>1463</td><td>3.75</td>
173 </tr>
174 <tr>
175 <td>100</td><td>6678</td><td>20082</td><td>3.01</td>
176 </tr>
177 <tr>
178 <td>1000</td><td>104344</td><td>374103</td><td>3.59</td>
179 </tr>
180 <tr>
181 <td>10000</td><td>1333816</td><td>5474000</td><td>4.10</td>
182 </tr>
183</tbody>
184</table>
185
186`TimSort.sort` **is faster** than `array.sort` on almost of the tested array types.
187In general, the more ordered the array is the better `TimSort.sort` performs with respect to `array.sort` (up to 243 times faster on already sorted arrays).
188And also, in general, the bigger the array the more we benefit from using
189the `timsort` module.
190
191These data strongly depend on Node.js version and the machine on which the benchmark is run. I strongly encourage you to run the benchmark on your own setup with:
192```
193npm run benchmark
194```
195Please also notice that:
196
197- This benchmark is far from exhaustive. Several cases are not considered
198and the results must be taken as partial
199- *inlining* is surely playing an active role in `timsort` module's good performance
200- A more accurate comparison of the algorithms would require implementing `array.sort` in pure javascript
201and counting element comparisons
202
203## Stability
204
205TimSort is *stable* which means that equal items maintain their relative order
206after sorting. Stability is a desirable property for a sorting algorithm.
207Consider the following array of items with an height and a weight.
208```javascript
209[
210 { height: 100, weight: 80 },
211 { height: 90, weight: 90 },
212 { height: 70, weight: 95 },
213 { height: 100, weight: 100 },
214 { height: 80, weight: 110 },
215 { height: 110, weight: 115 },
216 { height: 100, weight: 120 },
217 { height: 70, weight: 125 },
218 { height: 70, weight: 130 },
219 { height: 100, weight: 135 },
220 { height: 75, weight: 140 },
221 { height: 70, weight: 140 }
222]
223```
224Items are already sorted by `weight`. Sorting the array
225according to the item's `height` with the `timsort` module
226results in the following array:
227```javascript
228[
229 { height: 70, weight: 95 },
230 { height: 70, weight: 125 },
231 { height: 70, weight: 130 },
232 { height: 70, weight: 140 },
233 { height: 75, weight: 140 },
234 { height: 80, weight: 110 },
235 { height: 90, weight: 90 },
236 { height: 100, weight: 80 },
237 { height: 100, weight: 100 },
238 { height: 100, weight: 120 },
239 { height: 100, weight: 135 },
240 { height: 110, weight: 115 }
241]
242```
243Items with the same `height` are still sorted by `weight` which means they preserved their relative order.
244
245`array.sort`, instead, is not guarranteed to be *stable*. In Node v0.12.7
246sorting the previous array by `height` with `array.sort` results in:
247```javascript
248[
249 { height: 70, weight: 140 },
250 { height: 70, weight: 95 },
251 { height: 70, weight: 125 },
252 { height: 70, weight: 130 },
253 { height: 75, weight: 140 },
254 { height: 80, weight: 110 },
255 { height: 90, weight: 90 },
256 { height: 100, weight: 100 },
257 { height: 100, weight: 80 },
258 { height: 100, weight: 135 },
259 { height: 100, weight: 120 },
260 { height: 110, weight: 115 }
261]
262```
263As you can see the sorting did not preserve `weight` ordering for items with the
264same `height`.
Note: See TracBrowser for help on using the repository browser.