pattern - 什麼是最快的方式來計算C#中的數組頻率分佈?



step design pattern (2)

我只是想知道什麼是最好的方法來計算。 讓我們假設我有一個輸入值的數組和邊界數組 - 我想計算/ bucketize在邊界數組中的每個段的頻率分佈。

使用桶搜索是好主意嗎?

其實我發現這個問題計算集合的頻率分佈.Net / C#

但我不明白如何使用水桶為此目的造成每個水桶的大小可以在我的情況不同。

編輯:經過所有的討論,我有內部/外部循環的解決方案,但仍然我想消除內部循環與字典獲得O(N)的性能,如果我理解正確的話,我需要散列輸入值到一個桶索引。 所以我們需要某種具有O(1)複雜性的散列函數? 任何想法如何做到這一點?


Answer #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]++;
  }
}

Answer #2

桶排序已經是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個元素,我懷疑你會看到很多現實世界的性能優勢。





frequency-distribution