В большинстве реализаций STL существуют два подхода для организации отображений: map и hash_map. Ни тот, ни другой не являются эффективными для не-скалярных типов, таких как массивы, строки и т.п.
map использует red-black-tree со сравнением целых строк в каждом узле.
hash_map считает для целой строки хеш-код, затем сравнивает строки целиком, причём кол-во таких сравнений равно кол-ву строк с совпадающим хеш-кодом. Дополнительный недостаток — значения при добавлении не сортируются по ключам.
Но есть и третий подход — использование деревьев цифрового поиска (trie). Такая структура данных позволяет находить нужный узел на основании внутреннего представления строки, сравнивая строки лишь один раз. Наиболее эффективной из таких структур является PATRICIA trie, изобретенная в 1968 Дональдом Р. Моррисоном специально для быстрого поиска в больших объемах текстовой информации. Возможности такого дерева весьма высоки, краткое описание алгоритма добавления/поиска в нем можно увидеть, например, в 3-ем томе "Искусства программирования" Кнута.
Исходя из всего этого, у меня возникла идея создать шаблон контейнера pat_map, который бы в обобщённом виде реализовал структуру PATRICIA trie, и был бы однообразным и совместимым с другими контейнерами и алгоритмами STL. Заголовочный файл с шаблоном и пример использования (concordance). (компилируется MSVC 6, Intel C++ 6, MSVC 7.1)
Для тестирования производительности собрал два эквивалентных релиза (MSVC 7.1 with max optimization): этот
(с использованием std::map) и свой (using pat_map).
Времена подсчёта словоупотреблений для файла 72М (очищенные русские тексты, слова в нижнем регистре и пробел) на P4-2.8 1G RAM:
std::map — 39.1 сек.
pat_map — 29.0 сек.
Результаты вычислений совпадают. Максимум использования RAM для обеих программ был одинаков и составил 20М.
Как видно, производительность в случае использования правильной структуры данных повысилась на 25%.
Вообще говоря, это ещё не окончательная версия (в которой планируются pat_set + удаление узлов + некоторые оптимизации + полная возможная совместимость с STL), но даже в таком виде шаблон pat_map будет полезен.
PS Пожелания и предложения принимаются с благодарностью
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, cranky, Вы писали:
VD>Теперь возми хорошую реализацию хэш-таблицы и хэшфункции и убедись, что потратил время зря.
Достаточно хороши?
Получил на том же тексте 24.1 сек. и хорошо перемешанный список слов с их частотой. Или может есть хеш-функция, позволяющая хранить записи, сортированные по ключу?
На всякий случай напомню: это ещё только зачаточная версия контейнера. В нём планируются такие возможности, которые хешированию так же недоступны, как и хранение в отсортированном виде. В частности, PATRICIA trie позволяет использовать в качестве ключей бесконечные строки. Это может быть полезно для нахождения всех позиций в большом файле, где начинается искомая строка.
Здравствуйте, cranky, Вы писали:
C>Достаточно хороши? C>Получил на том же тексте 24.1 сек.
Я бы назвал эту реализацию посредственной. Но как видишь она уже показала себя лучше дерева.
C> и хорошо перемешанный список слов с их частотой. Или может есть хеш-функция, позволяющая хранить записи, сортированные по ключу?
Сортировку на больших объемах лучше выполнять отдельно. Я к тому, что алгоритмически для таких задач хэширование — оптимальный выбор. Лиш бы хэш-функция не подвела.
C>На всякий случай напомню: это ещё только зачаточная версия контейнера. В нём планируются такие возможности, которые хешированию так же недоступны, как и хранение в отсортированном виде. В частности, PATRICIA trie позволяет использовать в качестве ключей бесконечные строки. Это может быть полезно для нахождения всех позиций в большом файле, где начинается искомая строка.
Я не спорю, что твой контейнер имеет право на существование и хорош в некоторых случаях. Я не согласен с твоим утверждением:
В большинстве реализаций STL существуют два подхода для организации отображений: map и hash_map. Ни тот, ни другой не являются эффективными для не-скалярных типов, таких как массивы, строки и т.п.
Сам по себе hash_map — это классическая таблица. То что он не важно реализован в некоторых версиях STL еще ни о чем не говорит. К тому же hash_map не входит в стандарт и является частным расширением. Ну, а его опрадванность ты мог наблюдать сам.
Нумаю ты понимашь, что чем сложнее тип используемый в качестве ключа, тем эффективнее может быть хэш-таблица? Ведь хэш-значение можно вычислить один раз и закэшировать в кэземпляре. Далее поиск слота осуществляется практически в костантное время и при минимуме вычислений. А сравнение ведется на очень малом объеме списка. В итоге чем больше объем данных — тем фээективнее хэш-таблица. Для защиты от коллизий можно вместо списка коллизий хранить деревья или отсортированные массивы значений. В общем, алгоритмически у чистых деревьев просто нет шансов. Смысл в них есть только если нужна постоянная отсортированность. Что является довольно большой редкостью.
... << RSDN@Home 1.2.0 alpha rev. 606>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Я не спорю, что твой контейнер имеет право на существование и хорош в некоторых случаях. Я не согласен с твоим утверждением: VD>
В большинстве реализаций STL существуют два подхода для организации отображений: map и hash_map. Ни тот, ни другой не являются эффективными для не-скалярных типов, таких как массивы, строки и т.п.
VD>Сам по себе hash_map — это классическая таблица. То что он не важно реализован в некоторых версиях STL еще ни о чем не говорит. К тому же hash_map не входит в стандарт и является частным расширением. Ну, а его опрадванность ты мог наблюдать сам.
Оки, я согласен, что hash_map я зацепил по инерции, но тогда он просто не из той оперы, ибо добивается несколько иных целей и делает это, естественно, по-другому. Хотя... Дело в том, что положение узла в trie определяется исходя из значений битов, указывающих, в какую сторону поворачивать. Но никто не ограничивает, в каком порядке эти биты располагаются в ключе, и есть ли они там вообще. Следовательно, возможно придумать такой порядок вычисления битов, который будет эквивалентен значению хеш-функции от этого ключа. Получается, что на деревьях можно эмулировать работу сколь угодно сложной хеш-таблицы, естественно также без гарантии сортированности по ключу. Тем более в моей реализации выдача значений битов ключа вынесена в отдельный класс.
VD>Нумаю ты понимашь, что чем сложнее тип используемый в качестве ключа, тем эффективнее может быть хэш-таблица? Ведь хэш-значение можно вычислить один раз и закэшировать в кэземпляре. Далее поиск слота осуществляется практически в костантное время и при минимуме вычислений.
Аналогично и с порядком выборки битов: если его сложно вычислять — он кешируется.
VD>А сравнение ведется на очень малом объеме списка. В итоге чем больше объем данных — тем фээективнее хэш-таблица. Для защиты от коллизий можно вместо списка коллизий хранить деревья или отсортированные массивы значений. В общем, алгоритмически у чистых деревьев просто нет шансов.
Если смущает поиск по дереву — можно применить специальный вектор, содержащий указатели на вершины, соответствущие префиксу ключа заранее определённой длины. Тогда останется пройтись по дереву меньшего объёма — аналогия с деревом коллизий. Эта возможность тоже в планах.
VD>Смысл в них есть только если нужна постоянная отсортированность. Что является довольно большой редкостью.
Отсортированность — необязательное условие для деревьев цифрового поиска. Ею при необходимости можно пожертвовать.
Здравствуйте, cranky, Вы писали:
C>Оки, я согласен, что hash_map я зацепил по инерции, но тогда он просто не из той оперы, ибо добивается несколько иных целей и делает это, естественно, по-другому.
Именно. Причем в обычно задач для которых достаточно функциональности хэштаблицы намного больше. В дотнете любой объект обязательно реализует функцию хэширования. Это как раз сделано для того чтобы максимально упростить использование хэш-таблиц.
C> Хотя... Дело в том, что положение узла в trie определяется исходя из значений битов, указывающих, в какую сторону поворачивать. Но никто не ограничивает, в каком порядке эти биты располагаются в ключе, и есть ли они там вообще. Следовательно, возможно придумать такой порядок вычисления битов, который будет эквивалентен значению хеш-функции от этого ключа. Получается, что на деревьях можно эмулировать работу сколь угодно сложной хеш-таблицы, естественно также без гарантии сортированности по ключу. Тем более в моей реализации выдача значений битов ключа вынесена в отдельный класс.
Что то я тебя не пойму. Причем тут биты? Дериво и так польностью эмулирвет поведение хэш-таблицы. Только делает оно это на баже поддержания сортированности. А это, с одной стороны требует того чтобы элементы коллекции можно было сравнивать на болше/меньше, что не всегда удобно/допустимо (например, что больше Иванов или Сидоров?). А сдругой стороны — это банально более медненно. Ведь для поиска элементов в бинарном дереве поиска используется бинарный поиск (полвинным делением), а в хэш-таблице просто вычисляется хэш-функция и на ее основании вычисляется слот хэш-таблицы. Если коллезий нет, то скорость просто константная.
C>Аналогично и с порядком выборки битов: если его сложно вычислять — он кешируется.
О каких битах ты все время ведешь речь? Чтобы найти элемент в дереве ты обязан сравнить ключ с корневой веткой, если ключ больше начать поиск в левом поддереве, если меньше, в правом. В нем ты снова обязан полностью соравинть ключь с ключем из ветки и так далее пока не найдется нужны ключ или не обнаружится, что такового нет. Заранее сравнение вычислить нельзя. В случае же с хэш-значением его можно формировать при создании объекта, а потом пользоваться гтовым значением.
C>Если смущает поиск по дереву — можно применить специальный вектор, содержащий указатели на вершины, соответствущие префиксу ключа заранее определённой длины. Тогда останется пройтись по дереву меньшего объёма — аналогия с деревом коллизий. Эта возможность тоже в планах.
Ничего нельзя тут поделать. К тому же мы говорим о данных в памяти, а они всегда доступны напрямую. Еще раз повторюсь, эффективнее хэшировния является только простой идексный доступ в массиве и то он является практически частным случаем когда хэш-функция равна значению индекса.
C>Отсортированность — необязательное условие для деревьев цифрового поиска. Ею при необходимости можно пожертвовать.
Здравствуйте, VladD2, Вы писали:
VD>Что то я тебя не пойму. Причем тут биты? VD>О каких битах ты все время ведешь речь? VD>А то у тебя какие-то странные представления. Или изложи свои идеи. Как же можно искать в неупорядоченных деревьях.
Почитай теорию по Patricia деревьям, а...
А то похоже ты принцип их работы совершенно не понимаешь. Patricia дерево выглядит примерно так
0
0
1
0
-A-
0 1
0 0
1 0
B C 0 1 0 1
0 E 1 0
1 1 G
0 F
D
A — G — ноды (цифры над ними по дереву до самого верха — соответствующие им ключи)
т.е. для ноды F ключ = 0010100011, для ноды D = 00100010010
Но при этом можно создать такое дерево
Тут уже A = 001010, B = 0010001101, C = 00100010010
Если без оптимизаций, то поиск идет побитовым сравнением ключа поиска и ключа ноды. На различающемся бите просто происходит смена ноды и поиск идет дальше. Во втором дереве правый чайлд просто указывает на эту же ноду.
В результате поиск элемента в таком дереве линейна и зависит от длинны ключа.
Пример: ключ поиска = 0010001101
Нода А — совпало 0010. Бит разницы — 0, перехожу на левого чайлда и сравниваю дальше
Нода В — совпало 001. Бит разницы — 1, перехожу на правого чайлда и сравниваю дальше
Нода В — совпало 101. Больше чайлдов нет — нашел нужную ноду
Пример: ключ поиска = 00101101
Нода А — совпало 0010. Бит разницы — 1, перехожу на правого чайлда и сравниваю дальше
Нода А — совпало 1. До бита разницы не дошло — искомой ноды нет
[...]
CC>Если без оптимизаций, то поиск идет побитовым сравнением ключа поиска и ключа ноды. На различающемся бите просто происходит смена ноды и поиск идет дальше. Во втором дереве правый чайлд просто указывает на эту же ноду.
Стоит добавить только, что обычно "оптимизация" заключается в сохранении номера бита различия в ноде, что позволяет иметь всего один узел на ключ.
CC>В результате поиск элемента в таком дереве линейна и зависит от длинны ключа.
Скорее сложность поиска это сумма [O(ln N) + O(K)], где N — общее кол-во узлов в дереве, K — длина ключа.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, cranky, Вы писали:
C>>Скорее сложность поиска это сумма [O(ln N) + O(K)], где N — общее кол-во узлов в дереве, K — длина ключа.
VD>Здорово. Скоростная характеристика хэш-тиблицы в отсуствии коллизий O(1) и не завист от размера ключа.
А сложность вычисления хорошего хеш-значения ключа тоже стала константной и не зависит от длины ключа?
Здравствуйте, cranky, Вы писали:
C>А сложность вычисления хорошего хеш-значения ключа тоже стала константной и не зависит от длины ключа?
Зависит от алгоритма. Может и не зависить. Но если бы ты читал внимательнее, то заметил бы, что хэш легко кешируется. Так что вычислять его каждый раз не нужно.
... << RSDN@Home 1.2.0 alpha rev. 606>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Интересно, спасибо. Надо будет и себе такое сделать, думаю получится. Даже мнится, что перебор в partial_match будут делать итераторы, может даже стандартные
CS>На больших наборах TST лучше плюс всякие вкусности типа "найти похожий".
Хм, а если применить правильный аллокатор для узлов, возможно они и сравняются в производительности... Алгоритмы-то родственные, насколько я не напутал. Сложность одинакова. Вкусности и у моих шаблонов планируются, но потом
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, cranky, Вы писали:
C>>Достаточно хороши? C>>Получил на том же тексте 24.1 сек.
VD>Я бы назвал эту реализацию посредственной. Но как видишь она уже показала себя лучше дерева.
Такой вопрос: какая хеш-функция будет оптимальной для реализации хеш-таблицы в STL VC 7.1?
Интересуюсь, потому что в "Компиляторах" приведена такая:
size_t operator()(const string &key) const
{
size_t h=0,g;
for (string::const_iterator it=key.begin();it!=key.end();++it)
{
if (g=(h=(h<<4)+*it)&0xF0000000)
h^=g>>24^g;
}
return h;
}
Называется hashpjw и в тестировании даёт "неплохие результаты для всех размеров таблиц". "Неплохие" в этой цитате — это наиболее быстрые? Но проведённые мною эксперименты с замером производительности дают странный результат — hash_map с hashpjw всегда немного отстаёт от моего мапа, в то время как "посредственная реализация" всегда несколько опережает его. Почему так получается и какая функция будет самой эффективной для моих данных (большое кол-во (300-500К) повторяющихся с разной частотой строк длиной 1..25 символов)?
Здравствуйте, kluxer, Вы писали:
K>Такой вопрос: какая хеш-функция будет оптимальной для реализации хеш-таблицы в STL VC 7.1?
Вообще-то это зависит от того что из себя представляют строки. Ведь это могут быть фантастические рассказы, а могут идентификаторы из программы.
K>Интересуюсь, потому что в "Компиляторах" приведена такая: K>
K>Называется hashpjw и в тестировании даёт "неплохие результаты для всех размеров таблиц".
Это как я понимаю переделанный под С++ вариант из "Красного дракона". Я не проводил личных эксперементов, но и так понятно, что данная хэш-функция рассчитана на короткие идентификаторы обычно встречаемые в компиляторах.
Насколько мне извесно в дотнете используется очень неплохая хэш-ункция для строк. Ее можно выковырять из Ротора (SSCLI). В дотнетом форуме даже как-то был флэйм. Один орел не мог поверить, что хэш-функции не могут давать уникальные значения, а его тесты давали уникальные результаты.
K> "Неплохие" в этой цитате — это наиболее быстрые? Но проведённые мною эксперименты с замером производительности дают странный результат — hash_map с hashpjw всегда немного отстаёт от моего мапа, в то время как "посредственная реализация" всегда несколько опережает его. Почему так получается и какая функция будет самой эффективной для моих данных (большое кол-во (300-500К) повторяющихся с разной частотой строк длиной 1..25 символов)?
Возможно вычисление хэш-функции оказывается на тестируемых объемах более затратным чем сам поиск. А возможно что функция на твоих данных дает много коллизий. Это легко определить опытным путем. Если проблема в скорости хэш-функции, то можно просто кэшировать результат. Если в качестве, то нужно ее выбрасывать.
... << RSDN@Home 1.2.0 alpha rev. 606>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
C>Исходя из всего этого, у меня возникла идея создать шаблон контейнера pat_map, который бы в обобщённом виде реализовал структуру PATRICIA trie, и был бы однообразным и совместимым с другими контейнерами и алгоритмами STL. C>Заголовочный файл с шаблоном и пример использования (concordance). (компилируется MSVC 6, Intel C++ 6, MSVC 7.1)
trie_set и trie_map
вынос интерфейса bit_comparator из ключа
поддержка стандартных allocator'ов
реализация всех методов ассоциативных контейнеров (кроме некоторых конструкторов и erase)
слегка увеличена скорость
Отличия от set и map: некоторые различия в работе методов lower_bound и подобных. Обусловлены отсутствием предиката и присутствием бит-компаратора, а также возможностью бесконечного ключа. Но об этом в будущей документации.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, cranky, Вы писали:
C>>А сложность вычисления хорошего хеш-значения ключа тоже стала константной и не зависит от длины ключа?
VD>Зависит от алгоритма. Может и не зависить. Но если бы ты читал внимательнее, то заметил бы, что хэш легко кешируется. Так что вычислять его каждый раз не нужно.
Я этот алго использую в таких случаях, когда на вход приходят сырые строки полученные откуда-то. Т.е. хэш для них надо считать в любом случае.
Для меня еще является плюсом что мне не надо парится вопросом насколько подходит выбранный алгоритм хеширования для этого типа ключей.
Давайте этот спор решим просто: набросаем тестовую программку с выполнением пары-тройки приближенных к реальным задачам алгоритмов с применением hash_map и patricia trie (+можно еще и ternary tree до кучи)
И можно на практике посмотреть на эффективность.
Потому как к сырой теории у меня полного доверия нет. Сколько раз напарывался что в теории все гладко а на практике полное г.
... дополнение к моей мессаге
набросал сравнивалку. Но только без hash_map — я щас в отпуске а дома только VC6 со стандартным STL
В общем случае ternary в 3-5 раз быстрее patricia. Тестил на русских текстах и на телефонном справочнике (список ФИО).
Но при этом в ternary пробежаться по списку строк никак нельзя — надо их самому хранить отдельно. Что увеличивает требования к памяти.
947494 уникальных слов
вставка слов из файла
Patricia: 14.368569 sec. 8788 ticks per call 110.5Mb
Ternary: 4.221286 sec. 2597 ticks per call 68.4Mb (чистое дерево, сами строки не хранятся)
повторное чтение файла и поиск слов в map
Patricia: 17.433085 sec. 10662 ticks per call
Ternary: 2.179576 sec. 1341 ticks per call
lower_bound, upper_bound, equal_range и count получили второй параметр со значением по умолчанию (длина префикса в битах). Теперь можно получить итераторы границ интервала, содержащего все ключи с заданным префиксом. Пример см. в patcont.cpp;
insert с параметром hint (подсказка для вставки за O(1)) выкинут за ненадобностью;
введёны новые типы итераторов — partial match iterators (partimap ) — const_partimap, partimap. Позволяют обходить дерево не полностью, заходя только в нужные поддеревья. Шаблоны классов этих итераторов параметризуются типом Decision — функтором, определяющим надо ли заходить в указанное поддерево. Пример реализации класса Decision имеется в partial.h, PartialMatch, и реализует прохождение дерева для поиска всех частичных совпадений по ключу (как здесь
). В дальнейшем планируются const_reverse_partimap, reverse_partimap, а также другие реализации интерфейса Decision для разных задач поиска совпадений;
бит-компараторы для следующих типов ключей: standard finite std::basic_string<char> (тестировался только этот), simple infinite (char*) string, finite (char*) string with ASCIIZ semantics;
внутренний вектор shortcut — для константного доступа к узлу при поиске/вставке для префикса заранее заданной длины (в моей реализации бит-компараторов — 16 бит (см. bit_comp.h));
в качестве примера эмуляции хеш-таблицы (см. здесь
) реализован специальный класс DelusionString с соответствующим bit_comparator (bit_comp.h), кеширующий 16 младших бит хеш-значения для строки. Для сборки в режиме эмуляции хеш-таблицы следует раскомментировать #define PAT_DELUSION в patcont.cpp. После запуска получается неотсортированный по ключу результат, но зато даже немного быстрее, чем используя hash_map с той же хеш-функцией. В таком варианте контейнеры trie_map и trie_set теряют все свои возможности, связанные с последовательной выборкой битов из ключа;
возможно что-то ещё забыл
v0.05
Изменения к лучшему:
trie_set и trie_map
вынос интерфейса bit_comparator из ключа
поддержка стандартных allocator'ов
реализация всех методов ассоциативных контейнеров (кроме некоторых конструкторов и erase)
слегка увеличена скорость
Отличия от set и map: некоторые различия в работе методов lower_bound и подобных. Обусловлены отсутствием предиката и присутствием бит-компаратора, а также возможностью бесконечного ключа. Но об этом в будущей документации.
