加速您的线搜索算法的另一种方法是预先计算每一行的起始点,然后应用昂贵的逻辑来计算每个点的线。
我对逻辑进行了有限的观察(因为您没有提供完整的线路识别逻辑),它可以计算快速向量化代码中的起点。
在能够实现快速矢量化代码这样的事情的第一步是要能够找出哪些点在一条线上,但高于其直接点不在:在
import numpy
# using the array that was provided in the question
a = """0 x1 0 0 y1 0 z1
0 0 x2 0 y2 0 z2
0 0 x3 0 0 y3 z3
0 0 x4 0 0 y4 z4
0 x5 0 0 0 y5 z5
0 0 0 0 y6 0 0"""
array = numpy.array([int(v.strip()) if v.strip().isdigit() else i for i, v in enumerate(a.split(' '))]).reshape(6, 7)
结果它看起来像一个数组:
>>> print repr(array)
array([[ 0, 1, 0, 0, 4, 0, 6],
[ 0, 0 9, 0, 11, 0, 13],
[ 0, 0, 16, 0, 0, 19, 20],
[ 0, 0, 23, 0, 0, 26, 27],
[ 0, 29, 0, 0, 0, 33, 34],
[ 0, 0, 0, 0, 39, 0, 0]])
从这里,我们可以做一些numpy的滚动:
>>> print `numpy.roll(array, 1, axis=0)`
array([[ 0, 0, 0, 0, 39, 0, 0],
[ 0, 1, 0, 0, 4, 0, 6],
[ 0, 0, 9, 0, 11, 0, 13],
[ 0, 0, 16, 0, 0, 19, 20],
[ 0, 0, 23, 0, 0, 26, 27],
[ 0, 29, 0, 0, 0, 33, 34]])
可结合给我们的垂直起动点线:
>>> potential_start_points = (array != 0) & (numpy.roll(array, 1, axis=0) == 0)
>>> # include the top row points, as they are certainly start points
>>> potential_start_points[0, :] = (array != 0)[0, :]
>>> print `potential_start_points`
array([[False, True, False, False, True, False, True],
[False, False, True, False, False, False, False],
[False, False, False, False, False, True, False],
[False, False, False, False, False, False, False],
[False, True, False, False, False, False, False],
[False, False, False, False, True, False, False]], dtype=bool)
从这里,可以细化矢量化逻辑,挑对角线等等,但我会被诱惑遍历每个的Trues并应用更复杂的基于索引的逻辑。
xs, ys = numpy.where(potential_start_points)
for x, y in zip(xs, ys):
# do more complex logic here ...
毕竟,这个问题,在这种情况下,现在是从迭代6X7减少= 42号到迭代只是7.
我不认为这个问题是特别清楚。你有一个零和字符串的列表,如'x0'或他们是1吗?这条线是什么意思?线搜索算法的规则是什么?他们可以对角移动吗? – pelson 2012-07-18 20:51:22
@pelson'x1','x2','x3','y1','y2'...都是不同的值。我写了'x1'和'y1'来区分这些值属于不同的行。我添加一个链接到这个数字来说清楚。我从包含零和数值的数组中绘制图形,如原始文章中所示。我需要沿着每条线找到最大值(每行中的值不以降序排列)。我无法在这里上传图片,所以我附上了一个链接到这个图:i.imgur.com/W9O0I.png – user1535026 2012-07-19 12:36:43
在你提供的例子数组中,你会如何判断z3在y行上不存在?是不是你想要某种优先级而不是那些对角线移动的优先级(以行为单位)?线条可以水平移动吗? – pelson 2012-07-19 12:50:49