forループの長い文字列でのPython文字列の連結

Question

私はすでに文字列が不変であるためにforループで文字列連結を行うべきではないことを数回聞いたことがあるので、連結を新しい文字列インスタンスとして計算し、識別子。 Oで実行（N^2）

letters = "" 
for c in document: 
    if c.isalpha(): 
     letters += c 

グッド：Oで実行（nは結果にn個の文字のであれば、時間の複雑さはO（N^2）

悪いだろう私が読んだと同時に）

document = "" 
temp = [] 
for c in document: 
    if c.isalpha(): 
     temp.append(c) 
letters = "".join(temp) 

そのトンの

「いくつかの後に実装Pythonインタープリタは、このようなコードを線形時間で完成させるための最適化を開発しました。 "

最初の解決法も問題ありませんか？それは最新のPythonビルドにある最適化ですか？

Answer 1

まず、最も読みやすいコードを書く必要があります。実行時に問題がある場合にのみ、あなたは、最適化を考える必要があります。

letters = "".join(c for c in document if c.isalpha()) 

を現在のCPythonの実装ではjoinは「+」よりも高速です。

>>> def test(): 
... s = "" 
... for x in range(1000): 
...  s += 'x' 
... 
>>> timeit.timeit(test) 
157.9563412159987 
>>> def test(): 
... s = [] 
... for x in range(1000): 
...  s.append('x') 
... s = ''.join(s) 
... 
>>> timeit.timeit(test) 
147.74276081599965 

Answer 2

strは不変ですが、listはありません。 （ここで、複雑で話しているので）

my_list = [] 
for c in my_string: 
    if c.isalpha(): 
     my_list.append(c) 

しかし.append()は時間の面で非常に高価な操作です：それは次のようになり達成するためのより良い方法。チェック：HERE私は別の答えを求めて比較しました。より良い方法は次のようになります。

my_list = [c for c in my_string if c.isalpha()] 

今、あなたのようにstringにこのlistを変換することがあります。キーは一部の実装である

''.join(my_list) 

Answer 3

。すべてではない。 Pythonのすべての実装でコードが高速に実行されるようにしたい場合は、str.joinを使用してください。ドキュメントのサイズに応じて、異なるアプローチが高速になります。しかし、"".join(...)は非常にpythonicであり、人々はより迅速にあなたの意図を理解します。あなたが持っていない限り、ロットの小さなの書類はstr.joinと付いています。

しかし、str.joinと+=の両方で10倍の速度向上を得るには、str.translateを使用してください。この解決法は個々の文字を削除することに特有のものです。

from string import digits 
translation_table = str.maketrans("", "", digits) 
# first two args about translating characters, third is for removing characters 
letters = document.translate(translation_table) 

この速度向上の理由は、pythonがドキュメント内の各文字に対して新しい文字列を作成する必要があるためです。 str.translateはこれを行う必要がないため、はるかに高速です。