Orchid XP v7 nous apporta ses lumieres en ce 2007/11/12 13:23:
> Warp wrote:
>> Invisible <voi### [at] devnull> wrote:
>>> Alternatively, you could perform an index lookup.
>>
>>   It's enough for the values to be sorted. Then you can simply perform
>> a binary search. Assuming fast random access the search should take
>> much less than a second.
> 
> Indeed. A binary index lookup and a binary search are equally efficient.
> 
> However, inserting a record for a new atom becomes somewhat 
> compute-intensive if we have to keep all the data in sorted order. (If 
> it's a typical array-like structure, O(n) complexity again. For an 
> index, it's just O(log n) - assuming any rebalancing you choose to do 
> doesn't blow it up.)
> 
> Of course, whether you have an unordered table and seperate index or 
> whether the index *is* the table doesn't matter too much. (Depending on 
> just how much data you store per atom...)
If you have a sorted list of serial numbers, the next item will have it's number 
set as n+1, or 1 after the current last element.
In the case of a balanced tree structure, concidering a tree with about 10^80 
elements, randomly adding a few billions elements is prety much insignifient.

-- 
Alain
-------------------------------------------------
At the feast of ego everyone leaves hungry.
	Bentley's House of Coffee and Tea, Tucson, AZ

Post a reply to this message