У меня есть массив с плавающей точкой, отсортированный от наименьшего к наибольшему, и мне нужно иметь возможность выбрать ближайший с плавающей точкой больше или меньше, чем переданное входное значение. Это входное значение не обязательно присутствует в качестве значения в массиве.
Наивным подходом было бы сделать простой линейный поиск по массиву. Это может выглядеть так:
void FindClosestFloatsInArray( float input, std::vector<float> array,
float *min_out, float *max_out )
{
assert( input >= array[0] && input < array[ array.size()-1 ] );
for( int i = 1; i < array.size(); i++ )
{
if ( array[i] >= input )
{
*min = array[i-1];
*max = array[i];
}
}
}
Но очевидно, что по мере увеличения массива это будет становиться все медленнее и медленнее.
У кого-нибудь есть идея алгоритма, который позволил бы мне находить эти данные более оптимально? Я уже переключился на бинарный поиск, который несколько улучшил ситуацию, но он все еще намного медленнее, чем хотелось бы, и, поскольку я на самом деле не ищу конкретное значение, которое существует в массиве, оно никогда не может завершиться рано.
Дополнительная информация: Значения с плавающей запятой в массиве не обязательно распределены равномерно (то есть массив может состоять из значений "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f. 1203.f, 1400.f ".
Я делаю эту операцию сотни тысяч раз, но могу выполнить любую предварительную обработку массива с плавающей точкой, если это улучшит время поиска. Я абсолютно могу изменить, чтобы использовать что-то кроме вектора для их хранения, если это поможет.
источник
Ответы:
Код в вопросе (линейный поиск), как вы правильно заметили, будет работать медленно для больших массивов с плавающей точкой. Технически это O (n), где n - число значений с плавающей точкой в вашем массиве.
В общем, лучшее, что вы можете сделать, чтобы найти значение в упорядоченном массиве, - это рекурсивный поиск дерева некоторого вида (например, двоичный поиск), и в этом случае вы можете достичь времени поиска O (log n) по количеству элементов. в вашем массиве. O (log n) намного лучше, чем O (n) для больших значений n.
Поэтому мой предложенный подход будет простым бинарным поиском массива , а именно:
Это алгоритм O (log n), который должен быть достаточно быстрым практически для всех ситуаций. Интуитивно понятно, что он работает наполовину, чтобы искать диапазон на каждом шаге, пока вы не найдете правильное значение.
Простой бинарный поиск действительно трудно реализовать, поэтому, если вы уже правильно его реализовали, то, возможно, вы уже достаточно близки к оптимальному. Однако, если вы знаете распределение данных и / или имеете ограниченный диапазон значений поиска (x), есть еще некоторые более продвинутые приемы, которые вы можете попробовать:
Однако, если вы не находитесь в особой ситуации, я, вероятно, рекомендую придерживаться простого бинарного поиска. Причины:
источник
Это кажется достаточно простым:
Выполните бинарный поиск для поплавка, который вы хотите связать - O (log n) раз.
Тогда элемент слева от него является нижней границей, а элемент справа от него является верхней границей.
источник
Очевидный ответ - хранить поплавки в дереве . Поддержка операций «предыдущий» и «следующий» тривиальна в дереве. Так что просто сделайте 'next' для вашего значения, а затем сделайте 'previous' для значения, которое вы найдете на первом шаге.
источник
Эта статья («сублогарифмический поиск без умножений») может представлять интерес; он даже содержит некоторый исходный код. Для сравнения вы можете рассматривать число с плавающей запятой как целое число с одинаковым битовым шаблоном; это было одной из целей разработки стандарта IEEE с плавающей запятой.
источник