VPF::unordered_map<int,int> vs std::map<int,int> - Форум программистов

borisbn

Дата 11.11.2011, 01:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Пообщался на ИРКе на эту тему - стало яснее. Приведу выдержки

Цитата

borisbn: Hi, here is a little test - http://ideone.com/UndgI. Question: why *unordered_map* is so quicker, then 'ordered' one ?
kuponut: borisbn: unordered_map should be quicker than an ordered...it's offering less promises, namely whether the data is in sorted order
borisbn: kuponut: but I didn't use string or other big arrays as a key. I used int. I think, that hash value for int == int
kuponut: borisbn: <map> offers insert/lookup os O(log n), <unordered_map> as amortized O(1)
borisbn: kuponut: you want to say, that unordered_map converts my int into the array index and just returns arr[ n ] ?
kuponut: borisbn: well, I'd imagine that unordered_map still hashes your int to some other int value, which is used as an index into an array
kuponut: borisbn: and there shouldn't (hopefully) be many entries in that index of the array, no matter how many total elements are in the map
borisbn: kuponut: in my test I have a map with size ~1 000 000. and I picked up them all. How could they use an array lesser then 1 000 000 ?
kuponut: borisbn: each index in the array holds linked nodes...two keys might hash to the same index, so in that index will be two nodes with the two values
kuponut: borisbn: so a lookup has to check both nodes at that index

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 11.11.2011, 01:40 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(borisbn @ 11.11.2011, 01:18

)

ИРКе

это чё?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

borisbn

Дата 11.11.2011, 06:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

http://ru.wikipedia.org/wiki/IRC - онлайн чат (древний как понятно что мамонта, но всё ещё актуальный).
Существует несколько серверов, предоставляющих IRC-чат. Самый крупный - freenode.net.
На каждом сервере есть н-ное количество тематических каналов. На freenode - ~30000 каналов.
Я там зависаю на #c++ (~1500 участников), #qt (~1000) и #boost (~800).
Клиенты - Веб-клиент из браузера ( http://webchat.freenode.net/ ), Miranda, mIRC, QIP Infium + плагин для протокола IRC.
Я пользую последний. Не самый удобный, но так я получаю 3 в 1 (jabber, twitter, IRC).

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 11.11.2011, 06:52 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

borisbn, очень познавательно smile

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

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

volatile

Дата 11.11.2011, 15:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

borisbn, интересный тест, спасибо.

Безусловно, буст работает шустро, особенно на коротких значениях ключа, типа инт.
Тест на студии вашего кода, полностью подтвердил ваши данные, (с поправкой того что мой комп, в ~1.5 раза медленее вашего smile

).
Но относительные занчения были прмерно такие-же.
Студийный стл::мап, надежно проигрывал, против буст-анордеред.
Студийный stdext::hash_map оказался не на много лучше.

И меня заинтересовало, насколько буст будет хорош, на длинных значениях.
В качестве ключей использовал std::string с разной длиной. 4, 30 и 300.
При длине 4, результаты полностью совпали с вашими.

При длине ключа 30:
hash_map, уже догнал, и даже немного перегнал boost

Код


insert:
std   :      797 ms.
boost :      578 ms.
hash  :      563 ms.

std   :      484 ms.
boost :      172 ms.
hash  :      109 ms.

std   :      485 ms.
boost :      171 ms.
hash  :      110 ms.


find[] :
std   :      500 ms.
boost :      156 ms.
hash  :      109 ms.

std   :      500 ms.
boost :      157 ms.
hash  :      125 ms.

std   :      484 ms.
boost :      156 ms.
hash  :      125 ms.


find.find :
std   :      485 ms.
boost :      156 ms.
hash  :      109 ms.

std   :      485 ms.
boost :      156 ms.
hash  :      125 ms.

std   :      484 ms.
boost :      157 ms.
hash  :      109 ms.

При длине ключа 300:
boost отстает не только от hash_map, но даже и от std::map

Код


insert:
std   :     1094 ms.
boost :     2859 ms.
hash  :     1250 ms.

std   :      672 ms.
boost :     1063 ms.
hash  :      375 ms.

std   :      672 ms.
boost :     1062 ms.
hash  :      375 ms.


find[] :
std   :      672 ms.
boost :     1063 ms.
hash  :      390 ms.

std   :      656 ms.
boost :     1079 ms.
hash  :      375 ms.

std   :      671 ms.
boost :     1063 ms.
hash  :      391 ms.


find.find :
std   :      656 ms.
boost :     1078 ms.
hash  :      375 ms.

std   :      656 ms.
boost :     1078 ms.
hash  :      375 ms.

std   :      657 ms.
boost :     1078 ms.
hash  :      375 ms.

Код, на котором я тестировал. (На 95% процентов, код скопиапщен у borisbn)

Код


std::map< std::string, int > std_m;
boost::unordered_map< std::string, int > boost_m;
stdext::hash_map< std::string, int > hash_m;

std::vector< std::string > values;

const int N = 300000;
const int STRLEN = 300;

//const int N = 300000;
//const int STRLEN = 30;

//const int N = 1000000;
//const int STRLEN = 4;



// -----------------------------------------------------
template <typename TCONT, typename TARR>
double test_insert (TCONT & cont, TARR const & arr)
{
   int t1 = clock();
   for ( int i = 0; i < N; i++ )
   {
       cont[ arr[ i ] ] = i;
   }
   int t2 = clock();
   return (t2 - t1) / (double)CLOCKS_PER_SEC * 1000;
}

// -----------------------------------------------------
template <typename TCONT, typename TARR>
double test_find (TCONT & cont, TARR const & arr)
{
   int t1 = clock();
   int res = 1;
   for ( int i = 0; i < N; i++ )
   {
       res &= cont[ arr[ i ] ];
   }
   int t2 = clock();
   return (t2 - t1) / (double)CLOCKS_PER_SEC * 1000 + res; //здесь res, чтобы не соптимизировал :) res == 0;
}

// -----------------------------------------------------
template <typename TCONT, typename TARR>
double test_find_find (TCONT & cont, TARR const & arr)
{
   int t1 = clock();
   int res = 1;
   for ( int i = 0; i < N; i++ )
   {
      res &= cont.find( arr[ i ] )->second;
   }
   int t2 = clock();
   return (t2 - t1) / (double)CLOCKS_PER_SEC * 1000 + res; //здесь res, чтобы не соптимизировал :) res == 0;;
}


// -----------------------------------------------------
int main()
{
    values.reserve (N);
    for ( int i = 0; i < N; i++ )
    {
        static const char liters [] = "0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~";
        char newstr [STRLEN+1];
        for (int j=0; j<STRLEN; ++j)
             newstr [j] = liters [rand() % (sizeof liters - 1)];
        newstr [STRLEN] = 0;
        values.push_back( newstr );
    }
    
    std::cout << "insert:" << std::endl;
    for ( int k = 0; k < 3; k++ )
    {
        std::cout << "std   : " << std::setw( 8 ) << test_insert (std_m,   values) << " ms." << std::endl;
        std::cout << "boost : " << std::setw( 8 ) << test_insert (boost_m, values) << " ms." << std::endl;
        std::cout << "hash  : " << std::setw( 8 ) << test_insert (hash_m,  values) << " ms." << std::endl << std::endl;
    }

    std::cout << std::endl;
    std::cout << "find[] :" << std::endl;
    for ( int k = 0; k < 3; k++ )
    {
        std::cout << "std   : " << std::setw( 8 ) << test_find (std_m,   values) << " ms." << std::endl;
        std::cout << "boost : " << std::setw( 8 ) << test_find (boost_m, values) << " ms." << std::endl;
        std::cout << "hash  : " << std::setw( 8 ) << test_find (hash_m,  values) << " ms." << std::endl << std::endl;
    }

    std::cout << std::endl;
    std::cout << "find.find :" << std::endl;
    for ( int k = 0; k < 3; k++ )
    {
        std::cout << "std   : " << std::setw( 8 ) << test_find_find (std_m,   values) << " ms." << std::endl;
        std::cout << "boost : " << std::setw( 8 ) << test_find_find (boost_m, values) << " ms." << std::endl;
        std::cout << "hash  : " << std::setw( 8 ) << test_find_find (hash_m,  values) << " ms." << std::endl << std::endl;
    }
}

-----------

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

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

borisbn

Дата 11.11.2011, 17:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

volatile, очень интересно... Как раз следующим этапом я собирался сделать ключ из строки...
А вот результат Вашего нашего кода (со строкой), скомпилированного minGW 4.6.2 (вместо stdext::hash_map взят std::unordered_map)

Цитата

insert:
std   :      750 ms.
boost :      719 ms.
hash  :     1156 ms.

std   :      922 ms.
boost :      359 ms.
hash  :      469 ms.

std   :      922 ms.
boost :      375 ms.
hash  :      453 ms.

find[] :
std   :      953 ms.
boost :      375 ms.
hash  :      469 ms.

std   :      953 ms.
boost :      360 ms.
hash  :      484 ms.

std   :      953 ms.
boost :      359 ms.
hash  :      469 ms.

find.find :
std   :      969 ms.
boost :      359 ms.
hash  :      469 ms.

std   :      953 ms.
boost :      375 ms.
hash  :      453 ms.

std   :      969 ms.
boost :      359 ms.
hash  :      469 ms.

Цитата(volatile @ 11.11.2011, 15:13

)

И тип контейнера лучше подбирать на реальном, конкретном приложении.

Вывод: и компилятор тоже smile

P.S. Недавно возился со студийным hash'ем... У меня получилось, что он игнорирует последний символ в строке, т.е.
hash( "abcdefg0" ) == hash( "abcdefg1" )... м.б. это так и надо, а м.б. это глюк...

Добавлено через 2 минуты и 37 секунд
я так понял, что делить на [] и find теперь уже не нужно - это был глюк minGW 4.4.0

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

volatile

Дата 11.11.2011, 23:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(borisbn @ 11.11.2011, 17:30

)

Недавно возился со студийным hash'ем... У меня получилось, что он игнорирует последний символ в строке, т.е.
hash( "abcdefg0" ) == hash( "abcdefg1" )... м.б. это так и надо, а м.б. это глюк...

Не совсем понял, как это игнорирует?
   hash_m ["abcdefg0"] = 1;
   hash_m ["abcdefg1"] = 2;
   hash_m ["abcdefg2"] = 3;
   std::cout << hash_m.size () << std::endl;
Вывод 3, т.е разные хеши.

Конкретно сами числа хешей тоже можно посмотреть, приватный метод _Hashval. Там для данных строк хеши разные (2,3,0) соответственно.

Цитата(borisbn @ 11.11.2011, 17:30

)

вот результат Вашего нашего кода (со строкой), скомпилированного minGW 4.6.2 (

Да, там безусловно буст рулит. (Или стд не рулит?... smile

)

borisbn

Дата 11.11.2011, 23:38 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

не... я смотрел непосредственно ф-цию std::tr1::hash. для приведённых Вами строк она выдаст одно и то же значение. потом, конечно, map это всё разрулит

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

volatile

Дата 12.11.2011, 00:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(borisbn @ 11.11.2011, 23:38

)

для приведённых Вами строк она выдаст одно и то же значение

Щас, поставил брекпоинты, и посмотрел в дебагере значения хешей.
Для приведенных строк, значения подсчитываются в следеющей процедуре (файл <xhash>)

Код


template <class _InIt>
    inline size_t _Hash_value(_InIt _Begin, _InIt _End)
    {    // hash range of elements
    size_t _Val = 2166136261U;
    while(_Begin != _End)
        _Val = 16777619U * _Val ^ (size_t)*_Begin++;
    return (_Val);
    }

Брякпоинты ставил на выходе функции.
Конкретно значения хешей, для приведенных строк:
_Val = 3802362189
_Val = 3802362188
_Val = 3802362191

boostcoder

Дата 12.11.2011, 00:33 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(volatile @ 12.11.2011, 00:17

)

_Val = 16777619U * _Val ^ (size_t)*_Begin++;

FNV-1x

в GCC этот алгоритм используется только для строковых типов.

Добавлено @ 00:42
тут специализации: http://gcc.gnu.org/git/?p=gcc.git;a=blob;f...ab4ba92;hb=HEAD
тут реализация мур-мур хеш и FNV-1: http://gcc.gnu.org/git/?p=gcc.git;a=blob;f...217bf36;hb=HEAD

Это сообщение отредактировал(а) boostcoder - 12.11.2011, 00:42

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

volatile

Дата 12.11.2011, 00:49 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(boostcoder @ 12.11.2011, 00:33

)

в GCC этот алгоритм используется только для строковых типов.

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »