А в чем профит хешевых контейнеров?
Повседневная мудрость подсказывает, что стоимость подсчета хеша ключа длины n по крайней мере O(n)*.А сравнение для дерева за O(1)?
То есть, для дерева — log²(N для хеша без коллизий — log(N так?
То есть, для дерева — log²(N для хеша без коллизий — log(N так?Прости, не понял, что это за оценки. Можешь пояснить?
Сильно зависит от специфики задачи. В среднем по больнице, если сравнивать pure hash table с pure rb-tree, то hash table выигривает.
Деревья (по крайней мере низко-n-арные) плохи тем, что по памяти нужно много прыгать. А память сейчас — это те же самые проблемы, что и HDD 20 лет назад, — сильно плохое latency, 200+ тактов на доступ.
Доступ в хэш-таблице — это O(1) amortized time. Ситуация, когда тебе по бакетам линейно нужно ходить, неестественна. В джаве вот стандартный HashMap увеличивает количество бакетов при заполнении >= 75%, в cpp >= 100%.
Деревья (по крайней мере низко-n-арные) плохи тем, что по памяти нужно много прыгать. А память сейчас — это те же самые проблемы, что и HDD 20 лет назад, — сильно плохое latency, 200+ тактов на доступ.
Доступ в хэш-таблице — это O(1) amortized time. Ситуация, когда тебе по бакетам линейно нужно ходить, неестественна. В джаве вот стандартный HashMap увеличивает количество бакетов при заполнении >= 75%, в cpp >= 100%.
Прости, не понял, что это за оценки. Можешь пояснить?Сферический поиск в большом контейнере, а ч0?
Хеш логарифмический, как я писал.
В дереве логарифмическое число хопов, и на каждый, как ты писал, логарифмическое сравнение.
В добавок я не понял, как ты пытаешься сравнивать доступ в контейнер (O(log n) vs O(1 с подсчетом хэша (O(n. Ты ведь понимаешь, что 'n' в этих двух случаях — это разные 'n'?
А память сейчас — это те же самые проблемы, что и HDD 20 лет назад, — сильно плохое latency, 200+ тактов на доступ.А в идеальной памяти у хеша есть преимущество перед деревом?
Ты ведь понимаешь, что 'n' в этих двух случаях — это разные 'n'?Читай, как я это делаю:
стоимость подсчета хеша ключа длины n по крайней мере O(n)n в этой фразе связанная переменная.
Размер контейнера в другом посте я назвал N.
Заглавная буква, потому что большой контейнер.
Строчная буква, потому что недлинный ключ.
Ситуация, когда тебе по бакетам линейно нужно ходить, неестественна. В джаве вот стандартный HashMap увеличивает количество бакетов при заполнении >= 75%, в cpp >= 100%.75%, по-моему, уже не о том. Это не с бакетами хеш же.
В славные времена бакетов, вроде, считалось 8–10 средняя заполненность корзины порог для рехешинга.
Это доступ в которую бесплатен?
Тогда уже нужно сравнивать время подсчета хэша (один раз на доступ) с временем работы компаратора (коих log n на доступ).
BTW, для объектов, где время подсчета хэша существенно, обычно хэш делают полем класса. Что избавляет каждый раз его считать при доступе в хэшированный контейнер.
Тогда уже нужно сравнивать время подсчета хэша (один раз на доступ) с временем работы компаратора (коих log n на доступ).
BTW, для объектов, где время подсчета хэша существенно, обычно хэш делают полем класса. Что избавляет каждый раз его считать при доступе в хэшированный контейнер.
Сферический поиск в большом контейнере, а ч0?Ну если принять твои определения, то для 10^6 элементов ты получаешь 20 операций против 400. Вполне ощутимый профит.
BTW, для объектов, где время подсчета хэша существенно, обычно хэш делают полем класса. Что избавляет каждый раз его считать при доступе в хэшированный контейнер.Да, но от хотя бы одного сравнения это нас не спасает.
Ну я и говорю. Тогда да.
Плюс тут предлагает прямо в объекте его хеш мемоизировать, тоже профит.
Плюс тут предлагает прямо в объекте его хеш мемоизировать, тоже профит.
М-да.
В такой постановке hash map становится гирляндой пустых ведер. Omg.
Как это все звенит при малейшем порыве ветра.
В такой постановке hash map становится гирляндой пустых ведер. Omg.
Как это все звенит при малейшем порыве ветра.
Да, но от хотя бы одного сравнения это нас не спасает.Ну то есть остается тот же log(N) для хеша, разве что без мемоизации это было 2log(N).
Ну то есть остается тот же log(N) для хеша
не лучшечтобы сделать подобный вывод нужно очень сильно зажмуриться
если коротко, то профит хешированных контейнеров в хорошей (в частности, лучшей скорости работы по сравнению с балансированными деревьями) скорости при определенных обстоятельствах (то есть в конкретных ситуациях)
аналогичный плюс есть у деревьев
факторы, которые влияют на скорость:
1) сложность подсчета хеша
2) сложность сравнения элементов
3) кол-во колизий
чем ближе хешированный контейнер походит на разреженный массив, тем шустрее идет поиск (получаем почти произвольный доступ). дерево ну никак к этому не приблизится (оно всегда развесистое и надо log скачков\сравнений сделать для поиска глубоких элементов)
эти мысли в основном о поиске элементов. для операций модификации контейнера нужно отдельно взвешивать сложность рехешинга и балансировки. в целом, факторов так много, что асимптотически здесь сложно выдать какие-то оценки. проще рассмотреть лучшие\худшие варианты для обоих видов контейнера
если коротко, то профит хешированных контейнеров в хорошей (в частности, лучшей скорости работы по сравнению с балансированными деревьями) скорости при определенных обстоятельствах (то есть в конкретных ситуациях)Короче, получился очередной тред ниачом.
аналогичный плюс есть у деревьев
получился очередной тред ниачом.так точно
пытаться сравнить теплое с мягким, да еще и с учетом возможной аллергии
Ну на самом деле польза треда очевидна. Я хотя бы узнал, что в своих прикидках забыл про стоимость сравнения.
хэши банально проще во всём. при хорошем распределении отлично параллелятся - локи пилятся на мелкие части, попробуй сделай такое-же с деревьями.
для маленьких объёмов деревья конечно почти всегда лучше, а когда уже много то оттъюненый хэш рвёт всё.
для маленьких объёмов деревья конечно почти всегда лучше, а когда уже много то оттъюненый хэш рвёт всё.
Но это повседневность, а не асимптотика.
асимптотически всё повседневность — все умрут 
Для хранилищ в KVS больших объемов балансировка на каждой вставке (delete для простоты можно просто считать недоступной операцией) будет просто нагружать систему сверх положенного с минимальной пользой.
Для хранилищ в KVS больших объемов балансировка на каждой вставке (delete для простоты можно просто считать недоступной операцией) будет просто нагружать систему сверх положенного с минимальной пользой.RB-дерево не балансируется на каждой вставке.
Ну афтар вроде не только rb имел в виду, а мб любые двоичные
1. Верно.
2. Ну да, если у тебя строка длины n, то требуется порядка n операций чтобы найти её хэш.
3. Вот тут по-подробнее пожалуйста. Каким образом длина контейнера влияет на длину строки, которую ты там собираешься искать? Если у тебя строки в среднем длины n, а количество элементов в контейнере m, то поиск будет в среднем за O(n). Деревья дадут оценку O(n*logm т. е. всё ок, хэши круче, как и должно быть.
4. Вообще не расшифровал эту фразу. Пусть N - количество элементов в контейнере. В хэшах в худшем случае - поиск осуществляется за O(N). В среднем - за O(1). На практике, сильное замедление замедление хэшей - это скорее какой-то искусственный тест.
Во всяких rb-tree ассимптотика и в среднем и в худшем O(logN).
И ещё, где-то обсуждалось, что открытая адресация на int-ах круче бакетов по скорости, вот
Но тут конечно всего лишь вопрос константы.
2. Ну да, если у тебя строка длины n, то требуется порядка n операций чтобы найти её хэш.
3. Вот тут по-подробнее пожалуйста. Каким образом длина контейнера влияет на длину строки, которую ты там собираешься искать? Если у тебя строки в среднем длины n, а количество элементов в контейнере m, то поиск будет в среднем за O(n). Деревья дадут оценку O(n*logm т. е. всё ок, хэши круче, как и должно быть.
4. Вообще не расшифровал эту фразу. Пусть N - количество элементов в контейнере. В хэшах в худшем случае - поиск осуществляется за O(N). В среднем - за O(1). На практике, сильное замедление замедление хэшей - это скорее какой-то искусственный тест.
Во всяких rb-tree ассимптотика и в среднем и в худшем O(logN).
И ещё, где-то обсуждалось, что открытая адресация на int-ах круче бакетов по скорости, вот
Но тут конечно всего лишь вопрос константы.1. Верно.Короче, после второго тезиса сломался, да?
2. Ну да, если у тебя строка длины n, то требуется порядка n операций чтобы найти её хэш.
3. Вот тут по-подробнее пожалуйста. Каким образом длина контейнера влияет на длину строки, которую ты там собираешься искать? Если у тебя строки в среднем длины n, а количество элементов в контейнере m, то поиск будет в среднем за O(n). Деревья дадут оценку O(n*logm т. е. всё ок, хэши круче, как и должно быть.
4. Вообще не расшифровал эту фразу. Пусть N - количество элементов в контейнере. В хэшах в худшем случае - поиск осуществляется за O(N). В среднем - за O(1). На практике, сильное замедление замедление хэшей - это скорее какой-то искусственный тест.
Во всяких rb-tree ассимптотика и в среднем и в худшем O(logN).
И ещё, где-то обсуждалось, что открытая адресация на int-ах круче бакетов по скорости, вот
Каким образом длина контейнера влияет на длину строки, которую ты там собираешься искать?Давай так.
Издалека.
У тебя есть 256 записей в таблице.
Сколько бит нужно как минимум для ключей, чтобы точно закодировать их все?
Ок, если у тебя в таблице N записей, то офк нужно иметь logN информации. И всё-таки, при чём здесь длина строк?
А вот в первом сообщении ты под ключом подразумевал явно совершенно другое:
А вот в первом сообщении ты под ключом подразумевал явно совершенно другое:
3. Для достаточно большого контейнера длина ключа будет в среднем не ниже логарифма размера контейнера
Ок, если у тебя в таблице N записей, то офк нужно иметь logN информации. И всё-таки, при чём здесь длина строк?Да, извини, я сказал про биты, и ты совсем запутался, сразу представив деревья.
Давай сделаем проще.
Забудем про деревья и хеши.
Представь, что у тебя есть словарь совершенно нового, незнакомого тебе, чтобы не путаться, языка.
Бумажный словарь. Обычный бумажный словарь. Издание Мюллера.
Алфавит языка состоит из двадцати букв.
В словаре восемь тысяч слов.
Какова будет средняя длина слова?
Какова будет средняя длина слова?7 букв
Оставить комментарий
apl13
1. Для поиска ключа нужно посчитать его хеш.2. Повседневная мудрость подсказывает, что стоимость подсчета хеша ключа длины n по крайней мере O(n)*.
3. Для достаточно большого контейнера длина ключа будет в среднем не ниже логарифма размера контейнера
(собственно, это обстоятельство делает печальными и префиксные деревья, и прочие способы хитро и быстро хранить).
4. При этом в винтажном хеше с бакетами нас ждет еще вполне линейный поиск в ведре.
То есть получается, закрывая глаза на коэффициенты, асимптотика хешей не лучше, чем у балансирующихся деревьев.
* Вполне возможно, что в данной задаче хеши хорошо распределяются, даже если считать их по какой-нибудь маленькой проекции множества ключей; но эту же информацию можно использовать и для поиска по деревьям.
У меня перед глазами как живое стоит описание векторов в Скале, где не моргнув глазом пишут, что поскольку индекс — это инт, то хранить элементы в дереве по пять бит на уровень дает константный доступ. Ну в самом деле, число хопов ограничено сверху логарифмом по основанию 32, а для 32-битных чисел это, очевидно, ограничено константой.