def slices(seq, length, prefer_last=False):
unique = {}
if prefer_last: # this doesn't have to be a parameter, just choose one
for start in xrange(len(seq) - length + 1):
unique[seq[start:start+length]] = start
else: # prefer first
for start in xrange(len(seq) - length, -1, -1):
unique[seq[start:start+length]] = start
return unique
# or find all locations for each slice:
import collections
def slices(seq, length):
unique = collections.defaultdict(list)
for start in xrange(len(seq) - length + 1):
unique[seq[start:start+length]].append(start)
return unique
Эта функция (в настоящее время в моем модуле iter_util ) имеет значение O (n) (n - длина каждого слова), и вы должны использовать set(slices(..)) (с операциями над множествами, такими как разность), чтобы получить кусочки уникальный для всех слов (пример ниже). Вы также можете написать функцию для возврата набора, если вы не хотите отслеживать местоположения. Использование памяти будет высоким (хотя по-прежнему O (n), просто большой фактор), возможно, будет уменьшено (хотя и ненамного, если длина всего 20) с помощью специального класса «lazy slice» , который хранит базу последовательность (строка) плюс начало и конец (или начало и длина).
Печать уникальных ломтиков:
a = set(slices("aab", 2)) # {"aa", "ab"}
b = set(slices("abb", 2)) # {"ab", "bb"}
c = set(slices("abc", 2)) # {"ab", "bc"}
all = [a, b, c]
import operator
a_unique = reduce(operator.sub, (x for x in all if x is not a), a)
print a_unique # {"aa"}
Включая местоположения:
a = slices("aab", 2)
b = slices("abb", 2)
c = slices("abc", 2)
all = [a, b, c]
import operator
a_unique = reduce(operator.sub, (set(x) for x in all if x is not a), set(a))
# a_unique is only the keys so far
a_unique = dict((k, a[k]) for k in a_unique)
# now it's a dict of slice -> location(s)
print a_unique # {"aa": 0} or {"aa": [0]}
# (depending on which slices function used)
В тестовом сценарии, более близком к вашим условиям, с использованием случайно сгенерированных слов длиной 5 м и длиной фрагмента 20, использование памяти было настолько высоким, что мой тестовый сценарий быстро превысил предел основной памяти в 1 ГБ и начал перебивать виртуальную память. В этот момент Python потратил очень мало времени на процессор, и я его убил. Сокращение либо длины фрагмента, либо длины слова (так как я использовал совершенно случайные слова, которые уменьшают дубликаты и увеличивает использование памяти), чтобы уместиться в основную память, и это заняло меньше минуты. Эта ситуация плюс O (n ** 2) в вашем исходном коде будет длиться вечно, и поэтому важны алгоритмическая сложность времени и пространства.
import operator
import random
import string
def slices(seq, length):
unique = {}
for start in xrange(len(seq) - length, -1, -1):
unique[seq[start:start+length]] = start
return unique
def sample_with_repeat(population, length, choice=random.choice):
return "".join(choice(population) for _ in xrange(length))
word_length = 5*1000*1000
words = [sample_with_repeat(string.lowercase, word_length) for _ in xrange(3)]
slice_length = 20
words_slices_sets = [set(slices(x, slice_length)) for x in words]
unique_words_slices = [reduce(operator.sub,
(x for x in words_slices_sets if x is not n),
n)
for n in words_slices_sets]
print [len(x) for x in unique_words_slices]