使用列表来检查数组索引

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实际上是一个散列表。