Разница в производительности между map и unordered_map в c ++ - PullRequest
Новая
       12

Разница в производительности между map и unordered_map в c ++

18 голосов
/ 28 февраля 2010

У меня есть простое требование, мне нужна карта типа. однако мне нужно самое быстрое теоретически возможное время поиска.

я использовал и карту, и новый предложенный unordered_map из tr1 я обнаружил, что, по крайней мере, при разборе файла и создании карты, вставляя элемент одновременно.

Карта заняла всего 2 минуты, а unordered_map - 5 минут.

Поскольку он будет частью кода, который будет выполняться в кластере Hadoop, и будет содержать ~ 100 миллионов записей, мне нужно наименьшее возможное время поиска.

Также другая полезная информация: в настоящее время вставляемые данные (ключи) находятся в диапазоне целых чисел от 1,2, ... до ~ 10 миллионов.

Я также могу навязать пользователю указать максимальное значение и использовать порядок, как указано выше, это существенно повлияет на мою реализацию? (Я слышал, что карта основана на деревьях rb, и вставка в возрастающем порядке приводит к лучшей производительности (или к худшему?))

вот код 

map<int,int> Label // this is being changed to unordered_map  
fstream LabelFile("Labels.txt");  


// Creating the map from the Label.txt  
if (LabelFile.is_open())  
{  
    while (! LabelFile.eof() )  
    {             
        getline (LabelFile,inputLine);  
        try  
        {  
            curnode=inputLine.substr(0,inputLine.find_first_of("\t"));  
            nodelabel=inputLine.substr(inputLine.find_first_of("\t")+1,inputLine.size()-1);  
            Label[atoi(curnode.c_str())]=atoi(nodelabel.c_str());  
        }  
        catch(char* strerr)  
        {  
            failed=true;  
            break;  
        }  
    }  
    LabelFile.close(); 
}

Предварительное решение: После просмотра комментариев и ответов я считаю, что лучшим вариантом будет массив Dynamic C ++, поскольку в реализации будут использоваться плотные ключи. Спасибо

Ответы [ 3 ]

10 голосов
/ 28 февраля 2010

Вставка для unordered_map должна быть O (1) , а извлечение должно быть примерно O (1) , (по сути это хеш-таблица).

В результате вы получите OFF , или есть что-то НЕПРАВИЛЬНОЕ с вашей реализацией или использованием unordered_map.

Вам необходимо предоставить дополнительную информацию и, возможно, информацию о том, как вы используете контейнер.

Согласно разделу 6.3 из n1836, сложности для вставки / восстановления даны:

Одна проблема, которую вы должны учитывать, заключается в том, что вашей реализации может потребоваться постоянная перефразировка структуры, как вы говорите, у вас есть 100mil + items . В этом случае при создании экземпляра контейнера, если у вас есть приблизительное представление о том, сколько «уникальных» элементов будет вставлено в контейнер, вы можете передать это в качестве параметра конструктору, и контейнер будет создается соответственно с помощью таблицы ведра соответствующего размера.

2 голосов
/ 21 июня 2012

Дополнительное время загрузки unordered_map связано с изменением размера динамического массива. График изменения размера должен удваивать количество ячеек каждый, когда таблица превышает ее коэффициент загрузки. Поэтому из пустой таблицы ожидайте O (lg n) копий всей таблицы данных. Вы можете устранить эти дополнительные копии, предварительно определив размер хеш-таблицы. В частности 

Label.reserve(expected_number_of_entries / Label.max_load_factor());

Деление на max_load_factor предназначено для учета пустых ячеек, необходимых для работы хеш-таблицы.

1 голос
/ 28 февраля 2010

unordered_map (по крайней мере, в большинстве реализаций) обеспечивает быстрый поиск, но относительно низкую скорость вставки по сравнению с картой. Дерево, как правило, в лучшем случае, когда данные упорядочены случайным образом, и в худшем случае, когда данные упорядочены (вы постоянно вставляете один конец дерева, увеличивая частоту повторной балансировки).

Учитывая, что всего ~ 10 миллионов записей, вы можете просто выделить достаточно большой массив и получить действительно быстрый поиск - при условии достаточной физической памяти, чтобы она не вызывала перегрузок, но современный объем памяти не так уж велик. стандарты.

Редактировать: да, вектор - это в основном динамический массив.

Edit2: код, который вы добавили некоторые проблемы. Ваш while (! LabelFile.eof() ) сломан. Вы обычно хотите сделать что-то вроде while (LabelFile >> inputdata) вместо этого. Вы также читаете данные несколько неэффективно - то, что вы, очевидно, ожидаете, это два числа, разделенные табуляцией. В таком случае я бы написал цикл примерно так: 

while (LabelFile >> node >> label)
    Label[node] = label;
...