Cách hiệu quả nhất để tách các chuỗi trong Python

Question

Dự án Python hiện tại của tôi sẽ yêu cầu nhiều phân tách chuỗi để xử lý các gói đến. Vì tôi sẽ chạy nó trên một hệ thống khá chậm, tôi đã tự hỏi cách hiệu quả nhất để thực hiện điều này là gì. Các chuỗi sẽ được định dạng một cái gì đó như thế này:

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

Giải thích: ví dụ cụ thể này sẽ đến từ một danh sách nơi hai mục đầu tiên là một tiêu đề và một ngày, trong khi khoản 3 đến khoản 5 sẽ được mời người (The số lượng có thể là từ 0 đến n, trong đó n là số lượng người dùng đã đăng ký trên máy chủ).

Từ những gì tôi thấy, tôi có các tùy chọn sau:

1. nhiều lần sử dụng split()
2. Sử dụng một biểu thức chính quy và Regex chức năng
3. Một số chức năng Python khác tôi đã không nghĩ về chưa (Có có lẽ một số)

Giải pháp 1 sẽ bao gồm chia tách tại | và sau đó chia phần tử cuối cùng của danh sách kết quả tại <> ví dụ này, trong khi giải pháp 2 có lẽ sẽ cho kết quả trong một biểu thức chính quy như:

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

Okay, RegEx này là khủng khiếp, tôi có thể thấy rằng bản thân mình. Nó cũng chưa được kiểm tra. Nhưng bạn hiểu ý rồi đấy.

Bây giờ, tôi đang tìm cách mà a) mất ít thời gian nhất và b) lý tưởng sử dụng lượng bộ nhớ ít nhất. Nếu chỉ có một trong hai là có thể, tôi sẽ thích ít thời gian hơn. Giải pháp lý tưởng cũng sẽ hoạt động đối với các chuỗi có nhiều mục hơn được phân tách bằng | và các chuỗi hoàn toàn thiếu <>. Ít nhất là Giải pháp biểu dựa trên thường xuyên sẽ làm điều đó

hiểu biết của tôi sẽ là split() sẽ sử dụng nhiều bộ nhớ hơn (vì bạn về cơ bản có được hai danh sách kết quả, một trong những chia tại | và điều thứ hai để tách tại <>), nhưng Tôi không biết đủ về việc thực hiện các biểu thức chính quy của Pythons để đánh giá RegEx sẽ thực hiện như thế nào. split() cũng kém năng động hơn so với cụm từ thông dụng nếu nó hiển thị với số lượng mục khác nhau và sự vắng mặt của seperator thứ hai. Tuy nhiên, tôi không thể lắc ấn tượng rằng trăn có thể làm điều này tốt hơn mà không biểu thức thông thường, đó là lý do tại sao tôi yêu cầu

Một số lưu ý:

• Vâng, tôi có thể chỉ benchmark cả hai giải pháp, nhưng tôi cố gắng tìm hiểu một cái gì đó về python nói chung và cách nó hoạt động ở đây, và nếu tôi chỉ là điểm chuẩn hai, tôi vẫn không biết những gì python chức năng tôi đã bỏ qua.
• Có, tối ưu hóa ở cấp độ này chỉ thực sự cần thiết cho các công cụ hiệu suất cao, nhưng như tôi đã nói, tôi đang cố gắng tìm hiểu mọi thứ về python.
• Addition: trong câu hỏi ban đầu, tôi hoàn toàn quên đề cập đến mà tôi cần để có thể phân biệt các bộ phận được tách bởi | từ các bộ phận với seperator <>, do đó, một danh sách đơn giản bằng phẳng như được tạo ra bởi re.split(\||<>,input) (theo đề xuất của @obmarg) sẽ không hoạt động tốt. Các giải pháp phù hợp tiêu chí này được nhiều người đánh giá cao.

Để tổng hợp câu hỏi: Giải pháp nào là giải pháp hiệu quả nhất, vì lý do gì.

Do nhiều yêu cầu, tôi đã chạy một số timeit trên split() -solution và đề xuất biểu thức chính quy đầu tiên của @obmarg, cũng như các giải pháp bởi @mgibsonbr và @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() 

Kết quả :

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

tại thời điểm này, có vẻ như split2 bởi @duncan nhịp đập tất cả các thuật toán khác, bất kể chiều dài (với bộ dữ liệu hạn chế này ít nhất), và nó cũng giống như @ mgibsonbr của giải pháp có một số vấn đề hiệu suất (Xin lỗi 'bout rằng, b ut cảm ơn cho giải pháp bất kể).

Cảm ơn bạn đã nhập, mọi người.

Answer 1

Tôi hơi ngạc nhiên khi split() hoạt động quá tệ trong mã của bạn nên tôi đã xem xét kỹ hơn và nhận thấy rằng bạn đang gọi list.remove() trong vòng lặp bên trong. Ngoài ra, bạn đang gọi số split() một lần nữa trên mỗi chuỗi. Loại bỏ những người và một giải pháp bằng cách sử dụng split() đánh bại các tay regex xuống trên các chuỗi ngắn hơn và đến một thứ hai khá gần trên một dài hơn.

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) 


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

Mà cho kết quả sau:

split: 6.14933066757 
split2: 4.09465555192 
regex: 5.10777759588 
split: 47.0092413098 
split2: 26.9300592585 
regex: 25.9168630604 

và tất nhiên split2() đưa ra danh sách lồng nhau mà bạn muốn trong khi các giải pháp regex thì không.

Answer 2

Tôi không chắc chắn nếu đó là hiệu quả nhất, nhưng chắc chắn là dễ nhất để mã có vẻ là một cái gì đó như thế này:

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

tôi sẽ nghĩ rằng có một cơ hội hợp lý của nó là hiệu quả hơn so với một đồng bằng phân chia cũ (tùy thuộc vào dữ liệu đầu vào) vì bạn cần thực hiện thao tác tách thứ hai trên mọi chuỗi đầu ra từ lần tách đầu tiên, điều này dường như không hiệu quả cho bộ nhớ hoặc thời gian.

Mặc dù đã nói rằng tôi có thể dễ dàng bị sai, và cách duy nhất để chắc chắn sẽ là thời gian.

Answer 3

Chia tách cuộc gọi nhiều lần có khả năng là không chính xác, bởi vì nó có thể tạo ra các chuỗi trung gian không cần thiết. Sử dụng regex như bạn đã đề xuất sẽ không hoạt động, vì nhóm chụp sẽ chỉ nhận được mục cuối cùng chứ không phải từng mục. Tách bằng cách sử dụng một regex, như obmarg được đề xuất, có vẻ là tuyến đường tốt nhất, giả sử một danh sách "phẳng" là những gì bạn đang tìm kiếm.

Nếu bạn không muốn có một danh sách dẹt, bạn có thể chia nhỏ sử dụng một regex đầu tiên và sau đó lặp qua các kết quả, kiểm tra đầu vào ban đầu để xem những delimiter được sử dụng:

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 

Cuối cùng, nếu bạn không muốn các chất nền tạo ra ở tất cả (chỉ sử dụng các chỉ mục bắt đầu và kết thúc để tiết kiệm không gian, ví dụ), re.finditer có thể thực hiện công việc. Lặp lại các dấu phân cách và làm điều gì đó với văn bản giữa chúng tùy thuộc vào dấu phân cách (| hoặc <>) đã được tìm thấy. Đó là một hoạt động phức tạp hơn, vì bạn sẽ phải xử lý nhiều trường hợp góc, nhưng có thể đáng giá tùy thuộc vào nhu cầu của bạn.

Cập nhật: cho trường hợp cụ thể của bạn, nơi định dạng đầu vào là thống nhất, giải pháp của bạn là tốt nhất. Nếu bạn phải, sau quá trình kết quả để có một danh sách lồng nhau:

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

(mà danh sách cuối cùng hiểu là để đảm bảo bạn sẽ nhận được [] thay vì [''] nếu không có mục sau khi người cuối cùng |)

Cập nhật 2: Sau khi đọc câu hỏi được cập nhật, cuối cùng tôi đã hiểu những gì bạn đang cố gắng đạt được.Dưới đây là toàn bộ ví dụ, sử dụng khuôn khổ đề xuất trước đó:

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 

Tested nó với ví dụ của bạn, kết quả là:

['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

Nếu bạn biết rằng <> sẽ không xuất hiện ở những nơi khác trong chuỗi sau đó bạn có thể thay thế '<>' bằng '|' theo sau là một phần tách:

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

Điều này gần như chắc chắn sẽ nhanh hơn làm nhiều lần chia nhỏ. Nó có thể hoặc không thể nhanh hơn sử dụng re.split - timeit là bạn của bạn.

Sửa: Trên hệ thống của tôi với chuỗi mẫu mà bạn cung cấp phiên bản của tôi là nhanh hơn ba lần so với 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 này đang sử dụng ipython, trong đó có timeit như một được xây dựng trong lệnh).

Answer 5

Bạn có thể sử dụng thay thế. Trước tiên, hãy thay thế <> bằng | và sau đó chia cho |.

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

Thời gian thực hiện:

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

Kết quả trên máy tính của tôi:

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