1

这不是一个现实生活中的问题，它只是理论制作。

我有一个大数组，它由诸如[1,140,245,123443]、所有整数或具有低选择性的浮点数之类的元素组成，并且唯一值的数量是数组大小的十倍。在这种情况下，B*tree 索引并不好。

我也尝试实现位图索引，但在 Ruby 中，二进制操作并没有那么快。

有没有什么好的算法来搜索固定大小向量的二维数组？

而且，主要问题是，如何将向量转换为值，其中转换函数必须是单调的，因此我可以应用范围查询，例如：

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

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

4

2 回答 2

2

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

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.

现在我们知道我们要查找的行满足所有三个条件，因此我们列出了桶中匹配所有条件的所有行，在本例中为第 2 行和第 3 行。此时，即使对于大量数据，剩余的行数也会很少，具体取决于存储桶的粒度。您只需检查此时剩下的每一行，看看它们是否匹配。在此示例中，我们看到第 2 行匹配，但第 3 行不匹配。

这个算法在技术上是O(n)，但在实践中，如果你有大量的小桶，这个算法可以非常快。

于 2012-05-24T00:25:50.020 回答
0

使用索引:)

基本思想是将二维数组转换为一维排序数组（同时保持原始位置）并在后面应用二进制搜索。

此方法适用于任何 n 维数组，并被数据库广泛使用，可以将其视为具有可变长度的维数组。

于 2012-05-23T23:16:47.400 回答