for 루프 긴 문자열에서 파이썬 문자열 연결

Question

나는 문자열이 불변이므로 문자열 연결을해서는 안되므로 문자열 연결을 새로운 문자열 인스턴스로 계산 한 다음 다시 할당해야한다고 이미 몇 번 들었습니다. 식별자. O에서 실행 (N^2)

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

좋은 : O에 실행 (N 결과는 n 개의 문자가 그래서 경우 시간 복잡도는 (N^2)

나쁜 O 것 내가 읽은 동시에)

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

그 t의

"일부 나중에 구현 그는 파이썬 인터프리터가 이러한 코드를 선형 시간 내에 완료 할 수 있도록 최적화를 개발했습니다. "

그래서 첫 번째 해결책도 괜찮을 것입니다. 그것은 최신 파이썬 빌드에있는 최적화입니까?

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

지금이 list로 string에 변환 할 수

는

''.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이 작업을 수행 할 필요가 없으므로 훨씬 빠릅니다.