Pythonで文字列を分割する最も効率的な方法

Most efficient way to split strings in Python


質問 written by malexmave @2012-03-07 15:52:22Z

: 24 : 5 : 23

現在のPythonプロジェクトでは、着信パッケージを処理するために多くの文字列分割が必要になります。 かなり遅いシステムで実行するので、これを実行する最も効率的な方法は何だろうと思いました。 文字列は次のようにフォーマットされます。

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

説明:この特定の例は、最初の2つのアイテムがタイトルと日付であり、アイテム3からアイテム5が招待されるリストからのものです(それらの数は0からnまでのいずれかで、nは数字です)サーバー上の登録ユーザーの)。

私が見るものから、私は次のオプションがあります:

  1. split()繰り返し使用する
  2. 正規表現と正規表現関数を使用する
  3. まだ考えていない他のPython関数(おそらくいくつかあります)

ソリューション1には|分割が含まれます| この例では、結果リストの最後の要素を<>で分割しますが、ソリューション2はおそらく次のような正規表現になります。

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

さて、この正規表現は恐ろしい、私はそれを自分で見ることができます。 また、テストされていません。 しかし、あなたはアイデアを得る。

今、私はa)時間が最小であり、b)理想的には最小限のメモリを使用する方法を探しています。 2つのうち1つだけが可能な場合は、より短い時間を希望します。 理想的な解決策は、より多くの項目が分離された文字列でも機能します| および<>が完全に欠落している文字列。 少なくとも正規表現ベースのソリューションはそれを行います

私の理解では、 split()はより多くのメモリを使用します(基本的に2つの結果リストを取得します; 1つは|で分割され、2つ目は<>で分割されるため)。 RegExのパフォーマンスを判断するため。 split()は、異なる数のItemが存在し、2番目のセパレーターがない場合、正規表現よりも動的ではありません。 それでも、私はPythonが正規表現なしでこれをより良くできるという印象を揺るがすことはできません、それが私が尋ねている理由です

いくつかのメモ:

  • はい、両方のソリューションのベンチマークを行うことはできますが、私は一般的なPythonとここでどのように動作するかについて何かを学ぼうとしています。これら2つをベンチマークしても、私が逃したPython関数はまだわかりません。
  • はい、このレベルでの最適化は、高性能のものにのみ本当に必要ですが、私が言ったように、私はPythonについてのことを学ぼうとしています。
  • 加えて:元の質問で、私は完全に、私が分離された部分を区別できるようにする必要があるということを忘れていました| セパレーター<>持つパーツから、 re.split(\||<>,input) (@obmargによって提案されたre.split(\||<>,input)によって生成された単純なフラットリストはうまく機能しません。 この基準に適合するソリューションは大歓迎です。

質問を要約すると、どのソリューションがどのような理由で最も効率的なソリューションになるかです。

複数のリクエストがあるため、 split() -solutionと@obmargによる最初の提案正規表現、および@mgibsonbrと@duncanによるソリューションでtimeitを実行しました。

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

現時点では、@ duncanによるsplit2は、長さに関係なく他のすべてのアルゴリズムに勝っているようです(少なくともこの限定されたデータセットでは)。また、@ mgibsonbrのソリューションにはパフォーマンスの問題があるようです(申し訳ありませんが、ありがとうございます。に関係なくソリューション)。

みなさん、ご意見ありがとうございます。

コメント 1

timeittimeitを使用して自分で確認してください。それは簡単です。私の賭けはstr.splitます。

written by @2012-03-07 14:04:18Z

コメント 2

長い文字列の場合、 re方が高速になると思います。ただし、確実にベンチマークを行う必要があります。

written by Kien Truong @2012-03-07 14:11:35Z

コメント 3

これはIOバウンドだと思います。私の最初の推測は、あらゆるタイプの分割が、ディスクまたはネットワークから受け取る入力よりも高速になると言うことです。

written by スティーブンランバルスキー @2012-03-07 14:30:57Z

コメント 4

「招待された人がいない」場合、文字列は"Item 1 | Item 2"または"Item 1 | Item 2 |"

written by スティーブンランバルスキー @2012-03-07 14:33:18Z

コメント 5

@StevenRumbalski 2番目のオプション。

written by malexmave @2012-03-07 14:36:54Z

回答 1 written by Duncan @2018-09-25 08:47:23Z
18

コードでsplit()パフォーマンスが非常に悪かったので少し驚いたので、もう少し詳しく調べて、内側のループでlist.remove()を呼び出していることに気付きました。 また、各文字列でsplit()を余分に呼び出しています。 それらを取り除くと、 split()を使用したソリューションは、短い文字列で正規表現に勝ち、長い文字列ではかなり近い2番目になります。

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

次の結果が得られます。

Which gives the following result:

もちろん、 split2()は、必要なネストされたリストを提供しますが、正規表現ソリューションは提供しません。

編集:この回答を更新して、正規表現をコンパイルするとパフォーマンスが向上するという@ F1Rumorsの提案を含めました。 わずかな違いはありますが、Pythonはコンパイルされた正規表現をキャッシュするため、保存は期待したほど多くありません。 私は通常、速度のためにそれを行う価値はないと思います(場合によっては可能ですが)が、多くの場合、コードを明確にする価値があります。

また、Python 3で実行されるようにコードを更新しました。

コメント 1

良いキャッチ。テスト分割機能を実装するとき、それについてまったく考えませんでした。あなたがそれを指摘したので、リストから削除することは「高価」であり、コンテンツに関係なくすべてを分割することは言うまでもありません(javaのようなcontains探していましたcontains 、Pythonはこれとは異なるようです) 。どうもありがとう。

written by malexmave @2012-03-07 15:42:28Z

コメント 2

正規表現を「コンパイル」する、つまりrSplitter = re.compile("\||<>")のような行を追加すると、さらに改善できます。分割コードを定義します: def regexit2(input): return rSplitter.split(input) YYMV、しかし私にとって、このコンパイルされたバージョンは、元の正規表現バージョンよりも著しく高速であり、すべてのテストで快適に高速であると考えました。

written by F1Rumors @2018-09-24 18:15:38Z

コメント 3

@ F1Rumors、ありがとう。Pythonはコンパイル済みの正規表現をキャッシュするので、違いはそれほど大きくありませんが、サンプルコードを更新しました。

written by ダンカン @2018-09-25 08:50:23Z

回答 2 written by obmarg @2012-03-07 14:11:31Z
10

それが最も効率的かどうかはわかりませんが、確かに最も簡単なコードは次のようなものです。

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

最初のスプリットからのすべての文字列出力で2番目のスプリット操作を実行する必要があるため、プレーンな古いスプリット(入力データに応じて)よりも効率的である可能性がかなりあると思いますメモリまたは時間のいずれかで効率的であると思われます。

私は簡単に間違っている可能性があると言っていましたが、確実にするための唯一の方法はそれを計ることです。

コメント 1

アルゴリズムをありがとう。ネストされたリストとして2番目の部分(項目3-5)が他の部分と区別し、処理を容易にするために必要であることを忘れていました。しかし、私はそれを忘れていたので、あなたの解決策がそれをしないということをあなたに対して本当に保持することはできません

written by ; @2012-03-07 14:44:21Z

コメント 2

@malexmave:リストを作成したら簡単です。alist = re.split( "\||<>", input); result = [alist[0], alist[1], alist[2:]]alist = re.split( "\||<>", input); result = [alist[0], alist[1], alist[2:]]出来上がり。入れ子。

written by スティーブンランバルスキー @2012-03-07 15:24:00Z

コメント 3

おかげで、リスト内の位置を固定していれば間違いなく機能します。さらに下のコメントで説明した問題はどうですか?簡単な解決策はありますか?または、@ mgibsonbrが提案したものよりも簡単なものが少なくとも1つありますか?がんばってくれてありがとう!

written by malexmave @2012-03-07 15:31:37Z

回答 3 written by mgibsonbr @2012-03-07 15:22:02Z
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が仕事をするかもしれません。 区切り文字を反復処理し、見つかった区切り文字( |または<> )に応じて、それらの間のテキストに何かを行います。 多くのコーナーケースを処理する必要があるため、より複雑な操作ですが、ニーズに応じて価値がある場合があります。

更新:入力形式が統一されている特定のケースでは、obmargのソリューションが最適です。 必要な場合は、結果を後処理して、ネストされたリストを作成します。

Update: for your particular case, where the input format is uniform, obmarg's solutions is the best one. If you must, post-process the result to have a nested list:

(最後のリストの理解は、最後の|後にアイテムがない場合、 ['']代わりに[''] []を取得することを保証することです)

更新2:更新された質問を読んだ後、私は最終的にあなたが達成しようとしていることを理解しました。 前述のフレームワークを使用した完全な例を次に示します。

(that last list comprehension is to ensure you'll get [] instead of [''] if there are no items after the last |)

あなたの例でそれをテストした結果は:

Update 2: After reading the updated question, I finally understood what you're trying to achieve. Here's the full example, using the framework suggested earlier:

コメント 1

ご意見ありがとうございます。私は現在、あなたのfor Blockの機能を理解しようとしています。私が理解しているように、それは|オフセットを計算します-seperatedブロックが終了し、 <> -seperatedブロックが始まりますか?

written by malexmave @2012-03-07 14:47:26Z

コメント 2

そうではありません...各反復で、 offsetは次のアイテムの場所です。offset+len(i)は、次の区切り文字(または文字列の末尾)です。入力文字列を再度スキャンすることなく、区切り文字をすばやく見つけることができるように使用しました。ただし、文字列が通常の形式である場合、実際には必要ありません。更新された回答を参照してください。

written by mgibsonbr @2012-03-07 14:58:37Z

コメント 3

更新していただきありがとうございます。|によって区切られた可変数のアイテムで同じ結果を得るための同様に単純な方法はないと思います|<>始まる前に、正しいですか?item 1 | item 2 <> Item 3 | Item 4ような形式は言うまでもありませんitem 1 | item 2 <> Item 3 | Item 4item 1 | item 2 <> Item 3 | Item 4item 1 | item 2 <> Item 3 | Item 4は、もちろんクライアント側のフォーマット機能を変更することで回避できます。

written by malexmave @2012-03-07 15:08:00Z

コメント 4

更新された回答をご覧ください。ループを使用して提案された解決策は、まさにそれを解決することでした。デリミタのタイプに応じて、いくつかのネストが必要です。

written by mgibsonbr @2012-03-07 15:23:49Z

コメント 5

参考:新しいアルゴリズムにはパフォーマンスの問題があるようです(ベンチマークについてはOPをご覧ください)。

written by malexmave @2012-03-07 15:52:56Z

回答 4 written by Dave Kirby @2012-03-07 15:25:47Z
2

<>が文字列の他の場所に表示されないことがわかっている場合は、「<>」を「|」に置き換えることができます。 単一の分割が続きます:

>>> 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を使用するよりも高速である場合と高速でない場合があります。timeitはあなたの友達です。

編集 :あなたのバージョンを提供したサンプル文字列を持つ私のシステムでは、re.splitよりも3倍以上高速です:

Edit: On my system with the sample string you supplied my version is more than three times faster than re.split:

(NBこれは、組み込みコマンドとしてtimeitを持つipythonを使用しています)。

コメント 1

アイデアをありがとう。ただし、これにより、結果のサブストリングのいずれが|ではなく<>区切られているかを判別する方法のないフラットリストが作成されます|、OPに編集したコードの要件です。それでも、ネストされたリストを必要としない場合は良い考えです。

written by malexmave @2012-03-07 15:28:01Z

回答 5 written by Akavall @2012-03-07 15:37:17Z
1

replaceを使用できます。 最初に<>|置き換えます 、そして|

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

時間パフォーマンス:

Time Performance:

私のマシンでの結果:

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()
コメント 1

提案ありがとう。ただし、「内部」項目( |ではなく<>区切られた項目)のネストされたリストを返さないという問題があります。

written by malexmave @2012-03-07 15:40:03Z