Самый быстрый и наиболее эффективный способ искать лучшие 3 числа?
У меня в настоящее время есть массив приблизительно 8 - 10 чисел, который изменяется на периодической основе.
Таким образом около каждых 5 - 10 секунд числа обновляются.
Я должен получить лучшие 3 числа в массиве каждые 10 секунд.
Это все сделано на мобильном устройстве.
Массив является RSSI в настоящее время сканируемых точек доступа, таким образом, в моем офисе обычно приблизительно 10, но на полевом испытании он мог увеличиться приблизительно до 50.
В минуту я выполняю итерации через массив 3 раза и каждый раз, когда я вынимаю эти три самого большого количества и размещаю их в три ранее заявленных переменные.
Мой вопрос - то, что должно я надеяться делать для увеличения скорости и эффективности в этом экземпляре?
5 ответов
Числа всего 10 - ничего не делайте. Это уже достаточно эффективно.
Если размер увеличится, вы можете использовать max-heap для хранения чисел.
Почему бы не использовать метод Arrays.sort, который, насколько мне известно, использует quick sort под капотом.
Пол
РЕДАКТИРОВАТЬ: подтвердил, что он использует настроенную быструю сортировку
Ваш алгоритм уже O (n), быстрая сортировка> O (n log n), так что это определенно не способ сделать это. Вы можете увеличить скорость до O (log n), если используете древовидную структуру, например дерево AVL. Что касается только массивов, ваш текущий - самый быстрый способ сделать это.
Текущий алгоритм требует 3 * n сравнений. Вы можете выполнить вариант сортировки вставкой, чтобы улучшить это:
- Поместите первые 3 элемента входного массива в выходной массив, отсортируйте их
- Выполните итерацию по остальным элементам входного массива,
- Поместите каждый элемент в выходной массив в правильную позицию
- Обрежьте выходной массив до 3 элементов
Для этого потребуется 2 * n сравнений. (Хотя я не уверен, стоит ли это дополнительных сложностей.)
Я думаю, что в общем случае вам следует использовать алгоритм QuickSelect, основанный на QuickSort, и со временем O (n) модифицирует ваш массив в строке и «квазисортирует» его.
Допустим, ваш массив - A [1..10] и не отсортирован, вызывая QuickSelect (A, 7), вы спрашиваете: «Какое число в отсортированном массиве должно быть на седьмой позиции?» И это то же самое, что сказать: «Какое число третье больше в этом конкретном массиве?». Замечательно то, что QuickSelect гарантирует, что после этого вызова A [i] <= A [7] для всех 0 Алгоритм быстрого выбора .
В любом случае, поскольку размер всего 10, вы можете использовать сортировку вставкой (худший случай O (n ^ 2), но хорошо работает с небольшими массивами), а затем получить три первых / последних элемента
РЕДАКТИРОВАТЬ: - Древовидные структуры - это перебор всего для десяти элементов и, как правило, требуют компромисса между временем и пространством (вам нужно много указателей) - QuickSelect имеет наихудший сценарий O (n ^ 2), но «Median-of-Medians» дает тот же результат в наихудшем случае O (n)