我喜欢使用STL开发算法,但是,我有这个反复出现的问题,我的数据集对于堆来说太大了.
我一直在寻找支持磁盘的STL容器和算法的直接替换,即存储在磁盘而不是堆上的数据结构.
一位朋友最近向我指出了stxxl.在我太介入之前......我应该考虑使用其他任何支持磁盘的STL替换吗？
注意:我对持久性或嵌入式数据库不感兴趣.请不要提及boost :: serialization,POST ++,Relational Template Library,Berkeley DB,sqlite等.我知道这些项目并在它们适合我的目的时使用它们.
更新:有几个人提到了内存映射文件和使用自定义分配器,BTW提出了很好的建议,但我想指出他们在这里讨论David Abraham建议磁盘支持的容器需要自定义迭代器.这意味着自定义分配器方法不太可行.
我想知道如何最好地处理磁盘上的数据结构,因为存储布局需要与逻辑设计完全匹配.我发现当你需要为你的存储设置一个特定的布局时,结构对齐和打包并没有多大帮助.
我解决这个问题的方法是使用处理器指令定义结构的(宽度),并在添加跟随逻辑结构模型的数据后将写入磁盘的分配字符(字节)数组时使用宽度.
例如:
typedef struct __attribute__((packed, aligned(1))) foo {
uint64_t some_stuff;
uint8_t flag;
} foo;
如果我坚持foo on-disk,那么"flag"值将出现在数据的最后.鉴于我可以在使用&foo类型的fread读取数据时轻松使用foo,然后通常使用struct而不需要任何进一步的字节摆弄.
相反,我更喜欢这样做
#define foo_width sizeof(uint64_t)+sizeof(uint8_t)
uint8_t *foo = calloc(1, foo_width);
foo[0] = flag_value;
memcpy(foo+1, encode_int64(some_value), sizeof(uint64_t));
然后我只使用fwrite和fread来提交和读取字节,但稍后解压缩它们以便使用存储在各种逻辑字段中的数据.
我想知道哪种方法最好用,因为我希望磁盘存储的布局与逻辑布局相匹配......这只是一个例子......
如果有人知道每个方法在解码/解包字节方面的效率与直接从它的盘上表示复制结构请分享,我个人更喜欢使用第二种方法,因为它让我完全控制存储布局但我还没准备好牺牲性能寻找性能,因为这种方法需要大量的循环逻辑来解包/遍历字节到数据中的各个边界.
谢谢.
我想知道是否有一个带有 Python 绑定的快速磁盘键值存储，它支持对单独键的数百万次读/写调用。我的问题涉及计算一个非常大的语料库（维基百科）中的单词共现，并不断更新共现计数。这涉及使用 64 位密钥和 64 位值读取和写入约 3 亿个值 70 次。
我还可以将我的数据表示为尺寸约为 2M x 2M 的上三角稀疏矩阵。
到目前为止我已经尝试过：
目前唯一运行良好的解决方案是 LMDB，但运行时间约为 12 天，这似乎不合理，因为我感觉自己没有处理那么多数据。使用 .npz 将子矩阵（大约 300M 值）保存到磁盘几乎是即时的。
有任何想法吗？
有谁知道在哪里可以找到B + Tree磁盘实现？我经历了谷歌向前和向后,不幸的是我找不到任何明智的东西.其他线程建议可以从sqlite,sqljet或bdb中获取树,但这些树嵌套在整个数据库中,你不能真正"只"过滤掉B + Tree.我真的只是在寻找一个磁盘上的B + Tree ......没有任何奇特的东西.
我有大约5亿个128位整数,每年增加大约1亿个.什么都没有删除.这些数字的分布均匀,按比例和时间分布.
基本上,我只需要一个添加操作,它也会返回DB中是否已存在该数字.此外,我不想为这个系统使用太多RAM,所以只是将所有内容存储在内存中并不是我想要的.
到目前为止,我们一直在MySQL上使用几个MyISAM表,使用两个bigint作为主键.这给了我们好的表现,但我怀疑它不适合这项工作.在拆分表之前我们遇到了一些性能问题,而且我们在停电时已经损坏了.此外,DB为我们提供了许多我们不需要的功能.
我在Linux上使用Python,但我愿意接受建议.
更新:马塞洛的评论提到布卢姆过滤器,这似乎对我很有希望.由于我正在使用哈希,我已经放弃了完全准确性,所以这可能是一个很好的精度/性能折衷.
问题的简化版本
我有一个巨大的矩阵状的数据集,我们现在可以假装实际上是一个n-by- n矩阵存储在磁盘上的n^2IEEE-754双精度(详情请参阅该线之下如何,这是一个简化-它可能是重要的).该文件大约为千兆字节,但在某个(纯)函数中,我只需要n包含在其中的元素的顺序.究竟需要哪些元素是复杂的,而不是简单的切片.
从磁盘和计算中读取文件的解耦有哪些选择？最重要的是,我想把磁盘上的数据看作是在内存中(我当然准备向所有参考透明度的神发誓,磁盘上的数据不会改变).我看过mmap和朋友,但是一些粗略的测试显示这些似乎没有足够的自由记忆.
如果我需要对内存中保存多少文件进行细粒度控制,是否必须将计算结合到IO？
对磁盘数据的更诚实的描述
磁盘上的数据实际上并不像描述的那么简单.更接近事实的是:文件以32位整数开头n.然后恰好出现以下情况n:32位整数m_i> 0(1≤i≤n),紧接着是m_iIEEE-754双精度x_(i,1),…,x_(i, m_i).(所以,这是一个锯齿状的二维数组).
在实践中,确定i和j针对x_(i, j)需要高度依赖于m_i的.当用mmap解决问题时,需要读取这么多m_is似乎基本上将整个文件加载到内存中.问题是这一切似乎都停留在那里,我担心我必须将我的计算拉进去,IO以便对释放这个内存进行更细粒度的控制.
而且,"数据结构"实际上由大量按文件名参数化的文件组成.总之它们总量约一千兆字节.
尝试更加轻松,但可能更容易理解的问题版本
假设我在磁盘上有一些由n^2元素组成的数据.纯Haskell函数需要n元素的顺序,但它们中的哪一个以复杂的方式依赖于值.我不想将整个文件加载到内存中,因为它很大.一种解决方案是将我的函数放入IOmonad并在需要时读出元素,但我称之为"放弃".mmap让我们将磁盘上的数据看作是在内存中,基本上是在操作系统的虚拟内存系统的帮助下进行懒惰的IO.这很好,但是由于确定需要哪些数据元素需要访问大量文件,因此mmap似乎在内存中保留了太多的文件.在实践中,我发现在使用mmap时,读取我需要确定实际需要的数据所需的数据会将整个文件加载到内存中.
我有什么选择？