Fastware

Андрей Александреску — настоящая живая легенда. Это человек, внесший значительный вклад в историю современных языков программирования и приёмов обобщенного и метапрограммирования. Сколько копий было сломано в обсуждениях «Современного проектирования на С++» и «Coding Standards 101» (написанной вместе с Гербом «Exceptional C++» Саттером), и других книг и статей. Являясь соавтором языка D, он имел возможность не только теоретизировать, но и воплощать мечту в реальность — и, что характерно, воплотил.

Сейчас вы держите в руках его доклад с конференции DotNext 2018 Piter, в котором рассказывается о современных технологиях оптимизации. При чём тут .NET? Это фундаментальный доклад от человека, который всю жизнь занимается оптимизациями. Если тебе важен перформанс — его нужно смотреть (либо читать эту статью). Добро пожаловать под кат!

The art of benchmarking

Я хотел бы обсудить с вами несколько тем, касающихся бенчмаркинга. Для начала давайте повторим некоторые базовые вещи. Закон Амдала — часть классики computer science, он в основном используется в параллельных вычислениях, но работает в любой сложной системе. Если мы хотим улучшить работу некоторой системы, то начинать надо там, где сосредоточены основные проблемы этой системы. Сам закон очевиден: если компонент составляет 20% системы, то максимальное улучшение производительности системы, которого можно достичь, оптимизируя работу только этого компонента, составляет 20%. Мне слишком часто приходится встречаться с людьми (к ним, конечно, не относятся наши читатели), занимающимися вещами вроде оптимизации парсинга командной строки. На эти операции уходят первые 10 микросекунд работы вашей программы, а люди анализируют их алгоритмическую сложность и ужасаются, если время оказывается квадратичным.

Как вы наверняка знаете, прежде, чем начинать оптимизацию, необходимо провести профилирование приложения, выбрать в нём хот-споты. Здесь следует сказать о законе Ладмы (это ненастоящая фамилия, а Амдал, прочитанный задом наперёд). Вам необходимо сконцентрировать свои усилия на компоненте, приводящем к наибольшим затратам времени. Его нужно вынести за пределы приложения, провести необходимую работу, вернуть назад и снова протестировать. Причина, по которой так нужно поступать, заключается в том, что очень часто улучшение производительности на 20% является результатом десяти улучшений по 2%. А в рамках большой системы измерить такое небольшое улучшение невозможно. Для этого компонент нужно тестировать в тестовой сюите. Улучшение производительности одного из основных компонентов системы на 20% может означать улучшение на 5% для системы в целом, и для некоторых сфер это прекрасный результат. Не забывайте, что у оптимизаций может быть целый ряд глобальных эффектов, так что по результатам выборочного бенчмаркинга стоит очень осторожно делать выводы относительно работы системы в целом.

Ошибка, которую, я уверен, не допускают наши читатели, но которая в целом достаточно распространена: люди измеряют скорость отладочной сборки. Этого никогда не надо делать. Это аналогично тому, чтобы расстраиваться из-за низкой скорости улитки на скачках: она для такого соревнования не предназначена, у неё другие цели в жизни. Другая ошибка, несколько менее очевидная: люди вначале измеряют базовые показатели работы системы, и сразу же после этого выполняют бенчмаркинг. Но после сбора базовых показателей многие ресурсы оказываются прогретыми. Например, открытые файлы буферизируются и остаются в памяти (по крайней мере, под Linux). Таким образом, второе тестирование пройдёт быстрее только потому, что оно запущено после первого. Это происходит даже с вызовами malloc. После этих вызовов система не возвращается в исходное состояние даже если совершаются вызовы освобождения памяти. Внутренняя конфигурация, кэшинг и возможности, которыми воспользовался выделитель памяти, позволяют следующим вызовам malloc выполняться значительно быстрее. Даже без учёта эффекта от кэша, malloc помнит, что, например, некоторая функция много раз выделяла память под объекты размером в 4 килобайта — значит, необходимо иметь свободный список с размером элемента в 4 килобайта. Или другой пример: поиск DNS кэшируется для повторного использования после первого запроса. Если это возможно, при бенчмаркинге нужно каждый раз заново запускать весь процесс, от начала и до конца.

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

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

Перед вами пример со Stack Overflow. Автор часто сортирует уже отсортированные данные и удивляется, ведь функция `is_sorted, очевидно, значительно быстрее, чем `sort. Почему тогда в `sort первая строка не является `if is_sorted return? Вы проводите оптимизацию крайне редкого случая, полностью отсортированных данных, а всем остальным, у кого есть хотя бы один не отсортированный элемент, придётся нести издержки за эту оптимизацию. Так делать не стоит.

Я думаю, мне не придётся долго доказывать, что конкурирующие сегодня архитектуры крайне сложны: динамическое изменение частоты, прерывание другими процессами, виртуализация и т.д. Поэтому получить одинаковое время при измерении практически невозможно, ваши показатели всегда будут дрожать. Поэтому не следует полагаться на вещи, кажущиеся очевидными. Скажем, нам может показаться очевидным, что меньшее количество инструкций значит более быстрый код, а это вовсе не всегда верно. Может также казаться, что использовать сохранённые данные всегда будет быстрее, чем заново осуществлять вычисления, так что если вы кэшируете результаты, у вас всё будет в порядке. Как и в предыдущем случае, однозначно это утверждать нельзя, как и нельзя безоговорочно утверждать обратное — всё зависит от контекста. Очевидно вам должно быть только одно: всё необходимо измерять. Если вы будете измерять всё, вы будете получать лучшие результаты, чем эксперты со знаниями, которые не делают измерений.

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

Другое общее правило заключается в том, что компьютеры любят, чтобы всё было скучно. Вам нужно умножить друг на друга два вектора, по миллиарду элементов в каждом? Это идеальное задание для компьютера, всё оборудование в нём специально заточено под такой род задач. Анализировать эти данные, на основе них строить регулярное выражение — этим заниматься не хочется. Компьютерам не нравятся вещи наподобие ветвлений, зависимостей, косвенных вызовов, короче говоря — им не нравится умный код, им нравится скучный код. Компьютерам не нравится косвенная запись — сложная проблема, с которой люди, занимающиеся железом, бьются уже давно и не могут решить.

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

Наконец, последнее правило — чем меньше, тем красивее. Небольшие размеры позволяют компьютерам лучше всего реализовать свои преимущества, поскольку они предпочитают, чтобы данные и, в особенности, инструкции, находились близко друг к другу. Результаты нескольких измерений скорости работы приложения всегда будут отличаться, вы будете иметь некоторое распределение результатов. Обычно мы просто берем среднее значение этих нескольких результатов. Но проблема в том, что из-за специфики работы компьютеров среднее будет включать очень много шума. Когда Билл Гейтс едет на автобусе, в среднем каждый пассажир автобуса оказывается миллиардером. Это звучит прекрасно, но является слабым утешением для бездомного, едущего в том же автобусе. Аналогичная ситуация возникает с прерываниями: операция умножения занимает наносекунды, но когда вы осуществляете много измерений таких операций, на одно из них неизбежно придётся прерывание продолжительностью в две миллисекунды. Разница в три порядка, и тем не менее, разработчики не всегда учитывают это обстоятельство.

Итак, повторюсь: шум в компьютерах всегда аддитивный; для людей он может казаться незначительным, но для микробенчмаркинга он существенный, и среднее арифметическое будет включать в себя очень много шума. Вместо средней вам необходим показатель, который будет измерять только то время, на которое вы как-либо можете повлиять. Если мы подойдём к этому вопросу с точки зрения математики, то увидим, что нам нужно найти такое значение, которому будет соответствовать наибольшее количество проделанных нами измерений. Иначе говоря, нам нужна мода. Это сразу подводит нас к проблеме: что будет, если взять моду quicksort? Если алгоритм вероятностный или если данные случайные, то моды почти никогда не будет. Плотность значений будет почти одинаковой по всему спектру. В этом случае мы просто отбрасываем 5% наибольших измерений и после этого берём среднее значение — или максимальное, в последнем случае мы будем иметь потолок, который не будет превышен в 95% случаев. Практически всегда найдётся какой-нибудь один субъект, сидящий в старом подвале с медленным модемом, у которого каждая страница будет грузиться по часу. Чисто по-человечески мы ему, конечно же, сочувствуем, но технически помочь всем мы не можем — поэтому оставшимися 5% случаев приходится пренебречь. В целом, при решении сетевых задач мы достаточно часто ориентируемся на 95-й процентиль, потому что ориентироваться на 100-й невозможно. Сотый процентиль будет означать наиболее медленный результат из всех собранных измерений — это не информативно.

Replace branches with arithmetic

Как, я надеюсь, стало ясно, измерения — проблема непростая. Давайте рассмотрим некоторые примеры и начнём с того, что попробуем заменить ветвление арифметикой. Речь идёт о случаях, когда нам нужен оператор if, но при этом его слишком частое использование нежелательно. Вместо него мы будем интегрировать результат ветки как значение 0/1. Код будет выглядеть линейным, компьютеру нужно будет просто пройти его от начала до конца, не задумываясь о том, какой именно шаг необходимо предпринять дальше.

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

static void min4(double[] p) {
  int n = p.Length;
  int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4;
  for (; i < n / 4; ++i, ++j, ++k, ++l) {
    int m = p[i] <= p[j] ? i : j;
    if (p[k] < p[m]) m = k;
    if (p[l] < p[m]) m = l;
    Swap(ref p[i], ref p[m]);
  }
}

Выше приведен базовый вариант кода. Кстати говоря, могу с гордостью сообщить, что перевел эти примеры на С#, и они успешно компилируются. Сам код достаточно простой: `m присваивается индекс наименьшего из двух значений, находящихся по индексам `i и `j, а затем аналогичное присвоение повторяется ещё два раза, в зависимости от двух других индексов. Наконец, значение по индексу `m меняется местами в массиве со значением по индексу `i. Как видим, мы обходим массив при помощи четырёх индуктивных переменных.

Проблема тестирования такого алгоритма будет интересной и неочевидной. Нам нужно будет тестировать его не на одном наборе данных, а на данных, которые могли бы возникнуть в различных случаях. Например, на данных, которые выглядят как трубы органа: сначала возрастают, затем убывают; на случайных данных с однородным распределением; на случайном наборе нулей и единиц — от просто случайных данных здесь отличие в том, что будет много повторяющихся значений; на уже отсортированных данных; наконец, на данных, полученных реальным измерения некоторого физического явления. Это будет серьёзным подходом к измерению скорости алгоритма, и он является общепринятым среди людей, занимающихся изучением алгоритмов.

Попробуем улучшить код, с которым мы сейчас познакомились.

static void min4(double[] p) {
  int q = p.Length / 4;
  int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4;
  for (; i < q; ++i, ++j, ++k, ++l) {
    int m = p[i] <= p[j] ? i : j;
    if (p[k] < p[m]) m = k;
    if (p[l] < p[m]) m = l;
    Swap(ref p[i], ref p[m]);
  }
}

В качестве первой оптимизации мы попытаемся избежать чрезмерного повтора операций, для этого вынесем несколько операций деления из цикла — деление `n на 2 и на 4 и деление 3 * `n на 4. Но проведя эту оптимизацию, мы выясним, что вычисления не были для нас главной проблемой: код не станет быстрее, хоть и будет более компактным. В лучшем случае мы добьёмся улучшения в полпроцента.

static void min4(double[] p) {
  int q = p.Length / 4;
  int i = 0, j = q, k = 2 * q, l = 3 * q;
  for (; i < q; ++i, ++j, ++k, ++l) {
    int m0 = p[i] <= p[j] ? i : j;
    int m1 = p[k] <= p[l] ? k : l;
    Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]);
  }
}

Вторым изменением, которое мы внесём в код, будет сокращение зависимостей. В предыдущем варианте алгоритма присвоение `m значения `k или `l зависит от значения, присвоенного `m строчкой выше. Чтобы уменьшить число зависимостей `m мы отдельно вычислим `m0 и `m1, а затем сравним их. Когда я выполнял эту оптимизацию, я надеялся на существенное улучшение скорости алгоритма, но в итоге оно оказалось нулевым. Но, на мой взгляд, количество зависимостей важно держать минимальным, поэтому код я сохранил.

static void min4(double[] p) {
  int q = p.Length / 4;
  for (int  i = 0; i < q; ++i) {
    int m0 = p[i] <= p[i + q] ? i : i + q;
    int m1 = p[i + 2 * q] <= p[i + 3 * q] ?
      i + 2 * q : i + 3 * q;
    Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]);
  }
}

Попробуем теперь сократить количество индуктивных переменных с четырёх до одной, а остальные три будем рассчитывать арифметически, поскольку они находятся в постоянном отношении друг к другу. Это достаточно просто: вместо `k мы будем иметь `i + q, вместо двух других переменных — `i + 2 * q и `i + 3 * q. На эту оптимизацию я тоже возлагал большие надежды, но, как и прошлая, она не дала никаких результатов по времени. Это вновь доказывает важность измерений: без них я мог бы хвастаться, что существенно улучшил работу алгоритма, причём у меня были бы весьма существенные аргументы.

static void min4(double[] p) {
  int q = p.Length / 4, q2 = q + q;
  for (int i = q; i < q2: ++i) {
    int m0 = p[i - q] < p[i] ? i - q : i;
    int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q;
    Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]);
  }
}

В качестве четвёртой попытки реструктурируем цикл, чтобы избавимся от умножения на 3. Это даст нам улучшение на 3%. Результат по-прежнему не впечатляет. Далее, попробуем избавиться от троичных операторов.

// Returns: value if flag is true, 0 otherwise
static int optional(bool flag, int value) {
 return -Convert.ToInt329flag) & value;
}

Для этого я хотел бы познакомить вас с новой функцией — `static int optional(bool flag, int value). Она преобразует входное булево значение в Int32, умножает на -1 и передаёт его оператору битового «И» вместе со вторым входным значением. Если входной флаг был false, то в int32 он будет 0, и после всех преобразований на выходе мы по-прежнему получим 0. Если входной флаг был true, в int32 он будет 1, при умножении на -1 мы получим FFFFFFFF, которое после битового «И» с любым числом даст это второе число. Обратите внимание, что здесь нигде нет оператора if, код без ветвлений, для компьютера он скучный (хотя нам он как раз кажется замысловатым).

static void min4(double[] p) {
  int q = p.Length / 4, q2 = q + q;
  for (int i = q; i < q2; ++i) {
    int m0 = i - optional(p[i - q] <= p[i], q);
    int m1 = i + q + optional(p[i + q2] < p[i + q], q);
    Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]);
  }
}

Этой функцией `optional мы и заменим троичные операторы, будем интегрировать её внутри вычисления. Применим её два раза, а в третьем случае оставим знак вопроса. Таким образом, вместо четырёх проверок в этом цикле у меня будет только одна.

Из результатов измерений, которые вы видите на слайде, ясно, насколько важно было проверять алгоритм на нескольких различных наборах данных. На одном наборе мы не поняли бы ничего. На случайных и реальных данных мы имеем более чем двукратное ускорение, на трубах органа и отсортированных данных мы имеем небольшое замедление. Это происходит из-за того, что в случае с отсортированными данными для предсказателя переходов не будет никаких неожиданностей, он будет предсказывать со 100%-й точностью. В случае с трубами органа у нас будет одно неверное предсказание посредине набора данных — опять-таки, весьма высокая точность. В противоположность этому, со случайными данными разница между нашими двумя подходами будет огромной. Все непредсказуемые проверки мы заменили на простую логику. Здесь мы вновь возвращаемся к простой истине: компьютеры созданы для вычислений, как это следует из названия (computer — computing). Ветвление, отображение картинок на экране — всё это они выполняют значительно хуже. Выполнить битовое «И» для них значительно проще, чем пройти оператор if.

static void min4(double[] p) {
  int q = p.Length / 4, q2 = q + q;
  for (int i = 0; i < q; ++i) {
    int m = i + optional(p[i + q] < p[i], q);
    m += optional(p[i + q2] < p[m], q);
    m += optional(p[i + q2 + q] < p[m], q);
    Swap(ref p[i], ref p[m]);
  }
}

Добившись, наконец, положительного результата от оптимизации, попробуем заменить последний троичный оператор на нашу функцию `optional. На этот раз выигрыш в скорости будет небольшим. Чтобы разобраться, почему это происходит, необходимо взглянуть на сгенерированный код. В предыдущей версии кода, где ещё присутствовал знак вопроса, компилятор уже нашёл способ выполнять код без ветвлений. И когда же он добирается до тернарного оператора, он уже мог его предсказать. Замена этого последнего куска на `optional даст уже несколько худший код. Поэтому, повторюсь, важно каждый раз осуществлять измерение.

// Returns: v1 if flag is true, v2 otherwise
static int ifelse(bool flag, int v1, int v2) {
  return (-Convert.ToInt32(flag) & v1) |
    ((Convert.ToInt32(flag) - 1) & v2);
}

Другая функция, которую я хотел бы вам порекомендовать — `ifelse без ветвлений, которую вы сейчас видите на экране. Правда, мне не удалось добиться при помощи неё улучшений производительности в нашем примере. Если в качестве флага в неё передается 0, первая строка будет равна 0; во второй мы отнимем 1 от 0 в Int32 и получим FFFFFFFF, после чего это значение передаётся битовому «И» вместе с аргументом функции `v2, что даст нам сам этот аргумент без изменений; наконец, первая и вторая строка передаются битовому «ИЛИ», что, опять-таки, даст нам `v2. Если же флаг равен 1, то первая строка будет равна `v1; во второй мы отнимем 1 от 1 и получим 0, в результате чего вся строка будет равна 0, а 0 и `v1 в битовом «ИЛИ» дадут `v1.

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

Large set intersection

Немного сменим тему нашего разговора и перейдём к пересечению крупных множеств. До сих пор речь шла об отдельных операторах, сейчас же мы будем создавать новые алгоритмы, так что нужно будет отвлечься от деталей и открыть своё сознание более крупной перспективе. Я предполагаю, что вы знакомы с алгоритмами сортировки слиянием (merge sort), умножения двух векторов и поиска общих элементов двух отсортированных векторов. Осуществляется обход двух отсортированных множеств, и когда в них находятся равные элементы, это считается соответствием. Если же один из двух сопоставляемых элементов оказывается меньше, он смещается. Этот алгоритм достаточно простой, но очень распространённый — скорее всего, наиболее используемый в мире. Он используется во всех запросах из нескольких слов, каждый такой запрос является пересечением двух множеств. Этот алгоритм, в частности, использует Google, и он также должен применяться во всех запросах к базам данных.

int Intersect(double[] a1, double[] a2, double[] t) {
  if (a1.Length == 0 || a2.Length == 0) return 0;
  int i1 = 0, i2 = 0, i = 0;
  for (;;)
    if (a1[i1] < a2[i2]) {
      if (++i1 == a1.Length) break;
    } else if (a2[i2] < a1[i1]) {
      if (++i2 == a2.Length) break;
    } else {
      t[i++] = a1[i1];
      if (++i1 == a1.Length || ++i2 == a2.Length)
        break:
    }
  return i;
}

Взглянем на базовую реализацию этого алгоритма. Если оба входных множества пустые, то, очевидно, мы возвращаем 0. Далее мы запускаем бесконечный цикл, в котором в случае соответствия мы увеличиваем результат на 1 и проверяем, нужно ли завершить цикл. Вместо бесконечного цикла можно было бы использовать оператор for и указать условие окончания цикла в нём. Но это означало бы лишнюю работу. В реализации, которую вы видите на слайде, в первой ветке мы имеем `if (a1[i1] < a2[i2]), после чего происходит увеличение `i1 на 1, и нам остаётся только проверить `i1. Аналогично во второй ветке нам нужно только проверить `i2. Оба значения нужно проверять только в третьей ветке. Если бы эта проверка была в начале цикла, то мы выполняли бы лишнюю работу.

Попытаемся улучшить эту реализацию. В данный момент её алгоритмическая сложность линейна, с зависимостью от двух входных аргументов. В машинном обучении достаточно часто приходится находить пересечение множеств, очень сильно отличающихся друг от друга по размеру или по статистике. Например, у вас есть длинный входной вектор и короткий вектор признаков (feature vector), относительно которого осуществляется проверка. В нашем коде в `a1 может быть миллион записей, а в `a2 — тысяча. В этом случае мы не готовы будем пройти миллион шагов для выполнения этого алгоритма. Наибольшая нагрузка здесь будет на следующую строку кода: `if (++i1 == a1.length) break. Непосредственно перед этим происходит сравнение, а затем в этой строке — приращение значения; это, в сущности, является линейным поиском. Мы перебираем длинный вектор в поисках элементов короткого. В худшем случае мы будем осуществлять множество таких поисков, медленно продвигаясь по вектору.

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

int Intersect(double[] a1, double[] a2, double[] t) {
  int i1 = 0, i = 0;
  for (; i1 != a1.Length; ++i1) {
    auto m = Bsearch(a2, a1[i1]);
    if (m == a2.Length) continue;
    --m;
    if (!(a2[m] < a1[i1]))
      t[i++] = a1[i1];
  }
  return i;
}

Код выше — реализация нашего алгоритма с бинарным поиском. Она оказывается не слишком эффективной. Наихудшая ситуация здесь будет тогда, когда бинарный поиск будет каждый раз давать сбой. Она будет возникать в некоторых достаточно важных сценариях — например, при идентичных элементах множества. Здесь бинарный поиск окажется медленнее, чем классический линейный. Как сделать так, чтобы алгоритм одинаково успешно работал на идентичных и отличающихся данных? Проверять все данные будет слишком затратно по ресурсам. Оговорюсь, что речь идёт не о полностью идентичных данных, а об очень похожих, с похожей статистикой, размеры также могут отличаться. Можно проверять следующие несколько элементов. Очевидным решением является сокращение области поиска. Когда мы выполняем бинарный поиск, то, найдя некоторый элемент, нас уже не интересует элементы меньше него, поскольку второй вектор также отсортирован. Таким образом мы можем каждый раз сокращать нашу область поиска, отбрасывая все элементы меньше от найденного элемента.

int Intersect(double[] a1, double[] a2, double[] t) {
  int i1 = 0, i2 = 0, i = 0;
  for (; i1 != a1.Length; ++i1) {
    auto m = Bsearch(a2, i2, a2.Length, a1[i1]);
    if (m == i2) continue;
    if (!(a2[m - 1] < a1[i1]))
      t[i++] = a1[i1];
    i2 = m + 1;
  }
  return i;
}

Вот реализация этого подхода. Вы видите, что бинарный поиск мы осуществляем каждый раз по части исходного массива, начинающейся с `i2 и заканчивающейся `a2.length. Поскольку `i2 с каждым поиском будет увеличиваться, область поиска будет сокращаться.

Следующая оптимизация, которую я хотел бы здесь реализовать, связана с алгоритмом галопирующего поиска (Galloping Search). В сущности, это бинарный поиск с другим шагом. В случае с бинарным поиском мы начинаем каждый раз с середины — но давайте задумаемся, когда мы ищем имя в телефонной книге, мы же не открываем её в самой середине? Если фамилия человека начинается, скажем, на «Б», мы откроем книгу ближе к началу. Этот принцип и реализуется в галопирующем поиске: мы начинаем обход данных в направлении по возрастанию с шагом, экспоненциально возрастающем после каждой проверки: сначала 1, затем 2, затем 4. Это даёт нам хорошую алгоритмическую сложность. Если бы шаг рос линейно, сложность была бы квадратичной. Когда мы «перескакиваем» искомый элемент, мы выполняем обычный бинарный поиск по оставшемуся отрезку, который будет уже небольшим и на время выполнения алгоритма существенно влиять не будет. Таким образом, мы сочетаем все преимущества обоих подходов. Реализация такого алгоритма:

int GBsearch(double[] a, int i, int j, double v) {
  for (int step = 1;; step *= 2) {
    if (i >= j) break;
    if (a[i] > v) break;
    if (i + step >= j)
      return Bsearch(a, i + 1, J, v);
    if (a[i + step] > v)
      return Bsearch(a, i + 1, i + step, v);
    i += step + 1;
  }
  return i;
}

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

Работа над темами, которые мы сейчас обсуждаем, на практике сегодня имеет достаточно кустарную форму. На практике у нас чаще всего будет несколько множеств, а не только два, и по этой теме написано достаточно много работ. Классический алгоритм здесь — это SVS, в котором мы группируем множества, берём два наименьших и выбираем наиболее короткий в качестве кандидата. По ссылке можно найти неплохой обзор по этой теме. Проблемы, связанные с пересечением множеств, скалярным произведением разреженных векторов, сортировкой слиянием, любыми формами сравнения с образом со временем оказываются всё более и более интересными. Алгоритм, который я вам показал, зарекомендовал себя как весьма полезный. Cпасибо за внимание.

Андрей Александреску на DotNext 2018 Moscow не приедет, но зато там будут Джеффри Рихтер, Грег Янг, Павел Йосифович и другие. Имена спикеров и темы докладов можно посмотреть здесь, а билеты — здесь. Присоединяйтесь!

Автор: olegchir

Источник