Домашняя страница Тест на быстродействие: Hash Map vs Vector
Публикация
Отменить

Тест на быстродействие: Hash Map vs Vector

Время публикации 31/08/2010 Обновлено 10/07/2023
Автор Deynega Vasiliy
7 минут чтения

Задача: определить контейнер, в котором оптимальнее всего хранить данные (текстуры, буферы и т.п.). Сравним наиболее подходящие варианты: сортированный массив и Hash Map. Условие: контейнер один раз заполняется, а затем с ним ведется работа. (т.е. не рассматривается вариант изменения содержимого контейнера в реальном времени) Критерий:

  1. Скорость заполнения
  2. Скорость выборки Данные: поскольку задача поиска, то в качестве данных используются целые числа. Если требуется хранить структуры, то это повлияет только на скорость заполнения массива, но не время поиска данных. Ключ всегда лучше получать как хеш по данным или уникальное поле данных в структуре.

Проведем тестирование скорости заполнения и выборки данных с применением сортированного массива и структуры map, из стандартной библиотеки шаблонов(STL). Для проведения тестирования была написана программа в Visual Studio на языке C++. Проведем три измерения при разных конфигурациях алгоритма и приложения.

Конфигурации:

    • iN = 100000 - количество элементов в массиве
    • Debug
    • Не резервируем память вектора зарание
    • iN = 10000000 - количество элементов в массиве
    • Release
    • Не резервируем память вектора зарание
    • iN = 10000000 - количество элементов в массиве
    • Release
    • Зарезервируем память вектора зарание

В данной программе данные заполняются по порядку как в массив, так и в map. Затем, чтобы получить влияние времени сортировки на процесс заполнения данных вектора, данные сортируются в противоположном порядке. Эта операция не нужна для структуры map, поэтому затраты времени на сортировку будут ухудшать временные показатели работы с вектором.

Программа:

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

#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
#include <conio.h>
#include <conio.h>
#include <windows.h>

#pragma comment( lib, "Winmm.lib" )

typedef std::pair< int, int >        td_Pair;    // key / value
typedef std::vector< td_Pair  >        td_Vector;
typedef std::map< int, int >        td_Map;


struct st_FindValueStruct
{
    bool    operator()( const td_Pair& stLhs, const td_Pair& stRhs )
    {
        return stLhs.first > stRhs.second;
    }
    bool    operator()( int iKey, const td_Pair& stRhs )
    {
        return iKey > stRhs.second;
    }
    bool    operator() ( const td_Pair& stLhs, int iKey )
    {
        return stLhs.first > iKey;
    }
};

bool PairSortPred( td_Pair& stLhs, td_Pair& stRhs )
{
    return stLhs.first > stRhs.second;
}



int main()
{
    td_Vector    vl_arrItems;
    td_Map        vl_mapItems;
    unsigned int iTimeFirst, iTimeLast;
    unsigned int iN = 10000000;

    vl_arrItems.reserve( iN );
    
    // fill vector
    iTimeFirst = timeGetTime();
    for( unsigned int iInd = 0; iInd < iN; ++iInd )
        vl_arrItems.push_back( td_Pair( (int)iInd, (int)iInd ) );
    iTimeLast = timeGetTime();
    printf( "vector fill: %d\n ms", iTimeLast - iTimeFirst );
    std::sort( vl_arrItems.begin(), vl_arrItems.end(), PairSortPred );
     iTimeLast = timeGetTime();
    printf( "vector fill + sort: %d\n ms", iTimeLast - iTimeFirst );


    // fill map
    iTimeFirst = timeGetTime();
    for( unsigned int iInd = 0; iInd < iN; ++iInd )
        vl_mapItems[ iInd ] = iInd;
    iTimeLast = timeGetTime();
    printf( "map fill: %d ms\n", iTimeLast - iTimeFirst );


    int iTemp;

    // find all items into vector
    iTimeFirst = timeGetTime();
    for( unsigned int iInd = 0; iInd < iN; ++iInd )
    {
        td_Vector::iterator pIter = std::lower_bound( vl_arrItems.begin(), vl_arrItems.end(), iInd, st_FindValueStruct() );
        iTemp += pIter->second;
    }
    iTimeLast = timeGetTime();
    printf( "vector find all items: %d ms\n", iTimeLast - iTimeFirst );

    
    // find all items into map
    iTimeFirst = timeGetTime();
    for( unsigned int iInd = 0; iInd < iN; ++iInd )
    {
        td_Map::iterator pIter = vl_mapItems.find( iInd );
        iTemp += pIter->second;
    }
    iTimeLast = timeGetTime();
    printf( "map find all items: %d ms\n", iTimeLast - iTimeFirst );
    printf( "temp: %d ms\n", iTemp );

    getch();
    return 0;
}

Результаты:

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

1
2
3
4
5
6
7

1. Debug    /     iN = 100000;     /    vl_arrItems.reserve( iN );     - закоментирован
Vector fill: 94 ms
Vector fill + sort: 3297 ms
Map fill: 1500 ms
Vector find all items: 8922 ms
Map find all items: 609 ms
Map Победил по всем показателям.

1
2
3
4
5
6

2. Release    /    iN = 10000000;     /    vl_arrItems.reserve( iN );     - закоментирован
Vector fill: 281 ms
Vector fill + sort: 1203 ms
Map fill: 16516 ms
Vector find all items: 1203 ms
Map find all items: 2203 ms

1
2
3
4
5
6
7

3. Release    /    iN = 10000000;     /    vl_arrItems.reserve( iN );     - присутствует
Vector fill: 125 ms
Vector fill + sort: 1031 ms
Map fill: 16563 ms
Vector find all items: 1203 ms
Map find all items: 2359 ms
Vector Победил по всем показателям.

Вывод: Для данных, которые один раз создаются, а затем используются следует использовать сортированный массив. Он располагает элементы в памяти последовательно, что делает его наиболее быстрым в работе. Это происходит как за счет алгоритма бинарного поиска, так и за счет того, что работа с блоком данных идет быстрее, чем с данными разрозненными в памяти.

Комментарии

FiloXSee, 13 окт. 2010, 15:03

Комментарий 1: «gennadiy.brich: обо хеш мап: почему там map назван hash map? это же не правда»

Комментарий 2: «тестировать вообще нечего — хеш таблица будет оптимальным выбором, если интересует только скорость»

FiloXSee, 13 окт. 2010, 15:05

hash_map — это контейнер стандартной библиотеки. Сейчас его в STL нет, но это не важно. Контейнер становится хешевым не тогда, когда используется hash_map. Достаточно использовать map но в качестве первичного ключа использовать хеш значение чего либо, полученое каким либо алгоритмом. В статье тестируются не стандартные контейнеры, а способы хранения данных и работы с ними.

В примере используется хеш значение UInt32. Поэтому использование кантейнера map с первичным ключем типа UInt32 равносильно использованию хеш мепа. Причем в данном расмотрении я убрал из кода вычисление этого хеша от чего то, т.е. в действительности хеш меп будет работать еще дольше, т.к. будет вычислять этот хеш. В коде я оставил только основу, которой достаточно чтобы оценить скорость работы алгоритма.

И еще читайте внимательно вывод. Если данные создаются один раз, а затем только используются, то ВСЕГДА будет более оптимальным использовать сортированный массив (еще и в статической памяти). Это всегда быстрее по скорости и оптимальнее по памяти (если вы с этим не согласны то вам дорога к книге «Эффективное использование С++» Скота Майерса, или к написанию своих тестов). Хеш таблизу имеет смысл использовать только если идет постоянные добавления и удаление элементов из нее. Тогда сортировать каждый раз становится накладно.

FiloXSee, 13 окт. 2010, 17:10

Комментарий 1: «обо хеш мап: почему там map назван hash map? это же не правда»

Комментарий 2: «тестировать вообще нечего — хеш таблица будет оптимальным выбором, если интересует только скорость»

FiloXSee, 13 окт. 2010, 17:10

hash_map — это контейнер стандартной библиотеки. Сейчас его в STL нет, но это не важно. Контейнер становится хешевым не тогда, когда используется hash_map. Достаточно использовать map но в качестве первичного ключа использовать хеш значение чего либо, полученое каким либо алгоритмом. В статье тестируются не стандартные контейнеры, а способы хранения данных и работы с ними.

В примере используется хеш значение UInt32. Поэтому использование кантейнера map с первичным ключем типа UInt32 равносильно использованию хеш мепа. Причем в данном расмотрении я убрал из кода вычисление этого хеша от чего то, т.е. в действительности хеш меп будет работать еще дольше, т.к. будет вычислять этот хеш. В коде я оставил только основу, которой достаточно чтобы оценить скорость работы алгоритма.

И еще читайте внимательно вывод. Если данные создаются один раз, а затем только используются, то ВСЕГДА будет более оптимальным использовать сортированный массив (еще и в статической памяти). Это всегда быстрее по скорости и оптимальнее по памяти (если вы с этим не согласны то вам дорога к книге «Эффективное использование С++» Скота Майерса, или к написанию своих тестов). Хеш таблизу имеет смысл использовать только если идет постоянные добавления и удаление элементов из нее. Тогда сортировать каждый раз становится накладно.

C++
c++ тестирование vector hash map
Публикация защищена лицензией CC BY 4.0 .
Недавно обновлено
Содержание