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

typedef map< string, int, less< int > > IntList;
IntList intList;

подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

S>typedef map< string, int, less< int > > IntList;
S>IntList intList;
S>подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

Хеш?

Здравствуйте, sergey2b, Вы писали:

S>мне надо хранить список значений строка-число
S>использую для этого map

S>typedef map< string, int, less< int > > IntList;

странное какое-то объявление. не находите? Почему там less<int>, а не less<string>?

S>подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

при вашей постановке вопроса получается что кроме std::map ничего использовать нельзя и требуется ускорить чтение из std::map.
Правильно я понял вопрос?

Здравствуйте, sergey2b, Вы писали:

S>мне надо хранить список значений строка-число
S>использую для этого map

S>typedef map< string, int, less< int > > IntList;
S>IntList intList;

S>подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

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

Здравствуйте, korzhik, Вы писали:


K>странное какое-то объявление. не находите? Почему там less<int>, а не less<string>?
вы правы

K>при вашей постановке вопроса получается что кроме std::map ничего использовать нельзя и требуется ускорить чтение из std::map.
K>Правильно я понял вопрос?

нет можно использовать что угодно
делаю кешь для хранения ключь стринг — значение int
будет примерно 100k записей, время вставки несильно критично, желательно уменьшить время чтения

Здравствуйте, sergey2b, Вы писали:

S>нет можно использовать что угодно

Лучше всего ипользовать trie. Например Patricia trie. Где взять — не знаю. Я сам себе написал.

любой wrote:

> Лучше всего ипользовать trie. Например Patricia trie. Где взять — не
> знаю. Я сам себе написал.

Так внутри мапы дерево и сидит как раз.

Автор, тебе не подходит O(log N) ? Сколько ж тебе надо ?

Ну если не подходит, ищи реализацию хэштаблиц, они O(1),
да только вот беда -- статистически нестабильна производительность на
произвольных ключах. Может деградировать в O(N) например.
Из реализаций говорят есть hashmap-ы a la STD в некоторых
реализациях STL

Здравствуйте, MasterZiv, Вы писали:

>> Лучше всего ипользовать trie. Например Patricia trie. Где взять — не
>> знаю. Я сам себе написал.

MZ>Так внутри мапы дерево и сидит как раз.

Грубо говоря, внутри map<string, int> в качестве ключей сидит строка, а внутри специализированных деревьев — буква.
Соответственно, std::map им не конкурент ни по скорости, ни по памяти.
А уж если нужен поиск с частичным совпадением, например, для автокомплита, то std::map вообще не годится.

MZ>Автор, тебе не подходит O(log N) ? Сколько ж тебе надо ?

MZ>Ну если не подходит, ищи реализацию хэштаблиц, они O(1),
MZ>да только вот беда -- статистически нестабильна производительность на
MZ>произвольных ключах. Может деградировать в O(N) например.
MZ>Из реализаций говорят есть hashmap-ы a la STD в некоторых
MZ>реализациях STL

std::tr1::unordered_map уже вполне стандартна.

>> Лучше всего ипользовать trie.

MZ>Так внутри мапы дерево и сидит как раз.

trie != tree

MZ>Автор, тебе не подходит O(log N) ? Сколько ж тебе надо ?
MZ>Ну если не подходит, ищи реализацию хэштаблиц, они O(1),

то что хэши O(1) это самообман. Они O(1) если считать что вычисление хэша это константная операция. Но понятно, что с ростом N понадобится увеличивать битность хэша, а значит и операцию вычисления хэша. так что там тот же логарифм спрятан. Обосновывать хорошесть хэшей тем что они O(1) а дерево O(log N) это лукавство. Если хэш и лучше, то он лучше именно на практике, а не теоретически.

Если только string, и никаких ID, то что то там при проектировании забыли. Но если уж все так, то как советовали выше — хэширование наше всё.

Здравствуйте, sergey2b, Вы писали:

S>мне надо хранить список значений строка-число
S>использую для этого map

S>typedef map< string, int, less< int > > IntList;
S>IntList intList;

S>подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

Ternary tree (trie)
Имплементация здесь:
http://rsdn.ru/forum/src/824201.1.aspx

Автор: c-smile
Дата: 25.09.04

Надо помнить что:

A trie is optimized for speed at the expense of size.

Скорость нахождения значения пропорциональна только длине строки. Т.е. O(1) best и worst case.

Здравствуйте, Тот кто сидит в пруду, Вы писали:

ТКС>Грубо говоря, внутри map<string, int> в качестве ключей сидит строка, а внутри специализированных деревьев — буква.
У Patricia trie даже не буквы, а биты сидят. Причём только те, которые значимы для процесса поиска в заданном наборе строк.

Здравствуйте, c-smile, Вы писали:

CS>Ternary tree (trie)
CS>Имплементация здесь:
CS>http://rsdn.ru/forum/src/824201.1.aspx

Автор: c-smile
Дата: 25.09.04

Интересно.

Сделал пробную реализацию.
Сделал тест на 1 млн слов (числовые последовательности).

Результат по скорости оказался идентичный использованию std::map с числовым ключом и использования crc32 для вычисления ключа по строке.
Такие дела...


CS>Скорость нахождения значения пропорциональна только длине строки. Т.е. O(1) best и worst case.

Это неверно.

Также зависит от результата построения дерева, который зависит от количества слов и порядка их вставки.

Здравствуйте, sergey2b, Вы писали:

S>мне надо хранить список значений строка-число
S>использую для этого map

S>typedef map< string, int, less< int > > IntList;
S>IntList intList;

S>подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

Если алфавитная сортировка не принципиальна, то можно сперва сравнивать длины строк, а потом сами строки, да ещё и попеременно с начала и с конца, чтобы минимизировать количество сравнений:

int fastCompare( const string& s1, const string& s2 )
{
   typedef string::size_type size;
   size n1 = s1.length();
   size n2 = s2.length();
   if( n1 > n2 ) return 1;
   if( n1 < n2 ) return -1;
   size i = 0, j = n1-1;
   for( ; i <= j; ++i, --j )
   {
      {
         string::value_type c1 = s1[j];
         string::value_type c2 = s2[j];
         if( c1 > c2 ) return 1;
         if( c1 < c2 ) return -1;
      }
      {
         string::value_type c1 = s1[i];
         string::value_type c2 = s2[i];
         if( c1 > c2 ) return 1;
         if( c1 < c2 ) return -1;
      }
   }
   return 0;
}

template <class string>
class FastComp
{
public:
   bool operator()( const string& s1, const string& s2 ) const
   {
      return fastCompare( s1, s2 ) < 0;
   }
};

Использовать этот FastCompare в качестве компаратора.

А если нужно ещё больше ускорить без особых затрат, то можно добавить хеширование по первому или последнему символу, а ещё лучше по их суперпозиции:

std::vector<unsigned, std::map<..>>

Но если хочется потренироваться, то можно и специализированное буквенное дерево написать — там работы на час где-то.

Исправление: template <class string> — это опечатка, выдирал из своего кода с поиском и заменой. У меня было обобщено по типу строки

Здравствуйте, Тот кто сидит в пруду, Вы писали:

ТКС>А уж если нужен поиск с частичным совпадением, например, для автокомплита, то std::map вообще не годится.

подскажите пожалуйста что можно почитать как делать поиск по ключу с частиным совпадением
например типа "ab*fg*k" где * любые символы
надо не для этой задачи но интерестно понять как такое можно сделать (про agrep я знаю но он не подходит так как template поиска может быть неесколько)

Здравствуйте, rus blood, Вы писали:

RB>Здравствуйте, c-smile, Вы писали:

CS>>Ternary tree (trie)
CS>>Имплементация здесь:
CS>>http://rsdn.ru/forum/src/824201.1.aspx

Автор: c-smile
Дата: 25.09.04

RB>Интересно.

RB>Сделал пробную реализацию.
RB>Сделал тест на 1 млн слов (числовые последовательности).

Для больших наборов уже начинает играть роль cache misses и всё такое прочее.

RB>Результат по скорости оказался идентичный использованию std::map с числовым ключом и использования crc32 для вычисления ключа по строке.
RB>Такие дела...

Я не понял что это за конструкция и что дает crc32

CS>>Скорость нахождения значения пропорциональна только длине строки. Т.е. O(1) best и worst case.

RB>Это неверно.

А неверно что именно?
Каждый символ входной строки просматривается ровно один раз. Т.е. никаих log(n) strcmp нет.

RB>Также зависит от результата построения дерева, который зависит от количества слов и порядка их вставки.

Там в моей статье есть ссылка на эту вот статью в Dr.Dobb: http://www.drdobbs.com/184410528
по которой все и делалось в своё время. Там порядок вставки освещен.

Здравствуйте, c-smile, Вы писали:

CS>Для больших наборов уже начинает играть роль cache misses и всё такое прочее.

Мы говорим о ternary tree?
Что ты называешь "cache misses"?

CS>Я не понял что это за конструкция и что дает crc32

Обычный map из STL.
Только ключом вместо строк выступают соответствующие им уникальные числовые идентификаторы.
Для простоты взял crc32, хотя есть и более эффективные варианты.


CS>Каждый символ входной строки просматривается ровно один раз. Т.е. никаих log(n) strcmp нет.

Это верно.

Только многие (в общем случае каждый) из этих символов придется сравнить с большим количеством символов промежуточных нод дерева, которые задают "маршрут" до конечного "листа". И длина такого "маршрута" (и общее количество сравнений) будет зависеть от количества элементов и порядка вставки слов, т.е. от полученной структуры дерева.

Конечно, это будет быстрее, чем использовать строковые ключи в мапе и strcmp, но ведь можно же использовать уникальные числовые коды строк. Выигрыш у ternary tree есть, но буквально доли процента.


CS>Там в моей статье есть ссылка на эту вот статью в Dr.Dobb: http://www.drdobbs.com/184410528
CS>по которой все и делалось в своё время. Там порядок вставки освещен.

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

Здравствуйте, sergey2b, Вы писали:

S>подскажите пожалуйста есть ли возможность ускорить работу с map на чтение для такого случая

Ну например, если у вас достаточно часто происходит серия повторных обращений с одним и тем же ключем (а это типичная ситуация для некоторых случаев использования), можно запоминать ключ/результат последнего обращения и смотреть на него прежде, чем лезть в map.

Здравствуйте, sergey2b, Вы писали:

ТКС>>А уж если нужен поиск с частичным совпадением, например, для автокомплита, то std::map вообще не годится.

S>подскажите пожалуйста что можно почитать как делать поиск по ключу с частиным совпадением
S>например типа "ab*fg*k" где * любые символы
S>надо не для этой задачи но интерестно понять как такое можно сделать (про agrep я знаю но он не подходит так как template поиска может быть неесколько)

Про поиск с частичным совпаденем с помощью троичных деревьев у Седжвика более-менее подробно написано в Algorithms in Java. В его же книжке по алгоритмам на плюсах это кажется оставлено в качестве упражнения.

D>то что хэши O(1) это самообман.

а почему мне смайлики ставят? Поясните, что я написал смещного?
Один человек я еще понимаю -- пыхнуть мог, завидую. А у товарища Зудина зазудел стадный инстинкт?

Здравствуйте, dilmah, Вы писали:


D>>то что хэши O(1) это самообман.

D>а почему мне смайлики ставят? Поясните, что я написал смещного?
D>Один человек я еще понимаю -- пыхнуть мог, завидую. А у товарища Зудина зазудел стадный инстинкт?

Потому что глупость сморозил, поэтому и смайлики. И не груби.

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

С ростом N операция вычисления хеша, вообще-то не меняется.
При любом N все сводится к банальному hash_value % n, где hash_value — собственно, результат "операции вычисления хеша", зависит от длины ключа, а n — количество хеш-карманов (ну или "диапазон рассеивания").

При некотором навыке можно добиться от хеш таблицы даже O(N).

Если хэш и лучше, то он лучше именно на практике, а не теоретически.

Заявление подкреплено практикой или только теоретические рассуждения?

SVZ>Потому что глупость сморозил, поэтому и смайлики. И не груби.

SVZ>

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

SVZ>С ростом N операция вычисления хеша, вообще-то не меняется.

для N элементов необходима хэш-таблица размером K*N где K -- некая константа. Как ты понимаешь с ростом N настанет момент когда 32-битного хэша начнет не хватать. То есть с ростом N растет битность хэша, а значит и меняется операция хэширования.

Ах, ты не рассматривал такие большие N? Ну так и разговор был про асимптотическую сложность.

Здравствуйте, dilmah, Вы писали:

D>для N элементов необходима хэш-таблица размером K*N где K -- некая константа. Как ты понимаешь с ростом N настанет момент когда 32-битного хэша начнет не хватать. То есть с ростом N растет битность хэша, а значит и меняется операция хэширования.

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

Но мы увлеклись, топикстартеру для 100 килозаписей простой хеш-таблицы без прибамбасов хватит за глаза.

SVZ>Адресное пространство когда-нибудь заканчивается

я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)

Здравствуйте, dilmah, Вы писали:

D>а почему мне смайлики ставят? Поясните, что я написал смещного?

... он лучше именно на практике, а не теоретически.

Забавно

Здравствуйте, dilmah, Вы писали:


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 растет битность хэша, а значит и меняется операция хэширования.
Не надо все в одну кучу, в общем случае на ходу ни размер хэш таблицы, ни битность хэша не меняется. Когда не хватает битности, делаем хэш таблицу меньшего размера (уменьшаем К) и опять всего хватает, либо увеличиваем битность хэша, но это ведь не делается в рамках одной операции. Сложность оценивается для операций вставки, чтения, когда хэш таблица сконфигурирована: битность, размер таблицы константны.

Здравствуйте, dilmah, Вы писали:


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) — это самообман?
Ладно, пожалуй спорить не буду, пойду лучше подтяну теорию. В данном вопросе я больше практик чем теоретик