0

任意のハッシュの配列があり、ハッシュの要素は整数です (「id」と呼びます)。これらのハッシュを多数のバケット (配列全体で一定) に並べ替えたいと考えています。各バケットは任意の範囲の 'id' (1 ～ 10、15 ～ 20、20 ～ 30 など) です。これを行うための最良の並べ替え戦略は何ですか? ネストされたループなしで行うことは可能ですか?

4

3 に答える 3

1

バケットの数が少ない場合は、ネストされたループを使用した方がよいでしょう。ハッシュの外側のループと、バケットの内側のループ。 O(n*m).

ハッシュの数とバケットの数が多い場合は、次のことができます。

hashes = sort(hashes)
buckets = sort(buckets) # sort by lower-bound of bucket
i = 0

foreach (hash in hashes) {
  while (buckets[i].lower_bound > hash) {
    i = i + 1
  }
  bucket[i].add(hash)
}

基本的に、ハッシュをループして現在のバケットに追加し、必要に応じて次のバケットに進みます。O(n*log(n) + m*log(m))

于 2010-12-07T03:52:37.647 に答える
1

ハッシュの品質が良ければ、均等に分散されるため、均等に分散されたバケットを使用して、1 回のパスでコレクションを分割できます。

ハッシュもバケット内でソートする場合は、すべてがバケットに入った後で通常のソート アルゴリズムを使用します。ただし、これはハッシュの珍しい使用方法です。(バケット内でソートしようとしていない場合、「ソート」という言葉は誤称です。あなたが本当に望んでいたのはパーティショニングでした。)

于 2010-12-07T03:53:04.810 に答える
0

言語/プラットフォームについては言及していませんが、キーストローク（C＃）の観点から効率的です：

        var histogram = new[] { 0, 10, 15, 20, 30, 40 };
        var values = new[] { 12, 14, 5, 6, 7, 1, 34, 26, 17 };
        var bars = values.GroupBy(v => histogram.First(b => v < b));
于 2010-12-07T04:01:01.160 に答える