Мы возьмем набор данных, украсим каждый элемент подписью и
сортировать это. Подпись имеет свойство, которое сортирует сгруппировать
те элементы вместе, которые могут иметь дубликаты. когда
сравнивая data_set [j] с элементами в data_set [j + 1 ...], когда
Первая подпись в [j + 1 ...] проверке дубликатов проваливается, мы продвигаемся
я. Этот «критерий смежности» гарантирует, что нам не нужно смотреть дальше;
ни один элемент кроме этого не может быть дубликатом.
Это значительно уменьшает сравнение O (N ^ 2). Сколько я позволю
Аналитик алгоритма решает, но код, приведенный ниже, сравнивает ~ 400 Кб
вместо 100 м наивного 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), отметим, что
если проверка подписи не пройдена, она никогда не станет верной.
Критерий смежности имеет место. Кроме того, этот критерий смежности
выполняется для всех положительных значений, а не только для "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))