Existe uma versão do gerador de `string.split ()` em Python?

113

string.split()retorna uma instância de lista . Existe uma versão que retorna um gerador em vez disso? Há alguma razão para não ter uma versão do gerador?

Manoj Govindan
fonte
3
Esta questão pode estar relacionada.
Björn Pollex,
1
A razão é que é muito difícil pensar em um caso em que seja útil. Por que voce quer isso?
Glenn Maynard,
10
@Glenn: Recentemente, vi uma pergunta sobre como dividir uma string longa em pedaços de n palavras. Uma das soluções splitda string e, em seguida, retornou um gerador trabalhando no resultado de split. Isso me fez pensar se havia uma maneira de splitdevolver um gerador para começar.
Manoj Govindan,
5
Há uma discussão relevante sobre o rastreador de problemas Python: bugs.python.org/issue17343
saffsd
@GlennMaynard pode ser útil para string nua realmente grande / análise de arquivo, mas qualquer um pode escrever o analisador gerador com facilidade usando DFA auto-fabricado e rendimento
Dmitry Ponyatov

Respostas:

77

É altamente provável que re.finditeruse um overhead mínimo de memória.

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

Demo:

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

editar: Acabei de confirmar que isso leva memória constante no python 3.2.1, assumindo que minha metodologia de teste estava correta. Eu criei uma string de tamanho muito grande (1 GB ou mais), em seguida, iterou por meio do iterável com um forloop (NÃO uma compreensão de lista, o que teria gerado memória extra). Isso não resultou em um crescimento perceptível da memória (ou seja, se houve um aumento na memória, era muito menor do que a string de 1 GB).

ninjagecko
fonte
5
Excelente! Eu tinha me esquecido do localizador. Se alguém estiver interessado em fazer algo como linhas de divisão, sugiro usar esta RE: '(. * \ N |. + $)' Str.splitlines corta a nova linha de treinamento (algo que eu realmente não gosto ... ); se você quiser replicar essa parte do comportamento, poderá usar o agrupamento: (m.group (2) ou m.group (3) para m em re.finditer ('((. *) \ n | (. +) $) ', s)). PS: Acho que os parênteses externos na ER não são necessários; Eu apenas me sinto desconfortável em usar | sem
parentesco
3
E quanto ao desempenho? a nova correspondência deve ser mais lenta do que a pesquisa normal.
anatoly techtonik
1
Como você reescreveria esta função split_iter para funcionar a_string.split("delimiter")?
Moberg
split aceita expressões regulares de qualquer maneira, então não é realmente mais rápido, se você quiser usar o valor retornado de uma maneira anterior ao próximo, olhe minha resposta na parte inferior ...
Veltzer Doron
str.split()não aceita expressões regulares, é o que re.split()você está pensando ...
alexis
17

A maneira mais eficiente que posso pensar é escrever um usando o offsetparâmetro do str.find()método. Isso evita muito uso de memória e depende da sobrecarga de uma regexp quando ela não é necessária.

[editar 2016-8-2: atualizado para suportar opcionalmente separadores regex]

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

Isso pode ser usado como você quiser ...

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

Embora haja um pouco de custo de busca dentro da string cada vez que find () ou fatiamento for executado, isso deve ser mínimo, pois as strings são representadas como matrizes contíguas na memória.

Eli Collins
fonte
10

Esta é a versão do gerador do split()implementado via re.search()que não tem o problema de alocar muitas substrings.

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('][')

EDIT: Tratamento corrigido de espaços em branco circundantes se nenhum caractere separador for fornecido.

Bernd Petersohn
fonte
12
por que isso é melhor do que re.finditer?
Erik Kaplun,
@ErikKaplun Porque a lógica regex para os itens pode ser mais complexa do que para seus separadores. No meu caso, eu queria processar cada linha individualmente, para poder relatar se uma linha falhou.
rovyko
9

Fiz alguns testes de desempenho nos vários métodos propostos (não os repetirei aqui). Alguns resultados:

  • str.split (padrão = 0,3461570239996945
  • pesquisa manual (por caractere) (uma das respostas de Dave Webb) = 0,8260340550004912
  • re.finditer (resposta de ninjagecko) = 0,698872097000276
  • str.find (uma das respostas de Eli Collins) = 0,7230395330007013
  • itertools.takewhile (Resposta de Ignacio Vazquez-Abrams) = 2,023023967998597
  • str.split(..., maxsplit=1) recursão = N / A †

† As respostas de recursão ( string.splitcom maxsplit = 1) não são concluídas em um tempo razoável, dadostring.split a velocidade s, elas podem funcionar melhor em strings mais curtas, mas não consigo ver o caso de uso para strings curtas em que a memória não seja um problema de qualquer maneira.

Testado usando timeitem:

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

Isso levanta outra questão: por que string.splité tão mais rápido apesar do uso de memória.

cz
fonte
2
Isso ocorre porque a memória é mais lenta do que a cpu e, neste caso, a lista é carregada por blocos, onde todas as outras são carregadas elemento por elemento. Na mesma nota, muitos acadêmicos dirão que as listas vinculadas são mais rápidas e têm menos complexidade, enquanto o seu computador costuma ser mais rápido com matrizes, que são mais fáceis de otimizar. Você não pode presumir que uma opção é mais rápida do que outra, teste-a! 1 para teste.
Benoît P
O problema surge nas próximas etapas de uma cadeia de processamento. Se você quiser encontrar um fragmento específico e ignorar o resto quando encontrá-lo, terá a justificativa para usar uma divisão baseada em gerador em vez da solução embutida.
jgomo3
6

Aqui está minha implementação, que é muito, muito mais rápida e completa do que as outras respostas aqui. Possui 4 subfunções separadas para casos diferentes.

Vou apenas copiar a docstring da str_splitfunção principal :


str_split(s, *delims, empty=None)

Divida a string spelo resto dos argumentos, possivelmente omitindo partes vazias (empty argumento de palavra-chave é o responsável por isso). Esta é uma função geradora.

Quando apenas um delimitador é fornecido, a string é simplesmente dividida por ele. emptyé então Truepor padrão.

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

Quando vários delimitadores são fornecidos, a sequência é dividida pelas sequências mais longas possíveis desses delimitadores por padrão ou, se emptyfor definido como True, sequências vazias entre os delimitadores também são incluídas. Observe que os delimitadores, neste caso, podem ser apenas caracteres únicos.

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

Quando nenhum delimitador é fornecido, string.whitespaceé usado, então o efeito é o mesmo que str.split(), exceto que esta função é um gerador.

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)

Esta função funciona no Python 3 e uma correção fácil, embora bastante feia, pode ser aplicada para fazê-la funcionar nas versões 2 e 3. As primeiras linhas da função devem ser alteradas para:

def str_split(s, *delims, **kwargs):
    """...docstring..."""
    empty = kwargs.get('empty')
Oleh Prypin
fonte
3

Não, mas deve ser fácil escrever um usando itertools.takewhile().

EDITAR:

Implementação muito simples, meio quebrada:

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 Vazquez-Abrams
fonte
@Ignacio: O exemplo em docs usa uma lista de inteiros para ilustrar o uso de takeWhile. O que seria bom predicatepara dividir uma string em palavras (padrão split) usando takeWhile()?
Manoj Govindan,
Procure presença em string.whitespace.
Ignacio Vazquez-Abrams,
O separador pode ter vários caracteres,'abc<def<>ghi<><>lmn'.split('<>') == ['abc<def', 'ghi', '', 'lmn']
kennytm 05 de
@Ignacio: Você pode adicionar um exemplo à sua resposta?
Manoj Govindan,
1
Fácil de escrever, mas muitas ordens de magnitude mais lento. Esta é uma operação que realmente deve ser implementada em código nativo.
Glenn Maynard,
3

Não vejo nenhum benefício óbvio em uma versão geradora de split(). O objeto gerador terá que conter a string inteira para iterar, então você não vai economizar memória por ter um gerador.

Se você quisesse escrever um, seria bastante fácil:

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)
Dave Webb
fonte
3
Você reduziria pela metade a memória usada, por não ter que armazenar uma segunda cópia da string em cada parte resultante, mais o array e a sobrecarga do objeto (que normalmente é mais do que as próprias strings). No entanto, isso geralmente não importa (se você está dividindo strings tão grandes que isso importa, provavelmente está fazendo algo errado), e mesmo uma implementação de gerador C nativo sempre seria significativamente mais lenta do que fazer tudo de uma vez.
Glenn Maynard,
@Glenn Maynard - Acabei de perceber isso. Eu, por alguma razão, originalmente o gerador armazenaria uma cópia da string em vez de uma referência. Uma verificação rápida com id()me colocar no lugar. E, obviamente, como as strings são imutáveis, você não precisa se preocupar com alguém alterando a string original enquanto você está iterando sobre ela.
Dave Webb,
6
O ponto principal em usar um gerador não é o uso de memória, mas você pode evitar ter que dividir a string inteira se quiser sair mais cedo? (Isso não é um comentário sobre sua solução específica, fiquei apenas surpreso com a discussão sobre memória).
Scott Griffiths,
@Scott: É difícil pensar em um caso em que isso seja realmente uma vitória - onde 1: você deseja parar de se dividir no meio, 2: você não sabe quantas palavras está dividindo antecipadamente, 3: você tem um string grande o suficiente para ser importante e 4: você para consistentemente cedo o suficiente para que seja uma vitória significativa sobre str.split. Esse é um conjunto de condições muito estreito.
Glenn Maynard,
4
Você pode ter um benefício muito maior se sua string for gerada lentamente também (por exemplo, do tráfego de rede ou de leituras de arquivo)
Lie Ryan
3

Eu escrevi uma versão da resposta de @ninjagecko que se comporta mais como string.split (ou seja, espaço em branco delimitado por padrão e você pode especificar um delimitador).

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

Aqui estão os testes que usei (em python 3 e 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

O módulo regex do python diz que ele faz "a coisa certa" para espaços em branco unicode, mas eu realmente não testei.

Também disponível como uma essência .

pastor
fonte
3

Se você também gostaria de ler um iterador (bem como retornar um), tente isto:

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)

Uso

>>> list(iter_split(iter("Good evening, world!")))
['Good', 'evening,', 'world!']
Reubano
fonte
3

more_itertools.split_atoferece um análogo str.splitpara iteradores.

>>> 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 é um pacote de terceiros.

pilang
fonte
1
Observe que more_itertools.split_at () ainda está usando uma lista recém-alocada em cada chamada, então, embora isso retorne um iterador, não está atingindo o requisito de memória constante. Portanto, dependendo de por que você queria um iterador para começar, isso pode ou não ser útil.
jcater
@jcater Bom argumento. Os valores intermediários são de fato armazenados como sub-listas dentro do iterador, de acordo com sua implementação . Pode-se adaptar a fonte para substituir listas por iteradores, acrescentar itertools.chaine avaliar os resultados usando uma compreensão de lista. Dependendo da necessidade e solicitação, posso postar um exemplo.
pylang
2

Eu queria mostrar como usar a solução find_iter para retornar um gerador para determinados delimitadores e, em seguida, usar a receita de pares de itertools para construir uma próxima iteração anterior que obterá as palavras reais como no método de divisão original.


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

Nota:

  1. Eu uso prev & curr em vez de prev e next porque substituir next em python é uma ideia muito ruim
  2. Isso é bastante eficiente
Veltzer Doron
fonte
1

Método mais idiota, sem regex / 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
fonte
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
ossos viajando
fonte
por que você cede [f[j:i]]e não f[j:i]?
Moberg
0

aqui está uma resposta simples

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
fonte