¿Existe una versión generadora de `string.split ()` en Python?

113

string.split()devuelve una instancia de lista . ¿Hay alguna versión que devuelva un generador en su lugar? ¿Hay alguna razón para no tener una versión de generador?

Manoj Govindan
fuente
3
Esta pregunta podría estar relacionada.
Björn Pollex
1
La razón es que es muy difícil pensar en un caso en el que sea útil. ¿Por qué quieres esto?
Glenn Maynard
10
@Glenn: Recientemente vi una pregunta sobre cómo dividir una cadena larga en trozos de n palabras. Una de las soluciones splitla cadena y luego devolvió un generador trabajando en el resultado de split. Eso me hizo pensar si había una manera de splitdevolver un generador para empezar.
Manoj Govindan
5
Hay una discusión relevante sobre el rastreador de problemas de Python: bugs.python.org/issue17343
saffsd
@GlennMaynard puede ser útil para el análisis de archivos / cadenas desnudas realmente grandes, pero cualquiera puede escribir un analizador generador por sí mismo muy fácilmente usando DFA
autoelaborado

Respuestas:

77

Es muy probable que re.finditerutilice una sobrecarga de memoria bastante mínima.

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

Manifestación:

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

editar: Acabo de confirmar que esto requiere memoria constante en Python 3.2.1, asumiendo que mi metodología de prueba fuera correcta. Creé una cadena de tamaño muy grande (1GB más o menos), luego itere a través del iterable con un forbucle (NO una lista de comprensión, que habría generado memoria adicional). Esto no resultó en un crecimiento notable de la memoria (es decir, si hubo un crecimiento en la memoria, fue mucho menor que la cadena de 1GB).

ninjagecko
fuente
5
¡Excelente! Me había olvidado de Finditer. Si uno estuviera interesado en hacer algo como splitlines, sugeriría usar este RE: '(. * \ N |. + $)' Str.splitlines corta la nueva línea de trainling (algo que realmente no me gusta ... ); si desea replicar esa parte del comportamiento, puede usar la agrupación: (m.group (2) o m.group (3) para m en re.finditer ('((. *) \ n | (. +) $) ', s)). PD: Supongo que los parientes externos en el RE no son necesarios; Me siento incómodo por usar | sin par: P
allyourcode
3
¿Y el rendimiento? La búsqueda de coincidencias debería ser más lenta que la búsqueda normal.
anatoly techtonik
1
¿Cómo reescribiría esta función split_iter para que funcione a_string.split("delimiter")?
Moberg
split acepta expresiones regulares de todos modos, por lo que no es realmente más rápido, si desea usar el valor devuelto de una manera anterior al siguiente, mire mi respuesta en la parte inferior ...
Veltzer Doron
str.split()no acepta expresiones regulares, eso es lo re.split()que estás pensando ...
Alexis
17

La forma más eficiente en la que puedo pensar es escribir uno usando el offsetparámetro del str.find()método. Esto evita mucho uso de memoria y depende de la sobrecarga de una expresión regular cuando no es necesaria.

[editar 2016-8-2: actualizado esto para admitir opcionalmente separadores de expresiones regulares]

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

Esto se puede usar como quieras ...

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

Si bien hay un poco de búsqueda de costos dentro de la cadena cada vez que se realiza find () o corte, esto debería ser mínimo ya que las cadenas se representan como matrices continuas en la memoria.

Eli Collins
fuente
10

Esta es una versión del generador de split()implementada vía re.search()que no tiene el problema de asignar demasiadas subcadenas.

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

EDITAR: Se corrigió el manejo de los espacios en blanco circundantes si no se dan caracteres de separación.

Bernd Petersohn
fuente
12
¿Por qué es esto mejor que re.finditer?
Erik Kaplun
@ErikKaplun Porque la lógica de expresiones regulares para los elementos puede ser más compleja que para sus separadores. En mi caso, quería procesar cada línea individualmente, para poder informar si una línea no coincide.
rovyko
8

Hice algunas pruebas de rendimiento en los diversos métodos propuestos (no los repetiré aquí). Algunos resultados:

  • str.split (predeterminado = 0.3461570239996945
  • búsqueda manual (por carácter) (una de las respuestas de Dave Webb) = 0.8260340550004912
  • re.finditer (respuesta de ninjagecko) = 0.698872097000276
  • str.find (una de las respuestas de Eli Collins) = 0,7230395330007013
  • itertools.takewhile (Respuesta de Ignacio Vazquez-Abrams) = 2.023023967998597
  • str.split(..., maxsplit=1) recursividad = N / A †

† Las respuestas de recursividad ( string.splitcon maxsplit = 1) no se completan en un tiempo razonable, dadostring.split la velocidad, pueden funcionar mejor en cadenas más cortas, pero luego no puedo ver el caso de uso para cadenas cortas donde la memoria no es un problema de todos modos.

Probado usando timeiten:

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

Esto plantea otra pregunta sobre por qué string.splites mucho más rápido a pesar de su uso de memoria.

cz
fuente
1
Esto se debe a que la memoria es más lenta que la CPU y, en este caso, la lista se carga por fragmentos, mientras que todos los demás se cargan elemento por elemento. En la misma nota, muchos académicos le dirán que las listas vinculadas son más rápidas y tienen menos complejidad, mientras que su computadora a menudo será más rápida con arreglos, que encuentran más fácil de optimizar. No puede asumir que una opción es más rápida que otra, ¡pruébela! +1 para pruebas.
Benoît P
El problema surge en los siguientes pasos de una cadena de procesamiento. Si luego desea encontrar un fragmento específico e ignorar el resto cuando lo encuentre, entonces tiene la justificación para usar una división basada en generador en lugar de la solución incorporada.
jgomo3
6

Aquí está mi implementación, que es mucho, mucho más rápida y completa que las otras respuestas aquí. Tiene 4 subfunciones separadas para diferentes casos.

Solo copiaré la cadena de documentos de la str_splitfunción principal :


str_split(s, *delims, empty=None)

Divida la cadena spor el resto de los argumentos, posiblemente omitiendo partes vacías (empty argumento de palabra clave es responsable de eso). Esta es una función de generador.

Cuando solo se proporciona un delimitador, la cadena simplemente se divide por él. emptyes entonces Truepor defecto.

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

Cuando se proporcionan varios delimitadores, la cadena se divide por las secuencias más largas posibles de esos delimitadores de forma predeterminada o, si emptyse establece en True, también se incluyen cadenas vacías entre los delimitadores. Tenga en cuenta que los delimitadores en este caso pueden ser solo caracteres individuales.

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

Cuando no se suministran delimitadores, string.whitespacese usa, por lo que el efecto es el mismo que str.split(), excepto que esta función es un generador.

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 función funciona en Python 3, y se puede aplicar una solución fácil, aunque bastante fea, para que funcione en las versiones 2 y 3. Las primeras líneas de la función deben cambiarse a:

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

No, pero debería ser bastante fácil escribir uno usando itertools.takewhile().

EDITAR:

Implementación muy simple, medio rota:

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 Vázquez-Abrams
fuente
@Ignacio: El ejemplo en docs usa una lista de enteros para ilustrar el uso de takeWhile. ¿Qué sería bueno predicatepara dividir una cadena en palabras (predeterminado split) usando takeWhile()?
Manoj Govindan
Busque presencia en string.whitespace.
Ignacio Vazquez-Abrams
El separador puede tener varios caracteres,'abc<def<>ghi<><>lmn'.split('<>') == ['abc<def', 'ghi', '', 'lmn']
kennytm
@Ignacio: ¿Puedes agregar un ejemplo a tu respuesta?
Manoj Govindan
1
Fácil de escribir, pero muchos órdenes de magnitud más lento. Esta es una operación que realmente debería implementarse en código nativo.
Glenn Maynard
3

No veo ningún beneficio obvio en una versión de generador de split(). El objeto generador tendrá que contener toda la cadena para iterar, por lo que no va a ahorrar memoria al tener un generador.

Sin embargo, si quisieras escribir uno, sería 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
fuente
3
Reduciría a la mitad la memoria utilizada, al no tener que almacenar una segunda copia de la cadena en cada parte resultante, más la matriz y la sobrecarga del objeto (que suele ser más que las propias cadenas). Sin embargo, eso generalmente no importa (si está dividiendo cadenas tan grandes que esto importa, probablemente esté haciendo algo mal), e incluso una implementación del generador de C nativo siempre sería significativamente más lenta que hacerlo todo a la vez.
Glenn Maynard
@Glenn Maynard: me acabo de dar cuenta de eso. Por alguna razón, originalmente el generador almacenaría una copia de la cadena en lugar de una referencia. Un chequeo rápido id()me corrigió. Y, obviamente, como las cadenas son inmutables, no necesita preocuparse de que alguien cambie la cadena original mientras está iterando sobre ella.
Dave Webb
6
¿No es el punto principal de usar un generador no el uso de la memoria, sino que podría ahorrarse tener que dividir toda la cadena si quisiera salir antes? (Ese no es un comentario sobre su solución en particular, me sorprendió la discusión sobre la memoria).
Scott Griffiths
@Scott: Es difícil pensar en un caso en el que eso sea realmente una victoria, donde 1: quieres dejar de dividir a la mitad, 2: no sabes cuántas palabras estás dividiendo de antemano, 3: tienes un cadena lo suficientemente grande como para que importe, y 4: constantemente te detienes lo suficientemente temprano para que sea una victoria significativa sobre str.split. Ese es un conjunto de condiciones muy limitado.
Glenn Maynard
4
Puede obtener un beneficio mucho mayor si su cadena también se genera de manera perezosa (por ejemplo, a partir del tráfico de red o las lecturas de archivos)
Lie Ryan
3

Escribí una versión de la respuesta de @ ninjagecko que se comporta más como string.split (es decir, espacios en blanco delimitados por defecto y puedes especificar un 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))

Aquí están las pruebas que utilicé (tanto en python 3 como en 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

El módulo de expresiones regulares de python dice que hace "lo correcto" para los espacios en blanco Unicode, pero en realidad no lo he probado.

También disponible como esencia .

pastor
fuente
3

Si también desea poder leer un iterador (así como devolver uno), intente esto:

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
fuente
3

more_itertools.split_atofrece un análogo a 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 es un paquete de terceros.

pylang
fuente
1
Tenga en cuenta que more_itertools.split_at () todavía usa una lista recién asignada en cada llamada, por lo que si bien esto devuelve un iterador, no está logrando el requisito de memoria constante. Entonces, dependiendo de por qué deseaba comenzar con un iterador, esto puede ser útil o no.
jcater
@jcater Buen punto. De hecho, los valores intermedios se almacenan en búfer como sublistas dentro del iterador, según su implementación . Se podría adaptar la fuente para sustituir listas con iteradores, agregar itertools.chainy evaluar resultados usando una comprensión de lista. Dependiendo de la necesidad y solicitud, puedo publicar un ejemplo.
pylang
2

Quería mostrar cómo usar la solución find_iter para devolver un generador para delimitadores dados y luego usar la receta por pares de itertools para construir una siguiente iteración anterior que obtendrá las palabras reales como en el método de división 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. Uso prev & curr en lugar de prev & next porque anular el siguiente en python es una muy mala idea
  2. Esto es bastante eficiente
Veltzer Doron
fuente
1

Método más tonto, sin 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
fuente
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
huesos que viajan
fuente
¿Por qué cedes [f[j:i]]y no f[j:i]?
Moberg
0

aquí hay una respuesta simple

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:]
usuario1438644
fuente