[Перевод] Когда не стоит пользоваться алгоритмами STL. Пример с множествами
Товарищи, добрый вечер!
Вы так здорово разобрали у нас первый тираж книги «С++17 STL. Стандартная библиотека шаблонов» и продолжаете разбирать второй, что мы наконец-то решили изложить здесь и альтернативную точку зрения. Автор сегодняшней статьи — Иван Чукич (Ivan Čukić), перу которого также принадлежит книга «Functional Programming in C++», которая готовится к выходу в издательстве «Manning». Предлагаем оценить его скептические мысли, код и выкладки
Преамбула
Хотел назвать этот пост «О порочности STL-алгоритмов», чтобы проверить собственные навыки по провоцированию кликов. Но потом решил, что лучше написать статью для целевой аудитории, а не писать такой пост, куда слетятся желающие поспорить о моих вопиющих тезисах.
Таким образом, могу предположить, что вы интересуетесь алгоритмами, их сложностью и хотите писать максимально совершенный код.
Алгоритмы
В современном профессиональном сообществе C++шников часто советуют: чтобы ваша программа получилась безопаснее, быстрее, выразительнее, т.д. — пользуйтесь алгоритмами из стандартной библиотеки. Я также стараюсь популяризовать этот совет в моих книгах, выступлениях, на семинарах… везде, где есть подходящая аудитория.
Конечно, совершенно верно, что, если нас тянет написать цикл for для решения стоящей перед нами задачи, сначала нужно подумать, а не подходят ли для этого уже имеющиеся алгоритмы стандартной библиотеки (или boost), а не действовать вслепую.
Нам все равно нужно знать, как реализуются эти алгоритмы, какие требования и гарантии с ними связаны, какова их пространственная и временная сложность.
Обычно, если мы сталкиваемся с задачей, которая в точности соответствует требованиям STL-алгоритма, и его можно применить напрямую, именно этот алгоритм и будет наиболее эффективным решением.
Проблема может возникнуть, если перед применением алгоритма нам требуется каким-либо образом подготовить данные.
Пересечение множеств
Допустим, мы пишем для C++ разработчиков инструмент, который давал бы подсказки о замене вариантов захвата по умолчанию (речь о [=]и [&]) в лямбда-выражениях, причем, явно выводил бы список захваченных переменных.
std::partition(begin(elements), end(elements),
[=] (auto element) {
^~~ - неявность - это неприкольно, заменяем на [threshold]
return element > threshold;
});
При синтаксическом разборе файла нам понадобится коллекция, в которой хранились бы переменные из текущей и соседних областей видимости. Как только же нам встретится лямбда-выражение с захватом по умолчанию, нужно будет посмотреть, какие переменные там используются.
В итоге имеем два множества: в одном будут переменные из окружающих областей видимости, а в другом — переменные, используемые в теле лямбда-выражения.
Список вариантов захвата, которые мы собираемся предлагать на замену, должен быть пересечением двух этих множеств (лямбда-выражения могут использовать глобальные переменные, которые не требуется захватывать, и не все переменные из окружающих областей видимости будут использоваться в лямбда-выражении).
А, если нам требуется пересечение, то можно использовать алгоритм std::set_intersection.
Этот алгоритм довольно красив в своей простоте. Он принимает две отсортированные коллекции и параллельно проходит их из начала в конец:
- Если актуальный элемент в первой коллекции равен актуальному элементу во второй коллекции, он добавляется к результату, который алгоритм просто перемещает к следующему элементу в обоих коллекциях;
- Если актуальный элемент в первой коллекции меньше актуального элемента во второй коллекции, то алгоритм просто пропускает актуальный элемент в первой коллекции;
- Если актуальный элемент в первой коллекции больше актуального элемента во второй коллекции, то алгоритм просто пропускает актуальный элемент во второй коллекции;
12351351345
В каждой итерации как минимум один элемент (из первой или из второй входной коллекции) пропускается — следовательно, сложность алгоритма будет линейной — O(m + n), где m — это число элементов в первой коллекции, а n — число элементов во второй коллекции.
Просто и эффективно. До тех пор, пока входные коллекции отсортированы.
Сортировка
Вот проблема: что делать, если коллекции заранее не отсортированы?
В предыдущем примере было бы разумно хранить переменные из окружающих областей видимости в стекоподобной структуре, куда парсер мог бы попросту добавлять новые элементы, входя в новую область видимости, и удалять переменные текущей области видимости, как только покидает ее.
Таким образом, переменные не будут сортироваться по имени, и мы не сможем напрямую использовать std::set_intersection для операций над ними. Аналогично, если отслеживать переменные в теле лямбда-выражения, то мы, скорее всего, тоже не сможем сохранить их в отсортированном виде.
Поскольку std::set_intersection работает только с отсортированными коллекциями, во многих проектах встречается такой принцип: сначала сортируем коллекции, а затем вызываем алгоритм std::set_intersection.
Если забыть о том, что сортировка стека переменных в нашем примере совершенно девальвирует весь прок определенного нами стека, алгоритм пересечения для несортированных коллекций будет выглядеть примерно так:
template
auto unordered_intersection_1(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt dest)
{
std::sort(first1, last1);
std::sort(first2, last2);
return std::set_intersection(first1, last1, first2, last2, dest);
}
Какова сложность всего этого алгоритма?
На сортировку уходит квазилинейное время, поэтому общая сложность данного подхода равна O(n log n + m log m + n + m).
Сортируем меньшую
Можно ли обойтись без сортировки?
Если обе коллекции не отсортированы, то нам придется обойти вторую коллекцию по поводу каждого элемента из первой — чтобы решить, нужно ли включать его в результирующее множество. Хотя, такой подход довольно распространен в реальных проектах, он еще хуже предыдущего — его сложность равна O(n * m).
Вместо того, чтобы сортировать все подряд, либо не сортировать ничего, вспомним дзен и выберем Третий Путь — отсортируем только одну коллекцию.
Если сортируется всего одна коллекция, то все значения из несортированной мы можем перебрать одно за другим и для каждого значения проверить, есть ли оно в отсортированной коллекции. Для этого применим двоичный поиск.
В таком случае временная сложность будет равна O(n log n) для сортировки первой коллекции и O (m log n) для перебора и проверки. Общая сложность составит O((n + m) log n).
Если бы мы решили отсортировать вторую коллекцию, а не первую, то сложность была бы O((n + m) log m).
Чтобы добиться максимальной эффективности, мы всегда сортируем ту коллекцию, в которой меньше элементов, добиваясь таким образом, чтобы итоговая сложность нашего алгоритма была((m + n) log (min(m, n)).
Реализация будет выглядеть так:
template
auto unordered_intersection_2(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt dest)
{
const auto size1 = std::distance(first1, last1);
const auto size2 = std::distance(first2, last2);
if (size1 > size2) {
unordered_intersection_2(first2, last2, first1, last1, dest);
return;
}
std::sort(first1, last1);
return std::copy_if(first2, last2, dest,
[&] (auto&& value) {
return std::binary_search(first1, last1, FWD(value));
});
}
В нашем примере со списками захвата в лямбда-выражениях сортировке обычно подвергается коллекция переменных, присутствующих в лямбда-выражении, поскольку она, скорее всего, будет меньше, чем коллекция всех переменных из всех окружающих областей видимости.
Хеширование
Последний вариант — построить std::unordered_set (реализация неупорядоченного множества на основе хеша) из меньшей коллекции, а не сортировать ее. В таком случае сложность операций поиска составит в среднем O(1), но на сборку std::unordered_set понадобится время. Сложность построения может составить от O(n) до O(n*n), а это — потенциальная проблема.
template
void unordered_intersection_3(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt dest)
{
const auto size1 = std::distance(first1, last1);
const auto size2 = std::distance(first2, last2);
if (size1 > size2) {
unordered_intersection_3(first2, last2, first1, last1, dest);
return;
}
std::unordered_set test_set(first1, last1);
return std::copy_if(first2, last2, dest,
[&] (auto&& value) {
return test_set.count(FWD(value));
});
}
Подход с хешированием полностью выигрывает в случае, когда требуется вычислить пересечения нескольких множеств с единственным заранее определенным небольшим множеством. То есть, имеем множество A, множества B₁, B₂… и хотим вычислить A ∩ B₁, A ∩ B₂…
В данном случае можно игнорировать сложность конструкции std::unordered_set, и сложность вычисления каждого пересечения будет линейной — O(m), где m — число элементов во второй коллекции.
Контроль
Конечно, всегда полезно проверять сложность алгоритма, но в подобных случаях также разумно проверять различные подходы при помощи контрольных точек. Особенно при выборе из двух последних вариантов, где мы сравниваем двоичный поиск и множества на основе хешей.
Моя простейшая проверка показала, что первый вариант, где приходится сортировать обе коллекции — всегда самый медленный.
Сортировка меньшей коллекции немного выигрывает у std::unordered_set, но не особенно.
И второй, и третий подходы чуть быстрее первого в случае, когда в обеих коллекциях равное количество элементов, и значительно быстрее (до шести раз), когда количество элементов в одной коллекции примерно в 1000 раз больше, чем во второй.
