Hi, do you remember this one?
I've just made comparison of this code to Java, and Cython does, imo, well. The same edit distance loop is only, on average 25 percent faster on JVM.
Thanks.
Hi, do you remember this one?
I've just made comparison of this code to Java, and Cython does, imo, well. The same edit distance loop is only, on average 25 percent faster on JVM.
Thanks.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def edit_dist_dp(str1, str2, m, n):
store = [[0 for x in range(n + 1)] for x in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
store[i][j] = j
elif j == 0:
store[i][j] = i
elif str1[i - 1] == str2[j - 1]:
store[i][j] = store[i - 1][j - 1]
else:
store[i][j] = 1 + min(store[i][j - 1], store[i - 1][j],
store[i - 1][j - 1])
return store[m][n]
|
1
2
3
4
5
6
7
8
9
10
| import timeit
py = timeit.timeit('edit_distance.edit_dist_dp("asdsdhter", "dsfladrte", 9, 9)',
setup='import edit_distance', number=10000)
cy = timeit.timeit('edit_distance_cy.edit_dist_dp("asdsdhter", "dsfladrte", 9, 9)',
setup='import edit_distance_cy', number=10000)
print(f"Python and Cython times: {py}, Cython: {cy}")
print(f"Cython is {py/cy} x faster than Python")
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def edit_dist_dp(str1, str2, m, n):
store = [[0 for x in range(n + 1)] for x in range(m + 1)]
cdef int i, j
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
store[i][j] = j
elif j == 0:
store[i][j] = i
elif str1[i - 1] == str2[j - 1]:
store[i][j] = store[i - 1][j - 1]
else:
store[i][j] = 1 + min(store[i][j - 1], store[i - 1][j],
store[i - 1][j - 1])
return store[m][n]
|
1
2
| Python: 0.7150410660033231, Cython: 0.1197679779943428
Cython is 5.970219068381515 x faster than Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| cpdef int edit_dist_dp(str str1, str str2, int m, int n):
store = [[0 for x in range(n + 1)] for x in range(m + 1)]
cdef int i, j
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
store[i][j] = j
elif j == 0:
store[i][j] = i
elif str1[i - 1] == str2[j - 1]:
store[i][j] = store[i - 1][j - 1]
else:
store[i][j] = 1 + min(store[i][j - 1], store[i - 1][j],
store[i - 1][j - 1])
return store[m][n]
|
1
2
3
| (project_venv) $ python tests.py
Python: 0.7169225399993593, Cython: 0.07916731700242963
Cython is 9.055789271946113 x faster than Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | cpdef int edit_dist_dp(str str1, str str2, int m, int n): cdef int i, j, x, y cdef int store[50][50] for x in range(n + 1): for y in range(m + 1): store[x][y] = 0 for i in range(m + 1): for j in range(n + 1): if i == 0: store[i][j] = j elif j == 0: store[i][j] = i elif str1[i - 1] == str2[j - 1]: store[i][j] = store[i - 1][j - 1] else: store[i][j] = 1 + min(store[i][j - 1], store[i - 1][j], store[i - 1][j - 1]) return store[m][n] |
1 2 3 | (project_venv) $ python tests.py
Python: 0.7155497479980113, Cython: 0.027351742995961104
Cython is 26.16102922960606 x faster than Python
|
def fill_values(formula): """returns genexp with the all fillings with 0 and 1""" letters = "".join(set(re.findall("[A-Za-z]", formula))) for digits in product("10", repeat=len(letters)): table = str.maketrans(letters, "".join(digits)) yield formula.translate(table)
$ ./eval.py Propositional Logic Parser, press help, /h, -h or -usage for help > q ~ a Formula is satisfiable
public class SkewHeap <V extends Comparable<V>> { SkewNode root; public SkewHeap() { this.root = null; } class SkewNode { SkewNode leftChild, rightChild; V data; public SkewNode(V _data, SkewNode _left, SkewNode _right) { this.data = _data; this.leftChild = _left; this.rightChild = _right; } } }
And here the crucial merge:SkewNode merge(SkewNode left, SkewNode right) { if (null == left) return right; if (null == right) return left; if (left.data.compareTo(right.data) < 0 || left.data.compareTo(right.data) == 0) { return new SkewNode(left.data, merge(right, left.rightChild), left.leftChild); } else return new SkewNode(right.data, merge(left, right.rightChild), right.leftChild); }
SkewHeap listToHeap(List list) { SkewHeap o = new SkewHeap(); for (int i = 0; i < list.size(); i++) o.insert((Comparable) list.get(i)); return o; } List heapToList(SkewHeap tree) { List ll = new ArrayList(); try { while (true) { ll.add(tree.pop()); } } catch (IndexOutOfBoundsException e) { return ll; } } List sort(List list) { return heapToList(listToHeap(list)); }