python - 通过迭代创建列表的最快方法

Question

我最近创建了一个脚本来创建 Dragon Curve，并设法对代码进行了相当多的优化。基本上，我首先生成一个规则列表，看起来像 [1, 1, -1, 1, 1, -1, -1]，其中 1 代表右转，-1代表左转。这对于 numpy 数组来说非常快。

有关龙曲线的更多信息:http://en.wikipedia.org/wiki/Dragon_curve

但是，现在我想使用这个列表在平面上创建一条曲线。基本上:选择一个点 (x, y) 和一个方向 (东)，走一步，然后根据我们循环遍历的列表中的当前元素向右或向左转 90 度。我们最后还采取了额外的步骤，但这对问题来说应该无关紧要。

假设我们的起始位置是 (100, 100)，我们开始向东走，列表是 [1, 1, -1]。然后我们应该得到 [(100, 100), (101, 100), (101, 101), (101, 101), (100, 101), (100, 102)]，它给了我们龙曲线的第二次迭代。

目前我正在使用以下代码生成点序列:

pos = [100, 100]
ang = math.pi/2
for i in dragon + [0]:
    pos.extend([pos[-2]+math.cos(ang), pos[-1]+math.sin(ang)])
    ang += i*math.pi/2

其中 dragon 是之前生成的列表，例如[1, 1, -1, 1, 1, -1, -1]。我在最后添加 [0] 以采取额外的步骤。对于 19 次迭代，我的脚本输出:

array of length 1048575 completed in 0.00567 seconds
dragon created in 2.82039 seconds
dragon drawn in 0.01462 seconds
image saved in 0.01229 seconds

我们可以清楚地看到上面的代码是最耗时的。有没有更快的方法从我们之前生成的列表中生成所有这些点？

Answer 1

由于sin 和cos 的结果是零、一或负一，并且是循环的，您可以查找它们，模四:

pos = [100, 100]
direction = 0

east_west_lookup = [0, -1, 0, 1]
north_south_lookup = [1, 0, -1, 0]

for i in dragon + [0]:
    east_west_step = east_west_lookup[direction % 4]
    north_south_step = north_south_lookup[direction % 4]
    pos.extend([pos[-2] + east_west_step,
                pos[-1] + north_south_step])
    direction += i