В инструментах разработчика Chrome есть вкладка Timeline-Memory:
Мы можем наблюдать за занимаемой им памятью.
Также есть профили - Память, где мы можем сделать снимок и посмотреть, что внутри. Снимки можно сравнить друг с другом:
[!d2]
В большинстве случаев это ничего не говорит. Но, по крайней мере, вы можете видеть, какие объекты накапливаются и, возможно, структура утечки.
Другой способ использования 'Task Manager' здесь - статья, касающаяся этого:
http: //www.javascriptkit.com/javatutors/closuresleak/
Вы можете использовать двоичное дерево, процесс вставки которого пытается найти узлы, которые предшествуют значению:
class Tree:
def __init__(self, val=None):
self.left, self.value, self.right = None, val, None
def insert_val(self, _val):
if self.value is None or _val.startswith(self.value):
self.value = _val
else:
if _val < self.value:
getattr(self.left, 'insert_val', lambda x:setattr(self, 'left', Tree(x)))(_val)
else:
getattr(self.right, 'insert_val', lambda x:setattr(self, 'right', Tree(x)))(_val)
def flatten(self):
return [*getattr(self.left, 'flatten', lambda :[])(), self.value, *getattr(self.right, 'flatten', lambda :[])()]
t = Tree()
for i in open('filename.txt'):
t.insert_val(i.strip('\n'))
print(t.flatten())
Выход:
['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EAEUDNBNUW', 'EOEUDNBNUW', 'FGH']
# assuming list is sorted:
pattern = ["ABCDE",
"ABCDEFG",
"ABCDEFGH",
"ABCDEFGHIJKLMNO",
"CEST",
"DBTSFDE",
"DBTSFDEO",
"EOEUDNBNUW",
"EAEUDNBNUW",
"FG",
"FGH"]
pattern = list(reversed(pattern))
def iterate_patterns():
while pattern:
i = pattern.pop()
throw_it_away = False
for p in pattern:
if p.startswith(i):
throw_it_away = True
break
if throw_it_away == False:
yield i
print(list(iterate_patterns()))
Выход:
['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']
blockquote >
with open('demo.txt') as f:
lines = f.readlines()
l_lines = len(lines)
n_lst = []
for i, line in enumerate(lines):
line = line.strip()
if i == l_lines - 1:
if lines[-2] not in line:
n_lst.append(line)
break
if line not in lines[i + 1]:
n_lst.append(line)
print(n_lst)
Выход
['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']
Kenny, вы почти получили его, но есть две проблемы, которые указал @scharette:
for
цикл и удаление элемента списка не должны совпадать. Исправление состоит в том, чтобы использовать цикл while
и явно увеличивать индекс. Цикл while
менее эффективен, потому что он вызывает len()
несколько раз вместо этого один раз, но это то, что требуется для получения правильного результата. IndexError
. Это происходит только в последней строке. Мой способ справиться с этой проблемой - проигнорировать ошибку. При этом я изменил ваш код на:
with open('toy.txt' ,'r') as f:
pattern = f.read().splitlines()
print pattern
try:
i = 0
while i < len(pattern):
if pattern[i] in pattern[i+1]:
pattern.remove(pattern[i])
print pattern
i += 1
except IndexError:
pass
Как указано в других ответах, ваша ошибка возникает из расчета длины вашего ввода в начале, а затем не обновляя его, когда вы сокращаете список.
Вот еще одно взятие в рабочем решении:
with open('toy.txt', 'r') as infile:
input_lines = reversed(map(lambda s: s.strip(), infile.readlines()))
output = []
for pattern in input_lines:
if len(output) == 0 or not output[-1].startswith(pattern):
output.append(pattern)
print('\n'.join(reversed(output)))
Неточное совпадение с вашими ожиданиями, но, учитывая, что вы заявляете, что оно отсортировано (и это не так, рядом с EOEUDNBNUWD EAEUDNBNUW
), и что я не знаю, почему вы отсутствуете EOEUDNBNUWD
, я не уверен, ожидания правильно сформулированы или если я неправильно понял ваш вопрос.
(ах, да, я вижу, что понятие перекрытия бросает ключ в подход sort
и startswith
).
Может быть приятно, что OP повторит этот конкретный аспект, я прочитал комментарий @DSM, не понимая его проблемы. Теперь я делаю.
li = sorted([i.strip() for i in """
ABCDE
ABCDEFG
ABCDEFGH
ABCDEFGHIJKLMNO
CEST
DBTSFDE
DBTSFDEO
EOEUDNBNUW
EOEUDNBNUWD
EAEUDNBNUW
FEOEUDNBNUW
FG
FGH""".splitlines() if i.strip()])
def get_iter(li):
prev = ""
for i in li:
if not i.startswith(prev):
yield(prev)
prev = i
yield prev
for v in get_iter(li):
print(v)
вывод:
ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
EOEUDNBNUWD
FEOEUDNBNUW
FGH
Вы можете использовать groupby()
и max()
, чтобы помочь здесь:
from itertools import groupby
with open('toy.txt') as f_input:
for key, group in groupby(f_input, lambda x: x[:2]):
print(max(group, key=lambda x: len(x)).strip())
Это отобразится:
ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EOEUDNBNUW
EAEUDNBNUW
FGH
groupby()
работает, возвращая список совпадающих элементов на основе функции, в этом случае последовательные строки с теми же первыми двумя символами. Затем функция max()
берет этот список и возвращает элемент списка с самой длинной длиной.
Код
import collections as ct
def read_file(filepath):
"""Yield a generator of lines from a file."""
with open(filepath, "r") as f:
for line in f:
yield line.strip()
def find_longest_sequences(seqs):
"""Return a dict of the long common sequences."""
seqs = tuple(seqs)
dd = ct.defaultdict(list)
[dd[k].append(seq) for seq in seqs for k in seqs if k in seq]
return {max(v, key=len) for v in dd.values()}
data = read_file("test.txt")
find_longest_sequences(data)
Выход
{'ABCDEFGHIJKLMNO',
'CEST',
'DBTSFDEO',
'EAEUDNBNUW',
'EOEUDNBNUWD',
'FEOEUDNBNUW'}
Подробности
Мы используем read_file
для получения каждой строки файла.
find_longest_sequences
создает defaultdict , который группирует аналогичные последовательности вместе. Он выполняет итерацию данных с помощью двух циклов:
Набор значений производится из полученного dict, и возвращаются самые длинные последовательности.
Обратите внимание на некоторые несоответствия с вашим ожидаемым выходом:
FGH
перекрывается с ABCDEFGHIJKLMNO
и, следовательно, не является допустимым выходом. FEOEUDNBNUWD
не является исходной последовательностью. Пост-обработка необходима для перекрывающихся последовательностей. Есть другие рабочие ответы, но ни одна из них не объясняет вашу фактическую проблему. вы действительно были действительно близким к действительному решению и, на мой взгляд, наиболее читаемым ответом.
Ошибка возникла из-за того, что вы изменяли один и тот же список, проверяя индекс, используя range()
.
Таким образом, при увеличении переменной i
вы удаляли элемент из списка, который в какой-то момент неизбежно вызывает index error
.
Поэтому здесь приведена рабочая версия вашего исходного кода с некоторыми изменениями,
pattern = ["ABCDE","ABCDEFG","ABCDEFGH","ABCDEFGHIJKLMNO","CEST","DBTSFDE","DBTSFDEO","EOEUDNBNUW","EAEUDNBNUW","FG","FGH"]
output_pattern = []
for i in range(0, (len(pattern)-1)):
if not pattern[i] in pattern[i+1]:
output_pattern.append(pattern[i])
# Adding the last item
output_pattern.append(pattern[-1])
print (output_pattern)
>>>> ['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']
Обратите внимание, что этот код будет работать, если ваш список был ранее отсортирован, как вы упомянули в разделе комментариев .
Что делает этот код?
В основном, он использует ту же логику вашего первоначального ответа, где он итерации в списке, и проверяет, содержит ли следующий элемент текущий элемент. Но, используя другой список и итерацию до пункта до последнего , исправит вашу проблему с индексом. Но теперь возникает вопрос:
Что мне делать с последним?
Поскольку список отсортирован, вы можете рассматривать последний элемент как всегда будучи уникальным. Вот почему я использую
output_pattern.append(pattern[-1])
, который добавляет последний элемент исходного списка.
Важное примечание
Этот ответ был написан в ответ на начальный вопрос OP, где он хотел сохранить более длинное перекрытие, и я цитирую на основе следующего элемента в том же списке . Как указано в @Chris_Rands, если ваши проблемы связаны с биологической задачей и необходимо найти какое-либо перекрытие, это решение не подходит для ваших нужд.
Пример, где этот код не смог бы распознать потенциальное перекрытие,
pattern = ["ACD", "AD", "BACD"]
, где он выдаст тот же результат, не удаляя возможное перекрытие "ACD"
. Теперь, как пояснение, это будет означать гораздо более сложный алгоритм, и изначально я думал, что это выходит за рамки требований этого вопроса. Если когда-либо это ваш случай, я могу быть совершенно неправ здесь, но я действительно считаю, что реализация на C ++ кажется более подходящей. посмотрите алгоритм CD-Hit, предложенный @Chris_Rands в разделе комментариев.
"ABCD"
и "BABCD"
, код должен содержать первый. Это то, что он делает.
– scharette
15 July 2018 в 11:41
i+1
, например, это невозможно для pattern = ['ACD', 'AD', 'BACD']
– Chris_Rands
17 July 2018 в 09:26
Простым способом является обработка входного файла по одной строке за раз, сравните каждую строку с предыдущей и сохраните предыдущий , если он не содержится в текущем.
Код может быть таким же простым, как:
with open('toy.txt' ,'r') as f:
old = next(f).strip() # keep first line after stripping EOL
for pattern in f:
pattern = pattern.strip() # strip end of line...
if old not in pattern:
print old # keep old if it is not contained in current line
old = pattern # and store current line for next iteration
print old # do not forget last line
Это приведет вас туда, где вы хотите быть:
with open('toy.txt' ,'r') as f:
lines = f.readlines()
data = set(lines)
print(sorted([i for i in lines if len([j for j in data if j.startswith(i)])==1]))
#['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EAEUDNBNUW', 'EOEUDNBNUW', 'FGH']
Я добавил set
только в случае нескольких вхождений одного и того же текста.