文字列のすべての分割のリストをCythonize

Question

文字列のすべての可能な分割を生成するコードを高速化しようとしています。

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

Pythonで、このためのコードは非常に簡単です：

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

はcythonまたはいくつかの他の手段を介してこれをスピードアップする方法はありますか？コンテキストの場合、このコードの目的は、最も高い確率で文字列の分割を見つけることです。

Answer 1

これは、Cythonが大いに役立つ傾向がある問題の種類ではありません。これはスライスを使用しています。これは、純粋なPythonとほぼ同じ速度です（実際にはかなり良い）。 timeitで100文字の長いバイト文字列（b'0'*100）と10000回の反復を使用して

は私が取得：書かれたよう

• あなたのコード - 0.37s
• Cythonで書かれたが、コンパイルとしてのあなたのコード - 0.21s
• あなたのコードはcdef int iで、Cython - 0.20sでコンパイルされています（これは再現性のある小さな改良です）。
• cdef int iとパラメータt y = 0.228s（すなわち、0.232s）。悪い）。

• Python C APIを直接使用すると（以下のコードを参照）、0.11秒の速度が得られます。私は便宜上これを主にCythonで（しかし、API関数を自分自身で呼び出すことを）選択しましたが、少し手作業によるエラーチェックをすることでC言語で非常によく似たコードを直接書くことができました。あなたがバイトオブジェクト（PyStringの代わりにPyBytesの代わりに）を使用していると仮定して、Python 3 APIのためにこれを書いています。したがって、Python 2またはUnicodeとPython 3を使用している場合は少し変更する必要があります。

  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 
  

• あなたはCのAPIを使用してすべての道を行くにしたくない場合は、リストoutput = [None]*len(text)を事前に割り当ておよびループのためではなく、リスト内包したバージョンはオリジナルよりもわずかに、より効率的ですバージョン - 要約する0.18s

、ちょうどCythonでそれをコンパイルすると、あなたにまともな速度を断念（2倍より少し小さい）とiの種類を設定することはほとんどないのに役立ちます。これは、従来通り、Cythonで本当に達成できるすべてです。フルスピードを得るには、基本的にPython C APIを直接使用する必要があります。それはあなたが私がかなりまともなと思う4倍のスピードアップの下で少し得る。