我是一名物理学研究生,我正在编写一些代码来对数百 GB 的数据进行排序,并在我要求时返回该数据的切片。这是诀窍,我不知道排序和搜索这种数据的好方法。
我的数据本质上由大量的数字组成。这些集合中可以包含 1 到 n 个数字(尽管在 99.9% 的集合中,n 小于 15)并且这些集合中大约有 1.5 到 20 亿个(不幸的是,这个大小排除了蛮力搜索)。
我需要能够指定一个包含 k 个元素的集合,并让每个包含 k+1 个元素或更多元素的集合返回给我。
简单示例:
假设我的数据有以下集合:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
( 5,8,11)
如果我提出请求 (1,3),我将拥有以下集合:(1,2,3)、(1,2,3,4,5) 和 (1,3,8,9)。
请求 (11) 将返回集合:(5,8,11)。
请求 (1,2,3) 将返回集合:(1,2,3) 和 (1,2,3,4,5)
请求 (50) 将不返回集合:
现在模式应该很清楚了。这个例子和我的数据的主要区别是我的数据的集合更大,集合中每个元素使用的数字从 0 到 16383(14 位),还有很多很多很多的集合。
如果重要的话,我会用 C++ 编写这个程序,尽管我也知道 java、c、一些程序集、一些 fortran 和一些 perl。
有没有人知道如何解决这个问题?
编辑:
回答几个问题并补充几点:
1.) 数据不变。这一切都是在一组很长的运行中完成的(每个运行分为 2 个演出文件)。
2.) 至于存储空间。原始数据占用大约 250 GB。我估计,在处理和剥离了很多我不感兴趣的无关元数据之后,我可以将其降低到 36 到 48 GB 之间,具体取决于我决定保留多少元数据(没有索引)。此外,如果在我对数据的初始处理中遇到足够多的相同集合,我可能能够通过添加重复事件的计数器来进一步压缩数据,而不是简单地一遍又一遍地重复事件。
3.) Each number within a processed set actually contains at LEAST two numbers 14 bits for the data itself (detected energy) and 7 bits for metadata (detector number). So I will need at LEAST three bytes per number.
4.) My "though in 99.9% of the sets, n is less than 15" comment was misleading. In a preliminary glance through some of the chunks of the data I find that I have sets that contain as many as 22 numbers but the median is 5 numbers per set and the average is 6 numbers per set.
5.) While I like the idea of building an index of pointers into files I am a bit leery because for requests involving more than one number I am left with the semi slow task (at least I think it is slow) of finding the set of all pointers common to the lists, ie finding the greatest common subset for a given number of sets.
6.) In terms of resources available to me, I can muster approximately 300 gigs of space after I have the raw data on the system (The remainder of my quota on that system). The system is a dual processor server with 2 quad core amd opterons and 16 gigabytes of ram.
7.) Yes 0 can occur, it is an artifact of the data acquisition system when it does but it can occur.