map vs multimap in C++ (производительность)

Я работаю над структурой данных, где ввод очень большой, почти 1 ТБ. Мне нужно загрузить данные в ассоциативный контейнер.map vs multimap in C++ (производительность)

Данные имеют несколько дубликатов, поэтому я использую multimap, но кто-то предложил мне использовать карту вектора вместо этого. Могу ли я узнать, какова разница в производительности?

map<const char*, const char*, cmptr> mulmap; 

map <const char*, vector <const char*> ,cmptr> mmap;

источник

2013-02-18 Manish

Почему бы вам не попробовать их обоих и выяснить? –

На самом деле, в обоих случаях ваша производительность, скорее всего, будет зависеть от скорости диска, если у вас нет системы с 1 ТБ ОЗУ ... –

Если вы хотите использовать 'const char *' как ключ, вы также должны предоставить предикат сравнения для этого работать. Было бы проще использовать 'std :: map ' вместо этого. –

Вы тратите свое время думать о map против multimap. Предположим, что количество ячеек равно N, а среднее количество элементов на ячейку - M.

A std::multimap<Key, Val> обычно использует дерево RB с дублирующимися ключами.

Выборка представляет собой О (журнал N + войти M)
Вставка представляет собой О (журнал N + войти M)
Удаление представляет собой О (журнал N + войти M)
Итерация O (1)

A std::map<Key, std::vector<Val>> Обычно используется дерево RB с уникальными ключами.

Fetch является O (журнал N)
Вставки является O (журнал N)
удаляемого O (журнал N)
Итерации O (1)

Как вам может видеть, разница не стоит говорить, если М очень большой.

Однако хранение обоих ограничено оперативной памятью. 1 TB просто невозможно для большинства систем, и никакая материнская плата, о которой я слышал, не поддерживает ее.

Вам лучше использовать базу данных для 1 ТБ данных. Вы можете выбрать практически любую базу данных для этой задачи. Kyoto Cabinet прост и делает то, что вы хотите, но вы также можете использовать PostgreSQL, MySQL, Sqlite, Dynamo, Redis, MongoDB, Cassandra, Voldemort ...

источник

2013-02-18 08:29:13

Для «1 ТБ данных» на самом деле нужно быть осторожным, какая база данных и как доступ к данным. Существуют ограничения и т. д. – 2013-02-18 08:31:04

Я работаю над суперкомпьютером. – Manish

@ user15662: Я по-прежнему рекомендую Kyoto Cabinet над 'std ::' чем-нибудь для такого рода работы. –

С 1 ТБ ввода я бы не использовал ни один из них. Скорее всего, вам не хватает ОЗУ. Используйте некоторые данные на дисковой структуре данных, такие как B-tree.

источник

2013-02-18 08:31:35

map vs multimap in C++ (производительность)

ответ

Смежные вопросы