python - 索引嵌套列表

Question

我目前正在编写一个 python 程序，该程序涉及大量使用索引迷宫，如结构。我目前将列表设置为包含单独的嵌套列表，每个嵌套列表代表迷宫的一条线，我像 Maze[0][1] 一样为第一行和第二列上的网格迷宫的位置编制索引。如果我将迷宫转换为单个列表，同时跟踪一行的长度并相应地在列表中移动，我的程序会运行得更快吗？如果我使用 Maze[(0*row_length)+1] 而不是 Maze[0][1]，我将获得多少速度提升？

Answer 1

不要打扰。这几乎肯定不是您的瓶颈，而且管理索引计算和行长度变量不值得头疼。

时序数据：

>>> timeit("a[1][2]", setup="a = [[0]*5 for _ in xrange(4)]")
0.09207810811146055
>>> timeit("a[1*5+2]", setup="a = [0]*5*4")
0.06518904043262097
>>> timeit("a[1*row_length+2]", setup="a = [0]*5*4; row_length=5")
0.11411290029380439

当行长是内联常量时，扁平化列表获胜，但当行长是全局变量时，它会丢失。如果你试图通过扁平化你的列表来获得优势，你将浪费大量时间来管理索引，除非你非常小心，否则它甚至可能运行得更慢。不要打扰。

Answer 2

要进一步扩展，请运行以下命令：

from timeit import timeit

class slice_list(list):
    def __getitem__(self, iindex):
        return list.__getslice__(self, (iindex * 5), ((iindex + 1) * 5))

nested_list = \
[
    ["X", "X", "X", "X", "X"],
    ["X", " ", " ", " ", "X"],
    ["X", "X", "O", " ", "X"],
    ["X", "@", " ", " ", "X"],
    ["X", "X", "X", "X", "X"]
]

flat_list = \
[
    "X", "X", "X", "X", "X",
    "X", " ", " ", " ", "X",
    "X", "X", "O", " ", "X",
    "X", "@", " ", " ", "X",
    "X", "X", "X", "X", "X"
]

s_list = slice_list(flat_list)

nested_setup_str = \
'''
from __main__ import nested_list

test = nested_list
'''

flat_setup_str = \
'''
from __main__ import flat_list

test = flat_list
'''

slice_setup_str = \
'''
from __main__ import s_list

test = s_list
'''

print "Flat:", timeit("test[1 * 5 + 2]", setup=flat_setup_str)
print "Nested:", timeit("test[1][2]", setup=nested_setup_str)
print "Sliced:", timeit("test[1][2]", setup=slice_setup_str)

我有：

Flat:   0.1130175887
Nested: 0.182156054306
Sliced: 1.92594956774

所以无论你从一个平面列表中获得什么收益，它都会被试图将它视为一个嵌套列表来破坏（在上面的例子中使用类似于 slice_list 的东西）。

如果性能是一个问题，也许可以考虑一个 numpy 数组（尽管您可能必须创建一个数字到符号的映射）。