Главная » Хабрахабр » [Перевод] Когда не стоит пользоваться алгоритмами STL. Пример с множествами

[Перевод] Когда не стоит пользоваться алгоритмами STL. Пример с множествами

Товарищи, добрый вечер!

Стандартная библиотека шаблонов" и продолжаете разбирать второй, что мы наконец-то решили изложить здесь и альтернативную точку зрения. Вы так здорово разобрали у нас первый тираж книги "С++17 STL. Предлагаем оценить его скептические мысли, код и выкладки
Автор сегодняшней статьи — Иван Чукич (Ivan Čukić), перу которого также принадлежит книга "Functional Programming in C++", которая готовится к выходу в издательстве «Manning».

Преамбула

Но потом решил, что лучше написать статью для целевой аудитории, а не писать такой пост, куда слетятся желающие поспорить о моих вопиющих тезисах. Хотел назвать этот пост “О порочности STL-алгоритмов”, чтобы проверить собственные навыки по провоцированию кликов.

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

Алгоритмы

– пользуйтесь алгоритмами из стандартной библиотеки. В современном профессиональном сообществе C++шников часто советуют: чтобы ваша программа получилась безопаснее, быстрее, выразительнее, т.д. Я также стараюсь популяризовать этот совет в моих книгах, выступлениях, на семинарах… везде, где есть подходящая аудитория.

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

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

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

Проблема может возникнуть, если перед применением алгоритма нам требуется каким-либо образом подготовить данные.

Пересечение множеств

Допустим, мы пишем для C++ разработчиков инструмент, который давал бы подсказки о замене вариантов захвата по умолчанию (речь о [=]и [&]) в лямбда-выражениях, причем, явно выводил бы список захваченных переменных.

std::partition(begin(elements), end(elements), [=] (auto element) );

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

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

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

А, если нам требуется пересечение, то можно использовать алгоритм std::set_intersection.

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

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

12351351345

В каждой итерации как минимум один элемент (из первой или из второй входной коллекции) пропускается – следовательно, сложность алгоритма будет линейной – 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 + m) log n). В таком случае временная сложность будет равна O(n log n) для сортировки первой коллекции и O (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)); });
}

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

Хеширование

В таком случае сложность операций поиска составит в среднем O(1), но на сборку std::unordered_set понадобится время. Последний вариант — построить 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 раз больше, чем во второй.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Проект Keystone: доверенная среда для запуска приложений на базе RISC-V

Команда исследователей из MIT и Калифорнийского университета в Беркли при поддержке Facebook, Google, Microsoft и других ИТ-гигантов представила проект Keystone. Это open source компонент, позволяющий организовать доверенную среду для запуска программ (trusted execution environment, TEE) на базе архитектуры RISC-V. Далее ...

[Перевод] Руководство по Node.js, часть 4: npm, файлы package.json и package-lock.json

Сегодня мы публикуем четвёртую часть перевода руководства по Node.js. В этом материале мы начнём разговор об npm а также рассмотрим особенности файлов package.json и package-lock.json. [Советуем почитать] Другие части цикла Основы npm Npm (node package manager) — это менеджер пакетов ...