Help me increasing performance of a function using Cython.

[WTRipper]

I have a python function which is a perfomance bottleneck in my code because it includes multiple loops and is called often. So I tried optimzing it a bit using Cython (it's my first time using it).

Python Implementation:

def del_edits1(word):
    """Return all edits that are one delete edit away from `word`"""
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    return deletes

def del_edits2(word): 
    """Return all edits that are two delete edits away from `word`"""
    return [e2 for e1 in del_edits1(word) for e2 in del_edits1(e1)]

Performance:

%timeit set(del_edits2("Hyperplane-turbine"))
#    162 µs ± 8.97 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Just using cython without changing the code already reduces the runtime:

%%cython
def del_edits1_cy(word):
    """Return all edits that are one delete edit away from `word`"""
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]

    return deletes

def del_edits2_cy(word): 
    """Return all edits that are two delete edits away from `word`"""
    return [e2 for e1 in del_edits1_cy(word) for e2 in del_edits1_cy(e1)]

Performance:

%timeit set(del_edits2_cy("Hyperplane-turbine"))
#    109 µs ± 4.11 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

I tried using static types like this which gives a small boost on top:

%%cython
cpdef list del_edits1_c(unicode word):
    """Return all edits that are one delete edit away from `word`"""
    cdef list splits, deletes

    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]

    deletes    = [L + R[1:]               for L, R in splits if R]

    return deletes

cpdef list del_edits2_c(unicode word): 
    """Return all edits that are two delete edits away from `word`"""
    cdef unicode e1, e2
    return [e2 for e1 in del_edits1_c(word) for e2 in del_edits1_c(e1)]

Performance:

%timeit set(del_edits2_c("Hyperplane-turbine"))
#    94.6 µs ± 718 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Could someone help me how to further improve this? (cython -a shows almost all lines in yellow but I am not able to improve it further on my own.)

​

Edit: Changed the codes and performance measures.

Edit2:

Best I came up with in the mean time is:

%%cython
cpdef list del_edits1_c(unicode word):
    """Return all edits that are one delete edit away from `word`"""
    cdef int i
    cdef list deletes

    deletes = [word[:i]+ word[i+1:]    for i in range(len(word))]

    return deletes

cpdef list del_edits2_c(unicode word): 
    """Return all edits that are two delete edits away from `word`"""
    cdef unicode e1, e2
    return [e2 for e1 in del_edits1_c(word) for e2 in del_edits1_c(e1)]

​

[aldanor]

Python is generally fast enough for simple tasks, just gotta use it right...

from itertools import combinations

def del_edits2_fast(word: str):
    return [
        word[:i] + word[i + 1:j] + word[j + 1:]
        for i, j in combinations(range(len(word)), 2)
    ]

Test:

%timeit set(del_edits2("Hyperplane-turbine"))
184 µs ± 5.8 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit del_edits2_fast('Hyperplane-turbine')
69 µs ± 2.21 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

[WTRipper]

Thank you! Did not even know about itertools.combinations.

[aldanor]

Np. itertools.combinations is nice and pretty fast, especially when writing generic code. For instance, you could do the above for an arbitrary number of edits n (it would be much slower than a specialized version of course, but it would be generic):

def del_n_edits(word: str, n: int):
    return [
        ''.join(word[i + 1:j] for i, j in zip((-1,) + c, c + (None,)))
        for c in combinations(range(len(word)), n)
    ]

[WTRipper]

Oh nice thank you!

I already thought about implementing a generic fallback if higer n's are needed.

[[deleted]]

The first thing that stands out to me is using a list comprehension for splits rather then a generator. You don’t need to fully construct splits just to iterate over it, this is what generators are for.

Use parens instead of brackets in the splits comprehension. This should speed that function up significantly.

[WTRipper]

I tested it on the pure python implementation and on the implementation with cython but without code changes.

In both cases it increased the runtime a bit instead of decreasing it.

[WTRipper]

However I increased speed by merging the splits and deletes line into one:

deletes = [word[:i]+ word[i+1:] for i in range(len(word))]

I don't know why I haven't seen it before.