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

Question

问题:我有一个包含时间和值的数据列表(时间 = long milliSec 和 double 值)。我现在需要计算不同时间范围内的多个平均值。
我每秒最多获得 50 个值，但有时只有几个值并且需要保留最后 10 秒，所以有 500 个值。

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

我可以确保没有时间是双倍的，所以它可以用作 key 。

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

我不确定最快的方法是什么，例如手动搜索数组或使用列表、hashMap、Collection(带比较器？)或其他。我找不到类似 (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

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 秒的平均值，那么你可以将剩余的平均值添加到已经计算的一秒的平均值并将它除以 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;

但请记住有人说过:“先衡量再行动”- 也许您的表现就足够了？

---

更新通过使用 Circular buffer并做一些简单的技巧，您可以至少节省一次迭代。如果缓冲区已满(并且其容量为 50)，则存在已知的平均值并且会出现另一个值 - 您可以通过计算简单地重新计算它

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

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