这不是一个现实生活中的问题,它只是一个理论构思。
我有一个很大的数组,由[1,140,245,123443]等元素组成
低选择性的整数或浮点数,唯一值的数目为10
小于数组大小的倍在这种情况下,B*树索引是不好的。
我还尝试实现位图索引,但是在Ruby中,二进制操作不是那么快。
有没有好的算法搜索二维固定大小向量数组?
而且,主要的问题是,我如何转换向量的值,其中转换函数必须是单调的,所以我可以应用范围查询,例如:

(v[0]<10, v[2]>100, v[3]=32, 0.67*10^-8<v[4]<1.2154241410*10^-6)

我唯一的想法是为向量的每个组成部分创建单独的排序索引…二进制搜索然后合并…但这是一个坏主意,因为在最坏的情况下,它将需要O(N*N)操作。。。

最佳答案

假设每个“列”在已知范围内大致均匀地分布,您可以跟踪每个列的一系列bucket,以及满足bucket的行列表。每列的存储桶数量可以相同,也可以不同,这完全是任意的。更多的存储桶更快,但占用的内存略多。

my table:
range:    {1to10} {1to4m}    {-2mto2m}
row1:     {7      3427438335 420645075}
row2:     {5      3862506151 -1555396554}
row3:     {1      2793453667 -1743457796}

buckets for column 1:
bucket{1-3} : row3
bucket{4-6} : row2
bucket{7-10} : row1

buckets for column 2:
bucket{1-2m} :
bucket{2m-4m} : row1, row2, row4

buckets for column 3:
bucket{-2m--1m} : row2, row3
bucket{-1m-0} :
bucket{0-1m} :
bucket{1m-2m} : row1

然后,给定一系列条件:{v[0]<=5, v[2]>3*10^10},我们提取与该条件匹配的存储桶:
 column 1:
v[0]<=5 matches buckets {1-3} and {4-6}, which is rows 2 and 3.
 column 2:
v[2]>3*10^10} matches buckets {2m-4m} and {4-6}, which is rows 1, 2 and 3.
 column 3:
"" matches all , which is rows 1, 2 and 3.

现在我们知道我们要查找的行满足所有三个条件,所以我们列出bucket中与所有条件匹配的所有行,在本例中是第2行和第3行此时,即使对于大量数据,剩余的行数也将很小,这取决于存储桶的粒度。您只需检查此时剩下的每一行,看看它们是否匹配。在这个示例中,我们看到第2行匹配,但第3行不匹配。
这个算法在技术上是o(n),但是在实践中,如果有大量的小bucket,这个算法可以非常快。

关于ruby - 是否有针对大型二维数组的搜索算法?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10729131/

10-08 22:01
查看更多