Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Re-orderable keyed access structure?

by kvale (Monsignor)
on Aug 14, 2004 at 03:12 UTC ( #382885=note: print w/replies, xml ) Need Help??


in reply to Re-orderable keyed access structure?

If the array is kept sorted, for some appropriate comparison operator, then searches for keys in that array are all O(log N). Hash lookups are also typically logarithmic, so it seems that array + binary search would do what you want: reorder the array as needed while still locating keys with good efficiency.

-Mark

  • Comment on Re: Re-orderable keyed access structure?

Replies are listed 'Best First'.
Re^2: Re-orderable keyed access structure?
by BrowserUk (Pope) on Aug 14, 2004 at 03:49 UTC

    The ordering of the array isn't dependant upon the values of the referenced items. The positions change purely on the basis of theway in which they are accessed--kind of like a least-recently used or most recently used algorithm--so there is no sort order through which to perform a binary search. That I can see anyway.

    Each time an item is accessed, via it's key, it's position may be changed. Conversely, if an attempt is made to read a new item via its key, and it isn't already in the array, the top item may be popped off the array to free up room for the new item to be added. When this is done, the old item's hash reference must be nulled or deleted.

    Hence the need to able to discover the hash key via it's array index, and it's array index via it's hash key.


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://382885]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2020-02-28 20:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?










    Results (127 votes). Check out past polls.

    Notices?