----- Original Message -----
From: "Gene" <[EMAIL PROTECTED]>
To: "Algorithm Geeks" <algogeeks@googlegroups.com>
Sent: Sunday, November 20, 2005 11:58 PM
Subject: [algogeeks] Re: "Reverse Doubling List" is there an alias?
I didn't mean anything negative. You asked whether the idea was common
knowledge. I've seen it used as a homework problem e.g. after the
introduction of Fibonacci heaps.
I see, no harm done. Email has a way of making things sound more impolite
then intended.
Last time for sure was 1984. Usually
homework problems fall in the domain of "common knowedge."
Googling "linked list of arrays" provides
http://en.wikipedia.org/wiki/VList
Great link, thank you.
"... the VList is a persistent data structure designed by Phil Bagwell
in 2002 that combines the fast indexing of arrays with the easy
extension of cons-based (or singly-linked) linked lists ... "
I guess yours aren't persistent, but otherwise the idea seems to match.
You are correct on both fronts.
Certainly you've picked the benchmark cases where the vlist advantages
over a pointer to a single array. I can't see how the vlist would
intrinsically use less memory unless you mean they may causes less heap
fragmentation, which I can believe.
During allocations the doubling strategy requires 3N memory (the old array
and the new double array have to be kept in memory simultaneously, whereas
the VList strategy uses at most 2N at any one time.
As you say, applications tend to iterate over vectors. Indexing VLists
will require more instructions than indexing a single vector,
Iteration does not neccessarily imply indexing. Performance of my vlist
implementation is about twice as slow for indexing, but slightly better for
iteration. More benchmarks are provided at
http://www.artima.com/weblogs/viewpost.jsp?thread=137357
which
your benchmark shows. This was the basis for my "marginally better"
guess: what is saves while pushing can easily be lost again while
traversing.
So as I point out, iteration is very fast, and in my benchmarks actually
outperformed the C++ method. Due to the usage of function objects.
benchmarking : vector_iteration(vec) = 1358 msec
benchmarking : stack_iteration(grown_stack) = 1297 msec
I just want to point out though that that while iteration and indexing may
be frequent they often represent relatively little of the total processing
time of an application, due to the relatively expense of
allocation/deallocation operations. There is a big difference between the
operation count, and the total percentage of computing of an application it
represents. Perform lots of string concatenations in a naive fashion in a
C++ application, and you'll see what I mean.
To be fair about comparing with the usual STL implementation you ought
to point out that when many items are to be pushed onto a vector most
libraries let you pre-allocate the space.
I implemented this feature in the OOTL stack as well. However, I did not
view this as a particularly relevant detail. If the number of items are
predetermined then the most appropriate data structure would likely be an
array, and not a stack.
E.g. in C++ you can say
v.reserve(1000). before pushing a thousand new elements on v. In this
way you avoid a lot of copying overhead.
Best regards!
Thanks for responding, and especially for finding that information about
vlists!
Christopher Diggins
http://www.cdiggins.com
