Удалить элемент из списка на основе следующего элемента в том же списке

В инструментах разработчика Chrome есть вкладка Timeline-Memory:

Мы можем наблюдать за занимаемой им памятью.

Также есть профили - Память, где мы можем сделать снимок и посмотреть, что внутри. Снимки можно сравнить друг с другом:

enter image description here [!d2]

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

Другой способ использования 'Task Manager' здесь - статья, касающаяся этого:

http: //www.javascriptkit.com/javatutors/closuresleak/

20
задан scharette 14 July 2018 в 00:18
поделиться

11 ответов

Вы можете использовать двоичное дерево, процесс вставки которого пытается найти узлы, которые предшествуют значению:

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']
1
ответ дан Ajax1234 17 August 2018 в 12:34
поделиться
# 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']

4
ответ дан Andrej Kesely 17 August 2018 в 12:34
поделиться
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']
1
ответ дан Druta Ruslan 17 August 2018 в 12:34
поделиться

Kenny, вы почти получили его, но есть две проблемы, которые указал @scharette:

  1. for цикл и удаление элемента списка не должны совпадать. Исправление состоит в том, чтобы использовать цикл while и явно увеличивать индекс. Цикл while менее эффективен, потому что он вызывает len() несколько раз вместо этого один раз, но это то, что требуется для получения правильного результата.
  2. 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
1
ответ дан Hai Vu 17 August 2018 в 12:34
поделиться

Как указано в других ответах, ваша ошибка возникает из расчета длины вашего ввода в начале, а затем не обновляя его, когда вы сокращаете список.

Вот еще одно взятие в рабочем решении:

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)))
0
ответ дан jfg 17 August 2018 в 12:34
поделиться

Неточное совпадение с вашими ожиданиями, но, учитывая, что вы заявляете, что оно отсортировано (и это не так, рядом с 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
1
ответ дан JL Peyret 17 August 2018 в 12:34
поделиться

Вы можете использовать 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() берет этот список и возвращает элемент списка с самой длинной длиной.

5
ответ дан Martin Evans 17 August 2018 в 12:34
поделиться
  • 1
    Они не хотят просто группировать первые два символа, они хотят группироваться на основе одной строки, содержащей другую – Chris_Rands 13 July 2018 в 15:29

Код

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 , который группирует аналогичные последовательности вместе. Он выполняет итерацию данных с помощью двух циклов:

  1. Первый цикл строит диктовку пустых списков с уникальными последовательностями в качестве ключей.
  2. Второй цикл добавляет в качестве значений любые строки, похожие на ключ.

Набор значений производится из полученного dict, и возвращаются самые длинные последовательности.

Обратите внимание на некоторые несоответствия с вашим ожидаемым выходом:

  1. FGH перекрывается с ABCDEFGHIJKLMNO и, следовательно, не является допустимым выходом.
  2. FEOEUDNBNUWD не является исходной последовательностью. Пост-обработка необходима для перекрывающихся последовательностей.
1
ответ дан pylang 17 August 2018 в 12:34
поделиться

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

Ошибка возникла из-за того, что вы изменяли один и тот же список, проверяя индекс, используя 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 в разделе комментариев.

14
ответ дан scharette 17 August 2018 в 12:34
поделиться
  • 1
    Это не совсем правильно, потому что, например, 'abcd' в 'babcd' - & gt; Правда, но они разные. – Rob 15 July 2018 в 11:36
  • 2
    @Rob Нет. Это то, что хотел OP. Вопрос состоял в том, чтобы сохранить наибольшее перекрытие, если оно содержит следующее. Поэтому, учитывая "ABCD" и "BABCD", код должен содержать первый. Это то, что он делает. – scharette 15 July 2018 в 11:41
  • 3
    Вы можете не только рассмотреть i+1, например, это невозможно для pattern = ['ACD', 'AD', 'BACD'] – Chris_Rands 17 July 2018 в 09:26
  • 4
    @chris_rands Пожалуйста, прочитайте раздел комментариев. Я обсуждал этот вопрос с OP. Его первоначальный вопрос состоял в том, чтобы основывать его поиск, и я цитирую в следующем элементе списка . Поэтому это то, что я сделал. Он продолжал менять требования, поэтому я решил сохранить исходное состояние вопроса, который люди проголосовали. – scharette 17 July 2018 в 10:01
  • 5
    @Chris_Rands Я понимаю вашу озабоченность. Я добавлю заметку для будущих пользователей. – scharette 17 July 2018 в 12:09

Простым способом является обработка входного файла по одной строке за раз, сравните каждую строку с предыдущей и сохраните предыдущий , если он не содержится в текущем.

Код может быть таким же простым, как:

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
1
ответ дан Serge Ballesta 17 August 2018 в 12:34
поделиться

Это приведет вас туда, где вы хотите быть:

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 только в случае нескольких вхождений одного и того же текста.

1
ответ дан zipa 17 August 2018 в 12:34
поделиться
Другие вопросы по тегам:

Похожие вопросы: