题 获取包含字符串元素的列表,不包括前缀为初始列表中任何其他元素的元素


我在过滤字符串列表时遇到了一些麻烦。我发现了一个类似的问题 这里 但不是我需要的。

输入列表是:

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

而预期的结果是

['ab', 'xc', 'sdfdg']

结果中项目的顺序并不重要

过滤器功能必须快,因为列表的大小很大

我目前的解决方案是

l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
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]

print list(set(l)) 

编辑

在使用大输入数据进行多次测试后,列出了1500000个字符串,我的最佳解决方案是:

def filter(l):
    if l==[]:
        return []
    l2=[]
    l2.append(l[0])
    llen = len(l)
    k=0
    itter = 0
    while k<llen:
        addkelem = ''
        j=0
        l2len = len(l2)
        while j<l2len:
            if (l2[j].startswith(l[k]) and l[k]!= l2[j]):
                l2[j]=l[k]
                l.remove(l[k])
                llen-=1
                j-=1
                addkelem = ''
                continue
            if (l[k].startswith(l2[j])):
                addkelem = ''
                break
            elif(l[k] not in l2):
                addkelem = l[k]
            j+=1
        if addkelem != '':
            l2.append(addkelem)
            addkelem = ''
        k+=1
    return l2

执行时间约为213秒

样本输入数据  - 每一行都是列表中的字符串


13
2018-05-12 09:30


起源


结果顺序重要吗?我的意思是算法应该稳定并保持原始顺序吗? - bagrat
输出顺序并不重要,过滤和执行时间至关重要 - vasilenicusor
结账我的回答,我的2.7 GHz计算机上的1.500.000元素大约需要1.5秒。 - bagrat


答案:


该算法在我的计算机上以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)复杂性。


12
2018-05-15 03:03



快捷方便。是最快的解决方案,我喜欢这个 - vasilenicusor
如果优化并制成功能,这可能是最好的方法。 - Inbar Rose
优秀的解决方关键在于 append 需要不断的时间。 - bagrat
比我的解决方案简单得多,我需要解决问题的复杂性 map(str.rstrip.. 获取正确结果的文件对象,即251 - Padraic Cunningham
如果你想制造发电机 pastebin.com/U7tQnrja - Padraic Cunningham


您可以按首字母对项目进行分组,只搜索子列表,除非字符串至少包含相同的第一个字母,否则任何字符串都不能以子字符串开头:

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']

这正确地过滤了单词,正如您从下面的代码中看到的那样,reduce函数没有, '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

如果您知道最小字符串长度始终> 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每个循环增加5ms所以仍然<20ms为5k字。

如果数据已排序,则reduce方法应该有效:

 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 重复两次,所以使用一套或一个字典,而不记录时间 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") 应该是重复的元素:

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

8
2018-05-12 10:57



嗨Padraic。你会对我的答案进行测试吗?我想看看它是如何与相同数据和同一台机器上的其他人堆叠起来的。 - skolsuper
+1代表很好的例子。我已经测试了您的示例,并且可以使用小输入数据。如果数据输入增加,则执行以指数方式增加。这也没有重复。 - vasilenicusor
@vasilenicusor,最后一部分肯定会抓住欺骗。计数器字典统计所有出现的单词,并且不会出现两次出现的单词。你在运行它是什么? - Padraic Cunningham
这个脚本应该从一个包含文件路径的大列表中获取唯一的根路径(文件夹文件)。例如['a:/ dir1','a:/dir1/file1.txt','a:/ dir1 / dir2','a:/dir4/file4.tx','a:/dir4/file4.txt' ]结果是['a:/ dir1','a:/dir4/file4.tx'] - vasilenicusor
@Padraic Cunningham获取用于测试脚本的示例数据,使用带有来自HDD的路径的列表 - 我使用dir“C:*”/ s / b> e:/out.txt然后从列表中的out.tx加载每一行。在我的情况下,我有1498136文件。并且该脚本在10分钟后仍然运行:)在具有I5 3.2 GHz和16 GB RAM的PC上具有214 MB RAM和30%CPU - vasilenicusor


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,))

4
2018-05-12 09:43



获得7k stings的列表需要8秒钟 - Padraic Cunningham
编辑后你运行了吗? (加上'休息')? - Dzarafata
现在它是 2.96 s per loop - Padraic Cunningham
够了吗?你需要多久运行一次? - Dzarafata
@Dzarafata你能解释为什么你的代码很快吗? - Burger King


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)<min(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]

演示>>>

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

4
2018-05-12 09:43



@TonyYang它对列表中的每个n项进行n次比较。大O符号大约是n ^ 2。附:我没有考虑到的成本 startswith 操作本身,将其视为常数(O(1)) - Eli Korvigo
@PadraicCunningham其实我虽然使用了De Bruijn图。可以获得图形并找到孤立的顶点。那会很漂亮,虽然很慢。 - Eli Korvigo
@PadraicCunningham这个问题引起了我的极大关注:D然而我想出了一个线性算法(如果你不计算排序的复杂性)。我很高兴知道你对它的看法。 - Eli Korvigo
他的解决方案给出了与我们相同的结果,并且是速度的明显赢家(我们的大致相同) - skolsuper
@EliKorvigo我甚至无法弄清楚你的工作方式,但它简单快速,很好 - skolsuper


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)

编辑(再次)风格和非常小的优化


3
2018-05-12 09:50



@PadraicCunningham如果您可以使用与其他数据相同的数据和机器为我测试这将是很酷的。我认为它应该是O(n) - skolsuper
它速度很快,但在欺骗中给出了错误的结果 - Padraic Cunningham
如果没有像我的第一个答案那样的愚蠢行为,你的工作会很好。使用套装或字典的问题是,如果一个单词出现两次,它将被视为唯一,如果你根据我的回答添加了一个计数器检查我想你的也应该涵盖所有的情况 - Padraic Cunningham
是的,但你没有删除它们。如果你有两个 "abc"'s 你的代码将保留一个 - Padraic Cunningham
"abc".startswith("abc") -> True,除非OP只想考虑子串匹配然后才应该删除它,我留下了几个不同的版本,因为完整的实现细节是未知的 - Padraic Cunningham


解决方案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)

如果算法不需要稳定,即结果列表不需要保持元素的原始顺序,这里是一个使用的解决方案 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)) 复杂。


3
2018-05-15 22:09



53.2039999962秒,在PC上提供的演示输入为3.2 Ghz,i5,16 GB RAM。好的解决方案 - vasilenicusor
@vasilenicusor到目前为止你最好的结果是什么? - bagrat
优化,请参阅解决方案1,大约需要10秒的数据。 - bagrat
到目前为止,最好的解决方案是@Benoit Esnard提供的解决方案 0.582999944687 seconds - vasilenicusor


我相信以下内容很可能是最有效的。

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参数。此外,它还演示了“维护一个对目前看到的数据有效的解决方案,并将此解决方案扩展为对每个新数据都有效”的模式。这是一个熟悉的好模式。


3
2018-05-19 22:23



好的解决方案样本输入约10秒,输入列表混洗约18秒 - vasilenicusor
这与其他人相比如何?我想如果你创建一个超级大的输入文件仍然有一个合理大小的输出文件(比如,通过多次将你的文件连接在一起),我的仍然可以很好地扩展。您接受的答案需要能够将整个输入文件保存在内存中,而我的内容将更像内存中的输出文件。 - Pete Cacioppi
换句话说,此解决方案将在任何可迭代运行,包括生成器。 - Pete Cacioppi
这是真的,但是这个列表不是从文件加载的,而是在运行时构建的。我发布此文件仅用于测试,并概述了输入列表中的数据量。 - vasilenicusor
当然。但我们应该尽力解决这个问题。我相信对于输入集很大但输出设置合理的情况,这个解决方案将是最好的。这是一个需要考虑的重要案例,因为海量数据是真实的。 - Pete Cacioppi