Главная » Хабрахабр » [Перевод] Когда не стоит пользоваться алгоритмами 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 Интересное!

Как изучение критической уязвимости DHCP в Windows 10 привело к обнаружению еще двух ошибок безопасности

Изображение: Unsplash А в некоторых случаях таких новых уязвимостей оказывается больше одной. Как было описано в предыдущей статье про CVE-2019-0726, иногда поиск деталей об уже известной уязвимости приводит к обнаружению новой уязвимости. Как всегда происходит при поиске уязвимостей, даже если ...

Быстрорастворимое проектирование

Люди учатся архитектуре по старым книжкам, которые писались для Java. Книжки хорошие, но дают решение задач того времени инструментами того времени. Время поменялось, C# уже больше похож на лайтовую Scala, чем Java, а новых хороших книжек мало. Увидим обзор типовых ...