Текстовые индексы.

Судя по стилю Ваших ответов, у меня складывается стойкое ощущение, что Вы ошиблись форумом...

Нормальное сбалансированное бинарное дерево сделать намного проще, чем написать жалкий хэш. Но и профиты от дерева очевидны.

Ээээ... Профиты - простота написания и отладки? Да, любой дурак (читай стюдент) хорошее дерево напишет, в отличие от хорошего хэша.

А если строки заранее известны, то деревьям вообще и близко не светит, т.к. есть perfect hash, откуда ключи достаются за одно сравнивание. За то время, по дереву будем идти можно из хэша несколько ключей достать.

Что ты ко мне пристал? Не удасться тебе отшутиться, обосрался - обтекай.

но оно может (в самом общем случае) потребовать значительно больше памяти - веток много, и тупики тоже надо обозначать.

Да, дерево такое не идеально - все зависит от задачи. Если памяти оно будет жрать слишком много - использовать сбалансированное бинарное дерево поиска.

Деградирую вместе с ЛОРом :)

длина строки постоянна - 8 символов.

Тогда дерево, предложенное мной, 100% катит :)

В общем случае да, дерево пишется хоть с нуля и на коленке за пару минут, кто угодно справится, с хэшем номер не пройдёт, а пОгроммист потом будет вещать «видел я этот ваш хэш, деревья куда лучше».

Но зачем же планку опускать. И потом, сейчас столько реализаций хэшей хороших, бери, дополняй, используй.

Что ты ко мне пристал? Не удасться тебе отшутиться, обосрался - обтекай.

Да у Вас прямо мания какая то... запах, который Вы чувствуете, может исходить только из Ваших штанов (ну или штанов Вашего соседа, или с кем Вы там проводите суровые будни?).

А что, за каменты на ЛОР-е Вам тоже стали платить по 85 руб? Или это чисто для поддержания квалификации?

ЗЫ на простых тестах, при числе записей 10^6-10^7 что хэш, что map ~ 300 тактов на доступ (ключ long). Если Вам конечно это интересно...

Ну а так деревья проще, ломаться там нечему. Про балансировку по полкам всё разложено.

Скорость не сильно критична если, с деревом проще.

Что ж ты так много пишешь? Неужели ты думаешь, что я читаю твои сообщения дальше первых двух слов?

После отсылки к Кнуту с тобой всё стало ясно, твои сообщения можно пропускать.

Неужели ты думаешь, что я читаю твои сообщения дальше первых двух слов?

Да нет, я вообще сомневаюсь, что ты умеешь читать;-)

Профиты - простота написания и отладки?

Нет. Это антипрофиты: пишется что хэш, что дерево достаточно просто, а с отладкой у хэша проще. А сбалансированное бинарное дерево хорошо тем, что:

• O(logN) в худшем случае для вставки, удаления, поиска элемента, а также для выборки предыдущего и следующего в порядке сортировки элемента. С хэшом вставка - O(1), поиск и удаление элемента, а также поиск следующего и предыдущего - в худшем случае O(N).
• Бинарное дерево растет, причем абсолютно естественным для него путем. Классическая хэш-таблица расти не может: чтобы увеличить размер хэш-таблицы, придется перехэшировать все элементы. Можно решить эту проблему (избежать перехэширования элементов) прикладыванием костылей к хэш-таблице, но это далеко не лучшее решение.
• В дереве нет свободных ячеек.
• Данные, лежащие в бинарном дереве, отсортированы. В хэш-таблице - нет.

И посмотри: в файловых системах и СУБД применяют B-деревья, которые являются дальнейшим развитием идеи бинарных деревьев поиска с рассчетом на уменьшение количества операций ввода-вывода при хранении дерева на диске. И где твои хэши?

Ситуация, когда ключи заранее известны - единственное оправданное применение хэшей.

Си, строки хаотичные, но ASCII > 31. Могут добавляться в процессе работы программы.

Я согласен, тут моя ошибка в том, что я допустил (never assume anything), что строки у автора не часто меняются. Построили хэш, а дальше ищем. Если нужно постоянно добавлять/удалять, то с деревом проще.

в файловых системах и СУБД применяют B-деревья

...

И где твои хэши?

Ну правильно, идеальную хэш функцию на все случаи жизни написать нельзя, потому там и деревья.

Ситуация, когда ключи заранее известны - единственное оправданное применение хэшей.

Ну вот да, опять же, mea culpa. Never assume anything.

Это всего 225^8 вариантов ключей... действительно разреженный массив получается;-)

Есть вся эта теория что лучше (map/hash и тд), и есть суровая реальность - много зависит от реализации, в частности от того, как данные в памяти разложены. Я бы посоветовал таки сделать поиск в лоб, а потом если окажется, что скорость поиска (именно поиска!) недостаточна, то сделать дерево предложенное franchukroman (по буквам) и сравнить производительность всего хозяйства в целом.

Если найдете какую подходящую hash-таблицу, их до черта должно быть - можете еще с ней сравнить.

пишется что хэш, что дерево достаточно просто, а с отладкой у хэша проще

А вот тут я бы не сказал. Хэш пишется-то просто, а вот с плохо подобранной хэш функцией и хреновой работой с коллизиями можно просрать все преимущества хэша, что он медленнее дерева искать будет и одни сплошные коллизии пойдут.

> в файловых системах и СУБД применяют B-деревья
> ...
> И где твои хэши?
Ну правильно, идеальную хэш функцию на все случаи жизни написать нельзя, потому там и деревья.

... а вовсе не потому, что по деревьям поиск быстрее.

Даже в общем случае дерево с большой вероятностью просрёт хэшу, так что я бы на месте автора проверил оба варианта, благо их «интерфейс» мало чем отличается.

А Вы таки в общем и целом правы. Я непосредственно эти вещи никогда не тестил (ну оно мне и не нужно по жизни), а тут онанимный алгоритмист подтолкнул, спасибо ему за это;-)

~/tmp> cat test.cpp 
//#include "test.hpp"
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#ifdef HASH
#include <unordered_map>
#else
#include <map>
#endif


using namespace std;

int main( int argc, const char** argv ) {
#ifdef HASH
        unordered_map<long,int> table; 
#else
        map<long,int> table; 
#endif
        float N = atof(argv[1]), sz = 0;
        double alpha = N/RAND_MAX;
        for(long i=0; i<N; i++ ) table[i] = table.size();
        double t0 = omp_get_wtime();
        for(int i=0; i<1e6; i++) if( table.find(random()*alpha) != table.end() ) sz++;
        double t1 = omp_get_wtime();
        printf( "%g %g\n", N, t1-t0 );
        return 0;
}
~/tmp> g++ -O3 -std=c++0x test.cpp -fopenmp -lgomp -lrt
~/tmp> for i in .125e6 .25e6 .5e6 1e6 2e6 4e6 8e6 16e6 32e6 64e6 ; do ./a.out $i ; done > map8.dat
~/tmp> g++ -DHASH -O3 -std=c++0x test.cpp -fopenmp -lgomp -lrt
~/tmp> for i in .125e6 .25e6 .5e6 1e6 2e6 4e6 8e6 16e6 32e6 64e6 ; do ./a.out $i ; done > hash8.dat

Проц model name : Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz

Вот что получается http://a-iv.ru/trash/map-vs-hash.png (число тактов на запрос от размера таблицы)

Если исходный массив забить случайными ключами, то оба варианта дают по 300 тактов на запрос - большинство запросов уходят в молоко. Ну а если все запросы попадают в таблицу, то map сливает в 10 раз. Все таки динамические структуры данных размазанные по памяти это зло;-)

они бы были злом - если бы хеш функция была бы идеальной

Ты идиот?

Съебал с моего ЛОРа - быстро, решительно.

не в один доступ к памяти
а к 1 рандомный доступ к памяти + еще один рандомный и чтение блока за ним

если с хешем усиленно работать - то 1 доступ - в кеше будет

это для варианта - когда есть хеш таблица - в которой элемент это указатель на простой массив ключей со значениями

Ещё один гондон Нечего сказать - лучше промолчи

Ну есть еще требование упорядочивания. Хотя можно построить хэш ф-ю которая будет возвращать упорядоченные значения;-)

Ты идиот?

Нет, он просто обыкновенное хамло. Пожалейте убогого, ему и так в жизни нелегко... он хорошо знает хэш-таблицы, но совершенно асоциален и не умеет общаться ни с кем, кроме таких же хамов.

не в один доступ к памяти

а к 1 рандомный доступ к памяти + еще один рандомный и чтение блока за ним

И даже возможная длинная цепочка коллизий не влияет? %)

А как работает std::unordered_map? Я тут ее потестил и впал в глубокую задумчивость... там хэш ф-я для лонга это сам лонг. И как тогда искать вторичный массив, если ключи разрежены? Если припахивать дерево - так оно оказывается на порядок шустрей std::map. То ли в std::map реализация хромает из за универсальности, то ли тут какая то магия...

Тут какая то хрень...

В unordered_map хэш ф-я для лонга по дефолту - сам long. как это работает я ума не приложу;-(

Если подсунуть ей хэш ф-ю i%256 - сливает map-у на порядок сразу, и дальше квадратичный рост...

ближе к делу

http://uthash.sourceforge.net/
хеш библиотека для С чисто в .h файле

#include «uthash.h»

HASH_ADD_INT( users, id, s );
HASH_FIND_INT( users, &user_id, s );
HASH_DEL( users, user);

unordered_map появился уже после того, как я перестал программировать на Си++ :)

Но hash_map тогда ведь уже был? Вроде как это он же;-)

... раздался голос со стороны параши.

а ты уверен что этот unorder это именно хеш вообще ?

а ты уверен что этот unorder это именно хеш вообще ?

инфа 100%

Да. Это обертка для std::_Hashtable, ну а дальше там сплошное вырвиглазие. Есть у меня чуйка, что там первичный поиск половинным делением идет или что то вроде того...

ну - иногда хешем называеют бинарное дерево - где индекс этот хеш от ключа
яб неназвал это хешем - это именно и есть бинарно дерево

Ну, тогда если генерить хэш ограниченным (как и полагается для порядочных хэш-таблиц), то дальше на больших N в тестах просто все сливается из-за коллизий, как ис следует из рафинированной теории;-)

Но вообще конечно все зависит от задачи, спектра значений ключа, и т.д. Т.е. оптимум определяется только экспериментально...

ЛОР, ты меня расстраиваешь. Уровень вопросов падает все ниже и ниже.

Это вторая причина, по которой я в последние 2-3 недели даже техразделы просматриваю только по заголовкам в rss. Это грустно.

Доки не читают даже по самым базовым вещам.

Вот. Это главная причина деградации. И ведь ещё зачастую нагло врут, пишут нечто вроде: «маны и гугл результатов не дали». Лентяи!

сливаеться сливаеться - но все на свете ограниченно
памяти вот всего несколько гиг и так далее

зато когда оно работает оптимально ... да и добавление и удаление элементов
это все настолько просто и быстро - что и не юзал бы больше ничего

Но хуже бинарного поиска;-)

Не знаю, рассказывал ли тебе кто, но внутри каждого bucket'а ты волен творить что угодно. В том числе и хранить отсортированный массив ключей, по которому делать свой любимый бинарный поиск.

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

это все настолько просто и быстро - что и не юзал бы больше ничего

А потом получаются атаки вроде http://www.opennet.ru/opennews/art.shtml?num=32698

а хэш-таблица при правильно подобранных ключах может заставить тебя потратить на поиск O(N) сравнений

А на улице может убить метеоритом, упавшим на голову.

Намного лучше будет сделать дерево по буквам

В изотерической стране сферических эльфов и лепреконов — безусловно.

Бинарным деревьям ничего не случится на миллиардах записей.

Я так понимаю, что речь все-таки о стране эльфов и лепреконов, где не существует затрат на балансировку дерева?

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

Это тест, просто тест //Ваш КО

Не знаю, рассказывал ли тебе кто, но внутри каждого bucket'а ты волен творить что угодно. В том числе и хранить отсортированный массив ключей, по которому делать свой любимый бинарный поиск.

O(log(N)) vs O(log(N/n_k)) при n_k<<N??? Я не настолько вели и умен, что бы понять сакральный смысл подобных действий.

все зависит от реализации

все зависит от реализации

Реализация, которая избегает таких ошибок, уже не простая (и, наверное, не такая быстрая).

простая - рандом составляющая в хеше

А на улице может убить метеоритом, упавшим на голову.

Может. Но метеоритам не свойственны намерения, в отличии от злоумышленников, имеющих целью заставить не работать твою программу.

В изотерической стране сферических эльфов и лепреконов — безусловно.

Почему? Стоимость поиска по такому дереву равна стоимости генерации из искомой строки текста. Недочет только в том, что на хранение этого дерева на больших строках уйдет много памяти.

Затраты на балансировку дерева всегда меньше, чем на вставку элемента, после вставки которого эта самая балансировка осуществляется. Иными словами, падение быстродействия в самом клиническом случае в 2 раза.

Я не настолько вели и умен, что бы понять сакральный смысл подобных действий.

Во-первых, n_k << N — это твоя нездоровая фантазия. Во-вторых, для осуществления бинарного поиска нужны упорядоченные последовательности и если грамотно подойти к выбору параметров хэш-таблицы можно положиться на «небольшую длину» таких последовательностей в bucket'ах со всеми вытекающими оптимизациями.