Skip to content

Instantly share code, notes, and snippets.

@khia khia/gist:3900083
Created Oct 16, 2012

Embed
What would you like to do?
```
Performance:
| asymptotic | length |
| | 10 | 100 | 1000 | 10000 |
| |min med max avg|min med max avg|min med max avg|min med max avg|
cons | | 0, 0, 537, 0 | 0, 0, 572, 0 | 0, 0, 223, 0 | 0, 0, 431, 0 |
drop | | 0, 0, 204, 0 | 0, 1, 356, 1 | 1, 1, 204, 1 | 1, 1, 450, 2 |
drop_tail | | 2, 3, 393, 3 | 1, 2, 588, 2 |294,302,501,306|2627,2768,9390,2812|
drop_tail_r| | 1, 2, 588, 2 | 16,17,404,17 |156,165,385,167|1364,1486,3650,1498|
from_list_r| | 0, 1, 405, 1 | 9,10,519,10 |112,114,879,116| 996,1037,3104,1060|
head | | 0, 0, 293, 0 | 0, 0, 638, 0 | 0, 0, 314, 0 | 0, 0, 514, 0 |
head_tail | | 0, 0, 237, 0 | 0, 0, 341, 0 | 0, 0, 493, 0 | 0, 0, 434, 0 |
insert | | 7, 8, 216, 8 | 70,71,274,72 |649,667,2778,669|6391,7382,16841,7525|
is_empty | | 0, 0, 409, 0 | 0, 0, 451, 0 | 0, 0, 280, 0 | 0, 0, 554, 0 |
last | | 0, 0, 524, 0 | 0, 1, 622, 1 | 0, 1, 301, 1 | 1, 1, 723, 1 |
len | | 0, 0, 364, 0 | 0, 0, 403, 0 | 0, 0, 301, 0 | 0, 0, 334, 0 |
map | | 4, 5, 509, 5 | 50,54,237,54 |492,532,1351,533|4831,5316,13589,5445|
map_r | | 1, 1, 227, 2 | 13,14,284,14 |126,138,932,138|1346,1455,4835,1448|
next | | 0, 0, 217, 1 | 0, 0, 306, 0 | 0, 0, 230, 1 | 0, 0, 340, 0 |
nth | | 0, 0, 355, 0 | 0, 0, 509, 1 | 0, 1, 284, 1 | 0, 1, 418, 1 |
prev | | 0, 0, 360, 0 | 0, 0, 276, 0 | 0, 0, 224, 0 | 0, 0, 496, 0 |
reduce | | 1, 2, 864, 2 | 16,16,513,17 |153,156,1571,159|1563,1639,3658,1647|
reduce_r | | 0, 1, 512, 1 | 4, 4, 523, 4 | 38,40,732,40 |390,403,1148,404|
reverse | | 2, 2, 408, 2 |25, 26, 690, 27|265,274,503,274|2274,2453,6196,2507|
split | | 2, 3, 473, 3 |26, 27, 213, 27|255,265,2237,269|2275,2415,7137,2455|
tail | | 0, 0, 412, 0 | 0, 0, 593, 0 | 0, 0, 273, 0 | 0, 0, 567, 0 |
to_list | | 1, 1, 246, 1 | 13,14,577,14 |135,139,351,141|1240,1306,4052,1303|
to_r_list | | 1, 1, 400, 1 | 13,14,344,14 |135,139,2098,142|1243,1425,5175,1446|
update | | 0, 1, 214, 1 | 0, 1, 521, 1 | 1, 1, 247, 2 | 1, 2, 316, 2 |
zipper_head| | 1, 2, 198, 2 | 15,16,595,17 |135,142,978,144|1377,1489,3540,1507|
zipper_tail| | 1, 2, 98, 2 | 16,17,198,17 |148,163,2170,161|1363,1459,5004,1479|
For comparison on the same hardware performance of list structure is
| asymptotic | length |
| | 10 | 100 | 1000 | 10000 |
| |min med max avg|min med max avg|min med max avg|min med max avg|
cons: | | 0, 0, 713, 0 | 0, 0, 868, 0 | 0, 0, 538, 0 | 0, 0, 84, 0 |
head: | | 0, 0, 990, 0 | 0, 0, 747, 0 | 0, 0, 546, 0 | 0, 0, 2861, 0 |
is_empty:| | 0, 0, 1102, 0 | 0, 0, 790, 0 | 0, 0, 679, 0 | 0, 0, 2773, 0 |
len: | | 0, 0, 1039, 0 | 0, 0, 759, 0 | 1, 1, 740, 1 | 11,12,2941,13 |
map: | | 0, 0, 1709, 1 | 3, 4, 1490,4 | 34,36,1771,36 |358,383,2402,387|
reduce: | | 0, 0, 1154, 1 | 3, 3, 1168,3 | 29,31,3116,32 |299,300,3102,301|
reverse: | | 0, 0, 753, 0 | 0, 1, 1505,1 | 2, 4, 1723,5 | 44,70,3082,93 |
tail: | | 0, 0, 996, 0 | 0, 0, 764, 0 | 0, 0, 723, 0 | 0, 0, 2843, 0 |
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.