О глобальном потеплении - Ваши рубидии уже у кобальта во ртути — LiveJournal

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

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

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

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

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

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Thread)

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

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)

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

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

(Reply) (Parent) (Thread)

Ну вот где-то я видел утверждение, что 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)

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

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

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

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)

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

(Reply) (Parent) (Thread)