21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
1

Одинаковое время поиска boost::unrdered_map vs std::map

29.11.2017, 14:49. Показов 895. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Почемуто получаю одинаковое время на поиск как между контейнерами так и от одного размера к другому(для std::map тоже)
Толи я чтото напутал, толи....?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef HASH_WRAPPER_H
#define HASH_WRAPPER_H
#include "common.h"
#include "custstring.h"
 
namespace std
{
    struct THasher;
    typedef unordered_map<std::string,const char *,THasher> THContainer1;
    struct THasher
    {
      std::size_t operator () (const std::string &key) const
      {
            std::size_t result = 0;
            if (strlen(key.c_str()) == 1)
            {
                result = key[0];
                boost::hash_combine(result, boost::hash_value(key));
            }
            else
            {
                result = 0;
                boost::hash_combine(result, boost::hash_value(key));
            }
            return result;
      }
    };
}
typedef boost::unordered_map<std::string,const char *,std::THasher> TBHContainer1;
typedef std::unordered_map<std::string,const char *> THContainer2;
 
extern void test_hash();
 
#endif // HASH_WRAPPER_H

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "hash_wrapper.h"
 
const char * strarr[] = { "Hellow World !!!", "C++11 prog lang", "qtcreator" };
const char * newstr = "passed";
 
//#define debug_node
const auto c_maxindex = 13500;
template <typename T1>
unsigned show_collision(T1 & _map)
{
      unsigned ncollisions = 0;
      for (unsigned i = 0; i< _map.bucket_count(); ++i)
      {
        if (_map.bucket_size(i) > 1)
        {
            ncollisions += _map.bucket_size(i) - 1;
            if (_map.bucket_size(i) > 4)
            {
                std::cout << "bucket #" << i << " has " << _map.bucket_size(i) << " elements.\n";
            }
        }
      }
      return ncollisions;
}
 
template <typename T1>
std::pair<unsigned,unsigned> test_validality(T1 & _map)
{
    typename T1::iterator it;
    std::string key;
    std::pair<unsigned,unsigned> result;
    unsigned nfound = 0;
    unsigned empty = 0;
    unsigned char noise = 0;
    unsigned maxitems = _map.size();
    for (unsigned i1 = (c_maxindex/2) - 50; i1 < (c_maxindex/2) + 50; ++i1)
    {
        key = std::to_string(i1 + (noise%3)); noise++;
        it = _map.find(key);
        if (it != _map.end())
        {
            nfound++;
            it->second = newstr;
#ifdef debug_node
            if ((maxbuckets < 30) || (i1 < 10))
            {
                std::cout << "data: " << it->second << std::endl;
            }
#endif
        }
        else
        {
            empty++;
        }
    }
    result = std::pair<unsigned,unsigned>(nfound,empty);
    return result;
}
 
template <typename T1,typename ...Args>
void profile_func(T1 (*f)(Args&...),T1& t1 ,Args&... _args)
{
    using boost::chrono::duration_cast;
    using boost::chrono::microseconds;
    typedef boost::chrono::high_resolution_clock clock;
    typedef boost::chrono::time_point<clock> time_point;
    time_point tb__start, tb__end;
    long long duration = 0;
    tb__start = clock::now();
    t1 = f(_args...);
    tb__end = clock::now();
    duration = duration_cast<microseconds>(tb__end - tb__start).count();
    std::cout << " duration is:" << duration << std::endl;
}
 
template std::pair<unsigned,unsigned> test_validality<std::THContainer1>(std::THContainer1 & _map);
 
void test_hash()
{
 
    std::string str_item;
    std::pair<unsigned,unsigned> nefound;
    // немного кастомная буст-хеш-функция
    TBHContainer1 mapa1;
    std::map<std::string,const char *> mapu;
    mapa1.max_load_factor(0.98);
    // Заполнение хеш-таблицы
    std::cout << "boost collisions with buckets > 4: ";
    for (int i1 = 0; i1 < c_maxindex; i1++)
    {
        str_item = std::to_string(i1);
        mapa1.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
        mapu.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
    }
    std::cout << std::endl;
    // Вывод списка вёдер (buckets)
    std::cout << "number of collisions is " << show_collision(mapa1) << std::endl;
    std::cout << "bucket count " << mapa1.bucket_count() << std::endl;
    std::cout << "load factor " << mapa1.load_factor() << std::endl;
 
    // stl-хеш-функция,
    THContainer2 mapa2;
    std::cout << "stl collisions with buckets > 4: ";
    mapa2.max_load_factor(0.98);
    for (int i1 = 0; i1 < c_maxindex; i1++)
    {
        str_item = std::to_string(i1);
        mapa2.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
    }
    std::cout << std::endl;
    std::cout << "number of collisions is " << show_collision(mapa2) << std::endl;
    std::cout << "bucket count " << mapa2.bucket_count() << std::endl;
    std::cout << "load factor " << mapa2.load_factor() << std::endl;
 
 
    std::cout << "boost::unordered_map custom hasher: ";
    profile_func(&(test_validality<decltype(mapa1)>),nefound,mapa1);
    std::cout << "valid item found: " << nefound.first << std::endl;
 
    std::cout << "std::map (ordered): ";
    profile_func(&(test_validality<decltype(mapu)>),nefound,mapu);
    std::cout << "valid item found: " << nefound.first << std::endl;
 
    std::cout << "std::unordered_map std::hash:";
    profile_func(&(test_validality<decltype(mapa2)>),nefound,mapa2);
    std::cout << "valid item found: " << nefound.first;
 
}
Добавлено через 31 минуту
А вот если компилировать шлангом, то разница есть. Неужили gcc std::map сделан через хеш таблицы?

Добавлено через 3 минуты
https://wandbox.org/permlink/btb2unPU6CfSjZTT

Добавлено через 12 часов 55 минут
где Croesmah ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.11.2017, 14:49
Ответы с готовыми решениями:

Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map?
Здравствуйте. Возможно ли создать контейнер std::map, в котором в качестве значения была бы...

Emplace в std::map. Как добавить элемент в std::map без копирования?
здравствуйте... есть ли способ не писать так: std::map&lt;int, char&gt; ksa;...

Не могу разобраться как обновить в std::map<std::string, вектор_структур>
Не могу разобраться как обновить вектор структур после его добавления в map без удаления и...

Стоит ли очищать в деструкторе std::map , std::vecotor?
У меня ещё один нубский вопрос :) Вот если в классе объявлены мапы и вектора, которые по ходу...

10
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,113
Записей в блоге: 2
29.11.2017, 18:07 2
Цитата Сообщение от Pechkin80 Посмотреть сообщение
Неужили gcc std::map сделан через хеш таблицы?
Ага, со sleep'ами внутри функции поиска

Ты замеряешь на мапе размером 13500, логарифм от этого будет 13, т.е. ты сравниваешь работу хеш функции + индексация против 13 сравнений. Как бы не удивительно, что разницы не видно, дольше времени уйдет на обращение к функции получения времени, чем на поиск по мапе.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
29.11.2017, 18:14  [ТС] 3
Kastaneda, Ну я по всякому пробовал. Как надо чтобы результат был ?

Добавлено через 2 минуты
чтоб можно было увидеть существенную разницу, которая соответствовала теоретической оценки производительности. Там где логарифм - там логарифм. Там где константа - там константа.
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,113
Записей в блоге: 2
29.11.2017, 18:47 4
Цитата Сообщение от Pechkin80 Посмотреть сообщение
Там где логарифм - там логарифм. Там где константа - там константа.
Для этого нужно замерять время поиска на мапах разного размера. Где при 1000000 и 100 000000 элементов одинаковое время поиска, там константа, где различается - смотришь на сколько различается и попадает ли это под логарифм.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
29.11.2017, 18:49  [ТС] 5
Kastaneda, Ну я в первом посте сообщил что и это тоже проделовал.
Ваши результаты другие ?
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,113
Записей в блоге: 2
29.11.2017, 19:04 6
Цитата Сообщение от Pechkin80 Посмотреть сообщение
Ваши результаты другие ?
Я не запускал.

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

Кстати вмешательство в std это UB, тем более, что это и не надо.

Добавлено через 2 минуты
C++
1
if (strlen(key.c_str()) == 1)
это шутка такая?
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
29.11.2017, 19:08  [ТС] 7
Kastaneda, Я без того что вы называете шуткой пробовал т.е. на стандартной буствской хеш-функции. Разговоры про то какой код плохой негодный кошмарный ужасный смотреть на него невозможно увидут очень далеко от темы. Выкеньти что считаете ненужным или свой пример в студию.
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,113
Записей в блоге: 2
29.11.2017, 19:55 8
Pechkin80, я имел ввиду, что у std::string есть метод length() (и size())
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
29.11.2017, 20:07  [ТС] 9
Выкинул что не относится к профилированию.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <string.h>
#include <iostream>
#include <unordered_map>
 
#if defined(__GNUC__) || defined(__MINGW32__)
/// Disable boost warnings
#pragma GCC system_header
#endif
#include "boost/thread.hpp"
#include "boost/random.hpp"
#include "boost/random/random_device.hpp"
#include "boost/range/algorithm.hpp"
#include "boost/range/algorithm/random_shuffle.hpp"
#include "boost/lexical_cast.hpp"
#include "boost/circular_buffer.hpp"
#include "boost/lockfree/queue.hpp"
#include "boost/intrusive/list.hpp"
#include "boost/functional/hash.hpp"
#include "boost/unordered_map.hpp"
 
typedef std::unordered_map<std::string,const char *> THContainer1;
typedef boost::unordered_map<std::string,const char *> TBHContainer1;
typedef std::unordered_map<std::string,const char *> THContainer2;
 
extern void test_hash();
 
const char * strarr[] = { "Hellow World !!!", "C++11 prog lang", "qtcreator" };
const char * newstr = "passed";
 
//#define debug_node
const auto c_maxindex = 1350000;
 
 
template <typename T1>
std::pair<unsigned,unsigned> test_validality(T1 & _map)
{
    typename T1::iterator it;
    std::string key;
    std::pair<unsigned,unsigned> result;
    unsigned nfound = 0;
    unsigned empty = 0;
    unsigned char noise = 0;
    unsigned maxitems = _map.size();
    for (unsigned i1 = (c_maxindex/2) - 50; i1 < (c_maxindex/2) + 50; ++i1)
    {
        key = std::to_string(i1 + (noise%3)); noise++;
        it = _map.find(key);
        if (it != _map.end())
        {
            nfound++;
            it->second = newstr;
#ifdef debug_node
            if ((maxbuckets < 30) || (i1 < 10))
            {
                std::cout << "data: " << it->second << std::endl;
            }
#endif
        }
        else
        {
            empty++;
        }
    }
    result = std::pair<unsigned,unsigned>(nfound,empty);
    return result;
}
 
template <typename T1,typename ...Args>
void profile_func(T1 (*f)(Args&...),T1& t1 ,Args&... _args)
{
    using boost::chrono::duration_cast;
    using boost::chrono::microseconds;
    typedef boost::chrono::high_resolution_clock clock;
    typedef boost::chrono::time_point<clock> time_point;
    time_point tb__start, tb__end;
    long long duration = 0;
    tb__start = clock::now();
    t1 = f(_args...);
    tb__end = clock::now();
    duration = duration_cast<microseconds>(tb__end - tb__start).count();
    std::cout << " duration is:" << duration << std::endl;
}
 
 
void test_hash()
{
 
    std::string str_item;
    std::pair<unsigned,unsigned> nefound;
    // немного кастомная буст-хеш-функция
    TBHContainer1 mapa1;
    std::map<std::string,const char *> mapu;
    mapa1.max_load_factor(0.98);
    // Заполнение хеш-таблицы
    std::cout << "boost collisions with buckets > 4: ";
    for (int i1 = 0; i1 < c_maxindex; i1++)
    {
        str_item = std::to_string(i1);
        mapa1.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
        mapu.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
    }
    std::cout << std::endl;
    // Вывод списка вёдер (buckets)
    std::cout << "bucket count " << mapa1.bucket_count() << std::endl;
    std::cout << "load factor " << mapa1.load_factor() << std::endl;
 
    // stl-хеш-функция,
    THContainer2 mapa2;
    std::cout << "stl collisions with buckets > 4: ";
    mapa2.max_load_factor(0.98);
    for (int i1 = 0; i1 < c_maxindex; i1++)
    {
        str_item = std::to_string(i1);
        mapa2.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
    }
    std::cout << std::endl;
    std::cout << "bucket count " << mapa2.bucket_count() << std::endl;
    std::cout << "load factor " << mapa2.load_factor() << std::endl;
 
 
    std::cout << "boost::unordered_map custom hasher: ";
    profile_func(&(test_validality<decltype(mapa1)>),nefound,mapa1);
    std::cout << "valid item found: " << nefound.first << std::endl;
 
    std::cout << "std::map (ordered): ";
    profile_func(&(test_validality<decltype(mapu)>),nefound,mapu);
    std::cout << "valid item found: " << nefound.first << std::endl;
 
    std::cout << "std::unordered_map std::hash:";
    profile_func(&(test_validality<decltype(mapa2)>),nefound,mapa2);
    std::cout << "valid item found: " << nefound.first;
 
}
 
int main(int argc, char *argv[])
{
     test_hash();
    return 0;
}
Добавлено через 5 минут
Просто string не POD тип. Не было уверенности что с ним правильно обращаются когда берут хеш. mingw-w64 STL реализация хеш функций это вообще треш. Халтура на халтуре.
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,113
Записей в блоге: 2
29.11.2017, 20:26 10
Призовем croessmah,
Exorcizo te, immundissime spiritus, omnis incursio adversarii, omne phantasma, omnis legio, in nomine Domini nostri Jesu Christi eradicare, et effugare ab hoc plasmate Dei. Ipse tibi imperat, qui te de supernis caelorum in inferiora terrae demergi praecepit. Ipse tibi imperat, qui mari, ventis, et tempestatibus impersvit. Audi ergo, et time, satana, inimice fidei, hostis generis humani, mortis adductor, vitae raptor, justitiae declinator, malorum radix, fomes vitiorum, seductor hominum, proditor gentium, incitator invidiae, origo avaritiae, causa discordiae, excitator dolorum: quid stas, et resistis, cum scias. Christum Dominum vias tuas perdere? Illum metue, qui in Isaac immolatus est, in joseph venumdatus, in sgno occisus, in homine cruci- fixus, deinde inferni triumphator fuit. Sequentes cruces fiant in fronte obsessi. Recede ergo in nomine Patris et Filii, et Spiritus Sancti: da locum Spiritui Sancto, per hoc signum sanctae Cruci Jesu Christi Domini nostri: Qui cum Patre et eodem Spiritu Sancto vivit et regnat Deus, Per omnia saecula saeculorum. Et cum spiritu tuo
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
29.11.2017, 20:35 11
Цитата Сообщение от Kastaneda Посмотреть сообщение
Призовем croessmah,
Exorcizo te
Надо же призвать, а не изгнать.
0
29.11.2017, 20:35
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.11.2017, 20:35
Помогаю со студенческими работами здесь

std::map, std::vector и порядок обхода коллекции
Здравствуйте, уважаемые! Вопрос следующий - если я сохраняю какие-то значения в map или вектор, то...

Std::unordered_multimap<std::string, int> map
Приветствую. Как можно получить только &quot;уникальный&quot; ключ в контейнере? ...

Потокобезопасность std::map::end, std::list::end
Собсна сабж, могу ли я без синхронизаций выполнять подобного рода код if (myIter != map.end()) //...

Конфликты boost и std
Доброго времени суток. Пишу проект с использованием сторонних либ boost и mysql-connector-c. При...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru