Форум программистов, компьютерный форум, киберфорум
Наши страницы

Выбор хранилища - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массивы и связные списки http://www.cyberforum.ru/cpp-beginners/thread987836.html
Нужно взять како-то небольшой текст и напечатать все слова, которые начинаются с буквы, отличную от буквы, с которой начинается первое слово текста. Перед печатью удалить из слов все буквы 'a' и 'o'....
C++ Вывести слова строки в порядке убывания числа букв в них Собственно, имеется готовая на половину программа: #include "stdio.h" #include "conio.h" #include "math.h" #include "string.h" #include "stdafx.h" #include <iostream> http://www.cyberforum.ru/cpp-beginners/thread987826.html
C++ Borland C++
Форумчане , помогите. Начали изучение С++ в универе. Сделал 2 лбораторки, препод проверил , сказал ошибок нет.НО программа не работает. После run выдает: #include <stdio.h> #include <conio.h>...
Ссылка на экземпляр класса в DLL C++
Написал маленький каркасик для собственново фреймворка, и проблема возникла когда хотель экспортировать его в DLL. Фреймворк предпологает запуск приложения следующим образом: int WINAPI...
C++ Структуры и определение операторов для работы с ними http://www.cyberforum.ru/cpp-beginners/thread987804.html
Есть отдельный файл с базовыми структурами, которые используются во всём проекте. Есть файл с классом, в котором используется собственная структура, забивающая часть изначальных данных в остальные...
C++ Вычислить сколько товара можно купить без сдачи Задаётся произвольная цена товара (допустим 11,11) задается произвольное количество монет (10р 5р 2р 1р 50к 10к 5к) допустим каждой по 5 сколько можно купить пива на это количество монет (при данных... подробнее

Показать сообщение отдельно
kvadro
11 / 9 / 1
Регистрация: 12.03.2012
Сообщений: 127

Выбор хранилища - C++

25.10.2013, 17:28. Просмотров 605. Ответов 6
Метки (Все метки)

Есть объекты которые имеют свой id и которые должны хранится в хранилище. Далее переодически программа ищет нужный объект по id( int, присваивается не последовательно ) и работает с ним, т.е. важно время поиска объекта.

Появилось 2 способа реализации:
1) Хранить id в самом объекте как поле ( что и более правильно ), в качестве хранилища использовать std::vector.
2) Использовать std::unordered_map, id хранить как ключ объекта.

1 вариант быстрей и более правильный, возникает вопрос - нет ли подводных камней?

Набросал тест:
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 <iostream> 
#include <cstdlib>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <assert.h>
 
typedef int ClientId;
 
struct Client1
{
    Client1( ClientId _id ) : id( _id ) {}
 
    std::string name;
    ClientId id;
};
 
struct Client2
{
    std::string name;
};
 
// ================================================================================
Client1 *searchInVector( std::vector<Client1 *> &vec, ClientId id )
{
    for( Client1 *client : vec )
    {
        if ( client->id == id )
            return client;
    }
 
    return NULL;
}
 
// ================================================================================
Client2 *searchInMap( std::map<ClientId, Client2 *> &map, ClientId id )
{
    if ( map.find( id ) !=map.end() )
        return map[id];
 
    return NULL;
}
 
Client2 *searchInMap2( std::map<ClientId, Client2 *> &map, ClientId id )
{
    try
    {
        return map.at( id );
    }
    catch( std::out_of_range e )
    {
        return NULL;
    }
}
 
// ================================================================================
Client2 *searchInUnorderedMap( std::unordered_map<ClientId, Client2 *> &map, ClientId id )
{
    if ( map.find( id ) !=map.end() )
        return map[id];
 
    return NULL;
}
 
Client2 *searchInUnorderedMap2( std::unordered_map<ClientId, Client2 *> &map, ClientId id )
{
    try
    {
        return map.at( id );
    }
    catch( std::out_of_range e )
    {
        return NULL;
    }
}
 
 
int getTime( std::chrono::time_point<std::chrono::system_clock> start,
               std::chrono::time_point<std::chrono::system_clock> end )
{
    int elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();
    
    return elapsed;
}
 
 
std::vector<Client1 *> clients1;
std::map<ClientId, Client2 *> clients2;
std::unordered_map<ClientId, Client2 *> clients3;
 
 
int main( int argc, char* argv[] )
{
    std::chrono::time_point<std::chrono::system_clock> start, end;
 
    for( int i = 1; i <= 10000000; i++ )
    {
        Client1 *client1 = new Client1( i );
        Client2 *client2 = new Client2();
 
        clients1.push_back(client1);
        clients2.insert( { i, client2 } );
        clients3.insert( { i, client2 } );
    }
 
 
    for ( int test = 1; test < argc; test++ )
    {
        int cid = atoi( argv[test] );
 
        start = std::chrono::system_clock::now();
        searchInVector( clients1, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Vector, id " << cid << ": " << getTime( start, end ) << std::endl ;
 
        start = std::chrono::system_clock::now();
        searchInMap(clients2, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Map, id " << cid << ": " << getTime( start, end ) << std::endl ;
 
        start = std::chrono::system_clock::now();
        searchInMap2(clients2, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Map2, id " << cid << ": " << getTime( start, end ) << std::endl ;
 
        start = std::chrono::system_clock::now();
        searchInUnorderedMap(clients3, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Unordered map, id " << cid << ": " << getTime( start, end ) << std::endl ;
 
        start = std::chrono::system_clock::now();
        searchInUnorderedMap2(clients3, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Unordered map2, id " << cid << ": " << getTime( start, end ) << std::endl ;
 
        std::cout << "===================" << std::endl ;
    }
}
Bash
1
2
clang++ -std=c++11 -O3 search.cc -o search
./search 10 9999999 200000000
Результаты:
Поиск ближнего элемента:
Vector, id 10: 0
Map, id 10: 3000
Map2, id 10: 0
Unordered map, id 10: 1000
Unordered map2, id 10: 0

Поиск дального элемента:
Vector, id 999999: 0
Map, id 999999: 1000
Map2, id 999999: 1000
Unordered map, id 999999: 0
Unordered map2, id 999999: 0

Поиск несуществующего элемента:
Vector, id 2000000: 0
Map, id 2000000: 1000
Map2, id 2000000: 77000
Unordered map, id 2000000: 1000
Unordered map2, id 2000000: 4000
Добавлено через 4 минуты
И я не могу понять почему такие результаты выдаёт std::vector на дальних элементах.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru