Module binary_tree::count
[−]
[src]
Counting tree implementation.
When should you use CountTree
?
- You want to maintain a possibly large unsorted list.
- You want to access, modify, insert, and delete elements at arbitrary position with O(log(n)) time complexity.
- You can tolerate O(n log(n)) time-complexity for (not implemented yet):
- splitting at arbitrary position
- truncating the length (complexity unclear)
- appending another list (complexity unclear)
- You have less than 4.29 billion (
u32::MAX
) elements!
Benchmarks
The constants in the complexity bounds are not small enough to make an
immediate switch from Vec
to CountTree
. In the benchmarks below, *_ct
indicate CountTree
, *_ll
indicate LinkedList
and *_vec
indicate
Vec
. from_iter_*
indicate the performance of using collect()
,
insert_at_random_*
indicate that of inserting N elements at random
positions, and remove_at_random_*
indicate that of first creating an N
sized object using collect()
and then removing all N elements at random
one-by-one. See benches
directory for more details.
Bench: N=2048
Running target/release/from_iter-86b0c3c534a106e8
running 3 tests
test from_iter_ct ... bench: 316,440 ns/iter (+/- 92,914)
test from_iter_ll ... bench: 299,755 ns/iter (+/- 2,096)
test from_iter_vec ... bench: 2,839 ns/iter (+/- 24)
Running target/release/insert-892f694b6341f60d
running 3 tests
test insert_at_random_ct ... bench: 1,569,694 ns/iter (+/- 239,724)
test insert_at_random_ll ... bench: 2,882,318 ns/iter (+/- 20,555)
test insert_at_random_vec ... bench: 570,018 ns/iter (+/- 3,710)
Running target/release/remove-12ee8f5093c08f36
running 3 tests
test remove_at_random_ct ... bench: 1,800,295 ns/iter (+/- 5,761)
test remove_at_random_ll ... bench: 2,702,035 ns/iter (+/- 22,632)
test remove_at_random_vec ... bench: 568,502 ns/iter (+/- 3,626)
Bench: N=4096
Running target/release/from_iter-86b0c3c534a106e8
running 3 tests
test from_iter_ct ... bench: 698,944 ns/iter (+/- 25,819)
test from_iter_ll ... bench: 579,370 ns/iter (+/- 12,161)
test from_iter_vec ... bench: 5,582 ns/iter (+/- 26)
Running target/release/insert-892f694b6341f60d
running 3 tests
test insert_at_random_ct ... bench: 3,495,019 ns/iter (+/- 123,200)
test insert_at_random_ll ... bench: 14,470,666 ns/iter (+/- 39,605)
test insert_at_random_vec ... bench: 1,896,108 ns/iter (+/- 3,925)
Running target/release/remove-12ee8f5093c08f36
running 3 tests
test remove_at_random_ct ... bench: 3,966,049 ns/iter (+/- 25,852)
test remove_at_random_ll ... bench: 11,981,076 ns/iter (+/- 77,152)
test remove_at_random_vec ... bench: 1,909,054 ns/iter (+/- 5,475)
Bench: N=8192
Running target/release/from_iter-86b0c3c534a106e8
running 3 tests
test from_iter_ct ... bench: 1,422,694 ns/iter (+/- 224,526)
test from_iter_ll ... bench: 1,190,954 ns/iter (+/- 17,328)
test from_iter_vec ... bench: 11,487 ns/iter (+/- 52)
Running target/release/insert-892f694b6341f60d
running 3 tests
test insert_at_random_ct ... bench: 7,651,408 ns/iter (+/- 232,136)
test insert_at_random_ll ... bench: 67,522,968 ns/iter (+/- 508,089)
test insert_at_random_vec ... bench: 8,062,135 ns/iter (+/- 46,386)
Running target/release/remove-12ee8f5093c08f36
running 3 tests
test remove_at_random_ct ... bench: 8,972,611 ns/iter (+/- 99,882)
test remove_at_random_ll ... bench: 50,513,436 ns/iter (+/- 161,649)
test remove_at_random_vec ... bench: 8,166,272 ns/iter (+/- 35,268)
Conclusion
In short, if you want to maintiain a list of type T
such that:
[number of elements] * [size of T] > 256 KB
then CountTree
might be a good choice, otherwise you are better off using
Vec
.
Structs
CountNode |
Node of a |
CountTree |
Counting tree. |
IntoIter | |
Iter |
Type Definitions
NodePtr |