DjangoBB LoFi version

Полная версия: Поиск массива в массиве numpy

Начало » Python для новичков » Поиск массива в массиве numpy

1 2

jor77

Авг. 7, 2015 10:33:18

Добрый день, уважаемые!

Возможно, я торможу, но я не могу найти нормальный способ поиска маленького массива в большом и получения индексов, где маленький находится в большом.
Точнее, я знаю как это сделать через for и срезы, но это долго, массив большой.
Расскажу конкретней что требуется:

Есть массив, например:

Arr = numpy.array([[1,2,3,4,5],
                   [5,6,7,8,9],
                   [9,0,0,0,2],
                   [6,5,4,3,2],
                   [3,4,2,3,2]])

Требуется найти, например:

Arr_small = numpy.array([[5,4,3],
                         [4,2,3]])

Пройтись циклом со срезами я могу, но когда массив большой (например 1000x500) - это очень долго
Возможно, есть какой-нибудь способ сделать это средствами numpy?
Нашел один вариант, который по-началу показался нормальным.
Преобразовать Arr в массив “окон” типа:

numpy.array([[[1,2,3],
              [5,6,7]],
             [[2,3,4],
              [6,7,8]],
             [[3,4,5],
              [7,8,9]],
               ...
             [[4,3,2],
              [2,3,2]]])

После этого преобразовать его в список (tolist) и затем найти индекс Arr.index(Arr_small) и дальше уже вычислить позицию. Но, как оказалось, загвоздка в tolist - эта операция оказалась, внезапно, еще медленней, чем поиск обычным циклом.
Возможно, можно реализовать через numpy.where, но я так и не понял как.
Подскажите, пожалуйста, как можно это реализовать.

Kixiro

Авг. 7, 2015 11:08:40

А поиск нужно делать в одном большом массиве много маленьких или наборот? И размерность маленького массива меняется?

jor77

Авг. 7, 2015 11:25:39

Kixiro
А поиск нужно делать в одном большом массиве много маленьких или наборот? И размерность маленького массива меняется?

Нужно в одном большом найти один маленький.
Массивы двумерные. Количество строк и столбцов и в большом и в малом - произвольное.
Единственное - что большой больше малого и по строкам и по столбцам

py.user.next

Авг. 7, 2015 11:31:06

jor77
Точнее, я знаю как это сделать через for и срезы, но это долго, массив большой.

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

Просто перебираешь элементы по i,j, пока не встретишь совпадение с первым элементом в искомом массиве. Если встретил, продвигаешься на второй элемент в искомом массиве. Если равны - продвигаешься на третий. А если не равны, возвращаешь указатель (индекс) в искомом массиве на первый элемент.

FishHook

Авг. 7, 2015 11:31:37

Не знаю как там в нумпи, в питоне это делается так

s = [1, 3, 4, [1, 2, 3], 0, 0]
print([x for x in s if isinstance(x, list)])

py.user.next

Авг. 7, 2015 11:36:02

FishHook
Не знаю как там в нумпи, в питоне это делается так

Да со списками/кортежами всё точно так же делается - через индексы. Это оптимальное решение (по памяти).

Есть массив
[[1, 2, 3, 4], [5, 6, 7, 8]]
 
Найти подмассив
[[2, 3], [6, 7]]

jor77

Авг. 7, 2015 11:43:17

FishHook
Не знаю как там в нумпи, в питоне это делается так

s = [1, 3, 4, , 0, 0]
print()

Хммм.. Я только не понял как это решит мою задачу. Это находит просто любой список в списке. А мне нужно найти двумерный массив в двумерном массиве и получить его координаты.

FishHook

Авг. 7, 2015 11:46:26

А я не понял задачу, что значит найти массив? Мой код как раз буквально ищет список в списке.

jor77

Авг. 7, 2015 11:51:10

FishHook
А я не понял задачу, что значит найти массив? Мой код как раз буквально ищет список в списке.

Ну, я привел пример что и в чем нужно найти.
И написал, что нужно: “поиск маленького массива в большом и получение индексов, где маленький находится в большом.”
Потом уточнил - массивы двумерные. Впрочем, в примере они и описаны двумерными

Если упростить вопрос - есть большая картинка. И нужно найти маленькую картинку на большой и узнать координаты этой маленькой на большой.

Kixiro

Авг. 7, 2015 12:01:46

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