4

我有一个音频输入流，它接收当前播放音乐的音量。然后在最新卷的某个窗口大小（范围从 5 到 40）上，我想跟踪窗口内的最高和最低值。所以在每次迭代中，最旧的值被删除，最新的音量读数被添加。

所以说如果我以 5 个窗口运行程序 8 次迭代，这将导致。只有低值和高值很重要。

加 2

2

加 4

2 4

加 3

2 3 4

加 2

2 2 3 4

加 7

2 2 3 4 7

-first 2 从列表中删除添加 9

2 3 4 7 9

删除 4 个，添加 5 个

2 3 5 7 9

删除 3 个，添加 2 个

2 2 5 7 9

ETC

什么是最有效的方法和使用什么类型的集合？

编辑注意，这个循环在一个单独的线程上不断运行

值是浮点数

4

3 回答 3

3

在每次迭代中添加和删除一个数字，然后找到最小值和最大值，它们出现的数量相同

使用平衡二叉树，例如Treemap，所以在最坏的情况下，所有操作都是 O(log n)。我相信，如果这些操作连续发生，那么 3 个操作是 O(1) 和一个是 O(n) 是没有意义的。

顺便说一句，n=5 太小了，我不明白为什么你应该过分担心效率低下。

编辑： 要跟踪对象的顺序，您可以使用简单的队列作为二级结构。当您需要删除时，您删除队列的头部并将其用作在树中删除的键......添加和删除需要恒定的时间。

注：可以到此为止，原创思路如下

一个更好的复杂性数据结构将是一个调整过的min-max heap，它在你的所有操作之间提供了一个很好的权衡：

  • 插入是O(log n)
  • 删除是O(n)
  • 最小值和最大值都是O(l)。

如果您只删除最大/最小，删除将是对数的。调整是实现一个通用的删除，即 log n

于 2013-09-29T09:58:51.900 回答
1

您可以使用链表，因为您想在列表中存储重复值。此外，由于您计划添加到最后一个元素，因此您使用 LinkedList API 的 addLast() 方法。在您自己的 add() 方法中检查大小。如果大小达到最大大小，您可以调用链接列表的 removeFirst() 方法，然后调用 addLast() 方法。这样你的链接列表大小将保持在 5

public class Tester {
private LinkedList<Integer> values = new LinkedList<Integer>();
private static final int MAX_VAL = 5;

public void addvalue(int val) {
    if (values.size() == this.MAX_VAL) {
        values.removeFirst();
    }
    values.addLast(val);
}

public int getMaxValue(){           
    return Collections.min(values);
}

public int getMinValue(){
    return Collections.max(values);
}

}

于 2013-09-29T08:39:28.910 回答
0

由于这些值是整数 5 到 40，如果窗口很大，我们可以通过存储数组来尝试获得一个好的平均案例时间，该数组count[]记录每个卷的窗口数量。然后添加新元素并删除最后一个元素（保持 aQueue等LinkedList）是恒定时间，除非计数为low或high下降到 0。然后从最后一个最佳值开始逐个搜索值，O(35)但实际上可能更便宜，尤其是有一个大窗户。

在某种程度上，这是一个常数时间解决方案，在实际输入中，您添加的体积元素的数量。那里O(nk)听起来k只有三十多卷。我怀疑我们可以证明平均案例时间是窗口大小的\Theta(nk/w)位置w，假设数据分布合理。

这听起来确实不像是高吞吐量操作（用户多久可以更改一次音量，全部数百次？？）但这就是我在这些条件下实现它的方式。

于 2013-09-30T01:40:23.290 回答