О глобальном потеплении

[spamsink]

Интересно, сколько мегаватт-часов электроэнергии было потрачено впустую, и ещё будет потрачено из-за того, что гораздо проще написать
if (std::find_first_of(set1.begin(), set1.end(), set2.begin(), set2.end()) == set1.end())
вместо того, чтобы написать предикатик isEmptyIntersection из 5 строк, работающий линейно, а не квадратично. А всё из-за [expletive omitted] Степанова, не предусмотревшего в STL нормальные методы работы с множествами. Чтоб ему в аду черти code reviews делали!

Comments

[juan-gandhi.livejournal.com]

Да по-моему, у населения идея, что множества не являются списками, вызывает какой-то ступор.

Сегодня в одном месте добавил камент, что надо пофиксить - поиск столбца по имени ведется линейно.

[spamsink]

Да тут даже знать не надо бы было, что чем является, если бы в лего-наборе был кирпичик нужной формы. А его нет, и кое-какому контингенту лень его составить, и они пользуются дурацкой затычкой, потому что вот она готовая, да и умность в ней с виду имеется. Итераторы, панимаешь.
Ну чё, на одном тесте было 672 минуты, после фикса стало 366 секунд.

[yatur.livejournal.com]

> if (std::find_first_of(set1.begin(), set1.end(), set2.begin(), set2.end()) == set1.end())

Проще? Чур меня, чур. И я на этом супе программировал 10+ лет и считал, что так и надо.

[spamsink]

Проще, потому что меньше клавиш на клавиатуре давить надо, и меньше думать надо, знай себе из справочника копируй.

[yigal_s]

Прелестно, да.

[yurikhan]

Ну вот более-менее код, над которым ревьюер не будет смеяться:

std::vector<T> intersection;
std::set_intersection(set1.begin(), set1.end(),
                      set2.begin(), set2.end(),
                      std::back_inserter(intersection));
if (intersection.empty()) …

(Каждый раз, когда такое пишу/читаю, представляю себе разложение выражения c = a + b; в последовательность mov ax, [a]; add ax, [b]; mov [c], ax.)

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

[spamsink]

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

А так-то да, всё красиво, и линейно, и самодеятельного кода не надо...

[yurikhan]

Ну вот где-то я видел утверждение, что STL — не набор примитивов на все случаи жизни, а методология. Не хватает алгоритма — напиши по образу и подобию.

Из области извращений, можно ещё так сделать:

struct FoundMatch {};
class AnyAcceptor {
public:
    AnyAcceptor& operator++() { return *this; }
    AnyAcceptor& operator++(int) { return *this; }
    AnyAcceptor& operator*() { return *this; }
    template <typename AnyT>
    void operator=(const AnyT&) { throw FoundMatch(); }
};

template <typename SortedRange1T, typename SortedRange2T>
bool intersects(const SortedRange1T& set1, const SortedRange2T& set2)
{
    try {
        std::set_intersection(std::begin(set1), std::end(set1),
                              std::begin(set2), std::end(set2),
                              AnyAcceptor());
        return false;
    }
    catch (FoundMatch)
    {
        return true;
    }
}

Кстати, есть одна gotcha: решение на find_first_of проверяет равенство, а решения, линейные за счёт сортированности set’ов — только эквивалентность, порождённую тем слабым порядком, которым множества отсортированы. И, в общем случае, нет способа сделать проверку равенства, не потеряв линейную асимптотику алгоритма, если эта эквивалентность существенно отличается от равенства.

[spamsink]

Строго говоря, это не извращение; теоретически именно так и надо. :) Явный код чисто boilerplate, а алгоритм спрятан в стандартную функцию. Тут уже больше надежды на оптимизатор; даже интересно, насколько будет это решение отличаться по производительности от очевидного (тж. см. поправку в комментариях).

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

[yurikhan]

Теоретически так и надо, но на практике можно поспорить с сеньором о стоимости исключений на целевой платформе.

[spamsink]

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

[fatoff.livejournal.com]

И ведь никто не заставляет использовать параметризованные алгоритмы по любому поводу.

[spamsink]

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

[fatoff.livejournal.com]

C, C with classes, C++ without templates, and only then C++ with templates. Вот не надо слишком быстро прогрессировать новоиспечённым программистам. Повторяя эволюцию языка они будут привычны работать руками, не только головой. :)

[spamsink]

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

[gineer.livejournal.com]

Вот был гуглевский поисковик по коду... сейчас вроде бы тоже какой-то есть.

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

[spamsink]

Увы, по одной строчке не понять, в какой именно структуре данных ищут.

[stumari.livejournal.com]

а я то думал, вы про Челси Клинтон, которая полетала на самолете на конференцию по ГП, вмето того, чтобы по телефону обсудить :)

[spamsink]

lj-cut text="C++" как бы намекает, что не про неё.

[stumari.livejournal.com]

в новом дизайне, в котором это у меня было показано, "С++" видно не было, сейчас специально проверил (видно только в tool-tip-e, если мышку подвести к кружку со стрелочкой, означающей этот кат, но не нажать)

[spamsink]

Ну кто ж заставляет такой дизайн иметь? В моем старом дизайне, в котором я всё читаю (.../friends), всё видно явно.

[freeborn.livejournal.com]

Any_of отменили разве? 11 год вроде давно был

[spamsink]

Много ли в нём корысти? Ведь тоже квадратично получится.

[freeborn.livejournal.com]

Для unordered_set линейно
Для ордеред н лог н, ну тогда действительно лучше руками писать.

[spamsink]

Действительно, что это я. А для ordered можно даже логарифмически написать, пользуясь lower_bound вместо инкрементов.

[freeborn.livejournal.com]

Что то я не уверен в логарифмичности, если, к примеру, множества четных и нечетных чисел сравнивать

[spamsink]

Да. кроме вырожденных случаев. Но какая именно будет на самом деле сложность "в среднем", O(log N) или больше, не столь важно, лишь бы сублинейно было.

[freeborn.livejournal.com]

Я привык худший случай учитывать, похоже n log n получится - а инкрементами линейно всегда

[spamsink]

КМК, если бы в стандарте была специализация lower_bound для std::set с указанием места начала поиска, то могло бы быть и быстрее: можно избежать прохода по кускам дерева, в которых точно не будет желаемого элемента (напр., если мы начинаем с левого узла, родитель которого тоже левый, а прародитель - всё ещё меньше искомого значения, то правое сиблинг-поддерево можно не анализировать).