Быстрая генерация "последовательности треугольника": избегая неправильных прогнозов

Я заинтересован в расчете последовательности треугольника1, которая является последовательностью пар (i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ...который перебирает все пары (i, j) с ограничением, что i >= j, Та же самая последовательность с, но с ограничением i > j также интересна.

Эти последовательности представляют, помимо прочего, все способы выбора 2 (возможно, идентичных) элементов из набора из n элементов (для последовательности до (n, n)2) или индексы нижних триагулярных элементов матрицы3. Последовательность значений для i только A003056 в OEIS, в то время как j один A002262. Последовательность часто возникает в комбинаторных алгоритмах, где их производительность может быть критической.

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

if (i == j) {
    j = 0;
    i++;
  } else {
    j++;
  }      
}

Тем не менее, это страдает от многих ошибочных прогнозов при расчете начальных элементов последовательности, при проверке условия (i == j) - как правило, один неверный прогноз каждый раз i увеличивается Поскольку последовательность увеличивается, число ошибочных прогнозов становится меньше, так как i увеличивается с пониженной частотой, поэтому j++ Отрасль доминирует и хорошо предсказуема. Тем не менее, некоторые типы комбинаторного поиска многократно перебирают небольшие термины в последовательности, поэтому я ищу подход без ветвей или другой подход, который подвергается меньшему количеству ошибочных прогнозов.

Для многих случаев порядок последовательностей не так важен, поэтому допустимо генерирование значений в отличающемся от приведенного выше порядке, если оно приводит к лучшему решению. Например, j может считать, а не вверх: (0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ...,

1 Мне также интересно узнать, как правильно называть эту последовательность (возможно, поэтому я сделаю лучший заголовок для этого вопроса). Я просто изобразил "последовательность треугольников".

2 Здесь i >= j версия представляет суб-мультимножества (повторение разрешено), в то время как i > j Вариант представляет нормальные подмножества (без повторений).

3 Здесь i >= j версия включает в себя основную диагональ, а i > j вариант исключает это.

Источник

3 ответа

Решение

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

const bool eq = i == j;
i += eq;
j = (j + 1) & (eq - 1);

Второй использует сравнение и умножение:

const bool eq = i == j;
i += eq;
j = (j + 1) * (1 - eq);

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

Оба подхода приводят к созданию кода без ветвей только для процессоров, которые позволяют проводить сравнения без ветвей (например, x86). Также предполагается, что эти подходы будут реализованы с использованием языка, где результаты условных выражений могут быть легко преобразованы в целые числа (например, C/C++, где "ложные" сравнения преобразуются в нулевые целые числа, а "истинные" - в целые числа, равные "1").

Единственная проблема с этими подходами - производительность. Теоретически они могут превзойти разветвленный код, но только в том случае, если неправильные прогнозы действительно часты. Простой тест, в котором нет никакой другой работы, кроме генерации "последовательности треугольников" (см. Его на ideone), показывает жалкую скорость неверного прогнозирования и, следовательно, оба метода без ветвления примерно в 3 раза медленнее, чем метод с ветвлением. Объяснение простое: не должно быть много неправильных прогнозов для более длинных последовательностей; Что касается более коротких, современные процессоры имеют очень хорошие предикторы ветвления, которые почти никогда не выходят из строя в случае коротких паттернов ветвления; поэтому у нас не так много неправильных прогнозов, код ветвления почти всегда выполняет только 2 инструкции (сравнение, приращение), в то время как код без ветвлений выполняет как активные, так и относительные "ветки" плюс некоторые инструкции, характерные для подхода без ветвей.

В случае, если вы хотите repeatedly iterate over the small terms in the sequence Возможно, другой подход был бы предпочтительнее. Вы вычисляете последовательность только один раз, а затем повторно считываете ее из памяти.

Источник

В Python мы можем выразить это как:

i, j = i + (i == j), (j + 1) * (i != j)

но получается, что примерно на миллион итераций на моем компьютере следующий, более длинный и ленивый код оценки работает примерно на 20% быстрее:

from itertools import count, repeat

def gen_i():
    """ A003056 """
    for x in count(0):  # infinitely counts up
        yield from repeat(x, x + 1)  # replication

def gen_j():
    """ A002262 """
    for x in count(0):  # infinitely counts up
        yield from range(x + 1)  # count up to (including) x

sequence = zip(gen_i(), gen_j())

for _ in range(1000000):
    i, j = next(sequence)

В приведенном выше коде, gen_i(), gen_j(), count(), repeat(), а также zip() все генераторы (и range() это итератор) так sequence продолжает вызывать код по требованию, так как требуются новые (i, j) пары. Я предполагаю, что реализация range() а также repeat() прекратить с ошибочным прогнозом.

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

Итак, что важнее: быстро создать последовательность или избежать неправильных прогнозов?

Источник

Вы можете вывести j из i:

...set val...
old_j = j;
j = (j + 1) % (i + 1);
if (i == old_j) {
    i++;
}
...loop if more...

И, кроме того, я получаю приращение от j до текущего i:

...set val...
old_j = j;
j = (j + 1) % (i + 1);
i = i + (i / old_j);
...loop if more...

(Не могу проверить это в данный момент... Пожалуйста, просмотрите)

Источник
Другие вопросы по тегам