12

私はその計算のための最良のアプローチは何であるか疑問に思っています。値の入力配列と境界の配列があると仮定しましょう-境界配列の各セグメントの度数分布を計算/バケット化したいと思いました。

そのためにバケット検索を使用するのは良い考えですか？

実際、私はその質問を見つけました。.Net/ C＃を使用してコレクションの度数分布を計算する

しかし、その目的でバケットを使用する方法がわかりません。私の状況では、各バケットのサイズが異なる可能性があるためです。

編集：すべての議論の後、私は内部/外部ループの解決策を持っていますが、それでも辞書で内部ループを排除して、その場合にO（n）パフォーマンスを取得したいのですが、正しく理解していれば、入力値をバケットインデックスにハッシュする必要があります。では、O（1）の複雑さを持つある種のハッシュ関数が必要ですか？それを行う方法はありますか？

4

2 に答える 2

4

Bucket Sort はすでに O(n^2) の最悪のケースなので、ここでは単純な内部/外部ループを実行します。バケット配列は必然的に入力配列よりも短いため、内側のループに保持してください。カスタム バケット サイズを使用しているため、その内側のループを排除できる数学的トリックは実際にはありません。

int[] freq = new int[buckets.length - 1];
foreach(int d in input)
{
    for(int i = 0; i < buckets.length - 1; i++)
    {
         if(d >= buckets[i] && d < buckets[i+1])
         {
             freq[i]++;
             break;
         }
    }
}

これも O(n^2) の最悪のケースですが、コードの単純さに勝るものはありません。それが本当の問題になるまで、私は最適化について心配しません。より大きなバケット配列がある場合は、何らかのバイナリ検索を使用できます。しかし、度数分布は通常 100 要素未満であるため、現実世界でのパフォーマンス上のメリットが多く見られるとは思えません。

于 2011-08-31T15:42:52.670 に答える
1

入力配列が実世界のデータ (そのパターンを含む) を表し、境界の配列が大きい場合は、内側のループで何度も繰り返す必要があります。次のアプローチを検討できます。

  • まず、入力配列を並べ替えます。実世界のデータを扱う場合は、 Timsort - Wikiを検討することをお勧めします。これにより、実際のデータで見られるパターンに対して非常に優れたパフォーマンスが保証されます。

  • 並べ替えられた配列をトラバースし、境界の配列の最初の値と比較します。

    • 入力配列の値が境界よりも小さい場合 - この境界の頻度カウンターをインクリメントします
    • 入力配列の値が境界よりも大きい場合 - 境界の配列の次の値に移動し、新しい境界のカウンターをインクリメントします。

コードでは、次のようになります。

Timsort(myArray);
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>()

for (int i = 0; i<myArray.Lenght; i++) {
  if (myArray[i]<boundaries[boundPos]) { 
     boundaries[boubdPos]++;
  }
  else {
    boundPos++;
    boundaries[boubdPos]++;
  }
}
于 2011-09-01T06:50:09.780 に答える