在Python中,如何拆分字符串并重新连接而不创建中间列表?

9

假设我有以下内容:

dest = "\n".join( [line for line in src.split("\n") if line[:1]!="#"] )

(即从多行字符串src中删除任何以#开头的行)

src非常大,因此我假设.split()将创建一个大的中间列表。 我可以将列表推导式更改为生成器表达式,但是否有一种“xsplit”可用于仅逐行处理?我的假设正确吗?处理这个的最有效(内存)的方法是什么?

澄清:这是由于我的代码耗尽了内存而引起的。 我知道有办法完全重写我的代码来解决这个问题,但问题是关于Python:是否有一个类似生成器的split()版本(或等效习语),因此不会产生src的额外工作副本?


1
你打算如何处理练习后的大输入字符串和可能更小的结果字符串?将它们永久地保留在内存中吗?删除输入字符串并将输出字符串写入文件? - John Machin
1
为什么你需要在最后将大字符串存储在内存中?解释一下,也许我们可以更好地帮助你。 - Donal Fellows
你遇到了什么错误?如果没有错误,那么为什么会有问题?为什么要担心节省一种如此便宜且丰富的资源(内存)? - Mark Byers
如下评论所述,目标是在最小更改的情况下减少内存使用。当然,重写代码以保留数据在磁盘上会更好,但现在不是选项。src字符串可以丢弃,dest将进一步处理。 - Tom
你能否提供一个出现MemoryError错误的字符串的len(src)src.count('\n')的结果? - Mark Byers
5个回答

5
buffer = StringIO(src)
dest = "".join(line for line in buffer if line[:1]!="#")

当然,如果您一直使用StringIO,则这确实是最有意义的。 它的工作方式与文件大致相同。 您可以查找,读取,写入,迭代(如所示)等。

这很不错。但对于更通用的split()调用无法起作用,是吗?使用StringIO而不是join是一种选择。StringIO会复制缓冲区还是只是引用它? - Tom
不,我不知道有任何返回迭代器的分割方法。我认为StringIO会立即复制,因为字符串是不可变的。它可能是写时复制,但我不这么认为。 - Matthew Flaschen
1
我不建议使用 str 作为变量名。 - Mark Byers

5
这里有一种使用itertools进行一般类型分割的方法。
>>> import itertools as it
>>> src="hello\n#foo\n#bar\n#baz\nworld\n"
>>> line_gen = (''.join(j) for i,j in it.groupby(src, "\n".__ne__) if i)
>>> '\n'.join(s for s in line_gen if s[0]!="#")
'hello\nworld'

groupby会将src中的每个字符单独处理,因此性能可能不是最佳的,但它避免了创建任何中间巨大的数据结构。

最好花费一些时间编写一个生成器。

>>> src="hello\n#foo\n#bar\n#baz\nworld\n"
>>>
>>> def isplit(s, t): # iterator to split string s at character t
...     i=j=0
...     while True:
...         try:
...             j = s.index(t, i)
...         except ValueError:
...             if i<len(s):
...                 yield s[i:]
...             raise StopIteration
...         yield s[i:j]
...         i = j+1
...
>>> '\n'.join(x for x in isplit(src, '\n') if x[0]!='#')
'hello\nworld'

re有一个名为finditer的方法,也可用于此目的。

>>> import re
>>> src="hello\n#foo\n#bar\n#baz\nworld\n"
>>> line_gen = (m.group(1) for m in re.finditer("(.*?)(\n|$)",src))
>>> '\n'.join(s for s in line_gen if not s.startswith("#"))
'hello\nworld'

比较性能是一个练习,让OP尝试在实际数据上进行。


太好了!谢谢,re.finditer()正是我想要的东西。你的isplit()函数也很不错,但我希望它能在标准库中,并且最好有C实现或类似的东西。 - Tom
是和不是。是:行为符合OP的要求。否:它不像str.split那样在s.endswith(t)时产生最后一个'',而更像str.splitlines(False) - John Machin

4

在您现有的代码中,您可以将列表更改为生成器表达式:

dest = "\n".join(line for line in src.split("\n") if line[:1]!="#")

这个非常小的改变避免了你代码中两个临时列表之一的构造,并且不需要你做出任何努力。
另一个完全不同的方法是使用正则表达式来避免构建两个临时列表:
import re
regex = re.compile('^#.*\n?', re.M)
dest = regex.sub('', src)

这不仅避免了创建临时列表,还避免了为输入中的每一行创建临时字符串。以下是所提出解决方案的性能测量结果:
init = r'''
import re, StringIO
regex = re.compile('^#.*\n?', re.M)
src = ''.join('foo bar baz\n' for _ in range(100000))
'''
method1 = r'"\n".join([line for line in src.split("\n") if line[:1] != "#"])' method2 = r'"\n".join(line for line in src.split("\n") if line[:1] != "#")' method3 = 'regex.sub("", src)' method4 = ''' buffer = StringIO.StringIO(src) dest = "".join(line for line in buffer if line[:1] != "#") '''
import timeit
for method in [method1, method2, method3, method4]: print timeit.timeit(method, init, number = 100)

结果:

 9.38秒   # 分割后使用临时列表连接
 9.92秒   # 分割后使用生成器连接
 8.60秒   # 正则表达式
64.56秒   # StringIO

从结果可以看出,正则表达式是最快的方法。

从您的评论中可以看出,您实际上并不关心避免创建临时对象。您真正想要的是减少程序的内存需求。临时对象不一定会影响程序的内存消耗,因为Python可以快速清除内存。问题在于有些对象比需要更长时间地存在于内存中,而且所有这些方法都有这个问题。

如果您仍然遇到内存不足的问题,我建议您不要完全在内存中执行此操作。而是将输入和输出存储在磁盘上的文件中,并以流式方式从它们中读取。这意味着您从输入中读取一行,写入一行到输出中,再读取一行,再写入一行等等。这将创建大量的临时字符串,但即使如此,它也几乎不需要任何内存,因为您只需要逐个处理字符串。


我追求内存效率,而不是速度,避免创建临时数据副本是目标。生成器表达式有所帮助,但仍然会创建3个副本(据我估计)。您知道正则表达式中的regex.sub()在这方面如何衡量吗? - Tom
@Tom:另外,你当前代码遇到的问题或错误是什么?如果你收到了异常信息,能否把追踪信息发布在你的问题中?如果你的代码只是表现出不良行为,你能否更详细地描述你所看到的具体不良行为以及为什么它对你来说是一个问题? - Mark Byers
我在类似于发布的那一行代码上遇到了MemoryError异常。回溯中没有其他相关信息。 - Tom
不错,我正要写“尝试re.sub”,只是用了另一个正则表达式:r'(#[^\n]*)(?:\n|$)'。RE应该一次性创建输出字符串(而不是拆分和连接)。 - Jochen Ritzel

2

如果我正确理解您关于“更通用的split()调用”的问题,您可以使用re.finditer,如下所示:

output = ""

for i in re.finditer("^.*\n",input,re.M):
    i=i.group(0).strip()
    if i.startswith("#"):
        continue
    output += i + "\n"

在这里,您可以用更复杂的东西替换正则表达式。


1
问题在于Python中的字符串是不可变的,因此如果没有中间存储,做任何事情都会非常困难。

明白了。我的目标是尽量减少中间存储的使用。有源(src)、然后是由split制作的副本,接着是列表推导式中的一个副本,最后是目标(dest)。比理论要求多两倍的副本。 - Tom
2
我预计生成器将为您节省大量时间和精力。超出此范围的任何内容都可能是过早优化? - Andrew Jaffe
很遗憾,进程已经耗尽了内存... 生成器将其缩减到3个副本,StringIO也是如此,但生成器肯定更省力,这是更好的选择。 - Tom
4
如果你的内存不足,也许你在首次尝试进行这种内存操作时就不应该这么做?你可以选择将数据存储到磁盘上,并以流式方式读写它——读一行,写一行,再读一行,再写一行等。这样,整个操作只需要几KB的内存即可。但你应该测量性能,否则你只是在猜测,而即使是简单程序的性能猜测也非常困难。 - Mark Byers
@Mark,你可能是对的,但我希望尽量避免重写这段代码。减少一半的内存使用可能已经足够好了,减少33%可能也可以接受。 - Tom
@Tom:“将内存使用减半可能已经足够好了。”购买两倍的内存是否是一个选项? - Mark Byers

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接