Sort by value hash of hash of hashes Perl

Question

I have a hash structure similar to the following:

KeyA => {
         Key1 => {
                   Key4 => 4
                   Key5 => 9
                   Key6 => 10
                 }
         Key2 => {
                   Key7 => 5
                   Key8 => 9
                 }
        }
KeyB => {
         Key3 => {
                   Key9 => 6
                   Key10 => 3
                 }
        }

I need to print out the traversal path through the hash structure and the value at the end of the traversal, such that this is ordered by value. For example, for the above hash structure I need to print:

KeyB Key3 Key10 3
KeyA Key1 Key4  4
KeyA Key2 Key7  5
KeyB Key3 Key9  6
KeyA Key2 Key8  9
KeyA Key1 Key5  9
KeyA Key1 Key6  10

Currently, to solve this I am traversing the hash structure using nested foreach loops, and creating a flattened hash by inserting an element with key equal to the traversal path (e.g. "KeyA Key3 Key10") and value equal to the value at the end of the traversal path (e.g. 3), then doing another foreach loop which sorts the flattened hash by value.

Is there a more efficient way to do this?

Answer 1

Instead of creating a new hash, consider creating a sorted array. Iterate over the initial values, inserting in to the array, according to the value, the key-value pair, then iterate over the resulting array. This should give you O(n) on the initial iteration + O(lg n) for each insertion + O(n) for the final iteration.