使用cython在图形上进行框覆盖 [英] Perform the box covering on a graph using cython
问题描述
我编写了一个python脚本来执行对图形的覆盖,但是在小图形(100个节点)上运行它需要一分钟以上的时间。
今天有人推荐cython来提高效率,所以我遵循本指南来适应我的代码。
I wrote a python script to perform the box covering on a graph but it takes more than a minute when I run it on small graphs (100 nodes). Today someone recommend cython to improve its efficiency so I follow this guide to adadpt the code that I had.
运行python代码的结果如下:
Running the python code the results where:
In [6]: %timeit test.test()
1000 loops, best of 3: 1.88 ms per loop
遵循指南后,结果为:
In [7]: %timeit c_test.test()
1000 loops, best of 3: 1.05 ms per loop
性能更好,但我相信可以改进很多。鉴于我今天刚刚遇到cython,我想问你如何改善此代码:
The performance was better but I am sure that it is a lot that can be improved. Given that I just meet cython today, I want to ask you how can I improve this code:
import random as rnd
import numpy as np
cimport cython
cimport numpy as np
DTYPE = np.int
ctypedef np.int_t DTYPE_t
def choose_color(not_valid_colors, valid_colors):
possible_values = list(valid_colors - not_valid_colors)
if possible_values:
return rnd.choice(possible_values)
else:
return max(valid_colors.union(not_valid_colors)) + 1
@cython.boundscheck(False)
cdef np.ndarray[DTYPE_t, ndim=2] greedy_coloring(np.ndarray[DTYPE_t, ndim=2] distances, int num_nodes, int diameter):
cdef int i, lb, j
cdef np.ndarray[DTYPE_t, ndim=2] c = np.empty((num_nodes+1, diameter+2), dtype=DTYPE)
c.fill(-1)
# Matrix C will not use the 0 column and 0 row to
# let the algorithm look very similar to the paper
# pseudo-code
nodes = list(range(1, num_nodes+1))
rnd.shuffle(nodes)
c[nodes[0], :] = 0
# Algorithm
for i in nodes[1:]:
for lb in range(2, diameter+1):
not_valid_colors = set()
valid_colors = set()
for j in nodes[:i]:
if distances[i-1, j-1] >= lb:
not_valid_colors.add(c[j, lb])
else:
valid_colors.add(c[j, lb])
c[i, lb] = choose_color(not_valid_colors, valid_colors)
return c
def test():
distances = np.matrix('0 3 2 4 1 1; \
3 0 1 1 3 2; \
2 1 0 2 2 1; \
4 1 2 0 4 3; \
1 3 2 4 0 1; \
1 2 1 3 1 0')
c = greedy_coloring(distances, 6, 4)
推荐答案
在Cython中,随着在Cython函数中删除更多Python调用,您将获得更快的速度。
In Cython, you will get faster speed as you remove more Python calls inside your Cython functions.
例如,浏览代码,您正在<的嵌套循环中调用 choose_color()
code> greedy_coloring()。以及在函数内部定义的变量也应键入。由于将反复调用它,因此会带来很多开销。
For example, skimming through your code, you are making calls to choose_color()
inside the nested loop in greedy_coloring()
. That should be typed as well, along with variables defined inside the function. Since it will be called repeatedly, it will bring a lot of overhead.
您可以将 cython
与 -a
选项(例如 cython -a file.pyx
)来生成带注释的html文件,该文件可以直观地显示您的哪一部分代码正在进行Python调用(黄线)。
You can use cython
with -a
option (e.g., cython -a file.pyx
) to generate an annotated html file which shows visually which part of your code is making Python calls (yellow lines). This will help you a lot in terms of improving your Cython code.
很抱歉,由于缺少具体的指针,希望对您有所帮助。
I'm sorry for lack of specific pointers - hope this is helpful.
这篇关于使用cython在图形上进行框覆盖的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!