Re: Dynamic data structures

Roman Töngi <roman.toengi@xxxxxxxxxx> 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.
.

Relevant Pages

  • Re: why push and pop?
    ... > about where the names for stack operations came from until now. ... The canonical example of a stack is the "dishwell" at your local resturant. ... They apply to nearly any dynamic data structure. ... > find that Randall Hyde posts here. ...
    (comp.lang.asm.x86)
  • Re: ALLOCATABLE arrays
    ... || If try to create a very large array on the stack and you do not have enough ... || Allocating on the heap gives you access to a hell of a lot more memory (well ... and "heap" (and there probably are/were some computers which don't/didn't ... | Automatic arrays are always allocated on the stack. ...
    (comp.lang.fortran)
  • Re: Fortran memory allocation (stack/heap) issues
    ... > rather than Fortran, ... dynamic allocation, and relatively little stack allocation. ... value return and arrays by reference. ...
    (comp.lang.fortran)
  • Re: Stack or Heap
    ... it ran out of stack space. ... combined with a default that puts many arrays on the stack ... which conforms with the C-standard will compile without error ... seg fault due to stack/heap issues. ...
    (comp.lang.fortran)
  • Re: Need some help understanding array definitions
    ... Data structures defined with VARIABLE, CREATE, VALUE, CONSTANT, and related words are, indeed, all global. ... Unlike some languages, Forth doesn't discourage defining global data structures, but it's important to understand their proper use. ... They provide for "persistent" data, as well as space for strings and arrays. ... Strings and arrays should be in defined data structures and referenced by address and length or address on the stack. ...
    (comp.lang.forth)