sequences
Ross Paterson
ross at soi.city.ac.uk
Thu Jun 3 06:18:30 EDT 2004
I've done some crude benchmarking of different implementations of sequences:
(ghc -O, times in microseconds)
test cases
Stack Queue Deque Append Index Update
-------------------------------------------------------------
[] 5399 - - - - -
JoinList 8498 17897 18197 35194 - -
SimpleQueue 9198 12298 - - - -
RealtimeQueue 64290 72389 - - - -
BootQueue 17997 22896 - - - -
BankersQueue 12098 21196 - - - -
BankersDeque 16997 70589 22496 - - -
Catenable 41593 123881 - 77788 - -
CatDeque 57791 145477 62790 132879 - -
RandList 11598 - - - 13498 29895
FingerTree 24996 33894 32994 45293 - -
FingerTreeS 28995 44693 37894 68689 37094 37994
Test cases:
Stack: 100000 random stack operations on a sequence of 2000 elements
Queue: 100000 random queue operations on a sequence of 2000 elements
Deque: 100000 random deque operations on a sequence of 2000 elements
Append: building a sequence of fib 25 elements using appends
Index: 100000 accesses at random indices on a sequence of 2000 elements
Update: 10000 updates at random indices on a sequence of 2000 elements
Implementations:
[] you know; the rest are from Edison or Chris's book (RandList is skew
binary random access lists), except for the last two:
- an implementation using 2-3 finger trees, giving constant time access
to the ends and O(log n) append.
- a variant annotated with size information to support index, update and
split in time O(log(min(i,n-i)).
Conclusions:
- Cute though the real-time queue is, the Banker's version is much better.
- No implementation is clearly superior. A library would need [],
JoinList, BankersQueue, BankersDeque, RandList and at least one with
efficient append. (I've discounted SimpleQueue because it performs
badly in a shared context.) I've argued before that the best way
to express their commonality is using a Haskell 98 constructor class
(albeit a fairly big one).
- Catenable lists and catenable deques are still behind finger trees at
these sizes, though eventually their constant time append will win out.
- Finger trees with sizes look like a reasonable general purpose sequence
implementation. They're not too far behind on every operation,
and they also support split efficiently. Their main weakness is the
O(log n) bound on append. There's a structure by Kaplan and Tarjan
that improves that to O(log(log n)) while keeping the others, but it
looks very complicated (and thus may have large constant factors).
The code is at http://www.soi.city.ac.uk/~ross/seq.tar.gz
docs are at http://www.soi.city.ac.uk/~ross/seq/
More information about the Libraries
mailing list