performances

[1/3] from: olivier:flauzac:univ-reims at: 17-Jan-2002 11:29

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 ? Thanks Olivier Flauzac University of Reims (France)

[2/3] from: greggirwin:mindspring at: 17-Jan-2002 10:43

Hi Olivier, << 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 ? >> I don't think they publish that information, as it could change in the future. The few notes they do give are that you should use a HASH when you plan to do a lot of lookups and a LIST if you will be doing lots of additions and deletions. Assuming they are appropriately named, I would guess they use a hash table and a linked-list respectively. Was there something specific you wanted to know. Sometimes a member of the RT team will chime in with great technical details you have a specific question. --Gregg

[3/3] 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]