Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^5: Re-orderable keyed access structure?

by Aristotle (Chancellor)
on Aug 14, 2004 at 18:58 UTC ( #383001=note: print w/replies, xml ) Need Help??


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

You will only get away marginally cheaper at best. It's just the way things work in this universe. You need bidirectional lookup on keys and indices, so that's what you'll have to maintain one way or another.

If the double slice my suggestion requires irks you, you can use a $idx => $key hash instead of an array for %key_for. If you have a million short digit-only keys, hash collisions might ruin your day anyway though.

Makeshifts last the longest.

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

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

    I' not irked by the second slice, just exploring the options. Replacing @keyFor with a %keyFor wouldn't work. Once @array has been reordered, the key=>index mappings need an equivalent reordering (hence the second slice), but that would be impossible (or very expensive) using a hash to store them.


    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

      I don't understand your objection.

      sub swap_elements_by_idx { my ( $i, $j ) = @_; @actual_data[ $i, $j ] = @actual_data[ $j, $i ]; @key_for{ $i, $j } = @key_for{ $j, $i }; # note this is a hash now @index_of{ @key_for[ $i, $j ] } = @index_of{ @key_for[ $j, $i ] }; }

      And it doesn't work any differently for multi-element atomic operations.

      Makeshifts last the longest.

        The objection is that it doesn't do what I need it to. Taking an element from the middle of the stack and moving it to the top or the bottom.

        push @array, splice @array, $itemToMove, 1;

        Doing this using swap_elements_by_idx() would require iterating over the length of both @actual_data and @key_for arrays. Either of the working schemes is better than this as they only iterate one structure not two.


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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (2)
As of 2020-02-23 08:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?










    Results (102 votes). Check out past polls.

    Notices?