ph_piter Jul 27 2018 at 19:12

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

6 min

12K

Издательский дом «Питер» corporate blogC++*Algorithms*Professional literature*

Translation

+16

Comments 12

hdfan2 Jul 27 2018 at 20:10

Мне кажется, что в оригинале опечатка; в предложении

If the current item in the first collection is the same as the current item in the second collection, it gets added to the result the algorithm just moves on to the next item in both collections

после «to the result» должна быть точка с запятой. Соответственно, перевод становится намного яснее:

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

aamonster Jul 27 2018 at 23:57

Бррр… Вот что бывает, когда в задаче обработки данных берёшь за основу алгоритмы, а не структуры данных.
Сразу бы начал с третьего алгоритма, просто потому, что у нас два set. И про потери времени на построение unordered_set не думал бы, ибо строился бы он по мере получения данных. И уже потом при необходимости подумал про оптимизацию.
А взять два вектора, отсортировать их и слить — это типичное натягивание совы на глобус.

DYefimov Jul 28 2018 at 10:32

Да, после прочтения сложилось такое впечатление, что мысль в статье одна: «знайте с чем вы работаете». Но, разве, это не очевидно?

hdfan2 Jul 28 2018 at 13:32

Знаете, после прочтения хотел задать именно этот вопрос. Но потом подумал, что эта статься направлена на несколько иную аудиторию. Вот у вас (и, надеюсь, у меня) есть опыт, который позволяет сначала задуматься, применим ли в том или ином случае готовый алгоритм, и нет ли более простого/быстрого решения. А вот у недавних студентов, которые только-только изучили какой-нибудь ЯП, в голову вбито: «Не пытайся делать сам, всё равно лучше не сделаешь; используй готовую библиотеку». И дальше получается как в известной поговорке: «Если у тебя есть молоток, то любая проблема кажется гвоздём». Есть STL (или что-то ещё), и любая проблема сразу же решается с её помощью. Есть готовый алгоритм std::set_intersection, которому требуются отсортированные коллекции — значит, сортируем и используем, не раздумывая. Вот на этих-то людей и рассчитана эта статья.

multiprogramm Jul 28 2018 at 10:53

Хм, так причём тут STL? Эдак можно и минимум пытаться с помощью std::sort искать. Виновата не STL и не сортировка, просто в данном случае приоритет отдаётся уже реализованным алгоритмам, а не подходящим для задачи, что есть плохой подход (хотя и не всегда, кстати). По названию статьи подумал, что какой-то стандартный алгоритм над std::set работает хуже, чем велосипед, который будет приведён, хех.

MikailBag Jul 28 2018 at 12:39

Странно, что не упомянули бор. Честнейшая линия. А если серьезно, то подбирать алгоритмы по асимптотике для ограничений вида n<10 плохо. Не удивлюсь, если алгоритм за квадрат окажется самым быстрым.

DaylightIsBurning Jul 28 2018 at 14:16

Заголовок не отображает содержание. Статья иллюстрирует мысль, что использовать STL как реализацию необходимых алгоритмов — хорошо, а сводить необходимые для задачи алгоритмы к имеющимся в STL реализациям — скорее плохо. Не ново, но полезно напомнить.

Antervis Jul 28 2018 at 15:49

разумеется лучше сначала спроектировать эффективный алгоритм (или несколько для поиска оптимального), а потом реализовывать его этапы через «готовые кирпичики», нежели проектировать опираясь на них. Даже в примере Ивана варианты через unordered_set и sort могут работать быстрее/медленнее друг друга в зависимости от стоимостей сравнения/взятия хеша для конкретного типа данных

K010mb0 Jul 29 2018 at 01:33

Аналогичные подходы применяются в базах данных при объединении таблиц (LOOP/MERGE/HASH JOIN). И не важно даже на каком языке реализация.

ProstoUser Jul 30 2018 at 12:58

Вот чего тут не хватает, так это оценки абсолютной величины времени работы алгоритмов.

Если не эффективная реализация «в лоб» работает 0.1 сек, а эффективная 0.01 сек, то какая, в общем, разница, если это «продукт для разработчиков» — в любом случае, время работы меньше времени реакции человека.

В каких-то случаях, безусловно, эта разница будет существенной.

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

Orient Aug 11 2018 at 12:20

В unordered_intersection_2 первый return как-то не согласуется со вторым. Кто знает, может быть std::copy_if возвращает не void, это надо в справочнике ещё лезть смотреть.

Vladimir_Putin Mar 16 2022 at 16:55

Наверное, я поздно пишу, но ваш алгоритм с сортировкой никогда не будет правильно работать. Если на вход подать две множества {0}, {0, 0}, то результатом будет {0, 0}, потому что вы не проверяете, какие данные уже были обработаны. Без дополнительных выделений памяти в такой реализации не обойтись. В стандартном алгоритме, где оба множества отсортированы, вы работаете только с теми данными, которые еще не использовались, это реализовано с помощью движения двух лент в торону. Данные, которые слева от "считывателя" уже не могут повлиять на результат и ответом такого алгоритма будет множество только из одного элемента {0}.