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

Question

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

我想要的是：计算时间 >= 开始时间并且时间 <= 结束时间的值的平均值。

我可以确保没有重复的时间，因此它可以用作键。

目前我使用一个数组来存储值，并且有一个位置标记器，一旦达到500，就会被重置为0，因此旧条目会被回收。我可以轻松更改它。

我不确定最快的方法是什么，例如手动搜索数组还是使用列表、哈希映射、集合（带比较器？）或其他方式。我找不到一个（java）类似列表的函数，在其中我有一个内置的搜索，即“key >= x”或“value >= x”。

性能比漂亮或易于编码更重要。

指向正确方向会很好。

每次收到新值时，我都会计算最后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

- Gunnar Bernstein

---

平均速率应该有多精确？也许你应该减少刷新频率？ - Maciej Dobrowolski

查找二叉索引树。你可能需要一个动态版本。 - Ivaylo Strandjev

对于最后10个数值，使用10的先进先出队列可能会很有用。计算进入的值与退出的值之间的差异，除以10，并将其添加到平均值中。前10个值会产生副作用。我不知道这是否有帮助。 - Baptiste Gousset

如果你每秒钟“获取”50个值，并在10秒内获得500个值，那么你的性能问题是什么？这已经很慢了。即使你必须计算500个值的平均值 - 这样的速度有多慢，以至于你强调性能？顺便问一下 - 你是如何“获取”这些数据的？另外，更好地描述你的程序应该做什么以及为什么，因为看起来你正在尝试做一些奇怪的事情，可能在更奇怪的方式中进行。 - Artur

这是一个实时系统吗？当你说“每秒获取50个值”时，你是指读取的数据包含该频率的值，还是仅仅是指数据中包含了这些值？ - ninesided

我获取了那么多的数据。我需要近乎实时地修复一个时间戳，但平均值的计算可能会有些延迟。 - Gunnar Bernstein

Answer 1

首先，在计算平均值时，除非您在一个线程中完成所有操作，否则应创建结构的副本（或使用一个线程安全的结构，并且在添加或删除期间遍历它不会引起问题）。

我猜你的集合元素已经排序了，因为你是按顺序接收更新的（如果没有，请寻找等效的排序列表）。

我的方法是选择平均测量的最小间隔。假设是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秒的平均值，那么你只需要将剩余的平均数加到已经计算好的1秒的平均数上，然后除以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;

但是，请记住有人曾经说过：“先探测再行动”-也许您的性能已经足够了？

---

更新通过使用循环缓冲区和进行简单的技巧，您可以节省至少一次迭代。假设缓冲区已满（其容量为50），已知平均值并且另一个值进入 - 您可以通过计算来简单地重新计算它。

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

很不幸，由于浮点数有限的表示方式，这将对您的计算引入一些小错误，但由于您正在使用双精度值，我认为您并不需要如此高的精度。类似的解决方案也可以提供给其他平均值，但这需要更多思考 :)

- Maciej Dobrowolski

---

谢谢你的建议。我会采纳你的想法，使用一个小数组或集合来存储最后的数值。但是数据速率并不是恒定的，可能每秒只有很少的数值，这就是为什么我需要在计算平均值之前检查时间的原因。 - Gunnar Bernstein

@GunnarBernstein，你的数据是按顺序到达的吗？这样你就可以拥有已排序的数组而无需进行排序了吗？ - Maciej Dobrowolski

@Maciey：是的。但我不确定如何在不无限增加数组大小或移动所有值的情况下保持数组排序。 - Gunnar Bernstein

@GunnarBernstein 并不需要进行移位操作。您可以实现自己的CircularBuffer，或使用现有的CircularFifoBuffer。如果数据按正确顺序顺序到达，则可以确保将它们插入到这样的缓冲区后，它们是排序的。然后，您可以通过增量计算平均值（如上所述）并在值超出指定范围时停止迭代来提高性能。 - Maciej Dobrowolski

有趣。不知道已经有现成的了。使用“指针”实际上就是我所做的（“位置标记一旦达到500就会被重置为0，因此旧条目会被回收”）。 - Gunnar Bernstein

Answer 2

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

创建一个Comparable对象来存储您的时间和值，或者为SortedSet创建一个Comparator。确保您是基于时间进行排序（而不是值）。

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( new 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()来查找时间组。

- clay