Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
305 views
in Technique[技术] by (71.8m points)

python - Cythonize list of all splits of a string

I'm trying to speed up a piece of code that generates all possible splits of a string.

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

The code for this in python is very simple:

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

Is there a way to speed this up via cython or some other means? For context, the greater purpose of this code is to find the split of a string with the highest probability.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

This isn't the sort of problem that Cython tends to help with much. It's using slicing, which ends up largely the same speed as pure Python (i.e. actually pretty good).

Using a 100 character long byte string (b'0'*100) and 10000 iterations in timeit I get:

  • Your code as written - 0.37s
  • Your code as written but compiled in Cython - 0.21s
  • Your code with the line cdef int i and compiled in Cython - 0.20s (this is reproducably a small improvement. It's more significant with longer strings)
  • Your cdef int i and the parameter typed to bytes text - 0.28s (i.e. worse).
  • Best speed is got by using the Python C API directly (see code below) - 0.11s. I've chosen to do this mostly in Cython (but calling the API functions myself) for convenience, but you could write very similar code in C directly with a little more manual error checking. I've written this for the Python 3 API assuming you're using bytes objects (i.e. PyBytes instead of PyString) so if you're using Python 2, or Unicode and Python 3 you'll have to change it a little.

    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
    
  • If you don't want to go all the way with using the C API then a version that preallocates the list output = [None]*len(text) and does a for-loop rather than a list comprehension is marginally more efficient than your original version - 0.18s

In summary, just compiling it in Cython gives you a decent speed up (a bit less than 2x) and setting the type of i helps a little. This is all you can really achieve with Cython conventionally. To get full speed you basically need to resort to using the Python C API directly. That gets you a little under a 4x speed up which I think is pretty decent.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...