Есть ли в Python генераторная версия string.split ()?

113

string.split()возвращает экземпляр списка . Есть ли версия, которая вместо этого возвращает генератор ? Есть ли какие-то причины против использования генераторной версии?

Манодж Говиндан
источник
3
Этот вопрос может быть связан.
Björn Pollex 05
1
Причина в том, что очень трудно придумать случай, когда это было бы полезно. а зачем тебе это?
Гленн Мейнард
10
@Glenn: Недавно я увидел вопрос о разбиении длинной строки на блоки из n слов. Одно из решений split- строка, а затем возвращается генератор, работающий над результатом split. Это заставило меня задуматься, есть ли способ splitвернуть генератор для начала.
Манодж Говиндан
5
Соответствующее обсуждение в системе отслеживания проблем
saffsd
@GlennMaynard, это может быть полезно для действительно большого разбора строки / файла, но любой может очень легко написать парсер генератора, используя самодельный DFA и yield
Дмитрий Понятов

Ответы:

77

Весьма вероятно, что при этом 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']

edit: Я только что подтвердил, что для этого требуется постоянная память в python 3.2.1, если моя методология тестирования верна. Я создал строку очень большого размера (1 ГБ или около того), а затем повторил итерацию с помощью forцикла (НЕ понимание списка, которое привело бы к дополнительной памяти). Это не привело к заметному увеличению объема памяти (то есть, если было увеличение объема памяти, оно было намного меньше, чем строка в 1 ГБ).

ninjagecko
источник
5
Превосходно! Я забыл о финдитере. Если бы кто-то был заинтересован в том, чтобы сделать что-то вроде splitlines, я бы предложил использовать этот RE: '(. * \ N |. + $)' Str.splitlines отрезает новую строку обучения (что-то, что мне не очень нравится ... ); если вы хотите воспроизвести эту часть поведения, вы можете использовать группировку: (m.group (2) или m.group (3) для m в re.finditer ('((. *) \ n | (. +) $) ', с)). PS: я полагаю, что внешние символы в RE не нужны; Мне просто неудобно использовать | без парен: P
allyourcode
3
А как насчет производительности? повторное сопоставление должно быть медленнее, чем обычный поиск.
анатолий техтоник
1
Как бы вы переписали эту функцию split_iter, чтобы она работала a_string.split("delimiter")?
Moberg
split в любом случае принимает регулярные выражения, так что это не очень быстро, если вы хотите использовать возвращаемое значение в предыдущей следующей моде, посмотрите мой ответ внизу ...
Велтцер Дорон
str.split()не принимает регулярные выражения, это re.split()вы думаете ...
Алексис
17

Самый эффективный способ, который я могу придумать, - написать его, используя offsetпараметр str.find()метода. Это позволяет избежать использования большого количества памяти и дополнительных затрат на регулярное выражение, когда оно не нужно.

[изменить 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 () или нарезка, выполняется небольшой поиск стоимости внутри строки, это должно быть минимальным, поскольку строки представлены в виде непрерывных массивов в памяти.

Эли Коллинз
источник
10

Это генераторная версия, split()реализованная через re.search(), которая не имеет проблемы с выделением слишком большого количества подстрок.

import re

def itersplit(s, sep=None):
    exp = re.compile(r'\s+' if sep is None else re.escape(sep))
    pos = 0
    while True:
        m = exp.search(s, pos)
        if not m:
            if pos < len(s) or sep is not None:
                yield s[pos:]
            break
        if pos < m.start() or sep is not None:
            yield s[pos:m.start()]
        pos = m.end()


sample1 = "Good evening, world!"
sample2 = " Good evening, world! "
sample3 = "brackets][all][][over][here"
sample4 = "][brackets][all][][over][here]["

assert list(itersplit(sample1)) == sample1.split()
assert list(itersplit(sample2)) == sample2.split()
assert list(itersplit(sample3, '][')) == sample3.split('][')
assert list(itersplit(sample4, '][')) == sample4.split('][')

РЕДАКТИРОВАТЬ: исправлена ​​обработка окружающих пробелов, если не указаны символы разделителя.

Бернд Петерсон
источник
12
почему это лучше чем re.finditer?
Эрик Каплун
@ErikKaplun Потому что логика регулярных выражений для элементов может быть более сложной, чем для их разделителей. В моем случае я хотел обрабатывать каждую строку индивидуально, чтобы я мог сообщить, если строка не соответствует.
Ровыко
9

Провел некоторое тестирование производительности по различным предложенным методам (я не буду их здесь повторять). Некоторые результаты:

  • str.split (по умолчанию = 0,3461570239996945
  • ручной поиск (по символам) (один из ответов Дэйва Уэбба) = 0,8260340550004912
  • re.finditer (ответ ниндзягеко) = 0,698872097000276
  • str.find (один из ответов Эли Коллинза) = 0,7230395330007013
  • itertools.takewhile (Ответ Игнасио Васкеса-Абрамса) = 2,023023967998597
  • str.split(..., maxsplit=1) рекурсия = N / A †

† Рекурсивные ответы ( 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он намного быстрее, несмотря на использование памяти.

CZ
источник
2
Это связано с тем, что память медленнее, чем процессор, и в этом случае список загружается фрагментами, тогда как все остальные загружаются элемент за элементом. В то же время многие ученые скажут вам, что связанные списки быстрее и менее сложны, в то время как ваш компьютер часто будет быстрее работать с массивами, которые легче оптимизировать. Вы не можете предположить, что один вариант быстрее другого, проверьте его! +1 за тестирование.
Benoît P,
Проблема возникает на следующих этапах технологической цепочки. Если вы затем хотите найти конкретный фрагмент и проигнорировать остальное, когда вы его найдете, то у вас есть оправдание использовать разбиение на основе генератора вместо встроенного решения.
jgomo3
6

Вот моя реализация, которая намного, намного быстрее и полнее, чем другие ответы здесь. Он имеет 4 отдельные подфункции для разных случаев.

Я просто скопирую строку документации основной str_splitфункции:


str_split(s, *delims, empty=None)

Разделите строку sна остальные аргументы, возможно, опуская пустые части (за emptyэто отвечает аргумент ключевого слова). Это функция генератора.

Когда указан только один разделитель, строка просто разделяется им. emptyтогда Trueпо умолчанию.

str_split('[]aaa[][]bb[c', '[]')
    -> '', 'aaa', '', 'bb[c'
str_split('[]aaa[][]bb[c', '[]', empty=False)
    -> 'aaa', 'bb[c'

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

str_split('aaa, bb : c;', ' ', ',', ':', ';')
    -> 'aaa', 'bb', 'c'
str_split('aaa, bb : c;', *' ,:;', empty=True)
    -> 'aaa', '', 'bb', '', '', 'c', ''

Если разделители не указаны, string.whitespaceиспользуется, поэтому эффект такой же, как str.split(), за исключением того, что эта функция является генератором.

str_split('aaa\\t  bb c \\n')
    -> 'aaa', 'bb', 'c'

import string

def _str_split_chars(s, delims):
    "Split the string `s` by characters contained in `delims`, including the \
    empty parts between two consecutive delimiters"
    start = 0
    for i, c in enumerate(s):
        if c in delims:
            yield s[start:i]
            start = i+1
    yield s[start:]

def _str_split_chars_ne(s, delims):
    "Split the string `s` by longest possible sequences of characters \
    contained in `delims`"
    start = 0
    in_s = False
    for i, c in enumerate(s):
        if c in delims:
            if in_s:
                yield s[start:i]
                in_s = False
        else:
            if not in_s:
                in_s = True
                start = i
    if in_s:
        yield s[start:]


def _str_split_word(s, delim):
    "Split the string `s` by the string `delim`"
    dlen = len(delim)
    start = 0
    try:
        while True:
            i = s.index(delim, start)
            yield s[start:i]
            start = i+dlen
    except ValueError:
        pass
    yield s[start:]

def _str_split_word_ne(s, delim):
    "Split the string `s` by the string `delim`, not including empty parts \
    between two consecutive delimiters"
    dlen = len(delim)
    start = 0
    try:
        while True:
            i = s.index(delim, start)
            if start!=i:
                yield s[start:i]
            start = i+dlen
    except ValueError:
        pass
    if start<len(s):
        yield s[start:]


def str_split(s, *delims, empty=None):
    """\
Split the string `s` by the rest of the arguments, possibly omitting
empty parts (`empty` keyword argument is responsible for that).
This is a generator function.

When only one delimiter is supplied, the string is simply split by it.
`empty` is then `True` by default.
    str_split('[]aaa[][]bb[c', '[]')
        -> '', 'aaa', '', 'bb[c'
    str_split('[]aaa[][]bb[c', '[]', empty=False)
        -> 'aaa', 'bb[c'

When multiple delimiters are supplied, the string is split by longest
possible sequences of those delimiters by default, or, if `empty` is set to
`True`, empty strings between the delimiters are also included. Note that
the delimiters in this case may only be single characters.
    str_split('aaa, bb : c;', ' ', ',', ':', ';')
        -> 'aaa', 'bb', 'c'
    str_split('aaa, bb : c;', *' ,:;', empty=True)
        -> 'aaa', '', 'bb', '', '', 'c', ''

When no delimiters are supplied, `string.whitespace` is used, so the effect
is the same as `str.split()`, except this function is a generator.
    str_split('aaa\\t  bb c \\n')
        -> 'aaa', 'bb', 'c'
"""
    if len(delims)==1:
        f = _str_split_word if empty is None or empty else _str_split_word_ne
        return f(s, delims[0])
    if len(delims)==0:
        delims = string.whitespace
    delims = set(delims) if len(delims)>=4 else ''.join(delims)
    if any(len(d)>1 for d in delims):
        raise ValueError("Only 1-character multiple delimiters are supported")
    f = _str_split_chars if empty else _str_split_chars_ne
    return f(s, delims)

Эта функция работает в Python 3, и можно применить простое, хотя и довольно уродливое исправление, чтобы заставить ее работать как в версии 2, так и в версии 3. Первые строки функции следует изменить на:

def str_split(s, *delims, **kwargs):
    """...docstring..."""
    empty = kwargs.get('empty')
Олег Припин
источник
3

Нет, но написать его с помощью itertools.takewhile().

РЕДАКТИРОВАТЬ:

Очень простая, полуразрушенная реализация:

import itertools
import string

def isplitwords(s):
  i = iter(s)
  while True:
    r = []
    for c in itertools.takewhile(lambda x: not x in string.whitespace, i):
      r.append(c)
    else:
      if r:
        yield ''.join(r)
        continue
      else:
        raise StopIteration()
Игнасио Васкес-Абрамс
источник
@Ignacio: в примере в документации используется список целых чисел для иллюстрации использования takeWhile. Что было бы хорошо predicateдля разбиения строки на слова (по умолчанию split) с помощью takeWhile()?
Манодж Говиндан
Ищите присутствие в string.whitespace.
Игнасио Васкес-Абрамс
Разделитель может состоять из нескольких символов,'abc<def<>ghi<><>lmn'.split('<>') == ['abc<def', 'ghi', '', 'lmn']
kennytm
@Ignacio: Можете ли вы добавить пример к своему ответу?
Манодж Говиндан
1
Легко писать, но на много порядков медленнее. Это операция, которая действительно должна быть реализована в машинном коде.
Гленн Мейнард
3

Я не вижу очевидной пользы от генераторной версии split(). Объект-генератор должен содержать всю строку для итерации, поэтому вы не собираетесь экономить память, имея генератор.

Если бы вы захотели написать что-нибудь, это было бы довольно просто:

import string

def gsplit(s,sep=string.whitespace):
    word = []

    for c in s:
        if c in sep:
            if word:
                yield "".join(word)
                word = []
        else:
            word.append(c)

    if word:
        yield "".join(word)
Дэйв Уэбб
источник
3
Вы бы вдвое сократили объем используемой памяти, не храня вторую копию строки в каждой результирующей части, плюс накладные расходы на массив и объект (которые обычно больше, чем сами строки). Однако, как правило, это не имеет значения (если вы разбиваете строки настолько большими, что это имеет значение, вы, вероятно, делаете что-то не так), и даже реализация собственного генератора C всегда будет значительно медленнее, чем выполнение всего этого сразу.
Гленн Мейнард
@ Гленн Мейнард - я только что понял это. Я по какой-то причине изначально в генераторе хранил копию строки, а не ссылку. Быстрая проверка id()меня поправила. И, очевидно, поскольку строки неизменяемы, вам не нужно беспокоиться о том, что кто-то изменит исходную строку, пока вы повторяете ее.
Дэйв Уэбб
6
Разве основной смысл использования генератора не в использовании памяти, а в том, что вы могли бы избавить себя от необходимости разбивать всю строку, если хотите выйти раньше? (Это не комментарий к вашему конкретному решению, меня просто удивила дискуссия о памяти).
Скотт Гриффитс
@Scott: Трудно представить случай, когда это действительно победа - где 1: вы хотите перестать разделять на полпути, 2: вы не знаете, сколько слов вы заранее разбиваете, 3: у вас есть достаточно большая строка, чтобы это имело значение, и 4: вы постоянно останавливаетесь достаточно рано, чтобы это стало значительной победой над str.split. Это очень узкий набор условий.
Гленн Мейнард
4
Вы можете получить гораздо больше преимуществ, если ваша строка также генерируется лениво (например, из сетевого трафика или чтения файлов),
Ли Райан,
3

Я написал версию ответа @ ninjagecko, которая больше похожа на string.split (то есть по умолчанию разделены пробелами, и вы можете указать разделитель).

def isplit(string, delimiter = None):
    """Like string.split but returns an iterator (lazy)

    Multiple character delimters are not handled.
    """

    if delimiter is None:
        # Whitespace delimited by default
        delim = r"\s"

    elif len(delimiter) != 1:
        raise ValueError("Can only handle single character delimiters",
                        delimiter)

    else:
        # Escape, incase it's "\", "*" etc.
        delim = re.escape(delimiter)

    return (x.group(0) for x in re.finditer(r"[^{}]+".format(delim), string))

Вот тесты, которые я использовал (как в Python 3, так и в Python 2):

# Wrapper to make it a list
def helper(*args,  **kwargs):
    return list(isplit(*args, **kwargs))

# Normal delimiters
assert helper("1,2,3", ",") == ["1", "2", "3"]
assert helper("1;2;3,", ";") == ["1", "2", "3,"]
assert helper("1;2 ;3,  ", ";") == ["1", "2 ", "3,  "]

# Whitespace
assert helper("1 2 3") == ["1", "2", "3"]
assert helper("1\t2\t3") == ["1", "2", "3"]
assert helper("1\t2 \t3") == ["1", "2", "3"]
assert helper("1\n2\n3") == ["1", "2", "3"]

# Surrounding whitespace dropped
assert helper(" 1 2  3  ") == ["1", "2", "3"]

# Regex special characters
assert helper(r"1\2\3", "\\") == ["1", "2", "3"]
assert helper(r"1*2*3", "*") == ["1", "2", "3"]

# No multi-char delimiters allowed
try:
    helper(r"1,.2,.3", ",.")
    assert False
except ValueError:
    pass

Модуль регулярных выражений python говорит, что он делает «правильную вещь» для пробелов в Юникоде, но я на самом деле не тестировал его.

Также доступно как суть .

dshepherd
источник
3

Если вы также хотите иметь возможность читать итератор (а также возвращать его), попробуйте следующее:

import itertools as it

def iter_split(string, sep=None):
    sep = sep or ' '
    groups = it.groupby(string, lambda s: s != sep)
    return (''.join(g) for k, g in groups if k)

использование

>>> list(iter_split(iter("Good evening, world!")))
['Good', 'evening,', 'world!']
Reubano
источник
3

more_itertools.split_atпредлагает аналог str.splitдля итераторов.

>>> import more_itertools as mit


>>> list(mit.split_at("abcdcba", lambda x: x == "b"))
[['a'], ['c', 'd', 'c'], ['a']]

>>> "abcdcba".split("b")
['a', 'cdc', 'a']

more_itertools это сторонний пакет.

pylang
источник
1
Обратите внимание, что more_itertools.split_at () по-прежнему использует вновь выделенный список при каждом вызове, поэтому, хотя он возвращает итератор, он не обеспечивает требования к постоянной памяти. Итак, в зависимости от того, почему вы хотели использовать итератор, это может быть полезно, а может и нет.
jcater 06
@jcater Хорошее замечание. Промежуточные значения действительно помещаются в буфер как подсписки внутри итератора в соответствии с его реализацией . Можно адаптировать источник для замены списков итераторами, добавления itertools.chainи оценки результатов, используя понимание списка. В зависимости от потребности и запроса могу опубликовать пример.
pylang 06
2

Я хотел показать, как использовать решение find_iter для возврата генератора для заданных разделителей, а затем использовать попарный рецепт из itertools для построения предыдущей следующей итерации, которая получит фактические слова, как в исходном методе разделения.


from more_itertools import pairwise
import re

string = "dasdha hasud hasuid hsuia dhsuai dhasiu dhaui d"
delimiter = " "
# split according to the given delimiter including segments beginning at the beginning and ending at the end
for prev, curr in pairwise(re.finditer("^|[{0}]+|$".format(delimiter), string)):
    print(string[prev.end(): curr.start()])

нота:

  1. Я использую prev и curr вместо prev и next, потому что переопределение next в python - очень плохая идея
  2. Это довольно эффективно
Вельцер Дорон
источник
1

Самый тупой метод без регулярных выражений / itertools:

def isplit(text, split='\n'):
    while text != '':
        end = text.find(split)

        if end == -1:
            yield text
            text = ''
        else:
            yield text[:end]
            text = text[end + 1:]
Tavy
источник
0
def split_generator(f,s):
    """
    f is a string, s is the substring we split on.
    This produces a generator rather than a possibly
    memory intensive list. 
    """
    i=0
    j=0
    while j<len(f):
        if i>=len(f):
            yield f[j:]
            j=i
        elif f[i] != s:
            i=i+1
        else:
            yield [f[j:i]]
            j=i+1
            i=i+1
travelingbones
источник
почему ты уступаешь, [f[j:i]]а нет f[j:i]?
Moberg
0

вот простой ответ

def gen_str(some_string, sep):
    j=0
    guard = len(some_string)-1
    for i,s in enumerate(some_string):
        if s == sep:
           yield some_string[j:i]
           j=i+1
        elif i!=guard:
           continue
        else:
           yield some_string[j:]
user1438644
источник