Dynamic data structures
in [General Programming]
|
Prev: RS 232C programming for NEC LCD 4620
Next: boss herrenkleidung online linus herrenmode kaufen boss herrenmode kaufen herrenmode kaufen braeutigam we herrenmode kaufen
From: Roman Töngi on 26 Jul 2008 11:52 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 | | 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? Thanks a lot.
From: Pascal J. Bourguignon on 26 Jul 2008 12:41 Roman T�ngi <roman.toengi(a)hispeed.ch> writes: > 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. > [...] > 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? In the case of a stack, you don't need to use one big block, you can easily use a stack of small blocks. Even for datastructure with other access mode (eg arrays with random access), you can use this trick, adding just an indirection on each access. See for example: http://groups.google.com/group/comp.lang.lisp/msg/31dc2d17f972941c -- __Pascal Bourguignon__ http://www.informatimago.com/ Kitty like plastic. Confuses for litter box. Don't leave tarp around.
From: Gene on 27 Jul 2008 17:11
On Jul 26, 11:52 am, Roman Töngi <roman.toe...(a)hispeed.ch> 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). |