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

Question

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

Я использовал и карту, и новый предложенный 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++, поскольку в реализации будут использоваться плотные ключи. Спасибо

Answer 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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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