搜索前 3 个号码的最快、最有效的方法？
我目前有一个大约 8 - 10 个数字的数组，这些数字会定期更改。
因此，大约每 5 - 10 秒数字就会更新一次。
我需要每 10 秒获取数组中的前 3 个数字。
这一切都是在移动设备上完成的。
该数组是当前扫描的接入点的 RSSI，因此在我的办公室中，它通常约为 10，但在现场测试中，它可能会增加到 50 左右。
此刻，我迭代该数组 3 次，每次我取出三个最大的数字并将它们放置在三个先前声明的变量中。
我的问题是在这种情况下我应该采取什么措施来提高速度和效率？
I currently have an array of around 8 - 10 numbers that changes on a periodic basis.
So around every 5 - 10 seconds the numbers get updated.
I need to get the top 3 numbers in the array every 10 seconds.
This is all done on a mobile device.
The array is the RSSI of the currently scanned access points, so in my office its usually around 10 but out in field testing it could increase to around 50.
At the minute I iterate through the array 3 times and each time I take out the three highest numbers and place them in three previously declared variables.
My question is what should I look to do to increase speed and efficiency in this instance?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
数字只有 10 - 什么也不做。已经足够高效了。
如果大小增加，您可以使用 max-heap 来存储您的数字。
The numbers are only 10 - do nothing. It is already efficient enough.
If the size increases, you can use a max-heap to store your numbers.
为什么不使用 Arrays.sort 方法，据我所知，该方法使用 快速排序兜帽。
Paul
编辑：验证它使用 调整快速排序
Why not use the Arrays.sort method which uses as far as I am aware quick sort under the hood.
Paul
EDIT: verified it uses a tuned quick sort
您当前的算法需要 3*n 比较。您可以执行插入排序的变体来改进：
这需要 2*n 比较。 （不过，我不确定这是否值得额外的复杂性。）
You current algorithm needs 3*n comparisons. You could perform a variation of insertion sort to improve that:
This needs 2*n comparisons. (I'm not sure if it's worth the extra complexity, though.)
你的算法已经是O(n)了，快速排序是> O(n log n) 所以这肯定不是这样做的方法。如果使用树结构，例如 AVL 树，则可以将速度提高到 O(log n)。
仅就数组而言，当前的数组是最快的方法。
Your algorithm is already O(n), quick sort is > O(n log n) so that's certainly not the way to do it. You can increase the speed to O(log n) if you use a tree structure, e.g AVL tree.
As for arrays only, your current one is the fastest way to do it.
我认为在一般情况下，您应该使用基于 QuickSort 的 QuickSelect 算法，并且及时 O(n) 修改您的数组内联并对其进行“准排序”。
假设您的数组是 A[1..10] 并且未排序，通过调用 QuickSelect( A, 7 ) 您会询问“在排序数组中应该位于第七位置的数字是什么？”，这就是与“这个特定数组中第三大的数字是哪个数字？”相同。现在最棒的是 QuickSelect 确保在调用 A[i] <= A[7] 后，对于所有 0 <= A[7] 。我< 7 并且对于所有 7 <= A[7] <= A[j] j。更多信息请参见维基百科快速选择算法。
无论如何，由于大小仅为 10，您可以使用插入排序（最坏情况 O(n^2) 但适用于小数组），然后获取三个第一个/最后一个元素
编辑：
- 树结构对于仅十个元素来说是一种过度杀伤力，并且通常涉及时间/空间权衡（您需要很多指针）
- QuickSelect 的最坏情况为 O(n^2)，但“Median-of-Medians”在最坏情况下达到相同的结果 O(n)
I think in the general case you should use you use the QuickSelect algorithm which is based on QuickSort and, in time O(n) modifies your array inline and 'quasi-sort' it.
Say your array is A[1..10] and not sorted, by calling QuickSelect( A, 7 ) you are asking 'Which is the number that, in the sorted array should be in the seventh position?', and that is the same as saying 'Which number is the third bigger in this particular array?'. Now the great thing is that QuickSelect ensures that after this call A[i] <= A[7] for all 0 < i < 7 and that A[7] <= A[j] for all 7 < j. More info in wikipedia Quick Selection Algorithm.
Anyways as the size is just 10, you could use insertion-sort (worst case O(n^2) but works good with small arrays) and then get the three first/last elements
EDIT:
- Tree structures are an overkill for just ten elements, and in general involves a time/space tradeoff ( you need a lot of pointers )
- QuickSelect has an O(n^2) worst case scenario, but 'Median-of-Medians' achieves the same result in a worst case O(n)