Сравнить float array as int array

Question

Мне нужен оптимизированный алгоритм бинарного поиска в массиве отсортированных чисел. Я сделал это и обнаружил, что с помощью поплавка чисел магазина быстрее, чем при использовании целого числа, потому что в конце концов я должен вычислить

(frameNumber-this->frameNumber[imin])/(this->frameNumber[imax]-this->frameNumber[imin]) 

this->frameNumber[imin] является самым большим номер кадра меньше равно, что frameNumber и this->frameNumber[imax] является наименьшим один больше равнее что. Этот код предназначен для вычисления прогресса между этими двумя ключевыми кадрами. массив frameNumber является статическим. Мне нужно только разобраться. Но обращайтесь к нему много раз с бинарным поиском и приведенным выше кодом для расчета прогресса.

Преобразование из int в float проводило некоторые циклы. Тогда я обнаружил, что в asm есть много инструкций fpu. Я беспокоюсь, что они могут быть медленнее, чем целые.

Так что вот и вопрос. Можно ли преобразовать массив отсортированных чисел с плавающей запятой в int * и запустить на нем двоичный поиск?

Это означает, что:

void binary_search(float key,float* array,...) 
{ 
    int key_integer=*(int*)&key; 
    int* array_intege(int*)array; 
    binary_search_for_integers(key_integer,array_integer,...); 
} 

Или мой выше вывод неверны? (Такие, как литье междунар плавать не так costy или Comparision между плавающим точками такой же скоростью, как целые числа?

спасибо!

Answer 1

Это кажется плохой идеей. Используя целое сравнение данных с плавающей точкой на самом деле приведет к правильно упорядоченному массиву поплавков, а @rlbond указует (см. http://www.h-schmidt.net/FloatConverter/IEEE754.html играть с двоичными представлениями поплавков.) Убедитесь, что sizeof(int32_t) == sizeof(float) перед использованием этого.

хак, как это на самом деле не нужен. float сравнение не намного дороже, чем int сравнение, на современном оборудовании. (Intel Haswell: ucomiss - 1 мкп, с пропускной способностью 1 на каждый цикл. Сравнение с операндом памяти - 2 раза, без микро-слияния. И он не может быть с макро-предохранителем, как cmp/jcc) Однако FP add/sub и FP mul имеют более высокие задержки, чем их целые эквиваленты, и меньшую пропускную способность. Кажется глупым преобразовать целый массив в float, поскольку вы пишете ему только потому, что хотите сделать некоторую математику FP с минимальными и максимальными значениями в конце.

Команда load-and-convert-int-to-float (x86 cvtsi2ss (односкатное однозначное целое число с целым числом 2)) примерно так же быстро и занимает такое же кодовое пространство, что и обычная нагрузка (movss).

Если ваши данные первоначально были целыми числами, и вы используете их только, используйте int (избегая преобразования для значений, которые вам никогда не понадобятся позже). Если вы получаете доступ ко всему, и только когда-либо используете свои данные в качестве поплавков, сохраните их как float. Если вы используете его как для обоих, лучше всего сохранить его как int, так что это быстрее, когда вы используете его как целое, и примерно с той же скоростью, когда используете его как float.

С вашего образца кода вы просто используете значения в положениях min и max? Намного быстрее найти значения min и max в массиве, чем сортировать весь массив. мин/макс даже векторизован с инструкциями с упакованными минутами.

Многие платформы не имеют такой быстрой точки плавания, как современные процессоры Intel, поэтому не следует переходить с плавающей запятой.