search

apple / swift-collections

Commonly used data structures for Swift
Apache License 2.0
3.69k stars 283 forks source link

[Treap] Fast random insertions collection #124

Open alexdremov opened 2 years ago

alexdremov commented 2 years ago

At this moment, no collection can address random insertions. I have a data structure implemented through implicit Treap that behaves like a general array but can do random insertions/deletions/access with O(log n).

If such a container is needed, I can open a PR. What do you think?

alexdremov commented 2 years ago

At the meantime, here is the comparison. The better performance is noticeable at n ~ 10^4

Screenshot-2021-11-13-at-13-01-57 Screenshot-2021-11-13-at-12-54-34 Screenshot-2021-11-13-at-13-01-25 Screenshot-2021-11-13-at-13-04-55
alexdremov commented 2 years ago

Opened a topic on the forum: https://forums.swift.org/t/treap-fast-random-insertions-deletions-collection/53468

alexdremov commented 1 year ago

As it seems like it is not really needed in swift-collections, I've created a package that has more efficient implementation. Also, I benchmarked the solution and created comparison graphs.

AlexRoar/TreeArray

Preview:

Random insertions

Random removals

Prepend

Remove first