logo标签列表

C/C++中的大数据集表示

c++cdataset
3
什么是最好的方法来表示以下数据，以便进行后续的并行计算：
一个由整数组成的四元组集合（约20,000,000个），需要通过前三个元素作为索引进行访问？
计算应该使用C/C++中的MPI完成。
更新：我还应该强调一点，我有两个类似的数据结构，上面描述了它们唯一的区别是第一个是静态的，第二个是动态的。准确地说，第二个结构中每个元组的第四个元素应该被计算出来。
根据评论，我现在倾向于使用C++的向量，并通过前三个值对它们进行哈希。我想我需要创建一个哈希图。如何在C++中做到这一点？
前三个元素组成一个复合键（即它们三个作为整体是键），还是每个元素都可以独立地充当键？ - Peter Alexander
这些四元组中的第四个值是否会被计算修改，还是严格作为输入使用？并行处理的多个部分是否可能需要同时访问同一个四元组？ - Mark B
读写模式会是什么样子 - 任何静态数据结构都可以被多个线程读取而没有问题，但是改变数据结构可能会比较棘手。 - phkahler
@Poita_: 前三个元素构成一个键，但是单独的任何一个都不能作为一个键。 - Alex
@Mark B：实际上有两个集合：其中一个修改了第四个值，另一个没有修改。 - Alex
@phkahler：第一个数据结构是静态的，第二个数据结构只应该从一个进程中访问。 - Alex
4个回答
2
这听起来像是在三维空间中的点数据。针对这个问题有许多解决方案，其中最佳选择取决于您的索引范围和分布，以及数据访问模式。后者尤其重要——您是随机选择一组值作为键，并查看是否存在一个数据四元组，还是以更规则的方式访问它们？不同的数据结构对于常规和随机访问提供非常不同的成本。
为了描述起见，我将称你的数据四元组为 {X，Y，Z，W}，其中{X，Y，Z}是您的键，W是与该键相关联的值。
如果您拥有一个矩形范围 Xmin 到 Xmax，Ymin 到 Ymax，Zmin 到 Zmax，并且此范围密集地填充，以使该范围内的每个 X、Y 和 Z 都有一个关联的数据四元组，那么您只需使用由 X、Y 和 Z 索引的 3D 数组，在该数组中的每个点上存储 W。
如果你有类似的情况，只有一些值与数据四元组相关联，但比例相当大（例如25％或更多），那么仍然可以使用3D数组，在该数组的每个点上存储一个W值或“无”。 如果您需要能够回答X、Y、Z三元组是否在数据集中的问题，则可以存储一个不可能的W值（例如-1，如果它们是正整数，则为INT_MAX，如果它们是有限的），或者在每个点上存储一个W整数和一个布尔型“is_present”标志的结构，并为该索引是否存在于您的数据集中设置标志为true/false。
如果您的数据四元组比这更稀疏，但索引仍在合理范围内，您可以使用一种称为八叉树的结构来表示数据集。维基百科在此处提供了带有图表的说明：http://en.wikipedia.org/wiki/Octree。基本上，您将可能索引范围分成8个八分体。如果该八分体中只有几个数据四元组，则存储它们的列表；否则，您将递归地将该八分体分成8个子八分体，并重复此过程。最终，您会得到这个八分体和子八分体的树，每个叶子节点都是一个小的数据四元组列表。虽然在树中定位单个点很昂贵（您必须从顶部遍历树），但查找附近的邻居、在相同空间中查找多个点以及迭代树中所有点都很便宜。
1

你计划在什么样的系统上运行这个程序？

整个程序能够放入内存吗？还是有需要解决的I/O或缓存问题？

每个整数占用多少字节？

如果是32位，那么你大约需要(20M*4*4)≈305MB的数据量，这可以轻松放入专用系统的内存中，或者对于一个多功能PC来说也是可以的。

如果你有最理想的硬件条件，可以把整个程序连续地放入一块RAM中。这样排序一个由这些四元组构成的向量只需要O(N)的时间。然后从中进行索引将会非常快速。

@fbrereto：初始数据文件大小约为500MB，因此它适合存储在内存中。 - Alex
1

由于第一个结构是只读的，第二个结构仅通过一个线程访问（听起来是这样），您不必担心并发问题。

如果您知道索引的三个部分将在整数值的“小”范围内分组，则可以使用带有一些未使用内存的（可能嵌套的）向量并直接使用索引。 这具有相当快的优势，但如果索引可以涵盖大范围的整数值，则无法使用。

或者，如果您具有广泛的键值范围，可以使用映射，哈希映射或排序向量。 映射很容易使用，但具有每个节点的内存开销。 同样，哈希映射将提供出色的查找时间，但再次具有内存开销。 排序向量仍将提供O（log n）的查找，而不具有映射的每个节点开销。

@Mark B：索引的三个部分范围分别为100000:999999，10:99，100:999。 - Alex
0

正如评论者所建议的（或者我理解的那样），他们建议先对前三个值进行哈希处理，然后将其用作某个哈希映射表中的键。

你也可以尝试使用B树或B*树，并将数据存储在文件中。 - Gabriel Ščerbák
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接