为嵌套列表建立索引

Question

我目前正在写一个python程序，其中涉及大量使用索引迷宫，如结构。目前我将列表设置为包含单独的嵌套列表，每个列表代表迷宫的一行，我像这样为网格迷宫的位置建立索引，迷宫位于第一行和第二列。如果我将迷宫转换成单个列表，同时跟踪一行的长度，并相应地在列表中移动，我的程序会运行得更快吗？如果我使用迷宫(0*row_length)+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数组(尽管您可能需要创建一个数字到符号的映射)。