[REBOL] Re: performances
From: holger::rebol::com at: 17-Jan-2002 9:59
On Thu, Jan 17, 2002 at 11:29:58AM +0100, olivier flauzac wrote:
> Hi,
>
> is it possible to get complexity, memory structure, and performances, of
> rebol's elements, and more particularly rebol's list and blocks data types
> and algorithms ?
It should be pretty much self-explanatory, from the datatype.
Blocks are basically arrays. Hashes are arrays with a hash table for
all entries, making 'find operations quicker, and lists are linked
lists.
Complexities are as you would expect them, e.g. 'find is
O(n) in a block! or list!, and anywhere from O(1) to O(n) (O(n) worst
case) in a hash!, depending on the effectiveness of hashing. O(1) is
typical though. Insertion and deletion are O(1) at the tail of any data
structure, O(n) anywhere else, except for list!, where they are O(1)
everywhere.
Hashes are useful as a replacement for blocks when keyed lookups
are needed. Lists are useful for queues or stacks. Lists should be
used carefully though: generally you should only use insertion,
deletion and back,next,skip. Many other operations, even index?,
are O(n), and thus negate the advantage of using a list!.
--
Holger Kruse
[holger--rebol--com]
