C/C++ MultiMap库

我有一千一百万个键值对（一个键可以有多个值 - 最大2/3），其键是50位整数，值是32位（最大）整数。现在，我的要求是：C/C++ MultiMap库

（键，值）对快速插入[允许重复]
基于键值/值的快速检索。

是否有任何解决此问题的C/C++库（使用MultiMap，B + Tree，B Tree，R + Tree等）？我可以为此提供5/6 GB的主内存。欲了解更多信息：my previous post。

来源

2012-04-09 Arpssss

您的整个数据集可能需要9GB。有最简单的解决方案 - 使用std :: map/std :: multimap并依靠操作系统交换。这个怎么用？ – 2012-04-09 10:14:57

C或C++，挑一个。这两种语言的答案很可能会完全不同（如果有的话）。 – Mat 2012-04-09 10:15:13

您必须提供更多参数，例如从一开始就提供的所有值？速度还是空间是主要参数？最初的C++答案是将它全部加载到一个std :: vector中，并对其进行排序。然后使用二进制搜索。 – 2012-04-09 10:17:09

因为 “5/6千兆字节” 实际上是指5或6千兆字节...用50位的密钥和32位值

1.11亿键/值对将采取（1.11亿*（50 + 32））/（8 * 1024 * 1024 * 1024）= 1.05千兆字节或存储为紧密排列（位）阵列时的内存。

那么你有5倍以上的内存。

在最坏的情况下，64位系统上的10级深度跳过列表映射需要（111000000 *（64 + 32 + 10 * 16））/（8 * 1024 * 1024 * 1024）= 3.308千兆字节，您仍然拥有超过千兆字节的RAM来处理堆管理开销。

所以我建议抓住任何可用的multimap并尝试使用它 - 在我看来，你有足够的内存来处理你的情况，而无需使用任何额外的技巧。

- 编辑 -

其实，我不知道C/C++

嘛，你怎么想到用含有键的1.11亿，如果你不映射到工作知道C++吗？你必须做一些阅读。

标准库包括std :: multimap，boost库中有几个类。 Qt 4包含基于跳过列表的QMap。尝试使用其中的任何一个。

来源

2012-04-09 11:10:56 SigTerm

谢谢。其实，我不知道C/C++（只是在高中水平），这就是为什么我正在寻找现成的。任何指向一个不错的库的指针都会对我有所帮助。因为和Java一样，我无法解决它。 – Arpssss 2012-04-09 11:12:05

谢谢。我期待着你所说的，因为我在Java中面临同样的问题（如OOP）。但是，从我发现的一些讨论中，C应该有这样的设施和C++可能有。这就是为什么试图得到一个想法，因此可以从希望开始。如果C/C++有，我开始阅读。其实，我失去了很多时间，用一些愚蠢的工具。所以，只是有点强调。顺便说一句，谢谢。 – Arpssss 2012-04-09 11:56:04

C中的一个简单散列表每个元素需要50 + 32（+ 14填充）+ 32 +32位。（+也许32位对齐）。这是每个元素160（或192）位：=每个元素20（或24）字节。哈希表会花费您111 * 20（或111 * 24）MB的内存。这是2.2 GB或2.7GB。

来源

2012-04-09 10:45:06 wildplasser

谢谢。其实，我不知道C/C++（只是在高中水平），这就是为什么我正在寻找现成的。任何指向一个不错的库的指针都会对我有所帮助。 – Arpssss 2012-04-09 11:10:57

你是否为此付钱，还是作业？（不能做数学，不能自己创建代码，不能在网上搜索“易于使用”的库） – wildplasser 2012-04-09 11:17:58

我尝试了很多库和代码。但是，不能达到要求的性能。这就是为什么在开始新的之前，需要建议。顺便说一句，我因为我的父亲做这些愚蠢的事情而得到报酬:)。我必须解决很多项目和考试，这就是为什么会被问到一些愚蠢的问题。抱歉。 – Arpssss 2012-04-09 11:50:11

您的要求不包括任何需要订购的集合。使用哈希映射。如果你找不到现成的，创建一个并不是一个很大的挑战。

来源

2012-04-09 10:49:09 selalerer

C/C++ MultiMap库

回答

相关问题