1. C++ / Говнокод #24680

    +3

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    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, 28 Августа 2018

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

    • #so #algorithms #big-o-is-useless
      Ответить
      • O(n1*n2*log(n2))?
        Ответить
      • З.Ы. Забавно, что автор умудрился сделать асимптотику хуже чем у линейного поиска...
        Ответить
        • А, нет, просто O(n1*n2). std::binary_search всё-таки может фоллбекнуться на линейный поиск.
          Ответить
          • Насколько я понимаю, это не фолбек. Там тот же самый бинарный поиск, просто итераторы увеличиваются инкрементом, так что O(N) инкрементов доминирует логарифм сравнений.
            Ответить
            • > тот же самый бинарный поиск
              Да, и правда distance + advance. А логарифма не будет, получается один проход на distance и второй из пачки advance'ов. Т.е. просто O(n).
              Ответить
              • З.Ы. И походу линейный поиск отработал бы быстрее.
                Ответить
    • Разве binary_search любой итератор принимает, а не только рандом акцесс?
      Ответить
    • Вот к чему плюсоблядские абстракции приводят.
      Таким товарищам надо дать обычную сишку и сказать чтоб реализовали на ней аналог std::set через красно-черное дерево с итератором и std::binary_search работающий через итератор. Тогда такой хуйни не будет.
      Ответить
      • > Тогда такой хуйни не будет.

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

          Коричнево-розовое
          Ответить
          • Клён-раскудрявый-дерево.
            Ответить
          • Внезапно: коричнево-розовая древесина у палисандра — деревьев рода дальбергия.
            Ответить
        • > Разумеется не будет. Он тебя сразу нахер пошлёт и пойдёт юзать линейный поиск с двумя массивами.

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

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


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

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

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

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

                Впрочем в яве Vector и List есть. Но означают они совсем другое.
                Ответить
                • Он про "PHP" с его универсальным "массивом".
                  Ответить
                  • Кресты не такой уж и плохой язык для обучения.

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

                        Я когда-то одному студенту делал лабу на ассемблере под дос на турбопацкале для вуза (он при этом был уже работающим программистом на шарпе) и там в коде я сделал как раз такую "функцию" которая указатель на код принимает и объяснил что это callback. Он еще такой "а че, в ассемблере бывает такое?"
                        Ответить
                        • турбопацкале турбоассемблере
                          Ответить
                          • Турбоджава
                            Ответить
                          • В официальной документации по Трубоассемблеру есть глава «Creating object-oriented programs». В нём даже есть встроенные макросы для работы с таблицей виртуальных методов, хотя всё это не особенно и нужно.

                            А вообще интересно посмотреть, как программисты на языках высокого уровня уходят от реальности в абстрактный мир. Они забывают, что их программы в итоге компилируются в машинный код и в итоге процессор манипулирует указателями.
                            Ответить
                        • > массив из указателей на функции, принимающие int и возвращающие int
                          std::vector<std::function<int(int)>>
                          Ответить
                          • std::array<std::function<int(int)> *, size>

                            массив указателей же
                            Ответить
                            • Я тут подумал еще, и торжественно заявляю
                              std::array<std::unique_ptr<std::function<int(int)>>, size>
                              Ответить
    • Я минуснул, за пижжонство.
      Роман Кашицын хорошо выучил С++ и теперь тралирует своих малограмотных коллег.
      Ответить
      • Ага, лучше бы "PHP" так знал
        Ответить
      • > хорошо выучил С++

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

        Низя, это UB
        http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0551r1.pdf
        Ответить
        • >> Thou shalt

          Фу, как грубо! Ещё и обращение на «ты».
          Ответить
        • Ай, точно, это ж функция, а не класс *facepalm*

          Ну, неявные преобразования const_iterator <-> iterator тоже, наверное, не сильно соответствуют стандарту, что не мешало (не мешает?) существовать им в stl от visual c++ :)
          Ответить
        • https://youtu.be/hcRlypUPvGI?t=91
          Ответить
    • Дай дураку STL крестяный...
      Ответить
    • 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();
      Ответить
      • Не проще поискать элементы из меньшего множества в большем?
        Ответить
        • согласен
          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;
          Ответить
        • 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;
          }
          Ответить
    • Даже не заметил, что это мой юбилейный, сотый говнокод.
      Ответить
      • > Никто даже не заметил…

        /fxd
        Ответить
        • > Никто даже не заметил…

          Это звучит как "никто кроме меня".
          Даже если взять "никто" в логическом смысле: всем (кроме меня) должно быть абсолютно на это насрать, поэтому удивителен лишь факт, что я сам не сразу заметил.
          Ответить
          • Я сочиняю роман, рома-рома-роман,
            мущина всей моей жизни.
            Ответить
            • Господи, как же ты уныл и предсказуем.
              https://youtu.be/PBi6cu5aTzs?t=27s
              Ответить
              • http://www.lisperati.com/lisplogo_fancy_256.png == https://www.b17.ru/foto/uploaded/upl_1484464006_135067.jpg
                https://youtu.be/oUk8uXYk_6A?t=85

                Гомоиконность!
                Ответить
                • Там в конце функциональщик в адидасах взорвал мозг лиспера теорией категорий.
                  Ответить

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