Кресты / Говнокод #24680 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
#include <set>
#include <algorithm>

bool overlap(const std::set<int>& s1, const std::set<int>& s2)
{
    for( const auto& i : s1) {
        if(std::binary_search(s2.begin(), s2.end(), i))
            return true;
    }
    return false;
}

я зделял

https://stackoverflow.com/a/29421606/1683138
-- https://en.cppreference.com/w/cpp/container/set
iterator Constant BidirectionalIterator

Запостил: roman-kashitsyn roman-kashitsyn, (Updated )

Комментарии (69) RSS

    • ava bormand # Ссылка на оригинал 0 ⇈

      З.Ы. Забавно, что автор умудрился сделать асимптотику хуже чем у линейного поиска...
      Ответить

      • ava bormand # Ссылка на оригинал 0 ⇈

        А, нет, просто O(n1*n2). std::binary_search всё-таки может фоллбекнуться на линейный поиск.
        Ответить

        • ava guest # 0 ⇈

          Насколько я понимаю, это не фолбек. Там тот же самый бинарный поиск, просто итераторы увеличиваются инкрементом, так что O(N) инкрементов доминирует логарифм сравнений.
          Ответить

          • ava bormand # Ссылка на оригинал 0 ⇈

            > тот же самый бинарный поиск
            Да, и правда distance + advance. А логарифма не будет, получается один проход на distance и второй из пачки advance'ов. Т.е. просто O(n).
            Ответить

  • ava guest # 0

    Разве binary_search любой итератор принимает, а не только рандом акцесс?
    Ответить

  • ava j123123 # Ссылка на оригинал 0

    Вот к чему плюсоблядские абстракции приводят.
    Таким товарищам надо дать обычную сишку и сказать чтоб реализовали на ней аналог std::set через красно-черное дерево с итератором и std::binary_search работающий через итератор. Тогда такой хуйни не будет.
    Ответить

    • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

      > Тогда такой хуйни не будет.

      Разумеется не будет. Он тебя сразу нахер пошлёт и пойдёт юзать линейный поиск с двумя массивами.
      Ты сам-то КР-дерево когда последний раз писал?
      Ответить

        • ava guest # 0 ⇈

          Внезапно: коричнево-розовая древесина у палисандра — деревьев рода дальбергия.
          Ответить

      • ava j123123 # Ссылка на оригинал 0 ⇈

        > Разумеется не будет. Он тебя сразу нахер пошлёт и пойдёт юзать линейный поиск с двумя массивами.

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

        Проблема в том, что люди, подобные тому кто этот код на стековерфлоу написал, вообще не понимаю что за хуйню они используют. Для них всякие там std::map, std::set и так далее это просто какое-то волшебное ключевое слово, которое как-то там внутри что-то делает и предоставляет какое-то api.


        > Ты сам-то КР-дерево когда последний раз писал?

        Хрен знает, возможно я его вообще не реализовывал. Но свои реализации всяких структур данных, я иногда пишу по фану. http://govnokod.ru/23275
        Ответить

        • ava j123123 # Ссылка на оригинал 0 ⇈

          http://stolyarov.info/books/programming_intro/about.html

          > Учителям такой категории вообще, судя по всему, всё до лампочки: в C++ используется библиотека STL, а значит, надо рассказать ученикам STL; разумеется, дальше vector'а и list'а обучение никогда не заходит (при этом эти два контейнера, пожалуй, самые бесполезные из всего STL), но самое интересное, что ученики, разумеется, так и не понимают, о чём идёт речь. В самом деле, как можно объяснить разницу между vector и list человеку, который никогда в жизни не видел ни динамических массивов, ни списков и вообще не понимает, что такое указатель? Для такого ученика list отличается от vector тем, что в нём нет удобной операции индексирования (почему её там нет? ну, нам что-то объясняли, но я ничего не понял), так что вообще-то всегда надо использовать vector, ведь он гораздо удобнее. Что? Добавление в начало и в середину? Так оно и для вектора есть, какие проблемы. Ну да, нам говорили, что это «неэффективно», но ведь работает же! Переучить такого ученика практически нереально: попытки заставить его создать односвязный список вручную обречены на провал, ведь есть же list, а тут столько ненужного геморроя! Собственно говоря, всё: если нашему обучаемому дали в руки STL раньше, чем он освоил динамические структуры данных, то знать он их уже не будет никогда; путь в серьёзное программирование ему, таким образом, закрыт.
          Ответить

          • ava guest # 0 ⇈

            Поэтому в качестве учебных языков нужно использовать те, в которых никаких "STL", vector'ов и list'ов нет.
            Ответить

            • ava 3.14159265 # Ссылка на оригинал 0 ⇈

              >нужно использовать те, в которых никаких "STL", vector'ов и list'ов нет.

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

              Впрочем в яве Vector и List есть. Но означают они совсем другое.
              Ответить

                • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                  Кресты не такой уж и плохой язык для обучения.

                  Человек сходу поймёт как жесток мир, может даже бросит программирование навсегда.
                  Ответить

                  • ava bormand # Ссылка на оригинал 0 ⇈

                    Да не, почему-то кресты не пугают начинающих. Видимо весь пиздец можно разглядеть только через пару лет, когда уже поздно.
                    Ответить

                    • ava j123123 # Ссылка на оригинал 0 ⇈

                      Видел ли ты, какой пиздец потом получается от этих начинающих?
                      Я вот видел. Человек, который типа знает C++, который успешно сдает всякие лабы и сессии на этих плюсах и умеет жонглировать этой плюсовой стдлибой, но который нихера не понимает указателей, адресной арифметики. Он например нихрена не напишет вам массив из указателей на функции, принимающие int и возвращающие int. Он вообще даже не поймет что от него хотят. Он не будет знать про то что можно сделать функцию, принимающую указатель на функцию, которая потом по этому указателю что-то делает.

                      Я когда-то одному студенту делал лабу на ассемблере под дос на турбопацкале для вуза (он при этом был уже работающим программистом на шарпе) и там в коде я сделал как раз такую "функцию" которая указатель на код принимает и объяснил что это callback. Он еще такой "а че, в ассемблере бывает такое?"
                      Ответить

  • ava kir_rik # Ссылка на оригинал 0

    Я минуснул, за пижжонство.
    Роман Кашицын хорошо выучил С++ и теперь тралирует своих малограмотных коллег.
    Ответить

    • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

      > хорошо выучил С++

      Наизусть, разумеется, ещё в школе. На ёлке дед мороз заставлял за конфету стандарт по памяти читать.
      Ответить

  • ava Xom94ok # Ссылка на оригинал 0

    А вот щас какой-нибудь умный задрот возьмёт, да и специализирует binary_search для set.
    Ответить

  • ava guest # 0 

    std::set<int> roman;
for (int kashitsyn: s1) roman.insert(kashitsyn);
for (int kashitsyn: s2) roman.insert(kashitsyn);
return roman.size() != s1.size() + s2.size();
    Ответить

    • ava bormand # Ссылка на оригинал 0 ⇈

      Не проще поискать элементы из меньшего множества в большем?
      Ответить

      • ava guest # 0 ⇈

        согласен
        if (s1.size() > s2.size()) {
    for (int roman: s2) {
        auto kashitsyn = std::find(s1.begin(), s1.end(), roman);
        if (kashitsyn != s1.end()) {
            return true;
        }
    }
} else {
    for (int roman: s1) {
        auto kashitsyn = std::find(s2.begin(), s2.end(), roman);
        if (kashitsyn != s2.end()) {
            return true;
        }
    }
}

return false;
        Ответить

      • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

        STL интуитивно прост и понятен
        // https://ideone.com/nawyWP
struct flag {
  bool set = false;
  template <class T> void operator=(const T&) { set = true; }
  flag& operator++() { return *this; }
  flag& operator*()  { return *this; }
};

template <class CLeft, class CRight>
bool intersects(const CLeft& lhs, const CRight& rhs) {
  flag f;
  return std::set_intersection(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), f).set;
}
        Ответить

Добавить комментарий

Я, guest, находясь в здравом уме и твердой памяти, торжественно заявляю:

    А не использовать ли нам bbcode?

    ↑
    8
    ↓