6

我有一个包含许多字符串的巨大列表，例如：

['xxxx','xx','xy','yy','x',......]

现在我正在寻找一种有效的方法来删除另一个字符串中存在的所有字符串。例如“xx”“x”适合“xxxx”。

由于数据集很大，我想知道除此之外是否有有效的方法

if a in b:

完整的代码：可能有一些优化部分：

for x in range(len(taxlistcomplete)):
if delete == True:
    x = x - 1
    delete = False
for y in range(len(taxlistcomplete)):
    if taxlistcomplete[x] in taxlistcomplete[y]:
        if x != y:
            print x,y
            print taxlistcomplete[x]
            del taxlistcomplete[x]
            delete = True
            break
    print x, len(taxlistcomplete)

代码的更新版本：

for x in enumerate(taxlistcomplete):
if delete == True:
    #If element is removed, I need to step 1 back and continue looping.....
    delete = False
for y in enumerate(taxlistcomplete):
    if x[1] in y[1]:
        if x[1] != y[1]:
            print x[1],y[1]
            print taxlistcomplete[x]

            del taxlistcomplete[x[0]]
            delete = True
            break
print x, len(taxlistcomplete)

现在用枚举实现，只是现在我想知道这是否更有效以及如何实现删除步骤，所以我也有更少的搜索。

只是一个短暂的想法...

基本上是我想看的...

如果元素与列表中的任何其他元素不匹配，则将此元素写入文件。因此，如果 'xxxxx' 不在 'xx'、'xy'、'wfirfj' 等... 打印/保存

一个新的简单版本，因为我认为无论如何我都无法进一步优化它......

print 'comparison'

file = open('output.txt','a')

for x in enumerate(taxlistcomplete):
    delete = False
    for y in enumerate(taxlistcomplete):
        if x[1] in y[1]:
            if x[1] != y[1]:
                taxlistcomplete[x[0]] = ''
                delete = True
                break
    if delete == False:
        file.write(str(x))
4

4 回答 4

9

x in <string>速度很快，但是根据列表中的所有其他字符串检查每个字符串将花费 O(n^2) 时间。无需通过优化比较来节省几个周期，您可以通过使用不同的数据结构来节省大量成本，这样您只需一次查找即可检查每个字符串：对于两千个字符串，这是两千次检查而不是四百万次。

有一种称为“前缀树”（或 trie）的数据结构，可让您非常快速地检查字符串是否是您以前见过的某个字符串的前缀。去谷歌上查询。由于您还对出现在另一个字符串中间x的字符串感兴趣，因此索引表单x, x[1:], x[2:], x[3:],等的所有子字符串（因此：只有n长度字符串的子字符串n）。也就是说，您索引从位置 0、1、2 等开始并继续到字符串末尾的子字符串。这样您就可以检查新字符串是否是索引中某些内容的初始部分。

然后，您可以像这样在 O(n) 时间内解决您的问题：

  1. 按长度递减的顺序排列您的字符串。这确保没有字符串可以是您尚未看到的内容的子字符串。由于您只关心长度，因此您可以在 O(n) 时间内进行桶排序。

  2. 从一个空的前缀树开始，然后遍历您的有序字符串列表。对于每个 string x，使用您的前缀树来检查它是否是您以前见过的字符串的子字符串。如果不是，则将其子字符串x, x[1:], x[2:]等添加到前缀树中。

在长列表的中间删除非常昂贵，因此如果您将要保留的字符串收集到新列表中，您将获得进一步的加速（实际的字符串不会被复制，只是参考）。完成后，删除原始列表和前缀树。

如果这对你来说太复杂了，至少不要把所有事情都和所有事情进行比较。按大小对字符串进行排序（按降序排列），并仅将每个字符串与之前的字符串进行对比。这将使您毫不费力地加快 50% 的速度。并创建一个新列表（或立即写入文件）而不是就地删除。

于 2012-05-01T15:23:11.357 回答
2

'$'这是一个简单的方法，假设您可以识别一个保证不在任何原始字符串中的字符（我将在我的示例中使用）：

result = ''
for substring in taxlistcomplete:
    if substring not in result: result += '$' + substring
taxlistcomplete = result.split('$')

这利用了 Python 对子字符串搜索的内部优化，只需将一个大字符串创建为子字符串搜索 :)

于 2012-05-01T16:22:37.977 回答
0

使用列表理解——注意in——是解决问题的最快和更 Pythonic 的方法：

[element for element in arr if 'xx' in element]
于 2012-05-01T15:09:34.913 回答
0

这是我的建议。首先，我按长度对元素进行排序。因为显然字符串越短，它就越有可能是另一个字符串的子字符串。然后我有两个 for 循环，在其中我遍历列表并从列表中删除 el 是子字符串的每个元素。请注意，第一个 for 循环仅将每个元素传递一次。

通过首先对列表进行排序，我们破坏了列表中元素的顺序。因此，如果顺序很重要，则不能使用此解决方案。

编辑。我假设列表中没有相同的元素。所以当 el == el2 时，这是因为它是同一个元素。

a = ["xyy", "xx", "zy", "yy", "x"]
a.sort(key=len)

for el in a:
    for el2 in a:
        if el in el2 and el != el2:
            a.remove(el2)
于 2012-05-01T15:58:22.873 回答