?

Log in

No account? Create an account

О глобальном потеплении - Общество дровосеков Бердичева по изучению Мишны

Oct. 3rd, 2016

05:52 pm - О глобальном потеплении

Previous Entry Share Next Entry

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

Tags:

Comments:

[User Picture]
From:juan_gandhi
Date:October 4th, 2016 01:00 am (UTC)
(Link)
Да по-моему, у населения идея, что множества не являются списками, вызывает какой-то ступор.

Сегодня в одном месте добавил камент, что надо пофиксить - поиск столбца по имени ведется линейно.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 01:10 am (UTC)
(Link)
Да тут даже знать не надо бы было, что чем является, если бы в лего-наборе был кирпичик нужной формы. А его нет, и кое-какому контингенту лень его составить, и они пользуются дурацкой затычкой, потому что вот она готовая, да и умность в ней с виду имеется. Итераторы, панимаешь.
Ну чё, на одном тесте было 672 минуты, после фикса стало 366 секунд.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:October 4th, 2016 01:31 am (UTC)
(Link)
> if (std::find_first_of(set1.begin(), set1.end(), set2.begin(), set2.end()) == set1.end())

Проще? Чур меня, чур. И я на этом супе программировал 10+ лет и считал, что так и надо.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 01:41 am (UTC)
(Link)
Проще, потому что меньше клавиш на клавиатуре давить надо, и меньше думать надо, знай себе из справочника копируй.


(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:October 4th, 2016 02:13 am (UTC)
(Link)
Прелестно, да.
(Reply) (Thread)
[User Picture]
From:yurikhan
Date:October 4th, 2016 04:18 am (UTC)
(Link)

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

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, но прерывающий цикл сразу после первого совпадения.

(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 04:57 am (UTC)
(Link)
Ох, не родился еще такой оптимизатор, который сумеет генерить из этого код, прерывающий цикл после первой вставки.

А так-то да, всё красиво, и линейно, и самодеятельного кода не надо...
(Reply) (Parent) (Thread)
[User Picture]
From:yurikhan
Date:October 4th, 2016 05:35 am (UTC)
(Link)

Ну вот где-то я видел утверждение, что 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’ов — только эквивалентность, порождённую тем слабым порядком, которым множества отсортированы. И, в общем случае, нет способа сделать проверку равенства, не потеряв линейную асимптотику алгоритма, если эта эквивалентность существенно отличается от равенства.

(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 05:46 am (UTC)
(Link)
Строго говоря, это не извращение; теоретически именно так и надо. :) Явный код чисто boilerplate, а алгоритм спрятан в стандартную функцию. Тут уже больше надежды на оптимизатор; даже интересно, насколько будет это решение отличаться по производительности от очевидного (тж. см. поправку в комментариях).

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

(Reply) (Parent) (Thread)
[User Picture]
From:yurikhan
Date:October 4th, 2016 07:02 am (UTC)
(Link)
Теоретически так и надо, но на практике можно поспорить с сеньором о стоимости исключений на целевой платформе.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 07:27 am (UTC)
(Link)
Вот я и говорю: исключение, которое ловится локально, при небольшом умении может быть оптимизировано в простую передачу управления.
Это, по крайней мере, попроще будет, чем автоматически сообразить, что если единственное использование массива - проверка на empty, то его создавать не надо.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:October 4th, 2016 05:25 am (UTC)
(Link)
И ведь никто не заставляет использовать параметризованные алгоритмы по любому поводу.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 05:32 am (UTC)
(Link)
Казалось бы, логично, что если в ящике с принадлежностями есть шурупы, то должен быть и инструмент для их использования. Если не быть стопроцентно уверенным, что для шурупов нужна а) отвертка, и б) с подходящим шлицем, то можно по неопытности решить, что шурупы нужно забивать молотком, раз вот он, на самом видном месте. Вот и решают.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:October 4th, 2016 05:51 am (UTC)
(Link)
C, C with classes, C++ without templates, and only then C++ with templates. Вот не надо слишком быстро прогрессировать новоиспечённым программистам. Повторяя эволюцию языка они будут привычны работать руками, не только головой. :)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 06:01 am (UTC)
(Link)
С другой стороны, дурная голова рукам покоя не дает, и в сочетании с привычкой работать руками это может привести к худшим последствиям. Идеального метода обучения программированию пока не придумали.
(Reply) (Parent) (Thread)
[User Picture]
From:gineer
Date:October 4th, 2016 05:26 am (UTC)
(Link)
Вот был гуглевский поисковик по коду... сейчас вроде бы тоже какой-то есть.

Ввести туда эту строчку, и попробовать оценить -- а реально, сколько таких конструкций используется.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 4th, 2016 05:34 am (UTC)
(Link)
Увы, по одной строчке не понять, в какой именно структуре данных ищут.
(Reply) (Parent) (Thread)
[User Picture]
From:stumari
Date:October 4th, 2016 07:08 pm (UTC)
(Link)
а я то думал, вы про Челси Клинтон, которая полетала на самолете на конференцию по ГП, вмето того, чтобы по телефону обсудить :)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 5th, 2016 01:30 am (UTC)
(Link)
lj-cut text="C++" как бы намекает, что не про неё.
(Reply) (Parent) (Thread)
[User Picture]
From:stumari
Date:October 5th, 2016 03:52 am (UTC)
(Link)
в новом дизайне, в котором это у меня было показано, "С++" видно не было, сейчас специально проверил (видно только в tool-tip-e, если мышку подвести к кружку со стрелочкой, означающей этот кат, но не нажать)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 5th, 2016 03:54 am (UTC)
(Link)
Ну кто ж заставляет такой дизайн иметь? В моем старом дизайне, в котором я всё читаю (.../friends), всё видно явно.
(Reply) (Parent) (Thread)
[User Picture]
From:freeborn
Date:October 5th, 2016 01:26 am (UTC)
(Link)
Any_of отменили разве? 11 год вроде давно был
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 5th, 2016 01:29 am (UTC)
(Link)
Много ли в нём корысти? Ведь тоже квадратично получится.
(Reply) (Parent) (Thread)
[User Picture]
From:freeborn
Date:October 5th, 2016 01:37 am (UTC)
(Link)
Для unordered_set линейно
Для ордеред н лог н, ну тогда действительно лучше руками писать.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 5th, 2016 01:55 am (UTC)
(Link)
Действительно, что это я. А для ordered можно даже логарифмически написать, пользуясь lower_bound вместо инкрементов.
(Reply) (Parent) (Thread)
[User Picture]
From:freeborn
Date:October 5th, 2016 01:58 am (UTC)
(Link)
Что то я не уверен в логарифмичности, если, к примеру, множества четных и нечетных чисел сравнивать
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 5th, 2016 02:05 am (UTC)
(Link)
Да. кроме вырожденных случаев. Но какая именно будет на самом деле сложность "в среднем", O(log N) или больше, не столь важно, лишь бы сублинейно было.
(Reply) (Parent) (Thread)
[User Picture]
From:freeborn
Date:October 5th, 2016 02:09 am (UTC)
(Link)
Я привык худший случай учитывать, похоже n log n получится - а инкрементами линейно всегда
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 5th, 2016 02:23 am (UTC)
(Link)
КМК, если бы в стандарте была специализация lower_bound для std::set с указанием места начала поиска, то могло бы быть и быстрее: можно избежать прохода по кускам дерева, в которых точно не будет желаемого элемента (напр., если мы начинаем с левого узла, родитель которого тоже левый, а прародитель - всё ещё меньше искомого значения, то правое сиблинг-поддерево можно не анализировать).
(Reply) (Parent) (Thread)