Наименее дорогой поиск равенства для небольших несортированных массивов
Каков наиболее эффективный метод с точки зрения времени выполнения для поиска небольшого массива, состоящего из 4-16 элементов, для элемента, который равен тому, что вы ищете, в C ++? В этом случае искомый элемент является указателем, поэтому он относительно мал.
(Моя цель — не дать точкам в облаке точек создавать ребра с точками, которые уже имеют с ними ребро. Массив ребер мал для каждой точки, но может быть огромное количество точек. Кроме того, мне просто любопытно тоже!)
Решение
Лучше всего профилировать конкретное приложение с помощью различных механизмов и посмотреть, какие из них работают лучше всего.
Я подозреваю, что с учетом несортировки прямой линейный поиск будет лучшим для вас. Если вы можете предварительно отсортировать массив, и он обновляется нечасто или никогда, вы можете выполнить предварительную сортировку, а затем использовать бинарный поиск.
Другие решения
Попробуйте линейный поиск; Попробуйте начать с одного или нескольких этапов бинарной резки. Первый включает в себя больше сравнений в среднем; последний имеет больше возможностей для промахов кэша и неправильных прогнозов веток и требует предварительной сортировки массивов.
Только измеряя, вы можете определить, что быстрее, и только на той платформе, на которой вы измеряли.
Если вам нужно выполнить этот поиск более одного раза, и массив не меняется часто / вообще, сортируйте его и затем используйте бинарный поиск.