문자열의 모든 분할 목록을 Cythonize하십시오.

Question

문자열의 가능한 모든 분할을 생성하는 코드를 빠르게하려고합니다.

splits('foo') -> [('f', 'oo'), ('fo', 'o'), ('foo', '')] 

파이썬에서이 코드는 매우 간단합니다 : 사이 썬 또는 다른 수단을 통해이 속도를 높일 수있는 방법이

def splits(text): 
    return [(text[:i + 1], text[i + 1:]) 
      for i in range(len(text))] 

있습니까? 컨텍스트의 경우이 코드의 목적은 가장 높은 확률로 문자열의 분할을 찾는 것입니다.

Answer 1

이것은 Cython이 많은 도움을주는 종류의 문제가 아닙니다. 그것은 순수 파이썬과 거의 같은 속도로 끝나는 슬라이싱을 사용합니다 (즉 실제로는 꽤 좋음). timeit에서 100 문자 긴 바이트 문자열 (b'0'*100) 10000 반복 사용

내가 얻을 : 작성된

• 귀하의 코드 - 0.37s
• 사이 썬 작성하지만, 컴파일로 귀하의 코드 - 0.21s
• 코드가 cdef int i이고 Cython - 0.20으로 컴파일 된 코드 (재현 가능하게 작은 개선입니다. 더 긴 문자열의 경우 더 중요합니다)
• cdef int i 및 매개 변수 t yped는 bytes text-0.28s (즉, 보다 나쁜).

• Python C API를 직접 사용하면 속도가 빨라집니다 (아래 코드 참조) - 0.11s. 나는 대부분 Cython에서 (그러나 API 함수를 직접 호출하여) 편리하게하기로했지만, C에서 직접적으로 약간의 오류 검사를 통해 매우 유사한 코드를 작성할 수있다. 당신이 파이썬 2 나 유니 코드와 파이썬 3을 사용하고 있다면 바이트 객체 (예 : 대신)를 사용한다고 가정하고 파이썬 3 API를 위해 이것을 작성했습니다.

  from cpython cimport * 
  cdef extern from "Python.h": 
      # This isn't included in the cpython definitions 
      # using PyObject* rather than object lets us control refcounting 
      PyObject* Py_BuildValue(const char*,...) except NULL 
  
  def split(text): 
      cdef Py_ssize_t l,i 
      cdef char* s 
  
      # Cython automatically checks the return value and raises an error if 
      # these fail. This provides a type-check on text 
      PyBytes_AsStringAndSize(text,&s,&l) 
      output = PyList_New(l) 
  
      for i in range(l): 
       # PyList_SET_ITEM steals a reference 
       # the casting is necessary to ensure that Cython doesn't 
       # decref the result of Py_BuildValue 
       PyList_SET_ITEM(output,i, 
           <object>Py_BuildValue('y#y#',s,i+1,s+i+1,l-(i+1))) 
      return output 
  

• 당신이 다음 목록 output = [None]*len(text)을 미리 할당하고 수행하는 버전을 C API를 사용하여 모든 방법을 가고 싶어하지 않는 경우에 대한 루프 오히려 지능형리스트보다 소폭 더 효율적 원래보다 긴 버전 - 요약 0.18s

, 그냥 사이 썬에서 컴파일하는 것은 당신에게 알맞은 속도까지 (2 배보다 약간 이하) 및 i의 유형을 설정하는 것은 약간의 도움을 준다. 이것은 Cython으로 전통적으로 달성 할 수있는 모든 것입니다. 최고 속도를 얻으려면 기본적으로 Python C API를 직접 사용해야합니다. 그게 네가 네 배나 빠르다는 생각이 드네.