3

私は次のようなハッシュ構造を持っています:

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

ハッシュ構造を通るトラバーサルパスと、トラバーサルの最後の値を出力して、値順に並べる必要があります。たとえば、上記のハッシュ構造の場合、次のように出力する必要があります。

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

現在、これを解決するために、ネストされたforeachループを使用してハッシュ構造をトラバースし、トラバーサルパスに等しいキー(「KeyAKey3 Key10」など)と最後の値に等しい値を持つ要素を挿入してフラット化されたハッシュを作成していますトラバーサルパス(例:3)、次にフラット化されたハッシュを値でソートする別のforeachループを実行します。

これを行うためのより効率的な方法はありますか?

4

5 に答える 5

3

再帰的なソリューションを使用して、任意のネストの深さのネストされたデータ構造に対してこの問題を解決することもできます。パスと値を含む宛先配列を再帰的に構築し、その配列を並べ替えます。

use warnings;
use strict;

sub paths {
    my ($data, $cur_path, $dest) = @_; 
    if (ref $data eq 'HASH') {
        foreach my $key (keys %$data) {
            paths($data->{$key}, [@$cur_path, $key], $dest);
        }   
    } else {
        push @$dest, [$cur_path, $data];
    }   
}

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

my $dest = []; 
paths($data, [], $dest);

foreach my $result (sort { $a->[1] <=> $b->[1] } @$dest) {
    print join(' ', @{$result->[0]}, $result->[1]), "\n";
}
于 2009-04-18T07:16:38.577 に答える
3

新しいハッシュを作成する代わりに、並べ替えられた配列を作成することを検討してください。キーと値のペアの値に従って配列に挿入し、初期値を反復処理してから、結果の配列を反復処理します。これにより、最初の反復で O(n) + 各挿入で O(lg n) + 最後の反復で O(n) が得られます。

于 2009-04-17T22:28:35.773 に答える
0

多次元ハッシュ エミュレーション (perlvar の $; を参照) を使用してフラット ハッシュに変換し、結果のハッシュをソートします。

use strict;
use warnings;
my %hash = (
    KeyA => {
          Key1 => {
                    Key4 => 4,
                    Key5 => 9,
                    Key6 => 10,
                  },
          Key2 => {
                    Key7 => 5,
                    Key8 => 9,
                  }
         },
    KeyB => {
          Key3 => {
                    Key9 => 6,
                    Key10 => 3,
                  },
         },
);

my %fhash = 
   map {
        my @fh;
        foreach my $k2 (keys %{$hash{$_}}) {
                foreach my $k3 (keys %{$hash{$_}{$k2}}) {
                        push @fh, (join($;, $_, $k2, $k3) => $hash{$_}{$k2}{$k3});
                }   
        }
        @fh;
   } keys %hash;



foreach (sort { $fhash{$a} <=> $fhash{$b} } keys %fhash) {
    printf("%s\t%d\n", join("\t", split(/$;/, $_)), $fhash{$_});
}

fhash を生成する map / foreach ループを直接ソートに渡すことができます。

于 2010-08-17T06:16:38.883 に答える
-2

これらの他のソリューションは、「賢い」ため、より洗練されているように見えます。ただし、データ構造の単純さを考えると、メソッドは実際には問題ありません。その構造は簡単に平らになります。より効率的なソリューションを求めましたが、何も提供されませんでした。

于 2010-08-17T02:42:07.303 に答える