在C＃中計算數組頻率分佈的最快方法是什麼？

我只是想知道什麼是該計算的最佳方法。讓我們假設我有一個輸入數組和邊界數組 - 我想計算/ bucketize頻率分佈的每個分區在邊界數組中。在C＃中計算數組頻率分佈的最快方法是什麼？

使用桶搜索是個好主意嗎？

其實我發現這個問題Calculating frequency distribution of a collection with .Net/C#

但我不知道如何使用爲目的的桶引起每個桶的大小，可以在我的情況不同。

編輯：畢竟討論我有內部/外部循環解決方案，但仍然想消除內部循環與字典獲得O（N）性能在這種情況下，如果我理解正確我需要散列輸入值轉換爲存儲桶索引。所以我們需要某種具有O（1）複雜性的散列函數？任何想法如何做到這一點？

來源

2011-08-31 Andrey

你能描述邊界陣列更好一點？各種邊界之間是否存在任何關係（即它們是連續的）還是它們在大小和「位置」上是完全隨機的？我假設邊界數組完全覆蓋了可能值的範圍 - 這是真的嗎？另外，我假設沒有重疊 - 對嗎？ –

最快在大「O」的意思還是在小代碼的意思？一個簡單的方法是編寫一個函數Func 並將其與Linqs .GroupBy一起使用，將其分組爲「桶」 - 但可能有更快的計算方法來執行此操作。 – Carsten

是的，你是對的。邊界值是單調遞增的。它們沒有重疊，涵蓋了可能值的範圍。舉例來說：0,10,50,100,120。 – Andrey

桶排序已經是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-31 15:42:52 drharris

您如何看待Java中呈現的BucketizedHashtable實現？或者在執行開始時對數組進行排序呢，它有意義嗎？ –

使用'Dictionary '消除內部循環以獲得分期付款的O（n）perf。 –

@Hans你是什麼意思？我不明白:( – Andrey

如果輸入數組代表現實世界的數據（其圖案）和邊界的陣列是大一次又一次地重複它在內部循環，可以考慮以下方法：

首先排序你的輸入數組。如果你使用真實世界的數據我會建議考慮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-01 06:50:09

邊界用值數組表示。但複雜性呢？正如我對Timsort所理解的，在最壞的情況下O（nlogn）+ O（n）用於循環。我認爲內部/外部循環whith二進制搜索應該更好？ – Andrey

不完全正確。如果中間有一個「空」桶，這將失敗。也就是說，排序數組中有兩個輸入值彼此相鄰，但進入彼此不相鄰的桶中。但是可以修復。總而言之，這是一個非常好的主意。根據數據，甚至可以使用基數排序，即O（n），儘管它可能需要大量數據才能使其值得。但整體運行時將是一個乾淨的O（n）。 –

P.S.很抱歉發佈此文本作爲答案。這本來就是一個評論。 –

在C＃中計算數組頻率分佈的最快方法是什麼？

回答

相關問題