Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Re-orderable keyed access structure?

by BrowserUk (Pope)
on Aug 14, 2004 at 03:54 UTC ( #382891=note: print w/replies, xml ) Need Help??


in reply to Re: Re-orderable keyed access structure?
in thread Re-orderable keyed access structure?

Everytime an array element changed position, not only it's index changes, but a lot of--and sometimes all--other array elements indices change also. That would require iterating the hash (via the array of keys) to adjust all the embedded indices.

It's not the complexity that is the problem, it is the time element.


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
  • Comment on Re^2: Re-orderable keyed access structure?

Replies are listed 'Best First'.
Re^3: Re-orderable keyed access structure?
by etcshadow (Priest) on Aug 14, 2004 at 04:00 UTC
    So you want to be able to find the index by searching on the key (and you want this to be fast, i.e. not scanning an array)... this indicates that at some level you can find the array index from within the value of hash by key. But you also want to be able to update all of the indexes without iterating said hash? That seems like a contradiction. I must be misunderstanding something.
    ------------ :Wq Not an editor command: Wq

      If the hash values are references to the array elements (not indices), then even if I shuffle the array, I can still find the correct array elements directly through their hash keys. The references to the individual elements of the array don't change when the hash is re-ordered.


      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
        OK, so if you need to be able to get from key to payload, but not from key to index, then how about:
        • a hash of $key => $data
        • a hash of $data => $key (that is the stringification of the ref stored in $data... maybe consider making this a Tie::RefHash, if you want)
        • an array of hash keys
        ------------ :Wq Not an editor command: Wq

      If the hash values are references to the array elements (not indices), then even if I shuffle the array, I can still find the correct array elements directly through their hash keys. The references to the individual elements of the array don't change when the hash is re-ordered. The indices do.


      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://382891]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2019-10-16 21:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?