c# - Fastest way of getting most frequent and similar values inside an array?

Question

I have an array of ints in C# and I want to get 5% of the whole array, in the way that the new array includes the most frequent similar values. For an example, say I have an array with 100 entries that includes 40 siblings of 20 (15 to 25). What I want is to detect the 20 as the most frequent value (including it's siblings) as a new array and then 5 most frequent values inside the new array. I need to run the code on an ASP.net website and because of that, I need a fast algorithem. Could anyone help me with this please?

Answer 1

次のように、値をグループ化し、カウントで並べ替え、必要な 5% 配列を満たすまで値を取得することで、単純なアルゴリズムを構築できます。

// Build a set of {Value, Count} pairs using LINQ
var counts = data
    .GroupBy(v => v)
    .Select(g => new {
        Value = g => Key
    ,   Count = g.Count()
    }).OrderByDescending(p => p.Count)
    .Take(5);

編集 ：

配列のサイズは 1024*1024 で、範囲は 0 ～ 255 です。

範囲が非常に小さいため、次のように、グループの代わりにカウント配列を使用できます。

int counts = new int[256];
foreach (var b in data) {
    counts[b]++;
}

これで、クイック選択アルゴリズムを実行して 5 番目の項目を選択できます。の C# 実装を提供する回答を次に示しますQuickSelect。

var fifth = QuickSelect(counts, 5);
var res = new List<KeyValuePair<int,int>>();
for (int i = 0 ; i != counts.Length && res.Length != 5 ; i++) {
    if (counts[i] >= fifth) {
        res.Add(new KeyValuePair<int,int>(i, counts[i]));
    }
}

クイック選択アルゴリズムをmedian-of-medians アルゴリズムに置き換えることもできます。このアルゴリズムは同じ線形パフォーマンスを持ちますが、ランダム化されません。

Answer 2

var numbersByOccurrence = from numbers in yourNumberArrayVariable
                          group numbers by numbers into g
                          select new { Number = g.Key, Count = g.Count() };

var limitedSize = numbersByOccurrence.OrderByDescending(n => n.Count).Take(5);

これで、簡単にアクセスできる Number 変数と Count 変数を持つ 5 つのオブジェクトの変数 (配列またはリストとしてキャストできます) ができました。