긴 문자열로 모든 문자열 조각을 만드는 데 시간이 오래 걸립니다. 이상 O (N^2) (N 길이의 N 개의 문자열을 생성하므로 원본 데이터를 소스에서 가져와 메모리에 복사해야하므로 전체 성능이 저하되고 정렬이 적절하지 않습니다. 메모리 요구 사항은 말할 것도 없습니다! 실제로 만들지 않고 - 대신 실제로 문자열을 자르는
, 다음 생각은 결과 문자열 이 비교 얼마나의 순서로 순환 문자열을 만드는 데 사용하는 i 값을 주문하는 것입니다. 이것은 다소 까다로울 수밖에 없습니다. (은/제거 잘못 여기에 몇 가지 물건을 편집 한. @TimPeters '대답을 참조하십시오를)
내가 여기에 찍은 접근 방식은 표준 라이브러리 무시하는 것입니다 - 그것은 어렵게 (생각을를 불가능) 해당 문자열을 '요구시'와 비교하고 내 자신의 정렬을 수행합니다. 알고리즘의 자연 선택은 기수 정렬입니다. 왜냐하면 우리는 한 번에 한 문자 씩 문자열을 고려해야하기 때문입니다.
먼저 설정하십시오. 3.2 버전의 코드를 작성 중이므로 시즌을 맛보아야합니다. (특히, 3.3 이상에서는 yield from을 이용할 수있었습니다.'(우리를 물론
def radix_sort(values, key, step=0):
if len(values) < 2:
for value in values:
yield value
return
bins = {}
for value in values:
bins.setdefault(key(value, step), []).append(value)
for k in sorted(bins.keys()):
for r in radix_sort(bins[k], key, step + 1):
yield r
, 우리는 범용을 할 필요가 없습니다
from random import choice
from timeit import timeit
from functools import partial
내가 이런 범용 기수 정렬 기능을 썼다) 나는 다음과 같은 수입을 사용하고 있습니다 bins '는 하나의 문자로만 레이블 될 수 있으며 은
바이트)의 시퀀스에 알고리즘을 적용한다는 의미입니다.)),하지만 해를 끼치 지 않습니다. 재사용할만한 게 있겠지, 그렇지? 어쨌든 아이디어는 간단합니다. 기본 케이스를 처리 한 다음, 키 함수의 결과에 따라 각 요소를 "빈"에 놓은 다음 정렬 된 빈 순서로 빈에서 값을 가져 와서 재귀 적으로 정렬합니다 bin의 내용.
key(value, n)은 n의 "기수"를 value으로 제공해야합니다. 문자열을 직접 비교하는 간단한 경우에는 lambda v, n: return v[n]과 같이 간단 할 수 있습니다. 그러나 여기서 생각해 보면, 그 시점에있는 문자열의 데이터 (주기적으로 간주 됨)에 따라 인덱스를 문자열과 비교하는 것이 좋습니다. 그럼 키를 정의 할 수 있습니다 :
def bw_key(text, value, step):
return text[(value + step) % len(text)]
지금 올바른 결과를 얻는 데 트릭은 우리가 개념적으로 우리가 실제로 생성되지 않은 문자열의 마지막 문자를 결합하고 기억하는 것입니다. 인덱스
n을 사용하여 만든 가상 문자열을 고려하면 마지막 문자는
n - 1입니다. 왜냐하면 우리가 랩 어라운드 방식을 사용하기 때문입니다. 잠시 생각하면
n == 0;을 사용할 때 여전히 작동합니다. [그러나 앞으로 감쌀 때 문자열 인덱스를 인바운드로 유지해야합니다. 따라서 키 함수의 모듈러스 연산을 유지해야합니다.
이 키는 text에 전달되어야하는 일반 키 기능입니다. 비교를 위해 value을 변환 할 때 참조 할 것입니다. 그게 functools.partial이 나온 곳입니다. lambda으로 주위를 어지럽 힐 수도 있지만, 이것은 틀림없이 깨끗합니다.
어쨌든, 지금 우리가 쉽게 실제 키를 사용하여 변환을 작성할 수 있습니다
def burroughs_wheeler_custom(text):
return ''.join(text[i - 1] for i in radix_sort(range(len(text)), partial(bw_key, text)))
# Notice I've dropped the square brackets; this means I'm passing a generator
# expression to `join` instead of a list comprehension. In general, this is
# a little slower, but uses less memory. And the underlying code uses lazy
# evaluation heavily, so :)
니스와 꽤 있습니다. 어떻게되는지 보자, 그렇지? 우리는에 대해 비교하는 표준이 필요합니다
def burroughs_wheeler_standard(text):
return ''.join([i[-1] for i in sorted([text[i:] + text[:i] for i in range(len(text))])])
그리고 타이밍 루틴 :
def test(n):
data = ''.join(choice('abcdefghijklmnopqrstuvwxyz') for i in range(n)) + '$'
custom = partial(burroughs_wheeler_custom, data)
standard = partial(burroughs_wheeler_standard, data)
assert custom() == standard()
trials = 1000000 // n
custom_time = timeit(custom, number=trials)
standard_time = timeit(standard, number=trials)
print("custom: {} standard: {}".format(custom_time, standard_time))
공지 사항 내가했던 수학은 반비례의 길이와 관련, trials의 수를 결정하는 test 문자열. 이것은 합리적으로 좁은 범위에서 테스트에 사용 된 총 시간을 유지해야합니다 - 맞습니까? .,
>>> imp.reload(burroughs_wheeler)
<module 'burroughs_wheeler' from 'burroughs_wheeler.py'>
>>> burroughs_wheeler.test(100)
custom: 4.7095093091438684 standard: 0.9819262643716229
>>> burroughs_wheeler.test(1000)
custom: 5.532266880287807 standard: 2.1733253807396977
>>> burroughs_wheeler.test(10000)
custom: 5.954826800612864 standard: 42.50686064849015
워 :))
은의 그것 (* 드럼 롤의 *) 어떻게하는지 보자 (잘못된 물론, 이후 우리는 standard 알고리즘은 최소 O (N^2입니다 설립) 그것은 무서운 점프의 약간이다. 어쨌든, 당신이 볼 수 있듯이, 새로운 접근법은 짧은 문자열에 오버 헤드 톤을 추가하지만 문자열 정렬 대신 병목 현상이 될 실제 정렬을 가능하게합니다.:)
한 가지 간단한 방법 문자열 및 오프셋 및 구현 비교 그것이 인 것처럼 소요 프록시 클래스를 작성하는 것입니다 회전 된 문자열. 하지만 작은 문자열에 대해서는 많은 인터프리터 오버 헤드를 도입 할 것입니다. – user2357112
성능에 많은 관심이 있다면 원시 코드를 원시 컴퓨터 코드로 컴파일하는 언어를 사용하십시오. – xis
@XiaogeSu 여기서 문제는 언어가 아니라 문제 해결을위한 접근 방법입니다. –