Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массивы и связные списки http://www.cyberforum.ru/cpp-beginners/thread987836.html
Нужно взять како-то небольшой текст и напечатать все слова, которые начинаются с буквы, отличную от буквы, с которой начинается первое слово текста. Перед печатью удалить из слов все буквы 'a' и 'o'. - При выполнении задания НЕ использовать String. - использовать: 1. массив 2. связный список нужна помощь ..
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> #include <math.h> void main() { float a,k,b,m,x,p,z,y;
Ссылка на экземпляр класса в DLL C++
Написал маленький каркасик для собственново фреймворка, и проблема возникла когда хотель экспортировать его в DLL. Фреймворк предпологает запуск приложения следующим образом: int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE prevInstance,LPSTR cmdLine,int cmdShow) { apl = new Application(hInstance); Window w(NULL,L"Wirst Class",L"Example2",WS_OVERLAPPEDWINDOW|WS_VISIBLE, ...
C++ Структуры и определение операторов для работы с ними http://www.cyberforum.ru/cpp-beginners/thread987804.html
Есть отдельный файл с базовыми структурами, которые используются во всём проекте. Есть файл с классом, в котором используется собственная структура, забивающая часть изначальных данных в остальные структуры. Внутри проекта происходят преобразования из внутренней структуры во внешние с помощью operator=. Однако сам operator= прописать в классе не удаётся. Как и можно ли это реализовать не ломая...
C++ Вычислить сколько товара можно купить без сдачи Задаётся произвольная цена товара (допустим 11,11) задается произвольное количество монет (10р 5р 2р 1р 50к 10к 5к) допустим каждой по 5 сколько можно купить пива на это количество монет (при данных условиях = 8) сколько можно купить пива без сдачи? По данным условиям мы должны придти к ответу 5 так как самой маленькой монеты (5 копеек) у нас всего 5 штук. Подскажите как можно... подробнее

Показать сообщение отдельно
Shtirliz72
201 / 161 / 38
Регистрация: 25.10.2013
Сообщений: 527
26.10.2013, 01:16     Выбор хранилища
Цитата Сообщение от kvadro Посмотреть сообщение
И я не могу понять почему такие результаты выдаёт std::vector на дальних элементах.
А я не могу понять почему он у тебя вообще такие гиперактивные результаты выдаёт по сравнению с другими контейнерами. Может конечно это оптимизатор так постарался, но я сомневаюсь. Попробуй увеличить количество проходов по поиску, как ниже поступил я.

я немного переписал main
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
#define TURNS 10
#define TURNS2 (TURNS*1000)
int main(int argc, char *argv[])
{
    // QCoreApplication a(argc, argv);
    clock_t start, end;
 
    std::string strs[] = {"one", "two", "three", "four", "five", "six", "seven", "eight" };
    for( int i = 1; i <= 10000000; i++ )
    {
        int k = rand() % 8;
        Client1 *client1 = new Client1( i );
        client1->name = strs[k];
        Client2 *client2 = new Client2();
        client2->name = strs[k];
 
        if (!(i%100000))
            std::cout << "Generating test values: " << i/100000 << "%\r";
 
        clients1.push_back(client1);
        clients2.insert( std::pair<ClientId, Client2 *>(i, client2) );
        clients3.insert( std::pair<ClientId, Client2 *>(i, client2) );
    }
 
    // char str[][256] = {"sa", "10", "9999999", "200000000"};
    for ( int test = 1; test < /*4*/ argc; test++ )
    {
        long cid = atoi( /*str[test]*/argv[test] );
        std::cout << "turn " << test << " value: " << cid << std::endl;
 
        start = clock();
        for (int i = 0; i < TURNS; i++) searchInVector( clients1, cid );
        end = clock();
        std::cout << "Vector, id " << cid << ": " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS) << std::endl ; ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInMap(clients2, cid );
        end = clock();
        std::cout << "Map1, id " << cid << ": " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInMap2(clients2, cid );
        end = clock();
        std::cout << "Map2, id " << cid << ": " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInUnorderedMap(clients3, cid );
        end = clock();
        std::cout << "Unordered map, id " << cid << ": " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInUnorderedMap2(clients3, cid );
        end = clock();
        std::cout << "Unordered map2, id " << cid << ": " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        std::cout << "===================" << std::endl ;
    }
    // return a.exec();
}
и результаты:
turn 1 value: 10
Vector, id 10: 0
Map1, id 10: 1.5e-006
Map2, id 10: 7e-007
Unordered map, id 10: 7e-007
Unordered map2, id 10: 4e-007
===================
turn 2 value: 9999999
Vector, id 9999999: 0.4914
Map1, id 9999999: 2.5e-006
Map2, id 9999999: 1.2e-006
Unordered map, id 9999999: 7e-007
Unordered map2, id 9999999: 3e-007
===================
turn 3 value: 200000000
Vector, id 200000000: 0.4897
Map1, id 200000000: 1.4e-006
Map2, id 200000000: 5.3e-006
Unordered map, id 200000000: 2e-007
Unordered map2, id 200000000: 4.6e-006
===================
Добавлено через 5 часов 29 минут
Цитата Сообщение от kvadro Посмотреть сообщение

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

1 вариант быстрей и более правильный, возникает вопрос - нет ли подводных камней?
В общем - 2ой вариант явно быстрее.
Особенно его первая реализация searchInUnorderedMap.
Если же хочешь использовать vector, то лучше всего(по моим результатам - в два раза быстрей), будет версия с итераторами:
C++
1
2
3
4
5
6
7
8
9
10
11
Client1 *searchInVector2( std::vector<Client1 *> &vec, ClientId id )
{
    std::vector<Client1 *>::iterator endIt = vec.end();
    for(std::vector<Client1 *>::iterator i = vec.begin(); i < endIt; ++i )
    {
        if ( (*i)->id == id )
            return *i;
    }
 
    return NULL;
}
Также вскрылась ошибка из-за которой были странные результаты по времени.
std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count() возвращает long long, который у тебя преобразовывался в int - из-за этого были некорректные результаты.
Полный листинг:
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <assert.h>
 
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
 
// #include <QCoreApplication>
 
#define TURNS 10
#define TURNS2 (TURNS*10000)
 
typedef long 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;
}
 
Client1 *searchInVector2( std::vector<Client1 *> &vec, ClientId id )
{
    std::vector<Client1 *>::iterator endIt = vec.end();
    for(std::vector<Client1 *>::iterator i = vec.begin(); i < endIt; ++i )
    {
        if ( (*i)->id == id )
            return *i;
    }
 
    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;
    }
}
 
 
long long getTime( std::chrono::time_point<std::chrono::system_clock> start,
               std::chrono::time_point<std::chrono::system_clock> end )
{
    long long 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[])
{
    // QCoreApplication a(argc, argv);
    // clock_t start, end;
    std::chrono::time_point<std::chrono::system_clock> start, end;
 
    std::string strs[] = {"one", "two", "three", "four", "five", "six", "seven", "eight" };
    for( int i = 1; i <= 10000000; i++ )
    {
        int k = rand() % 8;
        Client1 *client1 = new Client1( i );
        client1->name = strs[k];
        Client2 *client2 = new Client2();
        client2->name = strs[k];
 
        if (!(i%100000))
            std::cout << "Generating test values: " << i/100000 << "%\r";
 
        clients1.push_back(client1);
        clients2.insert( std::pair<ClientId, Client2 *>(i, client2) );
        clients3.insert( std::pair<ClientId, Client2 *>(i, client2) );
    }
    std::cout << "                                                          \r";
 
    char str[][256] = {"sa", "10", "2353257", "5678335", "9999899", "200000000"};
    for ( int test = 1; test < 6 /*argc*/; test++ )
    {
        long cid = atoi( str/*argv*/[test] );
        std::cout << "turn " << test << " value: " << cid << std::endl;
 
        /*
        start = clock();
        for (int i = 0; i < TURNS; i++) searchInVector( clients1, cid );
        end = clock();
        std::cout << "Vector: " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS) << std::endl ; ;
 
        start = clock();
        for (int i = 0; i < TURNS; i++) searchInVector2( clients1, cid );
        end = clock();
        std::cout << "Vector2: " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS) << std::endl ; ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInMap(clients2, cid );
        end = clock();
        std::cout << "Map1: " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInMap2(clients2, cid );
        end = clock();
        std::cout << "Map2: " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInUnorderedMap(clients3, cid );
        end = clock();
        std::cout << "Unordered map: " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = clock();
        for (int i = 0; i < TURNS2; i++) searchInUnorderedMap2(clients3, cid );
        end = clock();
        std::cout << "Unordered map2: " << (double)(end - start) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
        */
 
        start = std::chrono::system_clock::now();
        for (int i = 0; i < TURNS; i++) searchInVector( clients1, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Vector: " << (double)getTime( start, end ) / (CLOCKS_PER_SEC * TURNS) << std::endl ;
 
        start = std::chrono::system_clock::now();
        for (int i = 0; i < TURNS; i++) searchInVector2( clients1, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Vector2: " << (double)getTime( start, end ) / (CLOCKS_PER_SEC * TURNS) << std::endl ;
 
        start = std::chrono::system_clock::now();
        for (int i = 0; i < TURNS2; i++) searchInMap(clients2, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Map: " << (double)getTime( start, end ) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = std::chrono::system_clock::now();
        for (int i = 0; i < TURNS2; i++) searchInMap2(clients2, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Map2: " << (double)getTime( start, end ) / (CLOCKS_PER_SEC * TURNS2)  << std::endl ;
 
        start = std::chrono::system_clock::now();
        for (int i = 0; i < TURNS2; i++) searchInUnorderedMap(clients3, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Unordered: " << (double)getTime( start, end ) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
        start = std::chrono::system_clock::now();
        for (int i = 0; i < TURNS2; i++) searchInUnorderedMap2(clients3, cid );
        end = std::chrono::system_clock::now();
        std::cout << "Unordered map2: " << (double)getTime( start, end ) / (CLOCKS_PER_SEC * TURNS2) << std::endl ;
 
 
        std::cout << "===================" << std::endl ;
 
 
    }
    // return a.exec();
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru