C#中整数数据的简单直方图生成

Question

C#中整数数据的简单直方图生成

10

作为我正在构建的测试平台的一部分，我正在寻找一个简单的类来计算整数值的直方图（用于解决问题的算法迭代次数）。答案应该被称为这样：

Histogram my_hist = new Histogram();

for( uint i = 0; i < NUMBER_OF_RESULTS; i++ )
{

    myHist.AddValue( some_result );
}

for( uint j = 0; j < myHist.NumOfBins; j++ )
{
     Console.WriteLine( "{0} occurred {1} times", myHist.BinValues[j], myHist.BinCounts[j] );
}

我有点惊讶于谷歌搜索没有找到一个简洁的解决方案，但也许是因为我没有搜索正确的关键词。是否存在通用解决方案，或者值得自己动手解决？

- Jon Cage

5个回答

6

根据BastardSaint的建议，我想出了一个简洁而通用的包装器：

public class Histogram<TVal> : SortedDictionary<TVal, uint>
{
    public void IncrementCount(TVal binToIncrement)
    {
        if (ContainsKey(binToIncrement))
        {
            this[binToIncrement]++;
        }
        else
        {
            Add(binToIncrement, 1);
        }
    }
}

现在我可以做到：

const uint numOfInputDataPoints = 5;
Histogram<uint> hist = new Histogram<uint>();

// Fill the histogram with data
for (uint i = 0; i < numOfInputDataPoints; i++)
{
    // Grab a result from my algorithm
    uint numOfIterationsForSolution = MyAlorithm.Run();

    // Add the number to the histogram
    hist.IncrementCount( numOfIterationsForSolution );
}

// Report the results
foreach (KeyValuePair<uint, uint> histEntry in hist.AsEnumerable())
{
    Console.WriteLine("{0} occurred {1} times", histEntry.Key, histEntry.Value);
}

花了我一段时间才弄清楚如何使它通用化（一开始我只是覆盖了SortedDictionary构造函数，这意味着你只能用它来处理uint键）。

- Jon Cage

BastardSaint使用Contains()方法进行检查比依赖于异常要明智得多。这将在每次存储新数字频率时产生一个峰值。 - Cecil Has a Name

现在想想，也许每次都进行检查是更好的存在检查方式。我猜这取决于你是否期望添加许多非常相似的项目（我是），或者你是否期望有许多更多唯一条目的直方图。我的直觉是，在我的情况下这样做会更快（？） - Jon Cage

将示例更改为使用if-else解决方案。 - Jon Cage

2

你能想到一个好的方法来扩展这种方法以处理大于1的容器吗？ - gap

你可以将键指定为String^值，然后添加一个类似于“0-10”的键吗？ - Jon Cage

5

You can use Linq:

var items = new[] {5, 6, 1, 2, 3, 1, 5, 2};
items
    .GroupBy(i => i)
    .Select(g => new {
        Item = g.Key,
        Count = g.Count()
    })
    .OrderBy(g => g.Item)
    .ToList()
    .ForEach(g => {
        Console.WriteLine("{0} occurred {1} times", g.Item, g.Count);
    });

- ken

2

这是在接受的答案基础上进行的改进。问题在于迭代构建SortedDictionary速度很慢，因为插入和检索都需要O(log(N))的时间复杂度。

如果不需要实时显示直方图，则可以避免这种情况。

我的修改使用普通的Dictionary，并在最后将其排序成SortedList。

对于10M个项目的样本大小，该版本比原版快约11倍（在我的机器上），但会增加略微更高的内存使用直到GC启动（额外10%的内存）。

//generate a random sample
Random r = new Random();
var items = Enumerable
    .Range(1, 10_000_000)
    .Select( _ => (uint)r.Next(100_000))
    .ToList();

//build the histogram using a normal dictionary with O(1) lookups and insertions.
var tempHistogram = new Dictionary<uint, int>();
foreach (uint item in items)
{
    if (tempHistogram.ContainsKey(item))
    {
        tempHistogram[item]++;
    }
    else
    {
        tempHistogram[item] = 1;
    }
}

//Sort it once. SortedList conveniently has a ctor that takes a dictionary.
var sortedHistogram = new SortedList<uint, int>(tempHistogram);

foreach (KeyValuePair<uint, int> pair in sortedHistogram.Take(100))
{
    Console.WriteLine("{0} occurred {1} times", pair.Key, pair.Value);
}

对于非常大的样本（大于可用内存），有一些惊人的概率算法可以解决这个问题。
它们也非常适用于流式数据。
寻找“分位数草图”。这里有一个Apache基金会的实现：https://datasketches.apache.org/

- Cristian Diaconescu

1

我实现了一个简单的扩展方法来创建直方图：

public static IReadOnlyDictionary<T, int> ToHistogram<T>(this IEnumerable<T> enumerable)
   => enumerable.GroupBy(item => item).ToDictionary(grouping => grouping.Key, grouping => grouping.Count());

- Mugen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steef · Accepted Answer

你可以使用SortedDictionary。

uint[] items = new uint[] {5, 6, 1, 2, 3, 1, 5, 2}; // sample data
SortedDictionary<uint, int> histogram = new SortedDictionary<uint, int>();
foreach (uint item in items) {
    if (histogram.ContainsKey(item)) {
        histogram[item]++;
    } else {
        histogram[item] = 1;
    }
}
foreach (KeyValuePair<uint, int> pair in histogram) {
    Console.WriteLine("{0} occurred {1} times", pair.Key, pair.Value);
}

然而，这将排除空箱子