Cython의 문자열 조작

Question

매우 CPU 집약적 인 문자열 조작을 수행하는 코드가 있으며 성능을 향상시킬 방법을 찾고있었습니다.

(편집 :. 나는 긴 일반적인 문자열을 찾는 더 나은 C의 상태 머신과 같이 표현 될 수있는 정규 표현식을 많이 실행처럼, HTML에서 물건을 주석을 제거 같은 물건을하고 있어요)

내가 현재 코드에 관한 많은 정보를들은 후에 코드 일부를 Cython으로 이식하는 방법을 모색 중입니다. 그러나 Cython의 주요 초점은 수치 계산이며 문자열로 작업하는 것은 간신히 문서화 된 것 같습니다.

유니 코드 또한 큰 문제 일 수 있습니다.

내 질문은 :

1. 난 문자열 물건 사이 썬 귀찮게해야 하는가? 누구든지 cython에서 이러한 유형의 처리 경험이 있으며 공유 할 수 있습니까?
2. Cython 문서에서 뭔가 빠졌습니까? 누구든지 Cython에서 문자열로 작업하는 방법에 대한 자습서/참조/설명서를 알고 있습니까?

Answer 1

나는 'profile it'답변을 표결에 넣었지만 이것을 추가하고 싶었습니다. 가능한 한 최상의 최적화는 원하는 작업을 수행하기 위해 Python 표준 라이브러리 나 내장 함수를 사용하는 것입니다. 이들은 일반적으로 C 언어로 구현되며 Cython으로 작성된 확장을 비롯하여 모든 확장 기능과 동등한 성능을 제공합니다. 알고리즘이 파이썬에서 문자 루프 (character by character loop)를 수행하고 있다면, 가능하다면 그 알고리즘은 먼저 갈 것입니다.

그러나 내장형 또는 다른 기존 표준 라이브러리와 관련하여 다시 작업 할 수없는 알고리즘이있는 경우 Cython은 합리적인 접근 방식 인 것 같습니다. 의사 코드를 네이티브 코드로 컴파일하기 만하면 다른 연산처럼 문자열 연산에 적합합니다. 하지만 저는 단지 관용적 인 파이썬 코드를 넘겨 주면 Cython을 사용하면 커다란 이점이 있다는 것을 확신하지 못합니다. C에서 각 알고리즘의 일부 또는 전부를 다시 작성하여 저수준 연산이 Python/C 장벽을 통해 변수를 지속적으로 변환하지 못하는 경우 최대 이점이 제공됩니다.

마지막으로 유니 코드 - '큰 문제'가 될 수 있지만 사용 방법은 지정하지 않았 음을 암시했습니다. Cython은 유니 코드를 처리하는 관련 Python API를 호출하는 C 코드를 생성하므로 기능이 제한적이지는 않습니다. 그러나 C에서 유니 코드 문자열을 처리하는 것은 쉬운 일이 아니므로 더 나은 성능을 위해 C로 알고리즘을 다시 작성하는 것은 그만한 가치가 없습니다. 고전적인 문자열 알고리즘은 문자 당 저장 단위가 1 개인 전통적인 '문자열'이 아닌 많은 유니 코드 인코딩에서 작동하지 않습니다.

Answer 2

이것은 매우 흥미로운 문제입니다. Cython은 파이썬과 C 데이터 유형을 통합하는 도구입니다. 문자열을 다루는 데 도움이되는 기능을 제공하지는 않습니다. 아마도 Numpy의 특정 기능에 대한 요구가 많지 않기 때문일 것입니다.

그렇다면 Cython을 사용하여 설명하는 문제 유형을 처리하도록 설계된 기존 C/C++ 라이브러리와 인터페이스 할 수 있습니다. HTML/XML을 처리하려면 예를 들어 libxml을 조사해야 할 수 있습니다. 그러나 (물론) ready-made python bindings 이미 사용할 수 있습니다. 저는 HTML 처리를 위해 lxml을 광범위하게 사용했으며 필요한 모든 작업을 수행했으며 은입니다. 또한 유니 코드를 잘 처리합니다.

당신의 경우에는 lxml과 사용자 정의 C 함수의 조합이 가장 좋을 것이라고 생각합니다. 예를 들어, C에서 가장 긴 하위 문자열을 찾는 빠른 기능을 "쉽게"만들 수 있습니다. 바이트 수준에서 수행 할 수 있습니다 (C의 문자열은 char *, 바이트 배열 임). 그럼 파이썬으로 다시 매핑 할 수 있습니다 (Cython은 당신을 위해 진짜로 쉽게 만들 것입니다) 그리고 유니 코드 추상적 인 천국에서 계속 :). 확실히 사소한 것은 아니지만 앱의 성능이 앱의 성능에 의존한다면 노력할 가치가 있습니다.

그렇다면 C/C++에서 유니 코드로 작업하는 데 좋은 방법 (물론 간단하지는 않지만)이 있습니다. Evan Jones의 This article은 노력이 필요한지 판단하는 데 도움이 될 수 있습니다. 그냥 완전성에 대한

Answer 3

, 내가 그것이 나오는 것에 따라 단지 (일부)

C.

에서 문자열 조작 코드를 작성한다하고 결국, 그것의 ridiculously easy는 파이썬에 C의 확장을 쓰기 시작합니다. 유니 코드 문자열은 파이썬 빌드에 따라 int 또는 short 인 Py_UNICODE의 배열입니다.

나는 C에

s = re.sub(r' +', ' ', s) 

과 같은 코드를 변환하는 X20 개선을 얻었다. 더 복잡한 정규 표현식을 사용하여 비슷한 개선점을 얻었지만 C 코드가 매우 복잡해졌습니다.

전체적으로 쓰루풋이 20 % 증가했습니다. 나는 지금 더 많은 것을 다시 쓸 것을 찾고있다. ...

Answer 4

"어리석게 쉬운"매우 상대적인 용어이다. "시작하기"는 바로 그 것입니다. C에서 강력한 확장 기능을 작성하려면 참조 계산, 메모리 할당/해제 및 오류 처리와 같은 사항에주의를 기울여야합니다. Cython이 당신을 위해 그 일을 많이합니다.

Cython의 비 유니 코드 문자열은 Python str 개체이거나 C의 char 배열입니다. 필요한 Cython 관련 설명서는 무엇이라고 생각하십니까?

직접 시도해 보시기 바랍니다. 하지만 그렇게하기 전에 비효율에 대한 Python 코드를 검사하는 것이 좋습니다. 때로는 큰 스피드 업을 어리석게 쉽게 얻을 수 있습니다.

re.sub(' +', ' ', s) # one space in pattern 

를 사용하여 공백 문자의 런 압축 예컨대

는 ... 런이 1의 길이를 갖는 것으로 추정 흔한 경우가 공백 스페이스를 교체 할 것을 의미한다. 모든 실행에 길이 1이 있으면 입력 문자열의 참조 횟수를 쉽게 늘리거나 줄이거 나 늘릴 수 없을 때 새로운 대체 문자열을 만들어 다시 전달합니다.

re.sub(' +', ' ', s) # two spaces in pattern 

정확히 같은 결과를 생산하고 보자 ... 빠르게 실행할 수 있습니다 :

모든 길이 1을 실행 : 그것은에서 3.4 배의 속도를 실행합니다. 표시되지 않음 : 입력 문자열이 길면 길수록 좋습니다.

\python26\python -mtimeit -s"s='now is the winter of our discontent'; import re; x = re.compile(' +').sub" "x(' ', s)" 
100000 loops, best of 3: 8.26 usec per loop 

\python26\python -mtimeit -s"s='now is the winter of our discontent'; import re; x = re.compile(' +').sub" "x(' ', s)" 
100000 loops, best of 3: 2.41 usec per loop 

하나의 런 길이가 2 인 경우 속도 비는 2.5입니다. 모든 런이 길이 2 인 경우 속도 비는 1.2입니다. 모든 것을 고려한 결과, 1 회의 키 입력에 대한 나쁜 수익이 아닙니다.

Answer 5

사실 Cython은 CPython의 Py_UNICODE 유형을 지원하므로 예를 들어 유니 코드 문자열을 직접 반복하거나 C 속도로 문자를 비교할 수 있습니다. 나는 최근 사이 썬에 도입 봤는데 중요한 프로젝트에서 사용하기에 큰 C 및 C++ 라이브러리를 감싸는 큰 성공을 있었다

http://docs.cython.org/src/tutorial/strings.html

Answer 6

참조하십시오. 생성 된 파이썬 확장 중 일부는 실제로 프로덕션 환경에서 이미 실행 중입니다. 먼저, Cython은 분명히 좋은 선택입니다.

Cython에서 모든 코드를 실제로 작성할지 또는 C/C++ 코드를 작성하고 Cython에서 해당 함수에 액세스 할 수있게할지 여부를 고려해야합니다. 분명히 이것은 부분적으로 C 및/또는 C++로 사용자의 안락 수준에 달려 있습니다.

문자열을 사용하여 작업 할 때 char*이 아닌 C++의 std::string을 사용하면 훨씬 간단하게 만들 수 있습니다. from libcpp.string cimport string을 사용하면 매우 쉽게 cython으로 가져올 수 있습니다. 변수는 표준 cython을 통해 문자열 유형을 사용하여 선언 할 수 있습니다. cdef string ...