Map vs multimap в С++ (производительность)

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

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

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

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

Ответы

Ответ 1

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

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

  • Fetch - это O (log N + log M)
  • Вставка - O (log N + log M)
  • Удалить - O (log N + log M)
  • Итерация - это O (1)

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

  • Fetch - это O (log N)
  • Вставка - O (log N)
  • Удалить - O (log N)
  • Итерация - это O (1)

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

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

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

Ответ 2

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