мне надо хранить список значений строка-число
использую для этого 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.