Есть ли способ поиска списка в Python путем быстрого преобразования его в пустую матрицу?

Question

Я пытаюсь выполнить поиск в массиве Python 2D, циклически перебирая строки массива и проверяя, соответствуют ли значения внутри условия условию. Пример здесь:

def searchList(list, v0, v1, v2, v3):
 for r in range(len(list)):
    if (list[r][0] == v0) & (list[r][1] == v1) & (list[r][2] == v2) & (list[r][3] == v3):
        return r

 return None

Это, однако, довольно медленно в Python по сравнению с другими языками.

Теперь основная проблема заключается в том, что этот список динамически растет и может содержать 1000 или более строк.

Когда я вышел в интернет, чтобы найти способ сделать это быстрее, я обнаружил, что переместил список в пустую матрицу и с помощью np.where() мог бы сделать это.

def searchList(list, v0, v1, v2, v3):
    tmpQ = np.array(list)
    locList = np.where((tmpQ[:,0] == v0) & (tmpQ[:,1] == v1) & (tmpQ[:,2] == v2) & (tmpQ[:,3] == v3))
    if locList[0].size == 0:
        return None
    else:
        return locList[0][0]

Теперь проблема заключается в том, что преобразование двумерного массива python в матрицу numpy состоит в том, что эта операция также занимает много времени.

Мой другой вариант - избавиться от двумерного массива python и использовать только пустую матрицу, однако это также не работает, поскольку матрица продолжает расти, операция конкатенации занимает много времени.

Есть ли способ сделать это быстро?

Я знаю, что является причиной того, что больше всего времени занимает использование cProfile и запуск кода.

Answer 1

Похоже, вы ищете в списке для 4 последовательных записей.Например, вы можете захотеть найти числа 1, 5, 6, и 7, появляющиеся рядом друг с другом в списке.

Это называется " алгоритм сопоставления строк одного шаблона "

Ваш код работает медленно, потому что вы реализовали решение проблемы методом "грубой силы".Алгоритм перебора требует времени, пропорционального n*m, где n - длина вашего списка, а m - длина вашего непрерывного подсписка (m = 4 для вашего примера).

Вместо того, чтобы писать код самостоятельно (заново изобретать колесо), я рекомендую вам использовать чужой код.Я не пробовал следующее, но похоже, что это реализация Python алгоритма Кнута-Морриса-Пратта :

реализация Python на github

Answer 2

это зависит от вашей формы данных, вы можете попробовать это:

def searchList(mylist, v0, v1, v2, v3):
    try:
        row_num = mylist.index([v0, v1, v2, v3])
    except ValueError:
        return None
    return row_num 


m = [[1,2,3,4], [5,6,7,8], [3,2,8,7], [1,3,6,9]]
print(searchList(m, 3, 2, 8, 7))

вывод:

2