使用列表來檢查數組索引

Question

在python中，我正在生成列表來表示狀態（例如，狀態可能是[1,3,2,2,5]）。

每個元素的值可以從1到某個特定的數字。 基於某些規則，這些狀態可以以特定方式發展。我對我已經遇到的國家不感興趣。

現在我的代碼只是檢查一個列表是否在列表列表中，如果不是，它將追加它。但是這個列表變得非常大，並且使用大量資源來檢查。

我想

• 創建零的多維數組，
• 檢查該陣列中的特定位置，並且如果該位爲0集它1.

如果我把狀態保存爲一個列表或一個數組，將其調整爲1 以對應於索引值，並嘗試將該值作爲索引 傳遞給零數組，它不僅僅更改這一個元素。

我認爲這是因爲該列表在括號內，其中index（）想要一個 參數只是用逗號分隔的整數。

有沒有辦法傳遞一個整數列表或數組來檢查一個數組的索引，它不會給我的代碼增加複雜性？或者甚至只是一些更有效的方式來 存儲和檢查我已經生成的狀態？

Answer 1

您應該保持您在set中遇到的狀態。這確保了包含檢查（state in visited）是O（1），而不是O（N）。由於lists不是哈希的，你就必須將它們轉換爲tuples，或首先使用元組：

visited = set() 
states = [[1,3,2,2,5], [...], ...] 

for state in states: 
    tpl = tuple(state) 
    if tpl not in visited: # instant check no matter the size of visted 
     # process state 
     visited.add(tpl) 

你的點子創建這個5維列表和傳遞的狀態值作爲指標是有效的，但會創建一個大的（n^5 n：每個槽的值數），並且可能是稀疏矩陣，因此也是等效矩陣。 順便說一下，您可以通過m[1][3][2][2][5]而不是m.index([1,3,2,2,5])訪問此矩陣中的插槽。

Answer 2

是的，你可以定義一個你的狀態類，並使用定義它的散列函數。以這種方式，一個查找的運行時間降低到O(1)和所需的空間減小到O(N)，其中N是數量的狀態代替數狀態*狀態大小的

的樣品類的狀態的：

class State(object): 
    def __init__(self, state_array): 
     self.state_array = state_array 
    def getHash(self): 
     return hash(self.state_array) # using python default hash function here, you can totally design your own. 

當儲存當前狀態：

# current_state is the state you currently have 
all_states = {} 
if current_state.getHash() not in all_state: 
    all_states[current_state.getHash()] = 1 
else: 
    # Do something else 

注意的是Python，element in dict需要O(1)，因爲Python中的dict實際上是一個散列表。