2

我有大量（15 亿）个整数对，其中每一对都与一个文档 ID 相关联。我现在的目标是搜索具有相同对的文档。

我的第一个想法是使用哈希映射（std::map），使用对值作为键，将文档 ID 作为关联值，即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 GB RAM。因此，我需要一个具有良好插入和查找性能的替代方案，以适应我的记忆。理论上我在1500 Million * 3 (PairVal1, PairVal2, Document-ID) * 4 (bytes per Integer) = 18GB不考虑间接费用时使用。那么我的问题有什么好的选择吗？

4

3 回答 3

2

这可能是嵌入式数据库的工作，例如 SQLite 或 BerkeleyDB 或 Tokyo Cabinet。

如果您使用的数据量超过了 RAM，那么您确实需要一些可以从磁盘工作的东西。

于 2016-06-14T16:51:20.520 回答
0

减少空间的一种解决方案是代替std::map<std::pair<int,int>, std::unordered_set<int>>使用std::unordered_map<int, std::unordered_set<int>>

要转换std::pair<int, int>为int您必须使用配对功能，例如：

康托尔配对函数

显然，您只能在成对中使用较小的数字。

两个最大最多 16 位有符号整数（32767、32767）的映射将是 2147418112，它刚好低于有符号 32 位整数的最大值。

其他选项是基于 B-Tree 创建自己的索引器，或者使用像xapian这样的开源搜索引擎库，它是用 C++ 编写的，并且快速且易于使用。

Xapian 是一个适应性很强的工具包，它允许开发人员轻松地将高级索引和搜索工具添加到他们自己的应用程序中。

于 2016-06-14T15:26:04.220 回答
0

可以使用文件系统吗？

在第一个整数之后命名目录，在每个以第二个整数命名的文本文件中创建，文本文件的每一行都可以是一个 Document ID。

您一定会在所有 I/O 上遭受重大的速度损失。尽可能快地获取磁盘。存储需求也将显着增长，因为目录名、文件名和文件内容变为 ascii 文本而不是二进制整数。

于 2016-06-14T15:20:52.273 回答