Здравствуйте, sergey2b, Вы писали:
ТКС>>А уж если нужен поиск с частичным совпадением, например, для автокомплита, то std::map вообще не годится.
S>подскажите пожалуйста что можно почитать как делать поиск по ключу с частиным совпадением S>например типа "ab*fg*k" где * любые символы S>надо не для этой задачи но интерестно понять как такое можно сделать (про agrep я знаю но он не подходит так как template поиска может быть неесколько)
Про поиск с частичным совпаденем с помощью троичных деревьев у Седжвика более-менее подробно написано в Algorithms in Java. В его же книжке по алгоритмам на плюсах это кажется оставлено в качестве упражнения.
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
а почему мне смайлики ставят? Поясните, что я написал смещного?
Один человек я еще понимаю -- пыхнуть мог, завидую. А у товарища Зудина зазудел стадный инстинкт?
D>>то что хэши O(1) это самообман.
D>а почему мне смайлики ставят? Поясните, что я написал смещного? D>Один человек я еще понимаю -- пыхнуть мог, завидую. А у товарища Зудина зазудел стадный инстинкт?
Потому что глупость сморозил, поэтому и смайлики. И не груби.
Но понятно, что с ростом N понадобится увеличивать битность хэша, а значит и операцию вычисления хэша. так что там тот же логарифм спрятан.
С ростом N операция вычисления хеша, вообще-то не меняется.
При любом N все сводится к банальному hash_value % n, где hash_value — собственно, результат "операции вычисления хеша", зависит от длины ключа, а n — количество хеш-карманов (ну или "диапазон рассеивания").
При некотором навыке можно добиться от хеш таблицы даже O(N).
Если хэш и лучше, то он лучше именно на практике, а не теоретически.
Заявление подкреплено практикой или только теоретические рассуждения?
_____________________
С уважением,
Stanislav V. Zudin
SVZ>Потому что глупость сморозил, поэтому и смайлики. И не груби.
SVZ>
Но понятно, что с ростом N понадобится увеличивать битность хэша, а значит и операцию вычисления хэша. так что там тот же логарифм спрятан.
SVZ>С ростом N операция вычисления хеша, вообще-то не меняется.
для N элементов необходима хэш-таблица размером K*N где K -- некая константа. Как ты понимаешь с ростом N настанет момент когда 32-битного хэша начнет не хватать. То есть с ростом N растет битность хэша, а значит и меняется операция хэширования.
Ах, ты не рассматривал такие большие N? Ну так и разговор был про асимптотическую сложность.
Здравствуйте, dilmah, Вы писали:
D>для N элементов необходима хэш-таблица размером K*N где K -- некая константа. Как ты понимаешь с ростом N настанет момент когда 32-битного хэша начнет не хватать. То есть с ростом N растет битность хэша, а значит и меняется операция хэширования.
Адресное пространство когда-нибудь заканчивается
Либо тупо переползать на х64, либо делать что-то с меньшим, по сравнению с хешем, аппетитом.
И для хранения коллизий придется использовать не список, а городить что-нибудь древоподобное.
Правда такую структуру данных хеш-таблицей назвать уже язык не поворачивается.
Но мы увлеклись, топикстартеру для 100 килозаписей простой хеш-таблицы без прибамбасов хватит за глаза.
_____________________
С уважением,
Stanislav V. Zudin
SVZ>Адресное пространство когда-нибудь заканчивается
я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)
SVZ>>Адресное пространство когда-нибудь заканчивается
D>я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)
Идеологический посыл хэша — в убыстрении поиска ключа (за счет константности), а не в асимптотическом стремлении впихнуть невпихуемое. Недаром столько копий сломано именно на поиске perfect hash — функции, которая для заданного диапазона/набора ключей (а не всех возможных) будет давать отсутствие коллизий, что упрощает жизнь. В отличие от дерева, хэш — это баланс между избыточностью и коллизиями. Выиграешь в одном — потеряешь в другом.
Здравствуйте, dilmah, Вы писали:
D>>то что хэши O(1) это самообман.
D>а почему мне смайлики ставят? Поясните, что я написал смещного? D>Один человек я еще понимаю -- пыхнуть мог, завидую. А у товарища Зудина зазудел стадный инстинкт?
Я, например, тоже смайлик поставил, не из-за стадного инстинкта, а потому что мне показалось что вы запутались. Рассуждаете правильно, но, по-моему, не совсем о том, о чем остальные участники. Если обидел — извините, по логике можно было ставить минус, потому что не согласен, но это тоже может оказаться еще обиднее.
> то что хэши O(1) это самообман.
зачастую на практике да — самообман, но не всегда, а при определенных условиях. Вообще сложность О(1) относится к случаю так называемого perfect hash, когда отсутствуют коллизии, если коллизии встречаются, но очень редко, сложность все еще можно считать O(1)
> Они O(1) если считать что вычисление хэша это константная операция. Но понятно, что с ростом N понадобится увеличивать битность хэша, а значит и операцию вычисления хэша.
Вот здесь, на мой взгляд вы запутались. Операция вычисления хэша, как правило, константна по времени, отсюда O(1), а далее все зависит от правильности выбора размера таблицы и от количества коллизий в этом диапазоне. Теоретически можно прийти к O(N) если хэш будет всегда возвращать одно и то же значение.
> Если хэш и лучше, то он лучше именно на практике, а не теоретически.
Так в том и дело что его нужно правильно применять
> для N элементов необходима хэш-таблица размером K*N где K -- некая константа. Как ты понимаешь с ростом N настанет момент когда 32-битного хэша начнет не хватать. То есть с ростом N растет битность хэша, а значит и меняется операция хэширования.
Не надо все в одну кучу, в общем случае на ходу ни размер хэш таблицы, ни битность хэша не меняется. Когда не хватает битности, делаем хэш таблицу меньшего размера (уменьшаем К) и опять всего хватает, либо увеличиваем битность хэша, но это ведь не делается в рамках одной операции. Сложность оценивается для операций вставки, чтения, когда хэш таблица сконфигурирована: битность, размер таблицы константны.
SVZ>>Адресное пространство когда-нибудь заканчивается
D>я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)
Мне кажется я вас не понимаю. Можете объяснить что такое N?
AF>зачастую на практике да — самообман, но не всегда, а при определенных условиях. Вообще сложность О(1) относится к случаю так называемого perfect hash, когда отсутствуют коллизии, если коллизии встречаются, но очень редко, сложность все еще можно считать O(1)
ну, тут мне кажется что ты сам еще не осознал до конца всего волшебства хэшей Оставим в стороне perfect hash.
Если хэш просто достаточно хорош, чтобы быть похожим на случайный, то в этом случае если сделать размер хэш-таблицы в КОНСТАНТУ (скажем, 3) (не в логарифм, а именно всего лишь в константу) раз больше чем количество элементов которых нужно захэшировать, то из легкого упражнения по теории вероятностей будет следовать что коллизий будет O(1), а это и означает, что доступ будет O(1).
Вообще, если человек сам не проделал это упражнение по теории вероятностей, я не поверю что он до конца понял волшебство хэш-таблиц
D>>я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)
AF>Мне кажется я вас не понимаю. Можете объяснить что такое N?
N -- это количество различных объектов, которое планируется хранить в дереве, либо хэш-таблице
Здравствуйте, dilmah, Вы писали:
D>Вообще, если человек сам не проделал это упражнение по теории вероятностей, я не поверю что он до конца понял волшебство хэш-таблиц
Может быть я действительно не до конца понял волшебство хэш-таблиц, но я вообще то всегда рассматривал конкретные, заранее просчитанные случаи использования хэш-таблиц. Широко известный факт, то что сложность доступа к таблице в общем случае варьируется от O(1) до O(N). И я приводил пример что если вычисление хэша это каждый раз коллизия, то будет O(N), думаю при желании и "правильной" реализации таблицы можно и больше. Вопрос в том что когда осознанно выбирают хэш-таблицы, стремятся сделать именно O(1) под конкретный случай, иначе зачем вообще хэш-таблица. Насколько я понял вы вели речь про какую то идеальную, безразмерную хэш-таблицу на все случаи жизни, правильно?
D>>>я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)
Здесь мне кажется я вас понял. Да, аргументация была псевдотеоретическая, а именно практическая, особенно случай автора со 100к ключами. Согласен, вы правы, мы ограничиваем сверху N и доступ O(1), но остается открытым вопрос как у дерева получилось O(1) даже если N ограничить сверху. Просто интересно, здесь действительно не понимаю
AF>>Мне кажется я вас не понимаю. Можете объяснить что такое N? D>N -- это количество различных объектов, которое планируется хранить в дереве, либо хэш-таблице
все таки понял вас правильно
AF>Может быть я действительно не до конца понял волшебство хэш-таблиц, но я вообще то всегда рассматривал конкретные, заранее просчитанные случаи использования хэш-таблиц. Широко известный факт, то что сложность доступа к таблице в общем случае варьируется от O(1) до O(N). И я приводил пример что если вычисление хэша это каждый раз коллизия, то будет O(N), думаю при желании и "правильной" реализации таблицы можно и больше. Вопрос в том что когда осознанно выбирают хэш-таблицы, стремятся сделать именно O(1) под конкретный случай, иначе зачем вообще хэш-таблица. Насколько я понял вы вели речь про какую то идеальную, безразмерную хэш-таблицу на все случаи жизни, правильно?
Я вел речь об обычной хэш-таблице, размер которой в несколько раз превышает количество объектов которые в ней хранят.
И я вел речь о хэш-функциях, которые на имеющихся данных ведут себя как случайные.
Эта случайность хэш-функции гарантирует, что матожидание (т.е. среднее ожидаемое) количество объектов попавших в одно значение хэш-функции будет O(1).
AF>Согласен, вы правы, мы ограничиваем сверху N и доступ O(1), но остается открытым вопрос как у дерева получилось O(1) даже если N ограничить сверху. Просто интересно, здесь действительно не понимаю
Все эти O(1), O(N), O(N^2) это характеристики поведения функции на бесконечности, а не на ограниченном интервале.
С точки зрения чистых теоретиков любое ограниченное число является O(1). Таким образом для теоретика если N ограничено, то и log(N) и даже N^3 и exp(N) являются O(1)
Здравствуйте, dilmah, Вы писали:
D>Я вел речь об обычной хэш-таблице, размер которой в несколько раз превышает количество объектов которые в ней хранят. D>И я вел речь о хэш-функциях, которые на имеющихся данных ведут себя как случайные. D>Эта случайность хэш-функции гарантирует, что матожидание (т.е. среднее ожидаемое) количество объектов попавших в одно значение хэш-функции будет O(1).
И при всем при этом вы считаете что сложность доступа к такой таблице выше O(1), а О(1) — это самообман?
Ладно, пожалуй спорить не буду, пойду лучше подтяну теорию. В данном вопросе я больше практик чем теоретик
