Когда не стоит пользоваться алгоритмами 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.

Этот алгоритм довольно красив в своей простоте. Он принимает две отсортированные коллекции и параллельно проходит их из начала в конец:

• Если актуальный элемент в первой коллекции равен актуальному элементу во второй коллекции, он добавляется к результату, который алгоритм просто перемещает к следующему элементу в обоих коллекциях;
• Если актуальный элемент в первой коллекции меньше актуального элемента во второй коллекции, то алгоритм просто пропускает актуальный элемент в первой коллекции;
• Если актуальный элемент в первой коллекции больше актуального элемента во второй коллекции, то алгоритм просто пропускает актуальный элемент во второй коллекции;

В каждой итерации как минимум один элемент (из первой или из второй входной коллекции) пропускается – следовательно, сложность алгоритма будет линейной – O(m + n), где m – это число элементов в первой коллекции, а n – число элементов во второй коллекции.

Просто и эффективно. До тех пор, пока входные коллекции отсортированы.

Сортировка

Вот проблема: что делать, если коллекции заранее не отсортированы?

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

Таким образом, переменные не будут сортироваться по имени, и мы не сможем напрямую использовать std::set_intersection для операций над ними. Аналогично, если отслеживать переменные в теле лямбда-выражения, то мы, скорее всего, тоже не сможем сохранить их в отсортированном виде.

Поскольку std::set_intersection работает только с отсортированными коллекциями, во многих проектах встречается такой принцип: сначала сортируем коллекции, а затем вызываем алгоритм std::set_intersection.

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

template <typename InputIt1, typename InputIt2, typename OutputIt>
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 <typename InputIt1, typename InputIt2, typename OutputIt>
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 <typename InputIt1, typename InputIt2, typename OutputIt>
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<int> 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 раз больше, чем во второй.