Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Re-orderable keyed access structure?

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


in reply to Re-orderable keyed access structure?

You don't need another level of indirection, you need to make your indirection bidirectional. Besides the actual array storing the values, use a hash to look up positions from keys and an array to look up keys from positions. You just need to be careful about updating the bookkeeping structures in the right order.

Makeshifts last the longest.

  • 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 04:21 UTC

    Could you elaborate this a bit?

    If I have an array of indices to the positions of the items in another array. When one of the items moves from the middle to the begining or end of it's array, all the indices for the items between it's old position and the end to which it has moved change. I'm not sure what that buys me?

    I think if I could get (readonly) references to the hash keys, not just the hash values it might allow bi-directional indirection. But I don't know how to do that.


    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

      No, no. I mean this:

      my @actual_data = ( [ ... ], [ ... ], [ ... ], ); my %index_of = ( foo => 0, bar => 1, baz => 2, ); my @key_for = qw( foo bar baz ); my $lookup_by_key = $actual_data[ $index_of{ 'bar' } ]; my $lookup_by_idx = $actual_data[ 1 ]; my $key_from_idx = $key_for[ 1 ];

      When you move things around in @actual_data, you need to the move the keys around in exactly the same fashion in @key_for. You also need to collect all keys whose values changed positions and update them in %index_of accordingly. To just swap two elements, this is trivial:

      sub swap_elements_by_idx { my ( $i, $j ) = @_; @actual_data[ $i, $j ] = @actual_data[ $j, $i ]; @key_for[ $i, $j ] = @key_for[ $j, $i ]; @index_of{ @key_for[ $i, $j ] } = @index_of{ @key_for[ $j, $i ] }; }

      Reformulating this for atomic operations involving more than two elements is trickier, since the order of operations is then significant, but shouldn't be very hard either.

      Makeshifts last the longest.

        Okay, I get where your going (I think). It work's but carries a fairly high cost.

        I was premature in accepting etcshadow's suggestion. When it came to implementing it, the shine fell away.

        This details the problem(s) as I see it so far:

        Using your technique,

        @actual %indexOf @keyFor 0 [ A_value ] { A => 0 } [ A ] 1 [ B_value ] { B => 1 } [ B ] 2 [ C_value ] { C => 2 } [ C ] 3 [ D_value ] { D => 3 } [ D ] 4 [ E_value ] { E => 4 } [ E ]

        Accessing C via key calls for C to become top item so calling getByKey( 'C' ); does:

        sub getByKey { my $key = shift; my $idx = $indexOf{ $key }; my $value = $actual[ $idx ]; push @actual, splice @actual, $idx, 1; push @keyFor, splice @keyFor, $idx, 1; ## Completely re-build %indexOf $indexOf{ $keyFor[ $_ ] } = $_ for 0 .. $#keyFor; return $value }

        Afterwards, all linkages are maintained:

        @actual %indexOf @keyFor 0 [ C_value ]* { A => 1 }* [ C ]* 1 [ A_value ] { B => 2 }* [ A ]* 2 [ B_value ] { C => 0 }* [ B ]* 3 [ D_value ] { D => 3 }* [ D ]* 4 [ E_value ] { E => 4 }* [ E ]*

        but requires two splices and the for loop is expensive!


        Using etcshadow's layout, if I use splice to reorder @keys, the linkages in the hashes are self maintaining; but:

        @keys %valByKey %keyByValRef 0 [ A ] { A => \A_value } { \A_value => A } 1 [ B ] { B => \B_value } { \B_value => B } 2 [ C ] { C => \C_value } { \C_value => C } 3 [ D ] { D => \D_value } { \D_value => D } 4 [ E ] { E => \E_value } { \E_value => E }

        If accessing C via key, calls for C to become top item getByKey( 'C' ); does?

        sub getByKey { my $key = shift; my $value = $valByKey{ $key }; ## In order to splice the C item to the top ## I need it's index, but I don't have a way ## to go from key 'C' to index? return $value; }

        If there was a version of splice that located the items to remove by its address rather than by index, I would be laughing.


        Using a hybrid of the two:

        @keys %valByKey %idxByVal 0 [ A ] { A => \A_value } { \A_value => 0 } 1 [ B ] { B => \B_value } { \B_value => 1 } 2 [ C ] { C => \C_value } { \C_value => 2 } 3 [ D ] { D => \D_value } { \D_value => 3 } 4 [ E ] { E => \E_value } { \E_value => 4 }

        Accessing C via key calls for C to become top item getByKey( 'C' ); does:

        sub getByKey { my $key = shift; my $value = $valByKey{ $key }; my $idx = $idxByVal{ $value }; push @keys, splice @keys, $idx, 1; ## To maintain linkage, it becomes necessary ## to completely re-build %idxByVal %idxByValue = map{ $valByKey{ $key[ $_ ] } => $_ } 0 .. $#keys; return $value; }

        Afterwards:

        @keys %valByKey %idxByVal 0 [ C ] { A => \A_value } { \A_value => 0 } 1 [ A ] { B => \B_value } { \B_value => 1 } 2 [ B ] { C => \C_value } { \C_value => 2 } 3 [ D ] { D => \D_value } { \D_value => 3 } 4 [ E ] { E => \E_value } { \E_value => 4 }

        One splice and a somewhat more expensive (because of double indirection) loop!

        I'm still looking at the other two suggestions.


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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2020-02-17 13:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?










    Results (71 votes). Check out past polls.

    Notices?