Python中有`string.split()`的生成器版本吗？

Question

string.split() 方法会返回一个列表。有没有返回 生成器 的版本呢？有没有什么理由不使用生成器版本？

Answer 1

我对一些提议的方法进行了性能测试（这里就不重复那些方法了）。以下是一些结果：

str.split（默认） = 0.3461570239996945
手动搜索（按字符）（这是Dave Webb的一个回答） = 0.8260340550004912
re.finditer（这是ninjagecko的回答） = 0.698872097000276
str.find（这是Eli Collins的一个回答） = 0.7230395330007013
itertools.takewhile（这是Ignacio Vazquez-Abrams的回答） = 2.023023967998597
str.split(..., maxsplit=1) 递归 = 不适用†

†递归的答案（string.split 和 maxsplit = 1）在合理的时间内无法完成，考虑到string.split的速度，它们可能在处理较短字符串时效果更好，但我看不出在内存不是问题的情况下，短字符串有什么使用场景。

测试是使用timeit进行的：

the_text = "100 " * 9999 + "100"

def test_function( method ):
    def fn( ):
        total = 0

        for x in method( the_text ):
            total += int( x )

        return total

    return fn

这又引出了一个问题，为什么string.split的速度如此之快，尽管它的内存使用量比较高。

Answer 2

我想到的最有效的方法是使用 str.find() 方法中的 offset 参数来写。这可以避免大量的内存使用，也不需要在不必要的时候依赖正则表达式的开销。

[编辑于2016-8-2：更新了这个内容以支持可选的正则分隔符]

def isplit(source, sep=None, regex=False):
    """
    generator version of str.split()

    :param source:
        source string (unicode or bytes)

    :param sep:
        separator to split on.

    :param regex:
        if True, will treat sep as regular expression.

    :returns:
        generator yielding elements of string.
    """
    if sep is None:
        # mimic default python behavior
        source = source.strip()
        sep = "\\s+"
        if isinstance(source, bytes):
            sep = sep.encode("ascii")
        regex = True
    if regex:
        # version using re.finditer()
        if not hasattr(sep, "finditer"):
            sep = re.compile(sep)
        start = 0
        for m in sep.finditer(source):
            idx = m.start()
            assert idx >= start
            yield source[start:idx]
            start = m.end()
        yield source[start:]
    else:
        # version using str.find(), less overhead than re.finditer()
        sepsize = len(sep)
        start = 0
        while True:
            idx = source.find(sep, start)
            if idx == -1:
                yield source[start:]
                return
            yield source[start:idx]
            start = idx + sepsize

这可以像你想要的那样使用...

>>> print list(isplit("abcb","b"))
['a','c','']

虽然每次调用 find() 或者切片时在字符串中查找会有一点点开销，但这应该是很小的，因为字符串在内存中是作为连续的数组来表示的。

Answer 3

很可能，re.finditer 在使用内存方面是比较节省的。

def split_iter(string):
    return (x.group(0) for x in re.finditer(r"[A-Za-z']+", string))

示例：

>>> list( split_iter("A programmer's RegEx test.") )
['A', "programmer's", 'RegEx', 'test']

我确认在 Python 3.2.1 中，这个方法的内存使用是恒定的，前提是我的测试方法是正确的。我创建了一个非常大的字符串（大约 1GB），然后用 for 循环遍历这个可迭代对象（而不是用列表推导式，因为那样会产生额外的内存）。结果没有明显的内存增长（也就是说，如果内存有增长，那也远远小于 1GB 的字符串）。

更一般的版本：

针对评论“我看不出与 str.split 的关系”，这里有一个更一般的版本：

def splitStr(string, sep="\s+"):
    # warning: does not yet work if sep is a lookahead like `(?=b)`
    if sep=='':
        return (c for c in string)
    else:
        return (_.group(1) for _ in re.finditer(f'(?:^|{sep})((?:(?!{sep}).)*)', string))

    # alternatively, more verbosely:
    regex = f'(?:^|{sep})((?:(?!{sep}).)*)'
    for match in re.finditer(regex, string):
        fragment = match.group(1)
        yield fragment

这个想法是 ((?!pat).)* 通过确保它贪婪地匹配，直到模式开始匹配，从而“否定”一个组（前瞻在正则表达式有限状态机中不会消耗字符串）。用伪代码表示就是：重复消耗（字符串开头 或 {sep}）+ 尽可能多地匹配，直到我们能够重新开始（或到达字符串末尾）

示例：

>>> splitStr('.......A...b...c....', sep='...')
<generator object splitStr.<locals>.<genexpr> at 0x7fe8530fb5e8>

>>> list(splitStr('A,b,c.', sep=','))
['A', 'b', 'c.']

>>> list(splitStr(',,A,b,c.,', sep=','))
['', '', 'A', 'b', 'c.', '']

>>> list(splitStr('.......A...b...c....', '\.\.\.'))
['', '', '.A', 'b', 'c', '.']

>>> list(splitStr('   A  b  c. '))
['', 'A', 'b', 'c.', '']

（需要注意的是，str.split 有一个不太好的行为：当 sep=None 时，它会特别处理，首先执行 str.strip 来去掉前后的空白。而上面的实现故意没有这样做；请参见最后一个示例，其中 sep="\s+"。）

（在尝试实现这个过程中，我遇到了各种错误（包括内部的 re.error）……负向前瞻会限制你只能使用固定长度的分隔符，所以我们不使用它。几乎任何其他正则表达式在处理字符串开头和结尾的边界情况时似乎都会出错（例如，r'(.*?)($|,)' 在 ',,,a,,b,c' 上返回 ['', '', '', 'a', '', 'b', 'c', '']，最后多了一个空字符串；可以查看编辑历史，发现另一个看似正确的正则表达式实际上也有微妙的错误。）

（如果你想自己实现这个以提高性能（虽然它们比较复杂，正则表达式最重要的是在 C 语言中运行），你可以写一些代码（用 ctypes？不确定如何让生成器与它一起工作？），对于固定长度的分隔符，伪代码如下：对长度为 L 的分隔符进行哈希。在扫描字符串时，保持一个长度为 L 的运行哈希，更新时间为 O(1)。每当哈希可能等于你的分隔符时，手动检查过去的几个字符是否是分隔符；如果是，那么就返回自上次返回以来的子字符串。对字符串的开头和结尾进行特殊处理。这将是教科书算法的生成器版本，用于 O(N) 文本搜索。也可以实现多进程版本。虽然看起来有些过于复杂，但问题暗示着你正在处理非常大的字符串……在这种情况下，你可能会考虑一些疯狂的事情，比如缓存字节偏移量（如果数量不多的话），或者使用一些基于磁盘的字节字符串视图对象，增加更多的内存等等。）

Python中有`string.split()`的生成器版本吗？

17 个回答

更一般的版本：

撰写回答