查找列表时间范围内元素的快速算法

Question

问题是：我有一个包含时间和值（时间=长毫秒和双值）的数据列表。我现在需要计算不同时间范围内的几个平均值
我每秒最多可以得到50个值，但有时只有几个值，需要保持最后10秒，所以500个值。

我想要的是：计算时间的平均值

我可以保证没有时间是双倍的，所以它可以用作一把钥匙。

目前，我使用一个数组来存储值，并且有一个位置标记，一旦达到500，它就会重置为0，所以旧的条目会被重新调整样式。我可以很容易地改变。

我不确定最快的方法是什么，例如手动搜索数组或使用列表、hashMap、集合（使用comparator？）否则。我找不到一个类似（java）列表的函数，其中我有一个内置搜索键

性能比简单的编码更重要。

被指向正确的方向会很好。

每次有新值进来时，我都会计算最后10个值的平均值，即每秒30-50次计算，这是最重要的数据。我需要区分测量中的小错误和实际变化。我额外计算每1/10秒的平均值（这可能会被删除），最后是一秒的平均值和最后10秒的平均值。这是每秒12次的额外平均计算。减少计算次数并不是一个真正的选择。

由于这有点抽象，下面是一个数据的示例（其中avg是最后10个值的计算结果，但这不是程序逻辑）。

value           Avg timeReading timeReadingISO
1024,6668701172 -       1385408750828   2013-11-25 19:45:50
1024,6668701172 -       1385408751350   2013-11-25 19:45:51
1024,6668701172 -       1385408751859   2013-11-25 19:45:51
1024,6683349609 -       1385408752373   2013-11-25 19:45:52
1024,6683349609 -       1385408752878   2013-11-25 19:45:52
1024,6689453125 -       1385408753385   2013-11-25 19:45:53
1024,6689453125 -       1385408753895   2013-11-25 19:45:53
1024,6721191406 -       1385408754406   2013-11-25 19:45:54
1024,6721191406 -       1385408754912   2013-11-25 19:45:54
1024,6774902344 -       1385408755432   2013-11-25 19:45:55
1024,6774902344 1024,67 1385408755994   2013-11-25 19:45:55
1024,6774902344 1024,67 1385408756502   2013-11-25 19:45:56
1024,6837158203 1024,67 1385408757012   2013-11-25 19:45:57
1024,6837158203 1024,67 1385408757520   2013-11-25 19:45:57
1024,689453125  1024,68 1385408758028   2013-11-25 19:45:58
1024,689453125  1024,68 1385408758536   2013-11-25 19:45:58
1024,6938476563 1024,68 1385408759055   2013-11-25 19:45:59
1024,6938476563 1024,68 1385408759560   2013-11-25 19:45:59
1024,6990966797 1024,68 1385408760075   2013-11-25 19:46:00
1024,6990966797 1024,69 1385408760579   2013-11-25 19:46:00
1024,7038574219 1024,69 1385408761086   2013-11-25 19:46:01
1024,7038574219 1024,69 1385408761596   2013-11-25 19:46:01
1024,7111816406 1024,69 1385408762103   2013-11-25 19:46:02
1024,7111816406 1024,70 1385408762606   2013-11-25 19:46:02
1024,7111816406 1024,70 1385408763112   2013-11-25 19:46:03
1024,7111816406 1024,70 1385408763622   2013-11-25 19:46:03
1024,7172851563 1024,70 1385408764128   2013-11-25 19:46:04
1024,7172851563 1024,71 1385408764637   2013-11-25 19:46:04
1024,7208251953 1024,71 1385408765149   2013-11-25 19:46:05

1026,5457763672 -       1385474621756   2013-11-26 14:03:41
1026,6057128906 -       1385474621790   2013-11-26 14:03:41
1026,6257324219 -       1385474621823   2013-11-26 14:03:41
1026,6057128906 -       1385474621858   2013-11-26 14:03:41
1026,6257324219 -       1385474621890   2013-11-26 14:03:41
1026,6257324219 -       1385474621921   2013-11-26 14:03:41
1026,6057128906 -       1385474621956   2013-11-26 14:03:41
1026,5457763672 -       1385474621988   2013-11-26 14:03:41
1026,6557617188 -       1385474622022   2013-11-26 14:03:42
1026,6657714844 -       1385474622057   2013-11-26 14:03:42
1026,6257324219 1026,61 1385474622090   2013-11-26 14:03:42
1026,6057128906 1026,62 1385474622123   2013-11-26 14:03:42
1026,6657714844 1026,62 1385474622159   2013-11-26 14:03:42
1026,6557617188 1026,62 1385474622193   2013-11-26 14:03:42
1026,6557617188 1026,63 1385474622227   2013-11-26 14:03:42
1026,6257324219 1026,63 1385474622260   2013-11-26 14:03:42
1026,6257324219 1026,63 1385474622298   2013-11-26 14:03:42
1026,6557617188 1026,63 1385474622330   2013-11-26 14:03:42
1026,6257324219 1026,64 1385474622365   2013-11-26 14:03:42
1026,6257324219 1026,64 1385474622401   2013-11-26 14:03:42
1026,6257324219 1026,64 1385474622431   2013-11-26 14:03:42
1026,5758056641 1026,64 1385474622466   2013-11-26 14:03:42
1026,6057128906 1026,63 1385474622501   2013-11-26 14:03:42
1026,5457763672 1026,63 1385474622533   2013-11-26 14:03:42
1026,5457763672 1026,62 1385474622565   2013-11-26 14:03:42
1026,6057128906 1026,61 1385474622599   2013-11-26 14:03:42
1026,6057128906 1026,60 1385474622631   2013-11-26 14:03:42
1026,5758056641 1026,60 1385474622665   2013-11-26 14:03:42
1026,5457763672 1026,59 1385474622702   2013-11-26 14:03:42
1026,6057128906 1026,59 1385474622734   2013-11-26 14:03:42
1026,6557617188 1026,58 1385474622766   2013-11-26 14:03:42
1026,5758056641 1026,59 1385474622800   2013-11-26 14:03:42
1026,6057128906 1026,59 1385474622836   2013-11-26 14:03:42
1026,6057128906 1026,59 1385474622868   2013-11-26 14:03:42
1026,5158691406 1026,59 1385474622901   2013-11-26 14:03:42
1026,5457763672 1026,59 1385474622935   2013-11-26 14:03:42
1026,6856689453 1026,58 1385474622966   2013-11-26 14:03:42

Answer 1

在Maciej的答案中缓存平均值组是一种有效的方法。当前列表的一个简单方法是Java的SortedSet，它是一个接口，因此最终将使用TreeSet。

创建一个比较对象来存储时间和值，或者为SortedSet创建一个比较器。确保您是根据时间（而不是值）排序的。

public class Holder implements Comparable
{
  private double time, value;
  public Holder (double t, double v)
  {
    this.time = t;
    this.value = v;
  }

  public double getValue()
  {  return this.value; }

  public double getTime()
  {  return this.time; }

  //You may want a better comparator.
  public int compareTo( Holder h )
  {
    return this.getTime < h.getTime() ? -1 : 1;
  }
}

只需为集合添加正常值，它们将根据时间自动排序。当你想要过去10秒的平均值时，找到当前时间并调用sortedSet。tailSet（新的CustomObject（currentTime-10000））。现在迭代返回的集合以计算平均值。

SortedSet<Holder> slice = allHolders.tailset( new Holder( currentTime - 10000 ) );
double sum = 0.0;
for( Holder h : slice )
{
  sum += h.getValue();
} 
double result = sum / slice.size();

您可以使用查找时间组。subSet（）如果您觉得平均呼叫有延迟。

Answer 2

首先，在计算平均值时，您应该创建一个结构的副本（或者使用一个线程安全的副本，并且在添加或删除过程中遍历它不会造成疼痛），除非您在一个线程中执行所有操作。

我猜你的集合中的元素是按区域排序的，因为你会按顺序接收更新（如果不是的话，请查找排序列表的等效项）。

我的方法是选择平均测量值的最小间隔。比如说10个值。然后，您可以创建50个集合（大小为10），其中每一个集合都属于同一级别，这为您提供了计算平均值的方法。然后，您可以选择要计算的平均值。只需计算集合的平均值 更重要的是，一旦计算出给定集合的平均值，就不会改变，所以可以缓存它

请注意，您不必将值从一个集合转移到另一个集合，因为已经处理了最小间隔。如果缓冲区中出现了新的10个元素，您只需重新分配引用即可。

/* initializing */
MySlicedCollection buffer = new MySlicedCollection();
MySlicedCollection[] mscArray = new MySlicedCollection[50];

/* when every 10 values came in */
for(int i = mscArray.length-1; i > 0 ; --i) {
    mscArray[i] = mscArray[i-1];
}
mscArray[0] = buffer;
buffer = new MySlicedCollection();

/* avg of all collection */
for(MySlicedCollection msc : mscArray) {
    sum += msc.getAverage();
}
sum /= 50;

你还应该考虑使用之前的结果计算平均值。如果你必须计算1秒和2秒的平均值，那么你可以把剩余的平均值加到已经计算的平均值上一秒钟，然后除以2。

/* avg for one second */
for(int i = 0; i < 5; ++i) {
    sumOneSec += mscArray[i].getAverage();
}
sumOneSec /= 5;

/* avg for two seconds */
for(int i = 5; i < 10; ++i) {
    sumTwoSec += mscArray[i].getAverage();
}
sumTwoSec = ((sumTwoSec/5) + sumOneSec) / 2;

但请记住有人说过的话：“先衡量然后行动”——也许你的表现就足够了？

avg = (avg * 50 - oldestValue + newValue)/50;

不幸的是，由于浮点变量的有限表示，这会给计算带来一点错误，但由于使用的是双值，我认为不需要这样的精度。类似的解决方案可以提供给另一个平均值，但这需要更多的思考：）