Используйте список для проверки индекса массива

Question

В python я создаю списки для представления состояний (например, состояние может быть [1,3,2,2,5]).

Значение каждого элемента может варьироваться от 1 до определенного номера. Основываясь на определенных правилах, эти состояния могут развиваться определенными способами. Меня не интересуют состояния, с которыми я столкнулся.

В настоящее время мой код проверяет, включен ли список в список списков, а если нет, он добавляет его. Но этот список становится очень большим и использует множество ресурсов для проверки.

Я хотел бы

• создать многомерный массив нулей,
• проверить конкретное место в этом массиве, и если это место является 0 множество его 1.

Если Я беру состояние, сохраненное в виде списка или как массив, настраивая его на 1 , чтобы соответствовать значениям индекса, и попытайтесь передать это значение как индекс для массива нулей, он не просто изменит один элемент.

Я думаю, это потому, что список находится в скобках, где index() хочет аргумент только целых чисел, разделенных запятыми.

Есть ли способ передать список или массив целых чисел, чтобы проверить индекс массива, который не будет добавлять осложнения к моему коду? Или даже просто более эффективный способ хранения и проверить состояния, которые я уже создал?

Answer 1

Вы должны поддерживать состояния, с которыми вы уже столкнулись в set. Это гарантирует, что a содержит проверку (state in visited) - O (1), а не O (N). Поскольку lists не hashable, вы должны преобразовать их в 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: количество значений для каждого слота) и предположительно разреженную и, следовательно, waisteful матрицу. BTW, вы получаете доступ к слоту в такой матрице через 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), потому что dict в python на самом деле является хэшмапом.