时间戳

首页 > 解决方案 > 我正在尝试找到一种更好的方法来查找数组中第 n 个最稀有的元素

c# - 我正在尝试找到一种更好的方法来查找数组中第 n 个最稀有的元素

问题描述

说，

elements=5, 4, 2, 2, 1, 5, 4, 3, 3, 4, 4, 3, 5, 5, 5  
return elements.GroupBy(x=>x).OrderBy(x=>x.Count()).Skip(n-1).FirstOrDefault().Key;

对于较大的数组，超出了内存限制。有一个更好的方法吗？

标签： c#performancelinqmemory

解决方案

更大是一个相对术语，但您可以尝试回到基础并计算自己。

var elements = new[] { 5, 4, 2, 2, 1, 5, 4, 3, 3, 4, 4, 3, 5, 5, 5 };
var counts = new Dictionary<int, int>(capacity: elements.Length); // Worst case capacity
for (int i = 0; i < elements.Length; i++)
{
    counts.TryGetValue(elements[i], out var count);
    counts[elements[i]] = ++count;
}

var n = 5;
var nthRarest = counts.OrderBy(x => x.Value).Skip(n - 1).FirstOrDefault();
Console.WriteLine($"'{nthRarest.Key}' with {nthRarest.Value}"); //'5' with 5

回复：@mjwills 的 TryGetValue 评论。

我使用的原始计数器ContainsKey和@mjwills 建议TryGetValue。以下是一些低质量的基准：

  • 与 ContainsKey: '3' 与 99829 @ 00:00:00.0808146
  • 使用 TryGetValue: '3' 使用 99829 @ 00:00:00.0594995
var elements = Enumerable.Range(0, 1_000_000).Select(i => r.Next(0,10)).ToArray();
var sw = Stopwatch.StartNew();

(...)

var elapsed = sw.Elapsed;
Console.WriteLine($"'{nthRarest.Key}' with {nthRarest.Value} @ {elapsed}");

老办法：

if (!counts.ContainsKey(elements[i]))
    counts[elements[i]] = 1;
else
    counts[elements[i]] += 1;

推荐阅读