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

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

或许尝试在列表中预分配 space，然后完全删除 extend 调用。像这样（未经测试）：

pos = [100] * len(dragon)*2 + 4
ang = math.pi / 2
for idx, i in enumerate(dragon + [0]):
    start = idx*2
    pos[start+2] = pos[start]+math.cos(ang)
    pos[start+3] = pos[start+1]+math.sin(ang)
    ang += i * math.pi / 2

Answer 2

由于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

Answer 3

这里有一种使用字典查找的方式，我觉得用一个tuple来表示你的位置，用一个list来表示整个路径比较合适。

我没有你的结果，所以请确保 face_dict 设置正确。

dragon = [1, 1, -1, 1, 1, -1, -1]
# format: old-direction -> (add-to-x, add-to-y, new-direction)
# using a list would be faster, but I don't have time to think about it :)
face_dict = {
    "EAST": {-1: (1, 0, "NORTH"), 1: (1, 0, "SOUTH")},
    "SOUTH": {-1: (0, -1, "EAST"), 1: (0, -1, "WEST")},
    "WEST": {-1: (1, 0, "SOUTH"), 1: (1, 0, "NORTH")},
    "NORTH": {-1: (0, 1, "WEST"), 1: (0, 1, "EAST")}
}

# indicate a position using a tuple, a tuple represents a single location
# while a list is suitable to represent a path
pos = (100, 100)
def make_path(directions, start_pos):
    # create empty path with starting position
    path = [None] * len(dragon)
    path[0] = start_pos

    # this is the current state, which is stored in the list after every step.
    current_pos = start_pos
    # this is where we're facing right now
    face = "EAST"
    # each iteration fills a single step in the semi-empty path
    for index, direction in enumerate(directions):
        move = face_dict[face][direction]
        current_pos = (current_pos[0] + move[0], current_pos[1] + move[1])
        face = move[2]
        path[index] = current_pos
    return path

注意：结合可以优化每次迭代的查找。

Answer 4

一个小的改进，但在我的系统上节省了 10-15% 的时间，就是不用每次都计算 math.pi/2。它不如 Peter Wood 的解决方案快，但如果您决定将 dragon 列表打开为 0、1 和 -1 以外的值，它可能会有用。

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

Answer 5

Numpy 也可以做到这一点，非常高效！使用 Peter Wood 的答案中的查找 table 我们可以写出 x 方向：

x0 = 100
directions = np.cumsum(2 - dragon) % 4
dx = np.take([0, -1, 0, 1], directions)
x = np.cumsum(np.r_[x0, dx])

2 - dragon是取模前去掉负值

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

Fastest way of creating a list through iteration

python

list

loops

optimization

numpy