PERFORMANCE: list versus a "dlist"

[Robin Becker]

In article <39398DC0.C04E9784 at san.rr.com>, Courageous
<jkraska1 at san.rr.com> writes
>
>Python lists, which are in actuality tail-preallocated dynamic
>arrays, are compared to the performance of a similar dynamic
>array using a head and tail preallocation strategy. This
>construct is referred to as a "dlist" -- a double-ended list.
>
>The tail preallocation strategy for the dlist involved
>keeping actual length and allocated length, and doubling the
>allocated space whenever an addition would involve appending
>past the allocated region.
>
>The head preallocation strategy involved keeping a "virtual
>index" into the array which is initially set to a position
>into the allocated region of memory at a position corresponding
>to 1/3 of the way through. Certain critical conditions are
>monitored which will trigger a reset to 1/3 of the way through
>via either a reallocate/copy or a simple move, depending on
>circumstance.
>
>The performance of this construct is compared to python's
>list as a FIFO (insert at head, pop at tail). Results are
>reported as follows:
>
>#insert/delete       DLIST            LIST
>
>100                  .006             .006
>1000                 .006             .018
>10000                .065             .365
>
>As before, on containers containing < 100 items or so, the
>use of this additional datatype made no measurable difference
>in performance of the tests. However, at list sizes at or near
>1000 elements, the DLIST implementation broke forth as a clear
>winner, where scaleability of the dlist imeplementation seemed
>to indicate at or near O(1)+k cost for insertion at the head.
>
>This is an early implemenation of this datstructure, and none
>of the typical sequence manipulation code is available for it
>as of yet.
>
>
>
>
>
>C/
so how about also doing some random tests (or assuming I'm perverse) the
worst case for your dlist ie insert and remove in the middle.
-- 
Robin Becker