Czy istnieje wersja generatora funkcji `string.split ()` w Pythonie?


113

string.split()zwraca instancję listy . Czy istnieje wersja, która zamiast tego zwraca generator ? Czy są jakieś powody, aby nie mieć wersji generatora?


3
To pytanie może być powiązane.
Björn Pollex

1
Powodem jest to, że bardzo trudno jest wymyślić przypadek, w którym jest to przydatne. Dlaczego tego chcesz?
Glenn Maynard,

10
@Glenn: Niedawno zobaczyłem pytanie dotyczące dzielenia długiego ciągu na fragmenty n słów. Jedno z rozwiązań splitzwróciło ciąg znaków, a następnie zwrócił generator pracujący na wyniku split. To sprawiło, że pomyślałem, czy istnieje sposób na splitzwrócenie generatora na początek.
Manoj Govindan

5
Istnieje odpowiednia dyskusja na temat narzędzia do śledzenia problemów
saffsd Kwietnia

@GlennMaynard może być przydatny do naprawdę dużego parsowania gołego ciągu / pliku, ale każdy może bardzo łatwo napisać parser generatora, używając samodzielnie zaparzonego DFA i wydajności
Dmitry Ponyatov

Odpowiedzi:


77

Jest wysoce prawdopodobne, że re.finditerwykorzystuje dość minimalne obciążenie pamięci.

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

Próbny:

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

edycja: Właśnie potwierdziłem, że zajmuje to stałą pamięć w Pythonie 3.2.1, zakładając, że moja metodologia testowania była poprawna. Utworzyłem ciąg o bardzo dużym rozmiarze (około 1 GB), a następnie iterowałem przez iterowalną forpętlę (NIE list składany, który wygenerowałby dodatkową pamięć). Nie spowodowało to zauważalnego wzrostu pamięci (to znaczy, jeśli nastąpił wzrost pamięci, był znacznie mniejszy niż ciąg 1 GB).


5
Doskonały! Zapomniałem o Finderze. Jeśli ktoś byłby zainteresowany zrobieniem czegoś w rodzaju podzielonych linii, sugerowałbym użycie tego RE: '(. * \ N |. + $)' Str.splitlines odcina jednak trenującą nową linię (coś, czego tak naprawdę nie lubię ... ); jeśli chcesz zreplikować tę część zachowania, możesz użyć grupowania: (m.group (2) lub m.group (3) for m in re.finditer ('((. *) \ n | (. +) $) ', s)). PS: Wydaje mi się, że zewnętrzne paren w RE nie są potrzebne; Po prostu czuję się nieswojo używając | bez paren: P
allyourcode

3
A co z wydajnością? ponowne dopasowywanie powinno być wolniejsze niż zwykłe wyszukiwanie.
anatoly techtonik

1
Jak przepisałbyś tę funkcję split_iter, aby działała a_string.split("delimiter")?
Moberg

split i tak akceptuje wyrażenia regularne, więc nie jest to naprawdę szybsze, jeśli chcesz użyć zwróconej wartości w poprzedni sposób, spójrz na moją odpowiedź na dole ...
Veltzer Doron

str.split()nie akceptuje wyrażeń regularnych, to re.split()właśnie myślisz ...
alexis

17

Najbardziej wydajnym sposobem, w jaki mogę wymyślić, jest napisanie jednego przy użyciu offsetparametru str.find()metody. Pozwala to uniknąć dużego wykorzystania pamięci i polegania na narzutu wyrażenia regularnego, gdy nie jest to potrzebne.

[edit 2016-8-2: zaktualizowano to, aby opcjonalnie obsługiwać separatory wyrażeń regularnych]

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

Można tego używać tak, jak chcesz ...

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

Chociaż za każdym razem, gdy wykonywana jest funkcja find () lub wycinanie, w ciągu występuje trochę kosztów wyszukiwania, powinno to być minimalne, ponieważ łańcuchy są reprezentowane jako ciągłe tablice w pamięci.


10

Jest to wersja generatora split()zaimplementowana przez re.search(), która nie ma problemu z przydzieleniem zbyt wielu podciągów.

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

EDYCJA: Poprawiono obsługę otaczających białych znaków, jeśli nie podano znaków separatora.


12
dlaczego to jest lepsze niż re.finditer?
Erik Kaplun,

@ErikKaplun Ponieważ logika regex dla elementów może być bardziej złożona niż dla ich separatorów. W moim przypadku chciałem przetworzyć każdą linię osobno, aby móc zgłosić, jeśli linia nie pasuje.
rovyko

9

Przeprowadziłem testy wydajności różnych proponowanych metod (nie będę ich tutaj powtarzać). Niektóre wyniki:

  • str.split (domyślnie = 0,3461570239996945
  • wyszukiwanie ręczne (po znaku) (jedna z odpowiedzi Dave'a Webba) = 0,8260340550004912
  • re.finditer (odpowiedź Ninjagecko) = 0,698872097000276
  • str.find (jedna z odpowiedzi Eli Collinsa) = 0,7230395330007013
  • itertools.takewhile (Odpowiedź Ignacio Vazqueza-Abramsa) = 2,023023967998597
  • str.split(..., maxsplit=1) rekurencja = nie dotyczy †

† Odpowiedzi rekursji ( string.splitz maxsplit = 1) nie kończą się w rozsądnym czasie, biorąc pod uwagę string.splitszybkość, mogą działać lepiej na krótszych ciągach, ale wtedy nie widzę przypadku użycia dla krótkich ciągów, w których pamięć i tak nie jest problemem.

Przetestowano timeitna:

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

Rodzi to kolejne pytanie, dlaczego string.splitjest o wiele szybszy pomimo zużycia pamięci.


2
Dzieje się tak, ponieważ pamięć jest wolniejsza niż procesor iw tym przypadku lista jest ładowana przez fragmenty, przy czym wszystkie inne są ładowane element po elemencie. Z tego samego powodu wielu naukowców powie, że połączone listy są szybsze i mniej skomplikowane, podczas gdy twój komputer często będzie szybszy dzięki tablicom, które łatwiej jest zoptymalizować. Nie możesz zakładać, że dana opcja jest szybsza niż inna, przetestuj ją! +1 do testów.
Benoît P

Problem pojawia się na kolejnych etapach łańcucha przetwarzania. Jeśli następnie chcesz znaleźć konkretną porcję i zignorować resztę, gdy ją znajdziesz, masz uzasadnienie, aby użyć podziału opartego na generatorze zamiast wbudowanego rozwiązania.
jgomo3

6

Oto moja implementacja, która jest dużo, dużo szybsza i bardziej kompletna niż inne odpowiedzi tutaj. Ma 4 oddzielne podfunkcje dla różnych przypadków.

Po prostu skopiuję dokumentację głównej str_splitfunkcji:


str_split(s, *delims, empty=None)

Podziel ciąg sna pozostałe argumenty, prawdopodobnie pomijając puste części (za emptyto odpowiada argument słowa kluczowego). To jest funkcja generatora.

Gdy podano tylko jeden separator, ciąg jest po prostu dzielony przez niego. emptyjest wtedy Truedomyślnie.

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

W przypadku podania wielu separatorów ciąg jest domyślnie dzielony na najdłuższe możliwe sekwencje tych separatorów lub, jeśli emptyjest ustawiona na True, dołączane są również puste ciągi między ogranicznikami. Zauważ, że ograniczniki w tym przypadku mogą być tylko pojedynczymi znakami.

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

Gdy nie podano ograniczników, string.whitespacejest używany, więc efekt jest taki sam, jak str.split(), z wyjątkiem tego, że ta funkcja jest generatorem.

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)

Ta funkcja działa w Pythonie 3 i można zastosować łatwą, choć dość brzydką poprawkę, aby działała zarówno w wersji 2, jak i 3. Pierwsze wiersze funkcji należy zmienić na:

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

3

Nie, ale napisanie takiego pliku powinno być łatwe itertools.takewhile().

EDYTOWAĆ:

Bardzo prosta, na wpół zepsuta implementacja:

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: przykład w dokumentach używa listy liczb całkowitych do zilustrowania użycia takeWhile. Co byłoby dobre predicatedo podzielenia ciągu na słowa (domyślnie split) za pomocą takeWhile()?
Manoj Govindan

Poszukaj obecności w string.whitespace.
Ignacio Vazquez-Abrams

Separator może mieć wiele znaków,'abc<def<>ghi<><>lmn'.split('<>') == ['abc<def', 'ghi', '', 'lmn']
kennytm

@Ignacio: Czy możesz dodać przykład do swojej odpowiedzi?
Manoj Govindan

1
Łatwe do napisania, ale o wiele rzędów wielkości wolniejsze. To jest operacja, która naprawdę powinna być zaimplementowana w kodzie natywnym.
Glenn Maynard,

3

Nie widzę żadnych oczywistych korzyści z wersji generatora split(). Obiekt generatora będzie musiał zawierać cały ciąg do iteracji, więc nie będziesz oszczędzać pamięci, mając generator.

Gdybyś chciał napisać taki napis, byłoby to dość łatwe:

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
Zmniejszyłbyś o połowę używaną pamięć, ponieważ nie musisz przechowywać drugiej kopii ciągu w każdej wynikowej części, a także narzut tablicy i obiektu (który jest zwykle większy niż same ciągi). Generalnie nie ma to jednak znaczenia (jeśli dzielisz łańcuchy tak duże, że ma to znaczenie, prawdopodobnie robisz coś źle), a nawet natywna implementacja generatora C zawsze byłaby znacznie wolniejsza niż robienie tego wszystkiego naraz.
Glenn Maynard,

@Glenn Maynard - właśnie to sobie uświadomiłem. Z jakiegoś powodu pierwotnie generator przechowywał kopię łańcucha zamiast odniesienia. Szybkie sprawdzenie u id()mnie. I oczywiście, ponieważ ciągi są niezmienne, nie musisz się martwić, że ktoś zmieni oryginalny ciąg podczas iteracji nad nim.
Dave Webb

6
Czy głównym celem korzystania z generatora nie jest użycie pamięci, ale to, że możesz zaoszczędzić sobie konieczności dzielenia całego ciągu, jeśli chcesz wyjść wcześniej? (To nie jest komentarz do twojego konkretnego rozwiązania, byłem po prostu zaskoczony dyskusją o pamięci).
Scott Griffiths

@Scott: Trudno wyobrazić sobie przypadek, w którym to naprawdę wygrana - gdzie 1: chcesz przestać się rozdzielać w połowie, 2: nie wiesz, ile słów z góry dzielisz, 3: masz wystarczająco duży, aby miał znaczenie, i 4: konsekwentnie zatrzymujesz się wystarczająco wcześnie, aby było to znaczące zwycięstwo nad str.split. To bardzo wąski zestaw warunków.
Glenn Maynard

4
Można mieć znacznie większą korzyść, jeśli ciąg jest generowany leniwie, jak również (na przykład z ruchem sieciowym lub pliku odsłon)
Lie Ryan

3

Napisałem wersję odpowiedzi @ ninjagecko, która zachowuje się bardziej jak string.split (tj. Domyślnie oddzielone białymi znakami i możesz określić separator).

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

Oto testy, których użyłem (zarówno w Pythonie 3, jak i Pythonie 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

Moduł regex w pythonie mówi, że robi „właściwą rzecz” dla białych znaków Unicode, ale tak naprawdę tego nie testowałem.

Dostępne również jako podsumowanie .


3

Jeśli chcesz również móc odczytać iterator (a także zwrócić go), spróbuj tego:

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)

Stosowanie

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

3

more_itertools.split_atoferuje analog str.splitdla iteratorów.

>>> 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 to pakiet innej firmy.


1
Zauważ, że more_itertools.split_at () nadal używa nowo przydzielonej listy przy każdym wywołaniu, więc chociaż zwraca iterator, nie spełnia wymagań stałej pamięci. Więc w zależności od tego, dlaczego chciałeś mieć iterator na początku, może to być pomocne lub nie.
jcater

@jcater Słuszna uwaga. Wartości pośrednie są rzeczywiście buforowane jako listy podrzędne w iteratorze, zgodnie z jego implementacją . Można by dostosować źródło do zastępowania list iteratorami, dołączania itertools.chaini oceny wyników przy użyciu funkcji rozumienia list. W zależności od potrzeby i prośby mogę zamieścić przykład.
pylang

2

Chciałem pokazać, jak użyć rozwiązania find_iter, aby zwrócić generator dla podanych ograniczników, a następnie użyć przepisu parami z narzędzi itertools, aby zbudować poprzednią następną iterację, która otrzyma rzeczywiste słowa jak w oryginalnej metodzie podziału.


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

Uwaga:

  1. Używam prev & curr zamiast prev & next, ponieważ nadpisywanie next w Pythonie jest bardzo złym pomysłem
  2. Jest to dość wydajne

1

Najgłupsza metoda, bez wyrażeń regularnych / 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:]

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

dlaczego się poddajesz, [f[j:i]]a nie f[j:i]?
Moberg,

0

oto prosta odpowiedź

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:]
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.