- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 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. Написал свой.
Follow us!
пароль, забыл, штоле?
>Использовал вектор как хештаблицу
Запахло фильтром Блума. Ну написать хорошую мапу - нетривиальная задача, а вот испоганить - запросто.
Разлогинило. Да я и рад. Тут куча школьников набежала, мне даже заходить суда не хочется. Я хоть и школьник, но каролевских питушков мне обсуждать не охота.
> Запахло фильтром Блума.
Немытым? Не, обычная хеш таблица, только разрешил одновременно больше коллизий делать в строке букета (в моем случае элемент вектора). А в качестве разруливателя колизий использовал std::map c двоичным поиском. Ну я ещё не оптимизировал и не игрался с параметрами, а там посмотрим. Может и обгонит.
пздц, я все волосы порву на очке от горя(
Нахуй ты тут кому сдался.
так вот ассимптотика - это хорошо, но нельзя забывать про скрытую константу:
поиск по списку из 1-5 элементов будет делаться быстрее чем по красно-черному дереву
добавление элементов в красно-черное дерево затратная операция
а поиск что по дереву, что по списку из 1-5 элементов - одно и тоже
Это только если хеш-функция хорошая. В целом правильно - дерево, для 1-5 элементов не нужно.
Там если в букете список маленький, то связный лист, если побольше, то дерево (бинарный поиск) - на случай плохих хешей.
Хотя код конечно запутанный и там много жабоговна, но может какие идеи подскажет.
Но я бы поигрался, а потом лучше стал искать готовый 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 не может более посещать LOR,
начиная с 02.06.2013 11:42:12.
Причина тому проста: унылый троллинг и провокации.
Мы сожалеем, правда.
Вопросы, пожелания по адресу [email protected].
Питушок, за что тебя на питушином сайте зобанели?
Бляяяяяяяяяяяяяяядь! xDDDDDDDDDDDDDDDDDD
Странно. А на ГК показывал.
Такой унылый.