Более сложный бит: эффективная реализация двоичного поиска по массиву фиксированного размера

Question

Еще раз, у меня есть проблема, из-за которой я бы хотел сбрить наносекунды. У меня есть небольшой постоянный массив, и я хотел бы найти его, чтобы увидеть, является ли данное число членом *.

Вход : 64-битное число n .

Выходные данные : Истина, если n находится в массиве, ложь, если n нет.

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

Особенности

У меня есть массив с 136 членами (хотя см. Ниже: есть некоторая гибкость) для поиска. Члены не равномерно распределены по диапазону: они объединяются в начало и конец диапазона. Входные числа можно считать выбранными с равномерной вероятностью. Вероятно, стоит воспользоваться этим нарушением.

Вот примерная картина распределения для массива из 136 элементов. Обратите внимание, что только 12 из 136 элементов находятся между 1% и 99% диапазона; баланс ниже 1% или более 99%.

http://math.crg4.com/distribution.png

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

Примечания

* На самом деле, у меня есть два массива. На самом деле, у меня есть выбор, какие массивы использовать: эффективность предполагает, что у первого должно быть, возможно, 10-40 членов, в то время как у второго может быть не более (точно) 136 членов. Моя проблема дает реальную гибкость в выборе размеров, а также ограниченную свободу выбора, какие именно элементы использовать. Если метод работает лучше с определенными размерами или ограничениями, укажите это, потому что я могу его использовать. При прочих равных условиях я бы предпочел, чтобы второй массив был максимально большим. По причинам, не связанным с бинарным поиском, мне может понадобиться уменьшить размер второго массива до <= 135 или <= 66 (это связано с трудностью определения числа <em>input , которое зависит от массива выбран).

Вот один из возможных массивов, если он помогает в тестировании идей. (Это довольно хорошо показывает мою цель ...!) Однако не спешите с необоснованными выводами на основе первых нескольких членов.

0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 9320093220751060618, 9999984858389672876, 10259680355300795461, 10358875208395550958, 10396764270768694864, 10411236604793371085, 10416764544494255842, 10418876029572233892, 10419682545105283285, 10419990606626453414, 10420108275656914408, 10420153221227127261, 10420170388907304826, 10420176946377624668, 10420179451108406629, 10420180407830432670, 10420180773265728832, 10420180912849591277, 10420180966165882450, 10420180986530893524, 10420180994309635573, 10420180997280850646, 10420180998415753816, 10420180998849248253, 10420180999014828394, 10420180999078074380, 10420180999102232197, 10420180999111459662, 10420180999114984240, 10420180999116330509, 10420180999116844738, 10420180999117041156, 10420180999117116181, 10420180999117144838, 10420180999117155784, 10420180999117159965, 10420180999117161562, 10420180999117162172, 10420180999117162405, 10420180999117162494, 10420180999117162528, 10420180999117162541, 10420180999117162546, 10420180999117162548

Первоначально я буду запускать программу на Phenom II x4, но оптимизация для других архитектур приветствуется.

Answer 1

Если все, что вас интересует, это член / не участник, а не местоположение, вы могли бы исключить некоторые условные ветви следующим образом:

bool b = false;
b |= (n == x[i]);
b |= (n == x[i+1]);
// ... etc. ...

Очевидно, что вы, вероятно, не хотите делать это для всех 136 записей. Но может быть приятным моментом, когда вы можете смешать крупнозернистый двоичный поиск, чтобы сначала определить, какая партия, например, 4 элемента n могут быть включены, а затем переключиться на вышеуказанный подход.

Answer 2

Поскольку вы знаете данные массива во время компиляции, вы можете рассмотреть возможность использования хеша вместо двоичного поиска. Тщательно выбранный хеш может быть быстрее, особенно если вы можете найти простую хеш-функцию, которая не сталкивается с вашими данными и вписывается в ваши ограничения памяти.

Редактировать: для дальнейшего объяснения ...

Вы хэшируете 64-битное значение с меньшим значением, которое является индексом в массиве. В вашем случае вы хотели бы иметь хеш без коллизий, поэтому ваш массив будет просто массивом а) для попаданий, 1 действительным значением, которое хэширует индекс этого массива, или б) для промахов, недопустимым значением.

Вы выбираете хеш-функцию, которая соответствует вашим целям. В вашем случае основными параметрами являются:

• размер хеш-вывода, который определяет размер массива, а также влияет на вероятность коллизии.
• функция, которая настолько проста (быстра), насколько это возможно.
• функция, которая не создает столкновений.

При условии отсутствия коллизий, вы используете его во время выполнения следующим образом:

1. Хешируйте ваш ввод.
2. Используйте полученное значение хеша для индексации в вашем массиве.
3. Проверьте, соответствует ли значение массива вашему вводу.

Если ваша хеш-функция создает коллизии, вы можете выбрать:

• Увеличьте выход хеша, чтобы уменьшить вероятность коллизий.
• Попробуйте найти другую хеш-функцию, которая не создает коллизий с вашим конкретным набором данных.
• Создайте массив чего-то более сложного, например, связанного списка допустимых 64-битных входных данных, которые хэшируют это значение. Но это замедляет работу, поскольку вышеприведенный шаг 3 становится более сложным: вам нужно сканировать связанный список, а не просто проверять одно значение.

Answer 3

В качестве очень простой возможной оптимизации создайте таблицу поиска с 256 записями для наиболее значимых 8 битов вашего 64-битного значения. В каждой строке таблицы хранятся индексы в фактическом массиве нижних и верхних границ значений с этими старшими 8 битами. Вам нужно только найти этот регион массива.

Если бы значения вашего массива были равномерно распределены, все области были бы примерно одинаковой длины, и это не обеспечивало бы большого усиления (если оно есть), оно не сильно отличалось бы от интерполяционного поиска. Так как ваши значения настолько искажены, большинство из 256 записей будут указывать на очень короткие области (около середины), которые быстры для двоичного поиска, или даже на области 0 размера. 2 или 3 записи на каждом конце будут указывать на гораздо большие области массива, которые затем будут искать относительно долго (почти столько же, сколько двоичный поиск по всему массиву). Поскольку ваши входы распределены равномерно, среднее время, затрачиваемое на поиск, будет уменьшено, и, надеюсь, это сокращение будет больше, чем стоимость первоначального поиска. Ваш худший случай вполне может оказаться медленнее.

Чтобы уточнить это, у вас может быть двухуровневая таблица поиска по 4 бита за раз. Первый уровень либо говорит «поиск между этими индексами», либо «ищет следующие 4 значащих бита в этой таблице второго уровня». Первый вариант подходит для средних значений, где 16-кратный диапазон значений по-прежнему соответствует очень маленькому диапазону индексов, поэтому поиск по-прежнему быстрый. Последний будет для концов диапазона, где пространство поиска больше. Общий размер таблиц будет меньшим, что может или не может дать лучшую производительность из-за лучшего кэширования меньшего количества данных. Сами таблицы могут быть сгенерированы во время выполнения или во время компиляции, если вы хотите сгенерировать код на С, когда известны значения массива. Вы могли бы даже закодировать таблицу поиска как гигантский оператор switch из ада, просто чтобы увидеть, ускоряет ли он вещи или нет.

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

Обратите внимание, что я работал над тем, чтобы уменьшить количество сравнений, выполненных в бинарном поиске, а не количество ошибочных прогнозов ветвей. В любом случае, они в некоторой степени пропорциональны - вы не можете избежать того, что каждый раз, когда вы вдвое сокращаете возможности в бинарном поиске, вы получите неправильное предсказание примерно в 50% случаев. Если вы действительно хотели минимизировать неправильные прогнозы, то линейный поиск гарантирует только одно неправильное прогнозирование на поиск (тот, который прерывает цикл). В общем, это не быстрее, но вы можете поэкспериментировать, чтобы узнать, есть ли размер для оставшегося массива, который нужно искать, ниже которого вы должны переключиться на линейный поиск, возможно, развернутый, возможно, полностью развернутый. Может быть какой-то другой гораздо более умный гибридный линейный / бинарный поиск, который можно настроить на относительную стоимость успешного сравнения или неудачного сравнения, но если это так, я этого не знаю.

Answer 4

Обычный бинарный поиск повторяется не более log_2 (n) раз.Каждая итерация обычно имеет три сравнения (мы закончили? Число выше? Это меньше?).Это три шанса потерпеть неудачу при предсказании ветвления на каждой итерации.

Если вы развернули бинарный поиск (который выполним, потому что ваш массив очень мал, а значения известны заранее), вы можете исключить «еслисделанный?"сравнения, и ваша типичная база будет идти от 3 * log_2 (n) до 2 * log_2 (n).Это меньше выполненных инструкций и меньше шансов для предсказания пропущенного перехода.Но это также более полные инструкции (и, следовательно, менее дружественные к кешу).Вы должны были бы профилировать, чтобы увидеть, поможет ли это в итоге.

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

Возможно, под управлением профиляОптимизация развернутого поиска может помочь в дальнейшем, используя неравномерное распределение.

Answer 5

Интересной альтернативой является использование модифицированной (двунаправленной) версии линейного поиска.

Псевдокод проще, чем код:

if the value is greater than or equal to 2^63
    linear search from middle to end
otherwise (if the value is less than 2^63)
    linear search from middle to beginning (must go in reverse direction)

Мой код довольно хакерский, но выможно сделать его более элегантным:

int in_set(unsigned long long value)
{
    const unsigned long long max_bit_mask = (1 << 63);

    if(value & max_bit_mask) //if max bit is set, use linear search from middle (50% probability)
    {
        unsigned long long *ullp = data + 91; //WARNING: ullp should point to data + 92 on first dereference due to prefix increment
        while(*++ullp < value); //FIXME: array must be capped with ULLONG_MAX on the right
        return *ullp == value; //&& ullp != right_sentinel
    }

    //otherwise use reverse linear search from middle

    unsigned long long *ullp = data + 92; //WARNING: ullp should point to data + 91 on first dereference due to prefix decrement
    while(*--ullp > value); //WARNING: array must be capped with zero on the left
    return *ullp == value; //&& ullp != left_sentinel
}

Для случайных входов в этот конкретный массив распределения Фибоначчи код будет представлять собой алгоритм O (1) в среднем (O (k) в худшем случае, когда kразмер таблицы).

Вы можете использовать стратегию поиска таблиц Стива Джессопа для кэширования индекса элемента, ближайшего к центру массива с определенной 8-битной сигнатурой, но это может сделать код медленнее, так как выдобавляем дополнительный O (1) временной фактор с дополнительным неправильным прогнозом ветвления.

const int lookup_table[256] = {/*...*/};

unsigned long long *ullp = data + lookup[value >> 56];

//if, while, and returns as before

Одна из проблем реализации этой стратегии заключается в том, что вам нужно дополнить минимальные и максимальные значения в левой и правой частях массива.или ошибки произойдут в конце концов (в этом случае 0 и ULLONG_MAX).Для нуля это не проблема, но для ULLONG_MAX значение отсутствует в наборе, и поэтому требуется дополнительная логика.В этом конкретном случае необходимо использовать и должным образом учитывать значения часового.

edit: сложность по времени в среднем составляет O (1), поскольку каждое продвижение курсора имеет ~ 40% (1 / phi ^2) вероятность возврата, ожидаемая стоимость представляет собой сумму n / phi ^ (n + 1) для n> = 1, что равняется 1 / (phi-1) ^ 2 (~ 2.6 продвижения курсора)

edit2: этот код должен иметь гораздо меньше ошибочных предсказаний ветвления, чем бинарный поиск, и должен быть в среднем быстрее, если запросы имеют «равномерное целочисленное распределение».

Answer 6

Поскольку в нем всего 136 членов, на новом компьютере я бы осуществлял поиск методом "грубой силы", используя 128-битные инструкции и предварительную выборку.

Если бы существовали тысячи членов, я бы повторил идею Стива Джессопа оТаблица поиска с 256 записями выше, но с функцией f (x), примененной к значению поиска, цель которой состоит в том, чтобы равномерно распределить элементы по 256 сегментам.

f (x) может быть своего рода полиномом, подобным"сгладить" из мира графики, но, возможно, не так гладко.

Answer 7

Интересная проблема.Сначала я подумал, что это одна из многих проблем, которые могут быть наиболее эффективно решены с помощью красно-черного дерева, отображающего возрастающие значения на индексы.

Однако , вы указали, чтораспределение настолько неравномерно.Если мы сначала рассмотрим это с человеческой точки зрения: что бы человек делал , он / она, вероятно, сначала проверит, ниже ли данное значение квантиля 0,01, затем выше квантиля 0,99 ипо этой стратегии уже ограничил пространство поиска на 49/50 только сделав 2 сравнения.

• Дальнейшие итерации в диапазоне 0,01-0,99 редки (эти числа являются отображением 0 ... 1, например, 64-битного пространства значений)

• Дальнейшие итерации в диапазоне 0,0-0,01 и 0,99-1,0 не требуют углубления, поскольку они уже близки к правильному значению.

Итак, как мы можем обобщить это?Нам не нужно.Вы заметили, что 0,0-0,01 часто и 0,99-1,0 в пространстве значений часто; но это, вероятно, не так во второй итерации и определенно не так в третьей итерации (вы не найдете такого же распределения в диапазоне значений 0,0-0,01, как в полном диапазоне).

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