Re: Dynamic data structures

On Jul 26, 11:52 am, Roman Töngi <roman.toe...@xxxxxxxxxx> wrote:
I've learned a strategy to resize the size of a data structure to
implement a dynamic data structure as follows:

E.g. for a stack:

- If the stack if full, create a new one with double of the old size.

before insertion operation it looks like:
|xxxxxxxxxx|
after insertion operation:
|xxxxxxxxxx|x         |

- If number of elements in the stack gets below a quarter of the size
   of the stack, create a new one of half the old size.

before deletion operation:
|xxxxx|               |
after deletion operation:
|xxxx |     |
dar
With such a strategy (doubling if full and halving if count gets below 25%),
an amortized worst case analysis shows that the average cost per operation is
constant.

Are there better strategies?

For any simple resizable array, this is the standard approach to limit
copy overhead.

There is no a priori reason the multiple should be 2. Any constant
factor will do.

Certainly for a stack you can use linked nodes or blocks of nodes to
eliminate copying completely.

There are many other approaches that don't require any copying even
for a general resizable array. See for example http://en.wikipedia.org/wiki/VList
(and the Variants note at the end).

.

Relevant Pages

  • Re: irp cloning...
    ... > to the primary device is always corrupted (I am currently unable to ... just looking at copying stack locations which are on the same ... So copying the completion routine or anything after might possibly be a bad ... object & file object pointers might not take kindly to being overwritten. ...
    (microsoft.public.development.device.drivers)
  • Re: Why does the stack have a fixed size?
    ... environments on 32-bit platforms because when you assign a multi-megabyte stack to each thread, address space runs out pretty quickly, even if just a few pages in each stack are ever used. ... Correct AR copying/sharing on stack is as we know very difficult, especially in MT environments. ... how actually do they implement stackless runtimes, there has to be some stack anyway, right? ... I mean both tuned mark'n'sweep and copying allocators should be faster. ...
    (comp.lang.functional)
  • Re: make tree-map tail recursive
    ... Marcin 'Qrczak' Kowalczyk writes: ... call-with-current-continuation efficiently (without copying the stack), ... already have a flexible call stack with no artificial size limit. ... I can't flatten the tree first, ...
    (comp.lang.scheme)
  • Re: make tree-map tail recursive
    ... call-with-current-continuation efficiently (without copying the stack), ... already have a flexible call stack with no artificial size limit. ... materializes the same amount of information in a list. ...
    (comp.lang.scheme)
  • Re: make tree-map tail recursive
    ... call-with-current-continuation efficiently (without copying the stack), ... already have a flexible call stack with no artificial size limit. ... how do repeatable continuations work without ... kept array-like until continuations are captured, ...
    (comp.lang.scheme)