Re^5: 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 (Patriarch) 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	[reply]
Re^7: Re-orderable keyed access structure? by Aristotle (Chancellor) on Aug 14, 2004 at 20:30 UTC
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 ] }; }` [download] And it doesn't work any differently for multi-element atomic operations. Makeshifts last the longest.	[reply] [d/l]
Re^8: Re-orderable keyed access structure? by BrowserUk (Patriarch) on Aug 14, 2004 at 20:53 UTC
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;` [download] 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	[reply] [d/l] [select]