1

我正在寻找一种数据结构来保存数据，以便插入需要保存数百万个无符号长整数的数据（如向量）。关键是它需要比 O(logn) 更好的查找，因为它将针对相同大小的相似向量进行搜索。有没有这样的东西存在？

如果我插入 10、20、30 然后遍历集合，我需要保证 10、20、30 的顺序。我的数据是一个字符串，我转换为无符号长整数以减少内存使用，即可以反向解码。

编辑：由于人们在问，我正在比较两个向量（两者都非常大）以获得差异。

小例子：

vector 1: 10 20 30 40 50 60

vector 2: 11 24 30 40 55 70 90

result:   30 40
4

3 回答 3

4

我自己从未使用过它，与最近的 C++ 版本功能相比，它可能已经过时（最后一次更新是从 2011 年开始），但STXXL旨在成为一组为大量数据构建的容器和算法。它可能适合您的需要。

STXXL 的核心是C++ 标准模板库STL 的实现，用于外部内存（核外）计算，即 STXXL 实现的容器和算法可以处理仅适合磁盘的海量数据。虽然接近 STL 支持易用性和与现有应用程序的兼容性，但另一个设计优先事项是高性能。

STXXL 的主要特点是：

  • 对并行磁盘的透明支持。该库提供基本并行磁盘算法的实现。STXXL 是唯一支持并行磁盘的外部存储器算法库。
  • 该库能够处理非常大的问题（测试高达数十 TB）。
  • 提高计算机资源的利用率。外部存储器算法和数据结构的 STXXL 实现受益于 I/O 和计算的重叠。
  • I/O 量中的小常数因子。一种称为“流水线”的独特库功能可以通过在算法组件之间传输数据而不是将它们临时存储在磁盘上，从而节省一半以上的 I/O 数量。开发分支支持算法组件的异步执行，从而实现高级任务并行。
  • 由于用于外部存储器算法和数据结构的众所周知的 STL 兼容接口，开发时间更短。
  • STL 算法可以直接应用于 STXXL 容器；此外，算法的 I/O 复杂度在大多数情况下仍然是最优的。

对于内部计算，可选择使用来自 MCSTL 或 libstdc++ 并行模式的并行算法，从而使算法从本质上受益于多核并行性。

于 2013-06-17T22:56:29.923 回答
1

哈希映射是一种比排序向量更快的查找方式。您必须有 c++11 支持才能使用它。
http://www.cplusplus.com/reference/unordered_map/unordered_map/
为了保持数据的顺序，唯一的方法是在它旁边维护一个向量，该向量也存储了 int
在你开始使用它之前，你应该考虑如何您将使用此数据结构（访问模式）。还要考虑您将获得的数据可能是什么。
这是同一件事的提升版本http://www.boost.org/doc/libs/1_53_0/doc/html/unordered.html

于 2013-06-17T22:35:28.490 回答
0

我认为您应该使用 unordered_map 与订单的双向链表相结合。

因此，每次向数据库添加新项目时，首先将其添加到链表的前面（或末尾），然后将其添加到哈希图中，其中键是值（无符号整数）和“值"（来自键/值对）是指向链表中对象的指针。所以现在如果你想要快速查找，你可以查看 hashmap，如果你想按顺序迭代，你可以使用链表。当然，当您想要删除一个对象时，您必须从两者中删除它们，但在复杂性方面它是相同的（O(1) 摊销所有内容）。

与仅使用哈希图相比，这当然会使您的内存增加 2 或 3 倍。

于 2013-06-17T22:50:35.807 回答