Память эффективная карта <пара <int,int>, комплект <int>> альтернативный

Question

У меня есть огромное количество (1500 миллионов) пар Integer, где каждый из них связан с идентификатором документа. Теперь моя цель - поиск документов, имеющих одну пару.

Моя первая идея состояла в том, чтобы использовать хэш-карту (std::map) с использованием значений пары в качестве ключей и документов идентификаторов в качестве ассоциированных значений, т.е. map<pair<int,int>, unordered_set<int>>

Например:

Document1 

- pair1: (3, 9) 
- pair2: (5,13) 

Document2 

- pair1: (4234, 13) 
- pair2: (5,13) 

map<pair<int,int>, unordered_set<int>> hashMap 
hashMap[{3, 9}].insert(1) 
hashMap[{5, 13}].insert(1) 

hashMap[{4234, 13}].insert(2) 
hashMap[{5, 13}].insert(2) 

приведет в

Key(3,9) = Documents(1) 
Key(5,13) = Documents(1,2) 
Key(4234,13) = Documents(2) 

Моя проблема в том, что это занимает огромное количество памяти, которая превышает мою доступную 24 ГБ ОЗУ. Поэтому мне нужна альтернатива с хорошей производительностью для вставок и поисковых запросов, которые могут вписаться в мою память. В теории я использую 1500 Million * 3 (PairVal1, PairVal2, Document-ID) * 4 (bytes per Integer) = 18GB, когда накладные расходы не учитываются. Итак, есть ли хорошие альтернативы для моей проблемы?

Answer 1

Можете ли вы использовать файловую систему?

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

На всех входах/выходах вы должны будете совершить значительные штрафные санкции. Получайте как можно быстрее диск. Требования к хранилищу также значительно возрастут, поскольку имена каталогов, имена файлов и содержимое файла становятся символами ascii вместо двоичных целых чисел.

Answer 2

Одно решение для сокращения пространства является вместо std::map<std::pair<int,int>, std::unordered_set<int>> использования std::unordered_map<int, std::unordered_set<int>>

Для обращенного std::pair<int, int> к int вы должны использовать функцию сопряжения, например:

Cantor’s Pairing Function

Очевидно вы ограничены используя меньшие числа в ваших парах.

Отображение для двух максимальных 16-разрядных знаковых целых чисел (32767, 32767) будет иметь значение 2147418112, что не соответствует максимальному значению для 32-битного целого числа.

Другой вариант создать свой собственный индексатор основе в B-Tree, или с использованием Open Source Search Engine библиотека как xapian, она написана на C++ и является быстрым и простым в использовании.

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

Answer 3

Возможно, это работа для встроенной базы данных, такой как SQLite или BerkeleyDB или Tokyo Cabinet.

Если объем данных, которые вы используете, превышает вашу оперативную память, вам действительно нужно что-то, что может работать с диска.