map::insert

Тема в разделе "LANGS.C", создана пользователем cupuyc, 5 авг 2011.

  1. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    вот такой код

    Код (Text):
    1. #include <Windows.h>
    2. #include <hash_map>
    3.  
    4. int main()
    5. {
    6.     stdext::hash_map<size_t, size_t>    hm;
    7.  
    8.     for (int i = 0; i < 1024; ++ i)
    9.     {
    10.         hm.insert(stdext::hash_map<size_t, size_t>::value_type(my_rand(), i));
    11.     }
    12. }
    даёт 330 коллизий. my_rand() - возвращает рандомное 32 битное число. на 1000 элементов 300 коллизий!
     
  2. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Коллизии вообще ни при чем, нужно смотреть среднюю длину списка. hash_map к тому же меняет свой размер при таком добавлении. А вдруг там получилось 400 списков из одного элемента и 300 списков из двух элементов, вот вам и 300 коллизий. А средняя длина списка ~1.5 :)

    P.S. Вот такой код налабал у себя:
    Код (Text):
    1.     stdext::hash_map<size_t, size_t> hm;
    2.     for (int i = 0; i < 1024; ++i)
    3.     {
    4.       rnd_next();
    5.       hm.insert(stdext::hash_map<size_t, size_t>::value_type(rnd_seed, i));
    6.     }
    7.     printf( "Buckets count: %d\r\n", hm.bucket_count() );
    8.     int k = 0;
    9.     int n = 0;
    10.     for (int i = 0; i < hm.bucket_count(); ++i )
    11.     {
    12.       if (hm.bucket_size( i ) > 0)
    13.       {
    14.         n += hm.bucket_size( i );
    15.         ++k;
    16.       }
    17.       printf( "Bucket %d: %d elements\r\n", i, hm.bucket_size( i ) );
    18.     }
    19.     printf( "Average list length: %.3f", double( n ) / k );
    Получилось на 1024 элемента он сделал 256 ячеек таблицы, средняя длина списка - чуть больше 4.

    P.P.S. Хотя если в самом начале добавить вызов
    Код (Text):
    1. hm.rehash(1024);
    то средняя длина списков уменьшается до 1.5. И таблица не будет лишний раз перестраиваться при добавлении элементов.
     
  3. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    в данной задаче хашмапа всё-равно не подходит, т.к. элементы должны быть отсортированы. можно, конечно, что-то напрядумывать с сортированным массивом вместо списка.. хз..