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...)

Post a reply to this message