python - 문자열에서 고유 한 "단어"를 찾는 가장 빠른 방법

Question

길이가 2 * 2 * 1092-1 = 4367 인 문자열 s가 있습니다. 다음은 처음 15 자입니다.

0 0 0 1 0 1 0 0 

나는 커플로서의 캐릭터에 관심이 있습니다. 처음 15 개 문자 예 :

00, 01, 01, 00 

내 캐릭터는 0과 1 포함하고 가능한 커플 따라서 다음과 같습니다

00, 01, 10 and 11 

내가 내 문자열에 존재하는 모든 커플의 정렬되지 않은 목록을 얻으려면 ; 즉 처음 15 자의 경우 :

00 and 01 

파이썬에서 가장 빠른 방법은 무엇입니까? 이러한 실행 시간 나는 각 방법의 10,000 시간 이상 반복하고있어

def method1(s): 
    l_couples = [s[4*i:4*i+3] for i in range(1092)] 
    set_couples = set(l_couples) 

def method2(s): 
    set_couples = [] 
    for i in range(1092): 
     couple = s[4*i:4*i+3] 
     if not couple in set_couples: 
      set_couples += [couple] 

def method3(s): 
    set_couples = set() 
    for i in range(1092): 
     couple = s[4*i:4*i+3] 
     set_couples |= set([couple]) 

:

방법 항목 : 3.94s

방법 2 : 5.64s

의 Method3 아래 3 가지 방법 (파이썬 3)이다 : 10.7s

전체 문자열은 4367 자로 구성됩니다.

0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

고맙습니다.

Answer 1

정말로 필요한 경우 이러한 낮은 수준에서만 최적화하십시오!

이렇게 적은 양의 데이터를 마이크로 최적화해야하는 이유는 없습니다. ~ 4000 자의 문자열은 거의 없습니다.

도널드 크 누스는 "우리는 사소한 효율성 시간의 약 97 %를 잊어한다 : 조기 최적화는 모든 악의 뿌리입니다"가장 읽기 쉽고 comprehensable이 경우에 따라서

솔루션이 최고 일 것입니다.

그러나 건설로, 여기 내 제안이다 :

def method5(s): 
    return {s[x:x+3] for x in xrange(0, len(s), 4)} 

%timeit method5(s) 
10000 loops, best of 3: 123 us per loop 

여기에 다른 사용자가 방법 :

def method4(s): 
    return {s[4*i:4*i + 3] for i in range(len(s)/4)} 

%timeit method4(s) 
10000 loops, best of 3: 176 us per loop 

과 다른 방법에 대한 벤치 마크 :

%timeit method1(s) 
10000 loops, best of 3: 184 us per loop 

%timeit method2(s) 
10000 loops, best of 3: 185 us per loop 

%timeit method3(s) 
1000 loops, best of 3: 513 us per loop 

Answer 2

배열과 같은 문자열을 통한 무차별 강제 색인 대신에, split과 같은 Python의 기능에 대해 배우고, 및 ITER 및 우편 번호 :

def uniqueCouples(s): 
    # get all the characters in a list, splitting on whitespace 
    items = source.split() 

    # create an iterator over this list 
    it = iter(items) 

    # using zip(it,it) will create a sequence of tuples, taking the generated list 
    # in pairs; then use ''.join() to merge the tuples into couples; then find the 
    # set of unique pairs 
    return set(''.join(couple) for couple in zip(it,it)) 

편집 : 추가 성능 수치

하드웨어의 차이를 정상화하기 위해, 나는 또한 참고 method5 반환 (michaelkrisper의 method5 내 시스템에 @ 달리고, 189에게 우리를 얻었다 요청시 '01'및 '00'이 아닌 '0 1'및 '0 0').

게시 된 위의 솔루션을 테스트하면 약 370 us의 시간이 주어집니다. 그런 다음 모든 압축 된 튜플에 ''.join을 호출한다는 사실을 깨달았습니다. 세트가 모든 복제본을 제거한 후에 감소 된 수의 항목 대신에 - 이제는 가입이 느리다면 신경 쓰지 만, 몇 번만 호출 할 것입니다. . 반환 명세서 변경 :

return [''.join(cpl) for cpl in set(zip(it,it))] 

은 209us로 시간을 단축합니다.

split()이 우리의 속도를 늦추고 있으므로 islice을 사용하여 입력 소스 문자열을 따라 슬라이스 반복기를 만드는 것으로 바뀔 것입니다. (물론 이것은 더 취약합니다. 값 사이에 여분의 공백과 같은 입력 소스 형식은 우리 코드를 깨뜨리는 반면, 분할 사용은 조금 느리지 만 더 견고합니다. 변경된 :

from itertools import islice 
def uniqueCouples(s): 
    it = islice(s, 0, None, 2) 
    return [''.join(cpl) for cpl in set(zip(it,it))] 

시간이 이제 197us로 떨어집니다. 목록 이해력을 변경하여 map(''.join, set(zip(it,it)))을 사용하면 약 194 us로 줄어 듭니다.

그래서 당신이 나누고 결합하는 정보가 어디서 느린 지 잘 모르겠습니다. 제 제출물의 비효율은 세트를 사용하여 복제본을 제거하기 전에 조인하는 것이 었습니다.