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

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

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

Карта

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

Как i, он будет частью кода, который будет выполняться на кластере 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(); 
}

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

Ответы

Ответ 1

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

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

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

В соответствии с разделом 6.3 из n1836 приведены сложности для вставки/возврата:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf

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

Ответ 2

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

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

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

Ответ 3

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

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

Изменить: да, вектор в основном представляет собой динамический массив.

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

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