Re^4: Re-orderable keyed access structure?

[BrowserUk]

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.

[Aristotle]

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.

[BrowserUk]

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.

[Aristotle]

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.