----- Original Message -----
From: "Gene" <[EMAIL PROTECTED]>
To: "Algorithm Geeks" <algogeeks@googlegroups.com>
Sent: Sunday, November 20, 2005 1:42 PM
Subject: [algogeeks] Re: "Reverse Doubling List" is there an alias?
It would make a nice homework question in an undergraduate data
structures course, and there might be some applications where it
performs marginally better than the standard approach, which is a
single pointer to a single array. To grow the array, allocate new
memory twice as large as the existing, copy the contents, change the
pointer, and free the old.
This data structure I describe both in theory and practice performs
significantly better than the array doubling strategy. It uses significantly
less memory, and doesn't have the worst case complexity of O(N).
I've demonstrated in practice over 2x speedups for push operations when
comparing industrial strength implementation of the C++ std::vector class
which use the doubling strategy. I provide a C++ implementation of this data
type along with detailed benchmarks for download at http://www.ootl.org and
I provide a more detailed explanation of the type at
http://www.ootl.org/doc/stack.html and
http://www.codeproject.com/useritems/fast-stack.asp
Amortized copying costs are O(1) per array
element. Indexing, normally by far the most frequently executed
operation,
That depends entirely on the application. In my experience applications
spend most of their time in iterative loops over the entire collection.
is about as fast as for a fixed size array.
Christopher Diggins
http://www.cdiggins.com
