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

    +14

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    template<class Key,class T,class H=Hash<Key>,
        class EQ=equal_to<Key>,class A=allocator<pair<const Key,T> > >
    class hash_map
    {
    public:
        //как map за исключением
        typedef H Hasher;
        typedef EQ key_equal;
        typedef size_t size_type;//из функции Hash видно что size_t нужно, а не int
        typedef Key key_type;
        typedef T mopped_type;
        //делаем объявление
        struct Entry;
        typedef T* iterator;
        typedef const Entry* const_iterator;
        typedef pair<iterator,iterator> equal_r;
    //...
     vector<map<key_type,mopped_type> *> v1;

    Тормозил std::unordered_map. Написал свой.

    Запостил: LispGovno, 09 Июля 2013

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

    • Не тормозит?
      Ответить
      • Тормозит. Оптимизация не удалась.
        .                       LispGovno
        Ответить
        • Использовал вектор как хештаблицу, а мап, как разруливатель колизий
          Ответить
        • >LispGovno
          пароль, забыл, штоле?

          >Использовал вектор как хештаблицу
          Запахло фильтром Блума. Ну написать хорошую мапу - нетривиальная задача, а вот испоганить - запросто.
          Ответить
          • > пароль, забыл, штоле?
            Разлогинило. Да я и рад. Тут куча школьников набежала, мне даже заходить суда не хочется. Я хоть и школьник, но каролевских питушков мне обсуждать не охота.

            > Запахло фильтром Блума.
            Немытым? Не, обычная хеш таблица, только разрешил одновременно больше коллизий делать в строке букета (в моем случае элемент вектора). А в качестве разруливателя колизий использовал std::map c двоичным поиском. Ну я ещё не оптимизировал и не игрался с параметрами, а там посмотрим. Может и обгонит.
            Ответить
            • показать все, что скрыто>>мне даже заходить суда не хочется.
              пздц, я все волосы порву на очке от горя(

              Нахуй ты тут кому сдался.
              Ответить
            • в каждом контейнере (в твоем случае мапе) каждой ячейки массива будет лежать мало элементов, в противном случае нужно будет сделать рехеширование (переложить все в массив большего размера)
              так вот ассимптотика - это хорошо, но нельзя забывать про скрытую константу:
              поиск по списку из 1-5 элементов будет делаться быстрее чем по красно-черному дереву
              Ответить
              • хм, глупость написал, и отредактировать не успел

                добавление элементов в красно-черное дерево затратная операция
                а поиск что по дереву, что по списку из 1-5 элементов - одно и тоже
                Ответить
              • >будет лежать мало элементов
                Это только если хеш-функция хорошая. В целом правильно - дерево, для 1-5 элементов не нужно.
                Ответить
            • см. ConcurentHashMapV8.
              Там если в букете список маленький, то связный лист, если побольше, то дерево (бинарный поиск) - на случай плохих хешей.
              Хотя код конечно запутанный и там много жабоговна, но может какие идеи подскажет.
              Но я бы поигрался, а потом лучше стал искать готовый production-quality крестокод.
              Ответить
            • Быстрые вещи пишутся не так. Хочешь перфоманса - пиши отдельную реализацию для каждого случая.


              Если твой подход будет как у обычного С++ питушка, который хочет быструю хешпаму для всех типов ключей/значений юзая один и тот же хеш. Юзая один и тотже размер массива, юзая один и тот же обработчик коллизий. Юзая стандартные аллокаторы( обычно об этом вы в своих питух-бенчах забываете, а именно это основа ваших тормазов). Кладя на память, кеша, пейджаулы и прочее.


              Такого не бывает, и ты сделаешь очередое говно, которое максимум на 2% будет быстрее стл-говна.
              Ответить
              • И где именно нужны эти "быстрые реализации", что затраты на написание и отладку будут ниже покупки пары серверов?
                Ответить
                • Животное, эти реализацию пишутся проще, чем стл-говно. В них нечего отлаживать - они либо работают, либо нет.

                  Сколько тебе надо отлаживать код, который выполняет конкретно одно действие '*' для 32битных интов, а сколько код, который выполняет то же действия для всех видов интов, флоатов, бигнумов всех майстей, да ещё и проверяет правильность - да ещё ввод пользователя чекает, да и ещё имеет 10050 функций.

                  Хеш на перфектхеше пишется вот так data_t data[1 << N]; return data[perfect_hash(key)]; Срани это с стл говном, что тут отлаживать? А именного такого хеша хватит в 50% случаев.

                  В остальных ты можешь отследить тип данных - написать нормальную реализацию, которая будет тебе давать 3-5каллизий на твой средний набор данных - ты просто запиливаешь вместо даты массив дат из 10дат. Получаешь O(3) в худшем случае, а это O(3) в худшем будет такое же, как O(1) в стл.

                  Если ты уверен в своём хеше, и знаешь, что в 90% случаев на 16битном хеше он не будет давать коллизии - ты пишешь тоже самое, что в первом, только после сравнения ключа - ты уже свичишся на другой массив, в котором уже разруливаешь коллизии.

                  Это тебе даёт возмножность со средним кешем в 10мегабайт - юзать 160байтные значения на 16битном хеше. Т.е. это будет намного быстрее stl-говна, а вставка у тебя всегда будет в кеш. Да, тебе прийдётся юзать nt и всякие хитрости - но это даст тебе возмножность создать хештаблицу из массива значений за примерно скорость памяти.

                  Я уже описал 3варианта, которых хватит в 80% случаев. Вызвает сложности только только 3-й вариант с тототальной оптимизацией - без неё он прост как топор. Тут просто нечего отлаживать.
                  Ответить
                  • > В них нечего отлаживать - они либо работают, либо нет.
                    А если они глючат, питух? Кому будут больше доверять - стандартным реализациям или твоим петушиным? И, питух, ты так и не ответил на вопрос - когда это пердоленье окупится?

                    >O(3)
                    Коэффициент в O роли не играет, питух.
                    Ответить
                    • показать все, что скрыто>А если они глючат, питух? Кому будут больше доверять - стандартным реализациям или твоим петушиным? И, питух, ты так и не ответил на вопрос - когда это пердоленье окупится?

                      Что конкретно вот тут может заглючить: data_t data[1 << N]; return data[perfect_hash(key)], опиши мне.

                      Нормальный человек это напишет минут за 5. Посчитай, сколько будет столько тебе надо нод, чтобы жаба на них выдавала такой же перфоманс - я думаю штук 2-3. Поский сколько жрут эти ноды, сколько надо жабиста на ноду, сколько стоит сама нода, место под неё и одмин.

                      Писать норамльный код всегда дешевле, просто суть в том, что писать его просто некому. Вот скажи - напишите мне сайтец на 10к$, который выдаёт 20-30тонн на ведро. Никто не напишет, ибо НЕКОМУ.

                      Поэтому покупают сервера не потому, что дешевле - а потому, что вас питух 100штук на одного нормального, которых даже если ты захочешь найти - не найдёшь. Да и лень им ваять твоё говно.

                      >Коэффициент в O роли не играет, питух.
                      Реальне? Ну да, анскильным питушкам наверное виднее.
                      Ответить
                      • >Что конкретно вот тут может заглючить
                        Питух, заглючить в вашей сишке может все, что угодно.

                        >Реальне? Ну да, анскильным питушкам наверное виднее.
                        >Функция T(n)=3n^3+2n^2 при n \rightarrow \infty имеет степень роста O(n^3).
                        Википедия же.

                        >Писать норамльный код всегда дешевле, просто суть в том, что писать его просто некому.
                        У нас слишком разные понятия о "нормально". И что там говорил Кнут про преждевременную оптимизацию, питух? Так вот, вся ваша сишка это преждевременная оптимизация.

                        >Поэтому покупают сервера не потому, что дешевле - а потому, что вас питух 100штук на одного нормального, которых даже если ты захочешь найти - не найдёшь.
                        Ахахахах, смотрите на уебка - есть секретные суперспециалисты, которых не берут, потому что не находят, прячутся они, а не потому, что в большинстве случаев дешевле без них обойтись.

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

                        >напишите мне сайтец на 10к$, который выдаёт 20-30тонн на ведро. Никто не напишет, ибо НЕКОМУ.
                        >Никто за эти бабки не будет ебаться
                        >Дешевле будет купить железо и написать на другом языке.
                        >Кококо, меня неопустили ведь совсем, кококо!

                        20-30тонн картошки на ведро? Многовато будет, питух, не влезет. Или ведро нужно очень большое.
                        Ответить
                        • >Питух, заглючить в вашей сишке может все, что угодно.
                          Т.е. что конкретно ты сказать не можешь - ты очередной балабол? Ок, так и запишем.

                          >Википедия же.
                          Меня не интересует твоя недокопипаста, либо копипасть всё - либо не кукарекай.

                          >У нас слишком разные понятия о "нормально". И что там говорил Кнут про преждевременную оптимизацию, питух? Так вот, вся ваша сишка это преждевременная оптимизация.
                          Твой кнут животное, прочитай вторую часть фразы. И да, выруби оптимизации в своём дотнете - они же "преждевременные" - врубай только когда будет тормазить. Выруби в майзке оптимизацию, кеша, выруби в процессоре кеш - преждевременная оптимизация.

                          Ты животное несёшь херню, такую херню, что я просто представить немогу уровень твоей упоротости.

                          >Ахахахах, смотрите на уебка - есть секретные суперспециалисты, которых не берут, потому что не находят, прячутся они, а не потому, что в большинстве случаев дешевле без них обойтись.
                          Ну дак их нет. Иди погугли сколько в мире нормальных сишников. Конпеляторы пилить некому - интел вон целую сеть центров в рашке запилил, чтобы хоть что-то пилили, ибо запильщиков нет.


                          >Питух, а что вы в вашей сишке будете делать, когда таки перфоманса одной машины не хватит и надо будет таки параллелиться на кластер?
                          Когда у сишнека кончится перфоманс машины - у тебя кончится 20-я нода. Сишнику не сложно взять mpi и захреначить связь между нодами.


                          >20-30тонн картошки на ведро? Многовато будет, питух, не влезет. Или ведро нужно очень большое.
                          Как же ты слился питушок. То-то блин за теме же запильщиками вебсерверов бегают по всему миру - лижбы не тормазило. Их же мильён - вот незадача.
                          Ответить
                          • >Т.е. что конкретно ты сказать не можешь - ты очередной балабол? Ок, так и запишем.
                            То же, что и в нормальных языках + UB на разных платформах + проблемы языков с ручным выделением памяти + нулевая встроенная библиотека, хочешь хешмеп? Давай сишечку суй поглубже в срачло.

                            >Меня не интересует твоя недокопипаста, либо копипасть всё - либо не кукарекай.
                            В гугле забанили, пидорва?
                            https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D 1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D 0%BC%D0%B0%D0%BB%D0%BE%D0%B5

                            >прочитай вторую часть фразы.
                            >что писать его просто некому.
                            То есть, за те же деньги никто не будет работать? Читай-ка и ты внимательнее, чепушила.
                            >в большинстве случаев дешевле без них обойтись.

                            >. И да, выруби оптимизации в своём дотнете - они же "преждевременные" - врубай только когда будет тормазить. Выруби в майзке оптимизацию, кеша, выруби в процессоре кеш - преждевременная оптимизация.
                            Мне эта оптимизация ничего не стоит. А вот пердолиться байтами вместо мыслях об архитектуре - это хуйня, да тебе сперма глаза залила.

                            >Ну дак их нет. Иди погугли сколько в мире нормальных сишников.Конпеляторы пилить некому
                            Какое отношение ты имеешь к ним, скатина? Ты хоть когда-то конпелятор пилил? Много напилил, петушила?

                            >Когда у сишнека кончится перфоманс машины - у тебя кончится 20-я нода.
                            Ты ебанутый? Бенчмарки си и явы в сраку не хочешь?

                            >То-то блин за теме же запильщиками вебсерверов бегают по всему миру
                            Это кто такие? Я на твоем питушином не разговариваю.
                            Ответить
                          • Пользователь superhackkiller1997 забанен.

                            К сожалению, пользователь superhackkiller1997 не может более посещать LOR,

                            начиная с 02.06.2013 11:42:12.

                            Причина тому проста: унылый троллинг и провокации.

                            Мы сожалеем, правда.

                            Вопросы, пожелания по адресу [email protected].

                            Питушок, за что тебя на питушином сайте зобанели?
                            Ответить
                            • >Царем ты себя называл неоднократно, скилламии бахвалился, а кода никакого ни разу так и не показал. То есть, ты тупо балабол, слабоумный ребенок.
                              Бляяяяяяяяяяяяяяядь! xDDDDDDDDDDDDDDDDDD
                              Ответить
                            • Смотрите сами на питуха http://www.linux.org.ru/forum/development/9218565.
                              Ответить
                            • >>унылый троллинг

                              Такой унылый.
                              Ответить

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