Python, огромная итеративная проблема выполнения

Позвольте мне развить ответ Роджера Пейта . Если проблема связана с памятью, я бы предложил вместо использования строк в качестве ключей к словарю вы могли бы использовать хешированное значение строки. Это позволит сэкономить на хранении дополнительной копии строк в качестве ключей (в худшем случае, в 20 раз больше, чем хранение отдельного «слова»).

import collections
def hashed_slices(seq, length, hasher=None):
  unique = collections.defaultdict(list)
  for start in xrange(len(seq) - length + 1):
    unique[hasher(seq[start:start+length])].append(start)
  return unique

(Если вы действительно хотите пофантазировать, вы можете использовать скользящий хэш , хотя вам нужно будет изменить функцию.)

Теперь мы можем объединить все хеши:

unique = []  # Unique words in first string

# create a dictionary of hash values -> word index -> start position
hashed_starts = [hashed_slices(word, 20, hashing_fcn) for word in words]
all_hashed = collections.defaultdict(dict)
for i, hashed in enumerate(hashed_starts) :
   for h, starts in hashed.iteritems() :
     # We only care about the first word
     if h in hashed_starts[0] :
       all_hashed[h][i]=starts

# Now check all hashes
for starts_by_word in all_hashed.itervalues() :
  if len(starts_by_word) == 1 :
    # if there's only one word for the hash, it's obviously valid
    unique.extend(words[0][i:i+20] for i in starts_by_word.values())
  else :
    # we might have a hash collision
    candidates = {}
    for word_idx, starts in starts_by_word.iteritems() :
      candidates[word_idx] = set(words[word_idx][j:j+20] for j in starts)
    # Now go that we have the candidate slices, find the unique ones
    valid = candidates[0]
    for word_idx, candidate_set in candidates.iteritems() :
      if word_idx != 0 :
        valid -= candidate_set
    unique.extend(valid)

(Я попытался расширить его, чтобы сделать все три. Это возможно, но сложности отвлекло бы от алгоритма.)

Будьте осторожны, я не тестировал это. Кроме того, вы, вероятно, можете многое сделать для упрощения кода, но алгоритм имеет смысл. Сложнее всего выбрать хеш. Слишком много столкновений, и вы ничего не получите. Слишком мало, и вы столкнетесь с проблемами памяти. Если вы имеете дело только с базовыми кодами ДНК, вы можете хешировать 20-символьную строку в 40-битное число, и при этом не возникнет коллизий. Таким образом, срезы будут занимать почти четверть памяти. Это позволит сэкономить примерно 250 МБ памяти в ответе Роджера Пейта.

Код по-прежнему O (N ^ 2), но константа должна быть намного меньше.

Вы говорите, что у вас есть «слово» длиной в 5 миллионов символов, но мне трудно поверить, что это слово в обычном смысле.

Если вы можете предоставить дополнительную информацию о своем входных данных, может быть доступно конкретное решение.

Например, английский текст (или любой другой письменный язык) может быть достаточно повторяющимся, чтобы можно было использовать дерево . Однако в худшем случае для построения всех 256 ^ 20 ключей ему не хватит памяти. Знание ваших входных данных имеет решающее значение.

edit

Я взглянул на некоторые данные генома, чтобы увидеть, как эта идея складывается, используя жестко запрограммированное отображение [acgt] -> [0123] и 4 дочерних элемента на каждый узел дерева.

1. аденовирус 2 : 35 937 пар оснований -> 35 899 различных последовательностей из 20 оснований с использованием 469 339 тройных узлов

2. энтеробактерий фаг лямбда : 48 502 пар оснований -> 40, 921 отдельная 20-базовая последовательность с использованием 529 384 trie-узлов.

Я не обнаружил никаких коллизий ни внутри, ни между двумя наборами данных, хотя, возможно, в ваших данных больше избыточности и / или перекрытия. Вам придется попробовать это, чтобы увидеть.

Если вы действительно получите полезное количество столкновений, вы можете попробовать пройти три входа вместе, построить единое дерево, записать происхождение каждого листа и отсечь столкновения из дерева как вы идете.

Если вы не можете найти способ сократить ключи, вы можете попробовать использовать более компактное представление. Например, вам нужно только 2 бита для хранения [acgt] / [0123], что может сэкономить вам место за счет чуть более сложного кода.

Я не думаю, что вы можете просто перебрать это хотя - вам нужно найти способ уменьшить масштаб проблемы,

Попробуем улучшить отличный ответ Роджера Пейта .

seqlen = 20
maxlength = max([len(word) for word in words])
for startletter in letters:
    for letterid in range(maxlength):
        for wordid,word in words:
            if (letterid < len(word)):
                letter = word[letterid]
                if letter is startletter:
                    seq = word[letterid:letterid+seqlen]
                    if seq in seqtrie and not wordid in seqtrie[seq]:
                        seqtrie[seq].append(wordid)