2013-07-20 173 views
0

我目前正在編寫一個python程序,其中涉及大量使用索引迷宮,如結構。我現在已經設置了列表,其中包含單獨的嵌套列表,每個列表代表迷宮中的一行,我將它編入像迷宮[0] [1]中的第一行和第二列的網格迷宮的位置。如果我將迷宮轉換爲單個列表,同時記錄行的長度並相應地移動列表,我的程序運行速度會更快嗎?如果我使用迷宮[(0 * row_length)+1]而不是迷宮[0] [1],我會獲得多少速度提升?索引嵌套列表

+0

也許給出你正在談論的數據結構的摘錄。 – dilbert

+0

我的數據結構是代表牆壁,空白空間,播放器或可移動框的字符索引。這裏是一個小例子:[['X','X','X','X','X'], ['X','','','','X'], ['X','X','O','','X'], ['X','@','','','X'], ['X','X ','X','X','X']] –

+0

如果是這樣,我傾向於同意給定的答案。 – dilbert

回答

2

不要打擾。這幾乎肯定不是你的瓶頸,並且不值得頭疼管理索引計算和行長度變量。

時序數據:

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

扁平列表贏得當行長度是內聯的常數,但它失去了當行長度是一個全局變量。如果您試圖通過拼湊清單來獲得優勢,那麼您將浪費大量時間來管理索引,除非您非常仔細地進行操作,否則它可能會運行得更慢。不要打擾。

0

爲了進一步擴大,通過運行以下:

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數組(儘管您可能必須創建一個數字到符號映射)。