logo标签列表

寻找前三大数字的最快、最有效的方法是什么？

javaandroidarrayslistcollections
5
我目前有一个包含8-10个数字的数组，这个数组会定期更新，大约每5-10秒更新一次。
我需要每10秒获取数组中的前3个数字。
这一切都是在移动设备上完成的。
该数组是当前扫描的接入点的RSSI，因此在我的办公室里通常为10，在现场测试中可能会增加到50左右。
目前，我要遍历数组3次，并每次取出三个最高的数字并将它们放入三个预先声明的变量中。
我的问题是，在这种情况下，我应该做些什么来提高速度和效率？
1
我的问题是 - 你的解决方案是否太慢，还是这是一个更加学术性的问题？我们正在谈论每10秒钟大约30次迭代... - Andreas Dolk
不，它并不慢，它更加学术化。 - Donal Rafferty
1
请在此上下文中定义“高效”的含义。 - Thorbjørn Ravn Andersen
比当前实现更快的任何东西 - Donal Rafferty
2
我建议您在谷歌搜索“过早优化是万恶之源”这句话。 - DJClayworth
5个回答
7

这些数字只有10个 - 无需操作。它已经足够高效。

如果大小增加，您可以使用最大堆来存储您的数字。

谢谢，这更多是一个学术问题，我还应该说明数组可能会增加，现在正在编辑问题。 - Donal Rafferty
6
2

您的算法已经是O(n)级别的，快速排序的时间复杂度大于O(n log n)，因此这绝对不是解决问题的方法。如果使用树结构（例如AVL树），则可以将速度提高到O(log n)级别。

至于仅使用数组，您当前的方法已经是最快的。

但是更新AVL树不会比O（n）更昂贵吗？ - Niki
2
你当前的算法需要3*n次比较。你可以进行插入排序的变体来改进它：
  1. 将输入数组的前三个项目放入输出数组中，对它们进行排序
  2. 遍历输入数组的其余项目，
    1. 将每个项目放入正确位置的输出数组中
    2. 将输出数组修剪为3个项目
这需要2*n次比较。（虽然我不确定这是否值得增加复杂性。）
1

我认为在一般情况下，你应该使用QuickSelect算法，它基于QuickSort，在O(n)的时间内修改你的数组，并“准排序”。

假设你的数组是A[1..10]且未排序，通过调用QuickSelect(A, 7)，你正在询问“在排序后的数组中应该在第七个位置的数字是什么？”，这与说“在这个特定的数组中第三大的数字是什么？”是相同的。现在很棒的是，QuickSelect确保在此调用之后，对于所有0 < i < 7，都有A[i] <= A[7]，并且对于所有7 < j，都有A[7] <= A[j]。更多信息请参见维基百科Quick Selection Algorithm。

无论如何，由于大小只有10，你可以使用插入排序（最坏情况下O(n^2)，但对于小数组效果很好），然后获取前/后三个元素。

编辑： - 对于只有十个元素的情况，树结构是过度设计，通常需要时间/空间权衡（需要大量指针） - QuickSelect 的最坏情况是 O(n^2)，但“中位数法”可以在最坏情况下以 O(n) 的时间复杂度实现相同的结果

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接