查找与输入数组具有最大交集的数组的有效方法
Efficient way to find array with the largest intersection to an input array
假设我有一大组数组(大小可达数百万),我想确定(最好是准确地确定,虽然近似是可以的)该组中与输入的交集最大的数组,最有效的方法是什么?我会在底部列出一些我想到的解决方案,将其简化为另一个问题,但我不确定它们是否一定是最好的。
这组数组可以存储在任何数据结构中,数组可以按任何方式排序存储。这里的想法是优化查询时间。
示例:假设我的数组集是(为方便起见,以类似基数的方式排序,可以选择任何方式排序):
[('a', 'b'), ('a', 'e', 'f'), ('b', 'f', 'g'), ('b', 'j', 'z'), ('d', 'l', 'f'), ('x', 'y', 'z')]
我的输入数组是:
('a', 'f')
那么各自的路口是:
[('a'), ('a', 'f'), ('f'), (), ('f'), ()]
所以输出将是 ('a', 'f')
,具有大小 2 的最大交集。作为奖励,拥有其中最大的 K
会更好,所以在这里,如果 K = 3,输出将是(以任何顺序):
[('a', 'f'), ('f'), ('a')]
我想到的一些可能的解决方案:
- 我的域的大小受到限制,(因为它可能是 a-z 或
数字 1-70 等)所以我可以将它们表示为二进制
字符串,现在的挑战变成了找到最小的汉明顿
距离,我现在可以用像局部散列这样的东西来做?例如
('a', 'f')
可以表示为 10000100000000000000000000
- 还利用域受限的事实,我可以创建一些
域中的项目指向不同的倒排索引
集合中的数组,然后为输入数组中的每个项目与这些结果(至少一些)相交——尽管我觉得这样
会非常低效(特别是如果十字路口转弯
出很小) - 类似于 google 搜索的工作方式,尽管我不知道他们算法的全部细节
感谢您对正确方向的任何回应或指示!
我建议使用哈希集的 straight-forward 方法。
如果 hashset 实现得很好,有一个好的 hash 函数,那么我们可以考虑检查一个元素是否是这个集合的一部分可以在 O(1)
.
中完成
然后,我们可以进行以下操作:
function find_closest_arrays(A, B_1, ..., B_n) {
result = [0, ..., 0] // array of size n
for elem in A {
for i in 1 ... n {
if elem is in B_i {
result[i] ++
}
}
}
return result
}
这个函数return一个数组result
。 result[i]
包含输入数组 A
和 B_i
之间共有的元素数。
从这里开始,获得 k
最好的是非常直接的,你所要做的就是获得 result
.
中 k
最大数字的索引
该算法的时间复杂度为 O(n * m)
,输入数组的大小为 m
,数组集的大小为 n
。
由于缺乏声誉,我无法通过评论预先提出的一些问题:
- 所有数组都是唯一的,但每个数组本身都是一个集合吗?
- 如果多个数组共享最大交集大小,是否需要将它们全部列出?
- 您的输入可能比给定的最长数组长?
迭代
如果没有哈希集,我会按长度对数组进行排序,并从最长的数组开始,最后可能会通过找到一个大于或等于较短数组大小的交集大小来跳过较短的数组。
如果您还对数组本身进行排序,则可以利用汉明顿距离,但您不必同时对所有数组进行排序和转换,而只需从其中的一部分开始。如果您不使用 Hammington 请记住,如果您将输入与输入大小为 + 1 的数组进行比较,则只需进行比较,直到遇到输入的最后一个元素小于当前数组的第一个比较元素.
a f
a c k z // since k > f we don't need to compare f and z
我认为这种方式会归结为 O(n lg n) 的复杂度,因为按大小对数组进行排序是 O(n lg n),计算大小 n * O(1) 并执行内基数排序 O(n)。比较本身将是 O(n lg n) (对此不太确定)所以总数将是 O(n lg n) * 2 + 2 * O(n) => O(n lg n).
树
只是一个粗略的想法:您可以使用 Radix 对所有数组进行排序并将它们转换为 Hemmington,然后从那里用它们填充一棵树并遍历它直到没有进一步的遍历会导致更小的距离。我不知道这有多有效。
假设我有一大组数组(大小可达数百万),我想确定(最好是准确地确定,虽然近似是可以的)该组中与输入的交集最大的数组,最有效的方法是什么?我会在底部列出一些我想到的解决方案,将其简化为另一个问题,但我不确定它们是否一定是最好的。
这组数组可以存储在任何数据结构中,数组可以按任何方式排序存储。这里的想法是优化查询时间。
示例:假设我的数组集是(为方便起见,以类似基数的方式排序,可以选择任何方式排序):
[('a', 'b'), ('a', 'e', 'f'), ('b', 'f', 'g'), ('b', 'j', 'z'), ('d', 'l', 'f'), ('x', 'y', 'z')]
我的输入数组是:
('a', 'f')
那么各自的路口是:
[('a'), ('a', 'f'), ('f'), (), ('f'), ()]
所以输出将是 ('a', 'f')
,具有大小 2 的最大交集。作为奖励,拥有其中最大的 K
会更好,所以在这里,如果 K = 3,输出将是(以任何顺序):
[('a', 'f'), ('f'), ('a')]
我想到的一些可能的解决方案:
- 我的域的大小受到限制,(因为它可能是 a-z 或
数字 1-70 等)所以我可以将它们表示为二进制
字符串,现在的挑战变成了找到最小的汉明顿
距离,我现在可以用像局部散列这样的东西来做?例如
('a', 'f')
可以表示为10000100000000000000000000
- 还利用域受限的事实,我可以创建一些 域中的项目指向不同的倒排索引 集合中的数组,然后为输入数组中的每个项目与这些结果(至少一些)相交——尽管我觉得这样 会非常低效(特别是如果十字路口转弯 出很小) - 类似于 google 搜索的工作方式,尽管我不知道他们算法的全部细节
感谢您对正确方向的任何回应或指示!
我建议使用哈希集的 straight-forward 方法。
如果 hashset 实现得很好,有一个好的 hash 函数,那么我们可以考虑检查一个元素是否是这个集合的一部分可以在 O(1)
.
中完成
然后,我们可以进行以下操作:
function find_closest_arrays(A, B_1, ..., B_n) {
result = [0, ..., 0] // array of size n
for elem in A {
for i in 1 ... n {
if elem is in B_i {
result[i] ++
}
}
}
return result
}
这个函数return一个数组result
。 result[i]
包含输入数组 A
和 B_i
之间共有的元素数。
从这里开始,获得 k
最好的是非常直接的,你所要做的就是获得 result
.
中 k
最大数字的索引
该算法的时间复杂度为 O(n * m)
,输入数组的大小为 m
,数组集的大小为 n
。
由于缺乏声誉,我无法通过评论预先提出的一些问题:
- 所有数组都是唯一的,但每个数组本身都是一个集合吗?
- 如果多个数组共享最大交集大小,是否需要将它们全部列出?
- 您的输入可能比给定的最长数组长?
迭代
如果没有哈希集,我会按长度对数组进行排序,并从最长的数组开始,最后可能会通过找到一个大于或等于较短数组大小的交集大小来跳过较短的数组。
如果您还对数组本身进行排序,则可以利用汉明顿距离,但您不必同时对所有数组进行排序和转换,而只需从其中的一部分开始。如果您不使用 Hammington 请记住,如果您将输入与输入大小为 + 1 的数组进行比较,则只需进行比较,直到遇到输入的最后一个元素小于当前数组的第一个比较元素.
a f
a c k z // since k > f we don't need to compare f and z
我认为这种方式会归结为 O(n lg n) 的复杂度,因为按大小对数组进行排序是 O(n lg n),计算大小 n * O(1) 并执行内基数排序 O(n)。比较本身将是 O(n lg n) (对此不太确定)所以总数将是 O(n lg n) * 2 + 2 * O(n) => O(n lg n).
树
只是一个粗略的想法:您可以使用 Radix 对所有数组进行排序并将它们转换为 Hemmington,然后从那里用它们填充一棵树并遍历它直到没有进一步的遍历会导致更小的距离。我不知道这有多有效。