Existe-t-il une version génératrice de `string.split()` en Python ?

Question

string.split() renvoie un liste instance. Existe-t-il une version qui renvoie un générateur à la place ? Y a-t-il des raisons qui s'opposent à l'existence d'une version du générateur ?

Answer 1

Il est très probable que re.finditer utilise une surcharge de mémoire assez minime.

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

Démonstration :

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

éditer : Je viens de confirmer que cela prend une mémoire constante dans python 3.2.1, en supposant que ma méthodologie de test était correcte. J'ai créé une chaîne de caractères de très grande taille (1GB ou plus), puis j'ai itéré dans l'itérable avec une fonction for (PAS une compréhension de liste, qui aurait généré de la mémoire supplémentaire). Cela n'a pas entraîné de croissance notable de la mémoire (c'est-à-dire que s'il y a eu une croissance de la mémoire, elle était bien inférieure à la chaîne de 1 Go).

Version plus générale :

En réponse à un commentaire "Je ne vois pas le rapport avec str.split ", voici une version plus générale :

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

L'idée est que ((?!pat).)* annule un groupe en s'assurant qu'il correspond de manière avide jusqu'à ce que le motif commence à correspondre (les lookaheads ne consomment pas la chaîne dans la machine à état fini de la regex). En pseudocode : consommer de manière répétée ( begin-of-string xor {sep} ) + as much as possible until we would be able to begin again (or hit end of string)

Démonstration :

>>> 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.', '']

(Il convient de noter que str.split a un comportement déplaisant : il s'agit d'un cas spécial où le fait d'avoir sep=None comme le fait d'abord str.strip pour supprimer les espaces en tête et en queue. La méthode ci-dessus ne le fait pas délibérément ; voir le dernier exemple où sep= "\s+" .)

(J'ai rencontré plusieurs bogues (y compris une erreur interne re.error) en essayant d'implémenter ceci...). Le lookbehind négatif vous limitera aux délimiteurs de longueur fixe, donc nous ne l'utilisons pas. Presque tout ce qui est autre que la regex ci-dessus semble entraîner des erreurs avec les cas limites de début de chaîne et de fin de chaîne (par ex. r'(.*?)($|,)' sur ',,,a,,b,c' renvoie à ['', '', '', 'a', '', 'b', 'c', ''] avec une chaîne vide étrangère à la fin ; on peut consulter l'historique des modifications pour trouver une autre regex apparemment correcte qui présente en fait de subtils bogues).

(Si vous voulez l'implémenter vous-même pour obtenir de meilleures performances (bien qu'elles soient lourdes, les regex s'exécutent principalement en C), vous écrirez du code (avec ctypes ? je ne sais pas comment faire fonctionner les générateurs avec ?), avec le pseudocode suivant pour les délimiteurs de longueur fixe : Hachez votre délimiteur de longueur L. Gardez un hachage courant de longueur L pendant que vous parcourez la chaîne de caractères en utilisant un algorithme de hachage courant, temps de mise à jour O(1). Chaque fois que le hachage pourrait être égal à votre délimiteur, vérifiez manuellement si les derniers caractères étaient le délimiteur ; si c'est le cas, donnez la sous-chaîne depuis le dernier rendement. Cas particulier pour le début et la fin de la chaîne. Ce serait une version génératrice de l'algorithme du manuel pour faire une recherche de texte O(N). Des versions multiprocesseurs sont également possibles. Elles peuvent sembler exagérées, mais la question implique que l'on travaille avec des chaînes de caractères vraiment énormes... À ce moment-là, on peut envisager des choses folles comme la mise en cache des offsets d'octets s'il y en a peu, ou travailler à partir du disque avec un objet de visualisation d'octets sauvegardé sur le disque, acheter plus de RAM, etc. etc.)

Answer 2

Le moyen le plus efficace auquel j'ai pensé est d'en écrire un en utilisant la fonction offset du paramètre str.find() méthode. Cela évite d'utiliser beaucoup de mémoire et de s'appuyer sur la surcharge d'une regexp quand elle n'est pas nécessaire.

[edit 2016-8-2 : mis à jour pour supporter optionnellement les séparateurs 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

On peut l'utiliser comme on veut...

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

Bien qu'il y ait un petit coût de recherche dans la chaîne chaque fois que find() ou le découpage est effectué, cela devrait être minime puisque les chaînes sont représentées comme des tableaux continus en mémoire.

Answer 3

Il s'agit de la version du générateur de split() mis en œuvre via re.search() qui n'a pas le problème d'allouer trop de sous-chaînes.

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 : Correction de la gestion des espaces blancs environnants si aucun caractère séparateur n'est donné.

Answer 4

Je ne vois pas d'avantage évident à une version de générateur de split() . L'objet générateur va devoir contenir la chaîne entière à itérer, donc vous n'allez pas économiser de la mémoire en ayant un générateur.

Si vous vouliez en écrire un, ce serait pourtant assez facile :

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)

Answer 5

Non, mais il devrait être assez facile d'en écrire un en utilisant les éléments suivants itertools.takewhile() .

EDIT :

Une mise en œuvre très simple, à moitié cassée :

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