代码之家 › 专栏 › 技术社区 › scubasteve

计算运行平均值的合适集合是什么?

algorithm c#

scubasteve · 技术社区 · 14 年前

我正在筛选一些旧的bug,在查看一些讨厌的代码时,我意识到我的平均或平滑算法非常糟糕。我做了一点研究,结果发现 "running mean" -有道理,很简单。我正在考虑一个可能的实现,并意识到我不知道哪个集合将提供我需要的“滑动”功能类型。换句话说,我需要将一个项目推/添加到集合的末尾,然后从集合中弹出/删除第一个项目。我想如果我知道这是什么,我可以找到正确的收藏,但我不知道要搜索什么。

理想情况下,设置最大大小的集合以及添加到其中的任何超过该大小的内容都将从第一个项中弹出。

为了说明这一点,我在闲逛时想到了:

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList<int> samples = new LinkedList<int>();

            //  Simulate packing the front of the samples, this would most like be a pre-averaged
            //  value from the raw samples
            for (int i = 0; i < 10; i++)
            {
                samples.AddLast(0);
            }

            for (int i = 0; i < 100; i++)
            {
                //  My attempt at a "sliding collection" - not really sure what to call it but as
                //  an item is added the first item is removed
                samples.RemoveFirst();
                samples.AddLast(i);

                foreach (int v in samples)
                {
                    Console.Write("{0:000} ", v);
                }

                Console.WriteLine(String.Empty);
            }

            Console.ReadLine();
        }
    }
}

如您所见,我正在手动处理第一个项目的删除。我只是在问是否有一个标准的集合针对这种类型的使用进行了优化?

4 回复 | 直到 14 年前

Community CDub 8 年前

看起来你在找一个 Circular Buffer . 这是一个 .NET implementation 在codeplex上。您可能还想看看这个问题: How would you code an efficient Circular Buffer in Java or C#?

从你提供的样本来看,还不清楚 确切地 这与在线平均算法有关。如果缓冲区上允许的唯一操作是追加,则缓存并更新缓冲区内的“总计”应该很简单(添加新值,减去删除的值);使平均值的保持为 O(1) 每个附加的操作。在这种情况下,缓冲区有效地保持 Simple Moving Average (sma)一系列的。

Adriaan Stander 14 年前

你看过吗 Queue Class

Rob 14 年前

清单能满足你的需求吗?

List<String> myList = new List<String>();

myList.Add("Something to the end");
myList.RemoveAt(0);

scubasteve 14 年前

@我正在创建一个新的答案而不是注释,因为我有一些代码要粘贴。我朝一个死的简单物体挥了挥杆,以帮助我的跑动方式,并得出以下结论:

class RollingMean
{
    int _pos;
    int _count;
    double[] _buffer;

    public RollingMean(int size)
    {
        _buffer = new double[size];
        _pos = 0;
        _count = 0;
    }

    public RollingMean(int size, double initialValue) 
        : this(size)
    {
        //  Believe it or not there doesn't seem to be a better(performance) way...
        for (int i = 0; i < size; i++)
        {
            _buffer[i] = initialValue;
        }

        _count = size;
    }

    public double Push(double value)
    {
        _buffer[_pos] = value;

        _pos = (++_pos > _buffer.Length - 1) ? 0 : _pos;
        _count = Math.Min(++_count, _buffer.Length);

        return Mean;
    }

    public double Mean
    {
        get
        {
            return _buffer.Sum() / _count;
        }
    }
}

我正在从一个数据采集系统中读取16个通道的数据,因此我将为每个通道实例化其中一个通道,我认为这比为每个通道管理多维数组或单独的一组缓冲区/位置更干净。

以下是感兴趣的用户的示例用法:

static void Main(string[] args)
{
    RollingMean mean = new RollingMean(10, 7);

    mean.Push(3);
    mean.Push(4);
    mean.Push(5);
    mean.Push(6);
    mean.Push(7.125);

    Console.WriteLine( mean.Mean );
    Console.ReadLine();
}

我打算将RollingMean对象设置为泛型,而不是锁定为Double,但是我找不到限制tpye数值类型的泛型约束。我继续前进,必须回去工作。谢谢你的帮助。