我们将获取数据集,用签名装饰每个元素,然后对其进行排序。签名具有排序将那些可能有重复的元素组合在一起的属性。在将 data_set[j] 与 data_set[j+1 ...] 中的项目进行比较时,当 [j+1 ...] 中的第一个签名重复检查失败时,我们推进 i。这个“邻接标准”确保我们不必进一步研究;除此之外的任何元素都不能重复。
这大大减少了 O(N^2) 比较。我会让算法分析师决定多少,但下面的代码进行了大约 400k 的比较,而不是 100m 的简单 O(N^2)。
签名从对元素进行分桶开始。我们将数字的范围划分为 N 个大小相等的桶:1..k, k+1..2k, 2k+1..3k, ... 当迭代元素时,如果数字落入,我们增加计数一个特殊的桶。这会产生形式 (0,0,0,1,3,0,0,...4,2) 的初始签名。
签名具有如果
sum(min(sig_a[i], sig_b[i]) for i in range(10)) >= 5
那么与签名关联的元素可能至少有 5 个重复项。但更重要的是,如果以上不成立,则元素不能有 5 个重复项。让我们称之为“签名匹配标准”。
但是,按上述签名排序不具有上述邻接性。但是,如果我们将签名修改为二元形式:
(sum(sig[:-1]), sig[-1])
那么“签名匹配标准”成立。但是邻接标准成立吗?是的。该签名的总和是 10。如果我们枚举,我们有以下可能的签名:
(0,10) (1, 9) (2, 8) (3, 7) (4, 6) (5, 5) (6, 4) (7, 3) (8, 2) (9, 1) (10,0)
如果我们将 (0,10) 与 (1,9) .. (10,0) 进行比较,我们注意到一旦签名测试失败,它就再也不会变为 true。邻接准则成立。此外,该邻接标准适用于所有正值,而不仅仅是“5”。
好的,这很好,但是将签名分成两个大桶不一定会减少 O(N^2) 搜索;签名过于笼统。我们通过为 sig[:-1] 创建签名来解决这个问题,产生
(sum(sig[:-1]), sig[-1]), (sum(sig[:-2]), sig[-2]), ...
等等。我相信这个签名仍然满足邻接,但我可能是错的。
有一些优化我没有做:签名只需要每个元组的最后一个值,而不是第一个值,但排序步骤必须修改。此外,当很明显进一步的扫描无法成功时,可以通过早期失败来优化签名比较。
# python 3.0
import random
# M number of elements, N size of each element
M = 10000
N = 10
# Bounds on the size of an element of each set
Vmin,Vmax = 0, (1 << 12)
# DupCount is number of identical numbers required for a duplicate
DupCount = 5
# R random number generator, same sequence each time through
R = random.Random()
R.seed(42)
# Create a data set of roughly the correct size
data_set = [list(s) for s in (set(R.randint(Vmin, Vmax) for n in range(N)) for m in range(M)) if len(s) == N]
# Adorn the data_set signatures and sort
def signature(element, width, n):
"Return a signature for the element"
def pearl(l, s):
def accrete(l, s, last, out):
if last == 0:
return out
r = l[last]
return accrete(l, s-r, last-1, out+[(s-r,r)])
return accrete(l, s, len(l)-1, [])
l = (n+1) * [0]
for i in element:
l[i // width] += 1
return pearl(l, len(element))
# O(n lg(n)) - with only 10k elements, lg(n) is a little over 13
adorned_data_set = sorted([signature(element, (Vmax-Vmin+1)//12, 12), element] for element in data_set)
# Count the number of possible intersections
def compare_signatures(sig_a, sig_b, n=DupCount):
"Return true if the signatures are compatible"
for ((head_a, tail_a), (head_b, tail_b)) in zip(sig_a, sig_b):
n -= min(tail_a, tail_b)
if n <= 0:
return True
return False
k = n = 0
for i, (sig_a, element_a) in enumerate(adorned_data_set):
if not element_a:
continue
for j in range(i+1, len(adorned_data_set)):
sig_b, element_b = adorned_data_set[j]
if not element_b:
continue
k += 1
if compare_signatures(sig_a, sig_b):
# here element_a and element_b would be compared for equality
# and the duplicate removed by adorned_data_set[j][1] = []
n += 1
else:
break
print("maximum of %d out of %d comparisons required" % (n,k))