索引嵌套列表

Question

我目前正在编写一个python程序，其中涉及大量使用索引迷宫，如结构。我现在已经设置了列表，其中包含单独的嵌套列表，每个列表代表迷宫中的一行，我将它编入像迷宫[0] [1]中的第一行和第二列的网格迷宫的位置。如果我将迷宫转换为单个列表，同时记录行的长度并相应地移动列表，我的程序运行速度会更快吗？如果我使用迷宫[（0 * row_length）+1]而不是迷宫[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数组（尽管您可能必须创建一个数字到符号映射）。