Разница в производительности между картой и unordered_map в C++
У меня есть простое требование, мне нужна карта типа. однако мне требуется самое быстрое теоретически возможное время поиска.
я использовал и карту и новый предложенный 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();
}
Предварительное Решение: После обзора комментариев и ответов, я полагаю, что Динамический массив C++ был бы наилучшим вариантом, так как реализация будет использовать плотные ключи. Спасибо
2 ответа
Вставка для unordered_map должна быть O(1) и извлечение должно быть примерно O(1), (это по сути хэш-таблица).
Ваши тайминги в результате намного ОФФ, или есть что-то НЕПРАВИЛЬНОЕ в вашей реализации или использовании unordered_map.
Вам нужно предоставить больше информации, и, возможно, как вы используете контейнер.
В соответствии с разделом 6.3 n1836 приведены сложности для вставки/возврата:
Один вопрос, который вам следует рассмотреть, заключается в том, что вашей реализации может потребоваться постоянное пересоздание структуры, поскольку вы говорите, что у вас 100mil+ элементов. В таком случае при инстанцировании контейнера, если вы примерно представляете, сколько "уникальных" элементов будет вставлено в контейнер, вы можете передать это в качестве параметра конструктору, и контейнер будет инстанцирован соответствующим образом с bucket-table соответствующего размера.
unordered_map (по крайней мере, в большинстве реализаций) дает быстрое извлечение, но относительно низкую скорость вставки по сравнению с map. Дерево обычно лучше всего, когда данные упорядочены случайным образом, и в худшем случае, когда данные упорядочены (вы постоянно вставляете на одном конце дерева, увеличивая частоту повторной балансировки).
Учитывая, что общее количество записей составляет ~ 10 миллионов, вы можете просто выделить достаточно большой массив и получить действительно быстрый поиск - при условии, что физической памяти достаточно, чтобы это не приводило к сбоям, но по современным меркам это не очень большой объем памяти. стандарты.
Изменить: да, вектор - это в основном динамический массив.
Edit2: Код, в который вы добавили некоторые проблемы. Ваш while (! LabelFile.eof ()) не работает. Обычно вместо этого вы хотите сделать что-то вроде while (LabelFile >> inputdata) . Вы также читаете данные несколько неэффективно - вы, по-видимому, ожидаете двух чисел, разделенных табуляцией. В этом случае я бы написал цикл примерно так:
while (LabelFile >> node >> label)
Label[node] = label;