Самый эффективный способ разделения строк в Python

Question

Мой текущий проект Python потребует много разделения строк для обработки входящих пакетов.Поскольку я буду запускать его на довольно медленной системе, мне было интересно, каким будет самый эффективный способ сделать это.Строки должны быть отформатированы примерно так:

Item 1 | Item 2 | Item 3 <> Item 4 <> Item 5

Объяснение: Этот конкретный пример будет взят из списка, в котором первые два элемента - это заголовок и дата, а от 3 до 5 будут приглашены люди.(Число может быть любым от нуля до n, где n - количество зарегистрированных пользователей на сервере).

Из того, что я вижу, у меня есть следующие опции:

1. многократно использовать split()
2. Использовать регулярное выражение и функции Regex
3. Некоторые другие функции Python, о которых я еще не думал (возможно, есть)

Решение 1 будет включать разбиение на | и последующее разбиение последнего элемента результирующего списка на <> для этого примера, в то время как решение 2, вероятно, приведет к регулярному выражению, например:

((.+)|)+((.+)(<>)?)+

Хорошо, этот RegEx ужасен, я сам это вижу.Это также не проверено.Но вы поняли.

Теперь я ищу способ, который а) занимает наименьшее количество времени и б) в идеале использует наименьшее количество памяти.Если возможен только один из двух вариантов, я бы предпочел меньше времени.Идеальное решение также подойдет для строк, в которых больше элементов разделено |, и для строк, в которых отсутствует <>.По крайней мере, решение на основе регулярных выражений сделало бы это

Насколько я понимаю, split() будет использовать больше памяти (поскольку вы в основном получаете два результирующих списка, один из которых разбивается на |, а второй -разделяется на <>), но я недостаточно знаю о реализации регулярных выражений в Pythons, чтобы судить о том, как будет работать RegEx.split() также менее динамичен, чем регулярное выражение, если оно относится к разным номерам Предметов и отсутствию второго разделителя.Тем не менее, я не могу избавиться от впечатления, что python может делать это лучше без регулярных выражений, поэтому я прошу

Некоторые примечания:

• Да, я мог бы просто сравнить оба решения, но я пытаюсь узнать кое-что о Python в целом и о том, как он работает здесь, и если я просто сравню эти два, я все еще не знаю, какие функции Python я пропустил.
• Да, оптимизация вэтот уровень действительно необходим только для высокопроизводительных вещей, но, как я уже сказал, я пытаюсь кое-что узнать о питоне.
• Добавление: в исходном вопросе я совершенно забыл упомянутьчто мне нужно иметь возможность отличить части, которые были отделены | от частей с разделителем <>, поэтому простой плоский список, сгенерированный re.split(\||<>,input) (как предложено @obmarg), не будет работать слишком хорошо,Решения, соответствующие этому критерию, высоко ценятся.

Подводя итоги вопроса: какое решение было бы наиболее эффективным и по каким причинам.

Из-за нескольких запросов я выполнилнекоторое время о split() -растворе и первом предложенном регулярном выражении @obmarg, а также о решениях @mgibsonbr и @duncan:

import timeit
import re

def splitit(input):
    res0 = input.split("|")
    res = []
    for element in res0:
        t = element.split("<>")
        if t != [element]:
            res0.remove(element)
            res.append(t)
    return (res0, res)

def regexit(input):
    return re.split( "\||<>", input )


def mgibsonbr(input): # Solution by @mgibsonbr
    items = re.split(r'\||<>', input) # Split input in items
    offset = 0
    result = [] # The result: strings for regular itens, lists for <> separated ones
    acc = None
    for i in items:
        delimiter = '|' if offset+len(i) < len(input) and input[offset+len(i)] == '|' else '<>'
        offset += len(i) + len(delimiter)
        if delimiter == '<>': # Will always put the item in a list
            if acc is None:
                acc = [i] # Create one if doesn't exist
                result.append(acc)
            else:
                acc.append(i)
        else:
            if acc is not None: # If there was a list, put the last item in it
                acc.append(i)
            else:
                result.append(i) # Add the regular items
            acc = None # Clear the list, since what will come next is a regular item or a new list
    return result

def split2(input): # Solution by @duncan
    res0 = input.split("|")
    res1, res2 = [], []
    for r in res0:
        if "<>" in r:
            res2.append(r.split("<>"))
        else:
            res1.append(r)
    return res1, res2

print "mgibs:", timeit.Timer("mgibsonbr('a|b|c|de|f<>ge<>ah')","from __main__ import mgibsonbr").timeit()
print "split:", timeit.Timer("splitit('a|b|c|de|f<>ge<>ah')","from __main__ import splitit").timeit()
print "split2:", timeit.Timer("split2('a|b|c|de|f<>ge<>ah')","from __main__ import split2").timeit()
print "regex:", timeit.Timer("regexit('a|b|c|de|f<>ge<>ah')","from __main__ import regexit").timeit()
print "mgibs:", timeit.Timer("mgibsonbr('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import mgibsonbr").timeit()
print "split:", timeit.Timer("splitit('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import splitit").timeit()
print "split:", timeit.Timer("split2('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import split2").timeit()
print "regex:", timeit.Timer("regexit('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import regexit").timeit()

Результаты:

mgibs: 14.7349407408
split: 6.403942732
split2: 3.68306812233
regex: 5.28414318792
mgibs: 107.046683735
split: 46.0844590775
split2: 26.5595985591
regex: 28.6513302646

В настоящий момент выглядит так, что split2 от @duncan превосходит все остальные алгоритмы, независимо от длины (по крайней мере, с этим ограниченным набором данных), а также похоже, что решение @ mgibsonbr имеет некоторые проблемы с производительностью (извините, но спасибоза решение независимо).

Спасибо за вклад, всем.

Answer 1

Я был немного удивлен, что split() работал так плохо в вашем коде, поэтому я посмотрел на него более внимательно и заметил, что вы вызываете list.remove() во внутреннем цикле.Также вы звоните split() дополнительное время для каждой строки.Избавьтесь от них, и решение, использующее split(), опережает руки регулярных выражений на более коротких строках и довольно близко уступает более длинным.

import timeit
import re

def splitit(input):
    res0 = input.split("|")
    res = []
    for element in res0:
        t = element.split("<>")
        if t != [element]:
            res0.remove(element)
            res.append(t)
    return (res0, res)

def split2(input):
    res0 = input.split("|")
    res1, res2 = [], []
    for r in res0:
        if "<>" in r:
            res2.append(r.split("<>"))
        else:
            res1.append(r)
    return res1, res2

def regexit(input):
    return re.split( "\||<>", input )

rSplitter = re.compile("\||<>")

def regexit2(input):
    return rSplitter.split(input)

print("split:", timeit.Timer("splitit('a|b|c|de|f<>ge<>ah')","from __main__ import splitit").timeit())
print("split2:", timeit.Timer("split2('a|b|c|de|f<>ge<>ah')","from __main__ import split2").timeit())
print("regex:", timeit.Timer("regexit('a|b|c|de|f<>ge<>ah')","from __main__ import regexit").timeit())
print("regex2:", timeit.Timer("regexit2('a|b|c|de|f<>ge<>ah')","from __main__ import regexit2").timeit())
print("split:", timeit.Timer("splitit('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import splitit").timeit())
print("split2:", timeit.Timer("split2('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import split2").timeit())
print("regex:", timeit.Timer("regexit('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import regexit").timeit())
print("regex2:", timeit.Timer("regexit2('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import regexit2").timeit())

Что дает следующий результат:

split: 1.8427431439631619
split2: 1.0897291360306554
regex: 1.6694280610536225
regex2: 1.2277749050408602
split: 14.356198082969058
split2: 8.009285948995966
regex: 9.526430513011292
regex2: 9.083608677960001

и, конечно, split2() дает нужные вам вложенные списки, тогда как решение для регулярных выражений этого не делает.

Редактирование: я обновил этот ответ, добавив в него предложение @ F1Rumors о том, что компиляция регулярного выражения улучшитсяспектакль.Это немного меняет дело, но Python кэширует скомпилированные регулярные выражения, поэтому экономия не так велика, как вы могли ожидать.Я думаю, что обычно это не стоит делать для скорости (хотя это может быть в некоторых случаях), но часто стоит сделать код более понятным.

Также я обновил код, чтобы он работал на Python 3.

Answer 2

Я не уверен, является ли это наиболее эффективным, но, безусловно, самый простой код, кажется, выглядит примерно так:

>>> input = "Item 1 | Item 2 | Item 3 <> Item 4 <> Item 5"
>>> re.split( "\||<>", input )
>>> ['Item 1 ', ' Item 2 ', ' Item 3 ', ' Item 4 ', ' Item 5']

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

Хотя, сказав, что я легко могу ошибаться, и единственный способ быть уверенным в этом, было бы рассчитать время.

Answer 3

Вызов split в несколько раз, вероятно, будет неэффективным, поскольку он может создать ненужные промежуточные строки.Использование предложенного вами регулярного выражения не сработает, поскольку группа захвата получит только последний элемент, а не каждый из них.Расщепление с использованием регулярных выражений, как предложил obmarg, кажется наилучшим путем, если предположить, что вы ищете "уплощенный" список.

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

items = re.split(r'\||<>', input)
offset = 0
for i in items:
    delimiter = '|' if input[offset+len(i)] == '|' else '<>'
    offset += len(i) + len(delimiter)
    # Do something with i, depending on whether | or <> was the delimiter

Наконец, если вы вообще не хотите создавать подстроки (используя только начало инапример, конечные индексы для экономии места), re.finditer может выполнить эту работу.Перебирайте разделители и делайте что-то с текстом между ними в зависимости от того, какой разделитель (| или <>) был найден.Это более сложная операция, поскольку вам придется обрабатывать множество угловых случаев, но, возможно, она того стоит в зависимости от ваших потребностей.

Обновление: для вашего конкретного случая, где формат вводаединообразно, решения обмарга - лучшие.Если необходимо, постобработайте результат, чтобы получить вложенный список:

split_result = re.split( "\||<>", input )
result = [split_result[0], split_result[1], [i for i in split_result[2:] if i]]

(последнее понимание списка должно обеспечить получение [] вместо [''], если послепоследний |)

Обновление 2: Прочитав обновленный вопрос, я наконец понял, чего вы пытаетесь достичь.Вот полный пример с использованием ранее предложенного фреймворка:

items = re.split(r'\||<>', input) # Split input in items
offset = 0
result = [] # The result: strings for regular itens, lists for <> separated ones
acc = None
for i in items:
    delimiter = '|' if offset+len(i) < len(input) and input[offset+len(i)] == '|' else '<>'
    offset += len(i) + len(delimiter)
    if delimiter == '<>': # Will always put the item in a list
        if acc is None:
            acc = [i] # Create one if doesn't exist
            result.append(acc)
        else:
            acc.append(i)
    else:
        if acc is not None: # If there was a list, put the last item in it
            acc.append(i)
        else:
            result.append(i) # Add the regular items
        acc = None # Clear the list, since what will come next is a regular item or a new list
print result

Протестировано на вашем примере, результат был:

['a', 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c','de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'aha'],
 'b', 'c', 'de', ['f', 'ge', 'ah']]

Answer 4

Если вы знаете, что <> не появится в другом месте строки, вы можете заменить '<>' на '|'с последующим одиночным разделением:

>>> input = "Item 1 | Item 2 | Item 3 <> Item 4 <> Item 5"
>>> input.replace("<>", "|").split("|")
['Item 1 ', ' Item 2 ', ' Item 3 ', ' Item 4 ', ' Item 5']

Это почти наверняка будет быстрее, чем выполнение нескольких разделений.Это может быть или не быть быстрее, чем с помощью re.split - время это ваш друг.

Редактировать : В моей системе с предоставленной вами строкой образца моя версия более чем в три раза быстрее, чем re.split:

>>> timeit input.replace("<>", "|").split("|")
1000000 loops, best of 3: 980 ns per loop
>>> import re
>>> timeit re.split(r"\||<>", input)
100000 loops, best of 3: 3.07 us per loop

(NB это используетipython, который имеет timeit как встроенную команду).

Answer 5

Вы можете использовать заменить .Сначала замените <> на |, а затем разделите на |.

def replace_way(input):
    return input.replace('<>','|').split('|')

Время Производительность:

import timeit
import re

def splitit(input):
    res0 = input.split("|")
    res = []
    for element in res0:
        t = element.split("<>")
        if t != [element]:
            res0.remove(element)
            res.append(t)
    return (res0, res)

def regexit(input):
    return re.split( "\||<>", input )

def replace_way(input):
    return input.replace('<>','|').split('|')


print "split:", timeit.Timer("splitit('a|b|c|de|f<>ge<>ah')","from __main__ import splitit").timeit()
print "regex:", timeit.Timer("regexit('a|b|c|de|f<>ge<>ah')","from __main__ import regexit").timeit()
print "replace:",timeit.Timer("replace_way('a|b|c|de|f<>ge<>ah')","from __main__ import replace_way").timeit()
print "split:", timeit.Timer("splitit('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import splitit").timeit()
print "regex:", timeit.Timer("regexit('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import regexit").timeit()
print "replace:",timeit.Timer("replace_way('a|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>aha|b|c|de|f<>ge<>ah')","from __main__ import replace_way").timeit()

Результаты на моей машине:

split: 11.8682055461
regex: 12.7430856814
replace: 2.54299265006
split: 79.2124379066
regex: 68.6917008003
replace: 10.944842347