큰 목록에서 색인 목록을 삭제하면

Question

간단한 질문처럼 보이지만 큰 파일에서 오는 거대한 문자열 인 색인의 쌍 사이에서 문자열 부분을 제거하는 방법 (실제로 예를 removeByIndex("Text aaa bbb", [(0,1), (5, 9)])를 들어 인덱스 쌍)

의 목록은 인덱스가 중복되지 ext bbb

을 반환합니다.

그것은 내용이

요약 (몇 메가 수백까지) 상대적으로 큰 있기 때문에 효율적이어야한다

: 그래서 솔루션은 인덱스 쌍의리스트를가는 수동으로 새 문자열을 만들고 참여 보인다 어떤 경우에 , 목록에없는 색인을 추가하십시오.

이 충분히 빨리 파이썬을 사용할 수 없습니다 만약 당신이 병목

s = s[:i] + s[j:] 

있다고 표시했습니다 때까지

Answer 1

(시작, 끝) 끝 부분에 포함되지 않습니다, 나는이 을 할 수 있습니다 (일부 성능 테스트를 실행할 수 있도록 내가 확장 가능한 테스트 케이스를 내장 한) :

N = 100000 
s = ''.join([ chr(c % 26 + ord('a')) for c in range(N) ]) 

l = [ (26*i,26*i+3) for i in range(N//26) ] 

l.sort(lambda x, y : cmp(x[0], y[0])) 

ns = [] 
i = 0 
for (start,end) in l: 
    ns.append(s[i:start]) 
    i = end 
ns.append(s[end:]) 
s = ''.join(ns) 

N = 100 000 000 (문자열 순서)로이 스크립트는 30 초 미만으로 실행됩니다. 느리지 만 견딜 수 있습니다. 물론 올바른 데이터 구조는이 특정 문제에 대한 로프입니다. 따라서 실행 횟수가 많은 경우 Python을 삭제하거나 Python에서 적절한 데이터 구조를 사용해야합니다.

Answer 2

성능에 대해 걱정하지 마십시오 - 또는 C. 당신은 더 나은 자료 구조를 선택해야합니다

Answer 3

당신은 그것을 필요 얼마나 빨리 수행하려고 :

In [9]: import string 

In [10]: import random 

In [11]: huge=''.join(random.choice(string.lowercase) for x in range(10000)) 

In [12]: len(huge) 
Out[12]: 10000 

In [13]: not_sohuge=huge[0:5000]+huge[6000:] 

In [14]: len(not_sohuge) 
Out[14]: 9000 

일부 타이밍 :

당신의 쌍 것을 가정하면 0,533,210

Answer 4

from itertools import izip 
def grouped(iterable, n): 
      return izip(*[iter(iterable)]*n) 
big_str="12345893483104921420948124" 
indexes = [2,4,5,7] 
# if needed, indexes = sorted(indexes) 
indexes.insert(0, 0) 
indexes.append(len(big_str)) 
sm_str="" 
for a,b in grouped(indexes,2): 
    sm_str=sm_str+big_str[a:b]