Самый быстрый и самый эффективный способ поиска трех лучших номеров?

Question

В настоящее время у меня есть массив из примерно 8 - 10 чисел, которые периодически изменяются.

Так что каждые 5 - 10 секунд числа обновляются.

Мне нужно получать первые 3 числа в массиве каждые 10 секунд.

Все это делается на мобильном устройстве.

Массив - это RSSI сканируемых в данный момент точек доступа, поэтому в моем офисе его обычно около 10, но в полевых испытаниях он может возрасти до 50.

В минуту я перебираю массив 3 раза и каждый раз вынимаю три старших числа и помещаю их в три ранее объявленные переменные.

У меня вопрос: что я должен делать, чтобы увеличить скорость и эффективность в этом случае?

Answer 1

Чисел всего 10 - ничего не делать. Это уже достаточно эффективно.

Если размер увеличивается, вы можете использовать max-heap для хранения ваших чисел.

Answer 2

Почему бы не использовать метод Arrays.sort, который, насколько я знаю, использует быструю сортировку под капотом.

Пол

РЕДАКТИРОВАТЬ: подтверждено, что используется настроенная быстрая сортировка

Answer 3

Ваш текущий алгоритм требует 3 * n сравнений. Вы можете выполнить вариант сортировки вставки, чтобы улучшить это:

1. Поместите первые 3 элемента входного массива в выходной массив, отсортируйте их
2. Итерация по остальным элементам входного массива,
   1. Поместите каждый элемент в выходной массив в правильном положении
   2. Обрезать выходной массив до 3 элементов

Это требует 2 * n сравнений. (Хотя я не уверен, стоит ли это дополнительной сложности.)

Answer 4

Ваш алгоритм уже O (n), быстрая сортировка> O (n log n), так что это определенно не тот способ, которым можно это сделать. Вы можете увеличить скорость до O (log n), если используете древовидную структуру, например, дерево AVL. Что касается только массивов, ваш текущий - самый быстрый способ сделать это.

Answer 5

Я думаю, что в общем случае вы должны использовать, вы используете алгоритм QuickSelect, который основан на QuickSort и, со временем O (n) изменяет ваш массив в строке и «квази-сортирует» его.

Скажем, ваш массив A [1..10] и не отсортирован, вызывая QuickSelect (A, 7), вы спрашиваете: «Какое число в отсортированном массиве должно быть на седьмой позиции?», И это то же самое, что сказать «Какое число на треть больше в этом конкретном массиве?». Теперь замечательно, что QuickSelect гарантирует, что после этого вызова A [i] <= A [7] для всех 0 <i <7 и что A [7] <= A [j] для всех 7 <j. Больше информации в википедии <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements" rel="nofollow noreferrer"> Алгоритм быстрого выбора .

В любом случае, так как размер всего 10, вы можете использовать вставку-сортировку (худший случай O (n ^ 2), но хорошо работает с небольшими массивами), а затем получить три первых / последних элемента

EDIT: - Древовидные структуры - это перебор только для десяти элементов, и, как правило, это компромисс между временем и пространством (вам нужно много указателей) - QuickSelect имеет O (n ^ 2) в худшем случае, но «Медиана медиан» достигает того же результата в худшем случае O (n)