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

Ответ 1

Этот алгоритм завершает задачу за 0.97 секунды на моем компьютере, входной файл, предоставленный автором (154MB):

l.sort()

last_str = l[0]
filtered = [last_str]
app      = filtered.append

for str in l:
    if not str.startswith(last_str):
        last_str = str
        app(str)

# Commented because of the massive amount of data to print.
# print filtered

Алгоритм прост: сначала отсортируйте список лексикографически, затем найдите первую строку, которая не имеет префикса по первому из списка, затем выполните поиск следующей, которая не префикса последней последней, и др.

Если список уже отсортирован (ваш примерный файл уже отсортирован), вы можете удалить строку l.sort(), что приведет к сложности O (n) как во времени, так и в памяти.

Ответ 2

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

from collections import defaultdict

def find(l):
    d = defaultdict(list)
    # group by first letter
    for ele in l:
        d[ele[0]].append(ele)
    for val in d.values():
        for v in val:
            # check each substring in the sublist
            if not any(v.startswith(s) and v != s  for s in val):
                yield v

print(list(find(l)))
['sdfdg', 'xc', 'ab']

Это правильно фильтрует слова, как вы можете видеть из приведенного ниже кода, что функция сокращения не работает, 'tool' не должен находиться в выводе:

In [56]: l = ["tool",'ab',"too", 'xc', 'abb',"toot", 'abed',"abel", 'sdfdg', 'abfdsdg', 'xccc',"xcew","xrew"]

In [57]: reduce(r,l)
Out[57]: ['tool', 'ab', 'too', 'xc', 'sdfdg', 'xrew']

In [58]: list(find(l))
Out[58]: ['sdfdg', 'too', 'xc', 'xrew', 'ab']

Он также делает это эффективно:

In [59]: l = ["".join(sample(ascii_lowercase, randint(2,25))) for _ in range(5000)]

In [60]: timeit reduce(r,l)
1 loops, best of 3: 2.12 s per loop

In [61]: timeit list(find(l))
1 loops, best of 3: 203 ms per loop

In [66]: %%timeit
..... result = []
....: for element in lst:
....:   is_prefixed = False
....:   for possible_prefix in lst:
....:     if element is not possible_prefix and  element.startswith(possible_prefix):
....:       is_prefixed = True
....:       break
....:   if not is_prefixed:
....:     result.append(element)
....: 
1 loops, best of 3: 4.39 s per loop

In [92]: timeit list(my_filter(l))
1 loops, best of 3: 2.94 s per loop

Если вы знаете, что минимальная длина строки всегдa > 1, вы можете оптимизировать ее еще раз, если строка минимальной длины 2, тогда слово должно иметь минимум две первые две буквы:

def find(l):
    d = defaultdict(list)
    # find shortest length string to use as key length
    mn = len(min(l, key=len))
    for ele in l:
        d[ele[:mn]].append(ele)

    for val in d.values():
        for v in val:
            if not any(v.startswith(s) and v != s for s in val):
                yield v


In [84]: timeit list(find(l))
100 loops, best of 3: 14.6 ms per loop

Наконец, если у вас есть обманщики, вы можете отфильтровать дублированные слова из своего списка, но вам нужно их сравнить:

from collections import defaultdict,Counter

def find(l):
    d = defaultdict(list)
    mn = len(min(l, key=len))
    cn = Counter(l)
    for ele in l:
        d[ele[:mn]].append(ele)
    for val in d.values():
        for v in val:
            if not any(v.startswith(s) and v != s for s in val): 
                # make sure v is not a dupe
                if cn[v] == 1:
                    yield v

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

Чтобы сохранить память, мы можем создать счетчик для каждого val/sublist, поэтому мы сохраняем только один счетчик слов из слов за раз:

def find(l):
    d = defaultdict(list)
    mn = len(min(l, key=len))
    for ele in l:
        d[ele[:mn]].append(ele)
    for val in d.values():
        # we only need check each grouping of words for dupes
        cn = Counter(val)
        for v in val:
            if not any(v.startswith(s) and v != s for s in val):
                if cn[v] == 1:
                    yield v

создавая dict, каждый цикл добавляет 5 мс, так что все равно < 20 мс для 5 тыс. Слов.

Метод уменьшения должен работать, если данные сортируются:

 reduce(r,sorted(l)) # -> ['ab', 'sdfdg', 'too', 'xc', 'xrew']

Чтобы отличить разницу между поведением:

In [202]: l = ["tool",'ab',"too", 'xc', 'abb',"toot", 'abed',
             "abel", 'sdfdg', 'abfdsdg', 'xccc',"xcew","xrew","ab"]

In [203]: list(filter_list(l))
Out[203]: ['ab', 'too', 'xc', 'sdfdg', 'xrew', 'ab']

In [204]: list(find(l))
Out[204]: ['sdfdg', 'too', 'xc', 'xrew', 'ab', 'ab']

In [205]: reduce(r,sorted(l))
Out[205]: ['ab', 'sdfdg', 'too', 'xc', 'xrew']

In [206]: list(find_dupe(l))
Out[206]: ['too', 'xrew', 'xc', 'sdfdg']

In [207]: list(my_filter(l))
Out[207]: ['sdfdg', 'xrew', 'too', 'xc']
In [208]: "ab".startswith("ab")
Out[208]: True

Итак, ab повторяется дважды, поэтому с помощью набора или dict, не отслеживая, как могут появляться времена ab, мы будем считать, что не было другого элемента, удовлетворяющего условию ab "ab".startswith(other ) == True, которое мы можем видеть, что это неверно.

Вы также можете использовать itertools.groupby для группировки на основе индекса минимального размера:

def find_dupe(l):
    l.sort()
    mn = len(min(l, key=len))
    for k, val in groupby(l, key=lambda x: x[:mn]):
        val = list(val)
        for v in val:
            cn = Counter(val)
            if not any(v.startswith(s) and v != s for s in val) and cn[v] == 1:
                yield v

Основываясь на ваших комментариях, мы можем настроить мой первый код, если вы не думаете, что "dd".startswith("dd") должен быть True с повторяющимися элементами:

l = ['abbb', 'xc', 'abb', 'abed', 'sdfdg', 'xc','abfdsdg', 'xccc', 'd','dd','sdfdg', 'xc','abfdsdg', 'xccc', 'd','dd']


def find_with_dupe(l):
    d = defaultdict(list)
    # group by first letter
    srt = sorted(set(l))
    ind = len(srt[0])
    for ele in srt:
        d[ele[:ind]].append(ele)
    for val in d.values():
        for v in val:
            # check each substring in the sublist
            if not any(v.startswith(s) and v != s for s in val):
                yield v


print(list(find_with_dupe(l)))

['abfdsdg', 'abed', 'abb', 'd', 'sdfdg', 'xc']

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

In [15]: l = open("/home/padraic/Downloads/sample.txt").read().split()

In [16]: timeit list(find(l))                                         
100 loops, best of 3: 19 ms per loop

In [17]: %%timeit
   ....: l = open("/home/padraic/Downloads/sample.txt").read().split()
   ....: for i in range(0, len(l) - 1):
   ....:     for j in range(i + 1, len(l)):
   ....:         if l[j].startswith(l[i]):
   ....:             l[j] = l[i]
   ....:         else:
   ....:             if l[i].startswith(l[j]):
   ....:                 l[i] = l[j]
   ....: 

1 loops, best of 3: 4.92 s per loop

Оба возвращают идентичный вывод:

In [41]: l = open("/home/padraic/Downloads/sample.txt").read().split()

In [42]:  
for i in range(0, len(l) - 1):
    for j in range(i + 1, len(l)):
        if l[j].startswith(l[i]):
            l[j] = l[i]
        else:
            if l[i].startswith(l[j]):
                l[i] = l[j]
   ....:                 


In [43]: 

In [43]: l2 = open("/home/padraic/Downloads/sample.txt").read().split()

In [44]: sorted(set(l)) == sorted(find(l2))
Out[44]: True

Ответ 3

Edit3 После некоторой медитации я написал этот алгоритм. Это в 1k раз быстрее, чем метод на основе reduce, основанный на большом наборе случайных данных, предоставленном Padraic Cunningham (спасибо за набор). Алгоритм имеет сложность ~ O (nlogn), хотя для незначительной оптимизации остается некоторое пространство. Это также очень эффективная память. Он занимает примерно n дополнительного пространства.

def my_filter(l):
    q = sorted(l, reverse=True)
    first = q.pop()
    addfirst = True
    while q:
        candidate = q.pop()
        if candidate == first:
            addfirst = False
            continue
        if not candidate.startswith(first):
            if addfirst:
                yield first
            first, addfirst = candidate, True
    if addfirst:
        yield first

Edit2 В моих тестах эта вещь работает так же быстро, как и алгоритм reduce, но это сравнение зависит от используемого набора данных. Я просто анализировал текстовую книгу на слова. Алгоритм основан на следующем наблюдении. Пусть A, B и C - строки, len (A) мин (len (B), len (C)). Заметим, что если A - префикс B, то достаточно проверить, является ли A префиксом C, чтобы сказать, что существует префикс C.

def my_filter(l):
    q = sorted(l, key=len)
    prefixed = []
    while q:
        candidate = q.pop()
        if any(candidate.startswith(prefix) for prefix in prefixed):
            continue
        if any(candidate.startswith(string) for string in q):
            prefixed.append(candidate)
        else:
           yield candidate

Оригинальное сообщение Это оригинальный алгоритм, который я предложил. на самом деле это краткая версия вашего алгоритма.

l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']

res = [string for string in l if sum(not string.startswith(prefix) for prefix in l) == len(l)-1]

Demo → >

print res
# ['ab', 'xc', 'sdfdg']

Ответ 4

lst = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
result = []

for element in lst:
  is_prefixed = False
  for possible_prefix in lst:
    if element is not possible_prefix and element.startswith(possible_prefix):
      is_prefixed = True
      break
  if not is_prefixed:
    result.append(element)

Ниже приведена экспериментальная многопоточная версия:

Проверьте это хорошо!

import thread
import math
import multiprocessing

list = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']

def get_results(list, thread_num, num_of_threads):  
  result = []
  part_size = int(math.ceil(len(list) * 1.0 / num_of_threads))
  for element in list[part_size * thread_num: part_size * (thread_num + 1)]:    
    is_prefixed = False
    for possible_prefix in list:
      if element is not possible_prefix and     element.startswith(possible_prefix):
    is_prefixed = True
    if not is_prefixed:
      result.append(element)
  return result

num_of_threads = multiprocessing.cpu_count()
results = []
for t in xrange(num_of_threads):  
  thread.start_new_thread(lambda list: results.extend(get_results(list, t, num_of_threads)), (list,))

Ответ 5

from collections import Counter


def filter_list(mylist):

    longest_string = len(max(mylist, key=len))

    set_list = [set(filter(lambda x: len(x) == i, mylist))
                for i in range(1, longest_string)]

    def unique_starts_with_filter(string):
        for i in range(1, len(string)):
            if string[:i] in set_list[i-1]: return False
        return True

    cn = Counter(mylist)
    mylist = filter(lambda x: cn[x] == 1, mylist)

    return filter(unique_starts_with_filter, mylist)

Отредактировано (снова) для стиля и очень незначительных оптимизаций

Ответ 6

Решение 1 (с использованием LinkedList)

Вот очень простое решение, использующее сортировку (O(n * log(n))) и LinkedList - итерацию (O(n)) и удаление элементов (O(1)). Если сортировать исходные данные, элементы будут упорядочены таким образом, что самый длинный префиксный элемент для другого элемента будет смежным с более поздним. Таким образом, этот элемент может быть удален.

Вот код, который отфильтровывает отсортированный LinkedList:

def filter_out(the_list):
    for element in the_list:
        if element.prev_node and element.get_data().startswith(element.prev_node.get_data()):
            the_list.remove(element)

    return the_list

И используйте его следующим образом:

linked_list = LinkedList(sorted(l))
filter_out(linked_list)

Затем ваш linked_list будет содержать отфильтрованные данные.

Это решение займет O(n * log(n))

И вот реализация LinkedList:

class Node(object):
    def __init__(self, data=None, next_node=None, prev_node=None):
        self.data = data
        self._next_node = next_node
        self._prev_node = prev_node

    def get_data(self):
        return self.data

    @property
    def next_node(self):
        return self._next_node

    @next_node.setter
    def next_node(self, node):
        self._next_node = node

    @property
    def prev_node(self):
        return self._prev_node

    @prev_node.setter
    def prev_node(self, node):
        self._prev_node = node

    def __repr__(self):
        return repr(self.get_data())


class LinkedList(object):
    def __init__(self, iterable=None):
        super(LinkedList, self).__init__()

        self.head = None
        self.tail = None
        self.size = 0

        if iterable:
            for element in iterable:
                self.insert(Node(element))

    def insert(self, node):
        if self.head:
            self.tail.next_node = node
            node.prev_node = self.tail
            self.tail = node
        else:
            self.head = node
            self.tail = node

        self.size += 1

    def remove(self, node):
        if self.size > 1:
            prev_node = node.prev_node
            next_node = node.next_node

            if prev_node:
                prev_node.next_node = next_node
            if next_node:
                next_node.prev_node = prev_node
        else:
            self.head = None
            self.tail = None

    def __iter__(self):
        return LinkedListIter(self.head)

    def __repr__(self):
        result = ''
        for node in self:
            result += str(node.get_data()) + ', '
        if result:
            result = result[:-2]
        return "[{}]".format(result)


class LinkedListIter(object):
    def __init__(self, start):
        super(LinkedListIter, self).__init__()

        self.node = start

    def __iter__(self):
        return self

    def next(self):
        this_node = self.node

        if not this_node:
            raise StopIteration

        self.node = self.node.next_node
        return this_node

Решение 2 (с использованием набора)

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

Итак, сделаем несколько определений:

n - размер вашего списка, т.е. количество элементов

m - максимально возможная длина строкового элемента вашего списка

Прежде всего, инициализируйте новый set inter из исходного list l:

inter = set(l)

этим мы удалим все дублирующие элементы, что облегчит нашу дальнейшую работу. Кроме того, эта операция будет иметь сложность O(n) в среднем и O(n^2) в худшем случае.

Затем сделайте еще один пустой set, где мы сохраним наши результаты:

result = set()

Итак, теперь давайте проверим для каждого из элементов, есть ли у него суффикс в нашем наборе inter:

for elem in inter:                   # This will take at most O(n)
    no_prefix = True
    for i in range(1, len(elem)):    # This will take at most O(m)
        if elem[:i] in inter:        # This will take avg: O(1), worst: O(n)
            no_prefix = False
            continue

    if no_prefix:
        result.add(elem)             # This will take avg: O(1), worst: O(n)

Итак, теперь у вас есть то, что вы хотели в result.

Этот последний и основной шаг будет принимать O(n * (1 * m + 1)) = O(n * m) в среднем и O(n * (m * n + n)) = O(n^2 * (m + 1)) в худшем случае, поэтому, если m является незначительным по сравнению с n, то вы в среднем O(n) и O(n ^ 2) в худшем случай.

Сложности вычисляются на основе того, что Python предоставляет структуру данных set. Для дальнейшей оптимизации алгоритма вы можете реализовать свою сложность tree-based set и получить O(n * log(n)).

Ответ 7

Я считаю, что наиболее вероятным может оказаться следующее:

from sortedcontainers import SortedSet
def prefixes(l) :
    rtn = SortedSet()
    for s in l:
        rtn.add(s)
        i = rtn.index(s)
        if (i > 0 and s.startswith(rtn[i-1])):
            rtn.remove(s)
        else :
            j = i+1
            while (j < len(rtn) and rtn[j].startswith(s)):
                j+=1
            remove = rtn[i+1:j]
            for r in remove:
                rtn.remove(r)
    return list(rtn)

Я считаю, что наиболее важным случаем является, вероятно, очень длинные входные файлы с гораздо меньшими выходными файлами. Это решение позволяет избежать хранения всего входного файла в памяти. Если входной файл отсортирован, он никогда не содержит аргумент rtn дольше, чем конечный возвращенный файл. Более того, в нем демонстрируется модель "поддерживать решение, которое является действительным для данных, рассматриваемых до сих пор, и расширить это решение, чтобы оно было действительным для каждой новой части данных". Это хороший образец, чтобы ознакомиться с ним.

Ответ 8

Решение с использованием функции уменьшения:

def r(a, b):
    if type(a) is list:
        if len([z for z in a if b.startswith(z)]) == 0:
            a.append(b)
        return a
    if a.startswith(b):
        return b
    if b.startswith(a):
        return a
    return [a, b]

print reduce(r, l)

Возможно, часть [z for z in a if b.startswith(z)] может быть дополнительно оптимизирована.

Ответ 9

Вы можете попробовать это короткое решение.

import re
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
newl=[]
newl.append(l[0])
con=re.escape(l[0])

for i in l[1:]:
    pattern=r"^(?!(?:"+con+r")).*$"
    if re.match(pattern,i):
        newl.append(i)
        con=con+"|"+re.escape(i)


print newl

EDIT: для длинных списков используйте

import re
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
newl=[]
newl.append(l[0])
con=re.escape(l[0])

for i in l[1:]:
    for x in re.split("\|",con):
        pattern=r"^(?="+x+r").*$"
        if re.match(pattern,i):
            break
    else:
        newl.append(i)
        con=con+"|"+re.escape(i)


print newl