Это потому, что метод Scanner.nextInt
не использует символ последней новой строки вашего ввода и, следовательно, newline потребляется в следующий вызов Scanner.nextLine
.
Вы столкнетесь с аналогичным поведением, когда вы используете Scanner.nextLine
после Scanner.next()
или любого метода Scanner.nextFoo
(кроме самого nextLine
).
Обход проблемы:
Scanner.nextLine
вызов после Scanner.nextInt
или Scanner.nextFoo
, чтобы потреблять остальную часть этой линии, включая newline int option = input.nextInt();
input.nextLine(); // Consume newline left-over
String str1 = input.nextLine();
Scanner.nextLine
и преобразуете свой ввод в нужный формат. Например, к целому числу с использованием метода Integer.parseInt(String)
. int option = 0;
try {
option = Integer.parseInt(input.nextLine());
} catch (NumberFormatException e) {
e.printStackTrace();
}
String str1 = input.nextLine();
Подход № 1
Этот подход основан на a solution
на Implement Matlab's im2col 'sliding' in python
, который был разработан для rearrange sliding blocks from a 2D array into columns
. Таким образом, чтобы решить наш случай, эти скользящие блоки из field_array
могут быть уложены в виде столбцов и сопоставлены с версией столбца match_array
.
Вот формальное определение функции для перегруппировки / укладки -
def im2col(A,BLKSZ):
# Parameters
M,N = A.shape
col_extent = N - BLKSZ[1] + 1
row_extent = M - BLKSZ[0] + 1
# Get Starting block indices
start_idx = np.arange(BLKSZ[0])[:,None]*N + np.arange(BLKSZ[1])
# Get offsetted indices across the height and width of input array
offset_idx = np.arange(row_extent)[:,None]*N + np.arange(col_extent)
# Get all actual indices & index into input array for final output
return np.take (A,start_idx.ravel()[:,None] + offset_idx.ravel())
Чтобы решить наш случай, вот реализация на основе im2col
-
# Get sliding blocks of shape same as match_array from field_array into columns
# Then, compare them with a column vector version of match array.
col_match = im2col(field_array,match_array.shape) == match_array.ravel()[:,None]
# Shape of output array that has field_array compared against a sliding match_array
out_shape = np.asarray(field_array.shape) - np.asarray(match_array.shape) + 1
# Now, see if all elements in a column are ONES and reshape to out_shape.
# Finally, find the position of TRUE indices
R,C = np.where(col_match.all(0).reshape(out_shape))
. Вывод для данного образца в вопросе будет -
In [151]: R,C
Out[151]: (array([6]), array([3]))
Подход # 2
Учитывая, что opencv уже имеет функцию сопоставления шаблонов, которая делает квадрат различий, вы можете использовать это и искать нулевые различия, которые будут вашими соответствующими позициями. Итак, если у вас есть доступ к cv2 (opencv module), реализация будет выглядеть примерно так:
import cv2
from cv2 import matchTemplate as cv2m
M = cv2m(field_array.astype('uint8'),match_array.astype('uint8'),cv2.TM_SQDIFF)
R,C = np.where(M==0)
дает нам -
In [204]: R,C
Out[204]: (array([6]), array([3]))
В этом разделе сравниваются времена выполнения для всех подходов, предложенных для решения вопроса.
Определения методов -
def seek_array(search_in, search_for, return_coords = False):
si_x, si_y = search_in.shape
sf_x, sf_y = search_for.shape
for y in xrange(si_y-sf_y+1):
for x in xrange(si_x-sf_x+1):
if numpy.array_equal(search_for, search_in[x:x+sf_x, y:y+sf_y]):
return (x,y) if return_coords else True
return None if return_coords else False
def skimage_based(field_array,match_array):
windows = view_as_windows(field_array, match_array.shape)
return (windows == match_array).all(axis=(2,3)).nonzero()
def im2col_based(field_array,match_array):
col_match = im2col(field_array,match_array.shape)==match_array.ravel()[:,None]
out_shape = np.asarray(field_array.shape) - np.asarray(match_array.shape) + 1
return np.where(col_match.all(0).reshape(out_shape))
def cv2_based(field_array,match_array):
M = cv2m(field_array.astype('uint8'),match_array.astype('uint8'),cv2.TM_SQDIFF)
return np.where(M==0)
Тесты времени выполнения -
Случай № 1 (Образец данные из вопроса):
In [11]: field_array
Out[11]:
array([[ 24, 25, 26, 27, 28, 29, 30, 31, 23],
[ 33, 34, 35, 36, 37, 38, 39, 40, 32],
[-39, -38, -37, -36, -35, -34, -33, -32, -40],
[-30, -29, -28, -27, -26, -25, -24, -23, -31],
[-21, -20, -19, -18, -17, -16, -15, -14, -22],
[-12, -11, -10, -9, -8, -7, -6, -5, -13],
[ -3, -2, -1, 0, 1, 2, 3, 4, -4],
[ 6, 7, 8, 4, 5, 6, 7, 13, 5],
[ 15, 16, 17, 8, 9, 10, 11, 22, 14]])
In [12]: match_array
Out[12]:
array([[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11]])
In [13]: %timeit seek_array(field_array, match_array, return_coords = False)
1000 loops, best of 3: 465 µs per loop
In [14]: %timeit skimage_based(field_array,match_array)
10000 loops, best of 3: 97.9 µs per loop
In [15]: %timeit im2col_based(field_array,match_array)
10000 loops, best of 3: 74.3 µs per loop
In [16]: %timeit cv2_based(field_array,match_array)
10000 loops, best of 3: 30 µs per loop
Случай №2 (большие случайные данные):
In [17]: field_array = np.random.randint(0,4,(256,256))
In [18]: match_array = field_array[100:116,100:116].copy()
In [19]: %timeit seek_array(field_array, match_array, return_coords = False)
1 loops, best of 3: 400 ms per loop
In [20]: %timeit skimage_based(field_array,match_array)
10 loops, best of 3: 54.3 ms per loop
In [21]: %timeit im2col_based(field_array,match_array)
10 loops, best of 3: 125 ms per loop
In [22]: %timeit cv2_based(field_array,match_array)
100 loops, best of 3: 4.08 ms per loop
В NumPy нет такой функции поиска, но в NumPy
это возможно сделать. Пока массивы не будут слишком массивными *, вы можете использовать подход к качению:
from skimage.util import view_as_windows
windows = view_as_windows(field_array, match_array.shape)
Функция view_as_windows
записывается чисто в NumPy, поэтому, если вы не имеете skimage, вы всегда можете скопировать код из здесь .
Затем, чтобы увидеть, появляется ли подматрица в более крупном массиве, вы можете написать:
>>> (windows == match_array).all(axis=(2,3)).any()
True
Найти индексы, в которых верхний левый угол подматрицы совпадений, вы можете написать:
>>> (windows == match_array).all(axis=(2,3)).nonzero()
(array([6]), array([3]))
Этот подход также должен работать для массивов более высоких измерений.
*, хотя массив windows
не занимает дополнительной памяти ( только изменения шага и формы изменяются для создания нового представления данных), запись windows == match_array
создает логический массив размера (7, 6, 3, 4), который составляет 504 байта памяти. Если вы работаете с очень большими массивами, этот подход может оказаться невозможным.
Одним из решений является поиск по всему массиву search_in
массива по времени («блок» является search_for
образным фрагментом) до тех пор, пока не будет найден соответствующий сегмент или не будет исчерпан массив search_for
, Я могу использовать его для получения координат для соответствующего блока или только результата bool
, отправив True
или False
для необязательного аргумента return_coords
...
def seek_array(search_in, search_for, return_coords = False):
"""Searches for a contiguous instance of a 2d array `search_for` within a larger `search_in` 2d array.
If the optional argument return_coords is True, the xy coordinates of the zeroeth value of the first matching segment of search_in will be returned, or None if there is no matching segment.
If return_coords is False, a boolean will be returned.
* Both arrays must be sent as two-dimensional!"""
si_x, si_y = search_in.shape
sf_x, sf_y = search_for.shape
for y in xrange(si_y-sf_y+1):
for x in xrange(si_x-sf_x+1):
if numpy.array_equal(search_for, search_in[x:x+sf_x, y:y+sf_y]):
return (x,y) if return_coords else True # don't forget that coordinates are transposed when viewing NumPy arrays!
return None if return_coords else False
Мне интересно если NumPy
еще не имеет функции, которая может делать то же самое, хотя ...
Чтобы добавить к уже опубликованным ответам, я хотел бы добавить тот, который учитывает ошибки из-за точности с плавающей запятой в том случае, если матрицы происходят, скажем, при обработке изображений, например, где числа подпадают под плавучую точку операции.
Вы можете пересчитать индексы большей матрицы, ища меньшую матрицу. Затем вы можете извлечь подматрицу большей матрицы, соответствующую размеру меньшей матрицы.
У вас есть совпадение, если совпадение содержимого как подматрицы «большой», так и «малой» матрицы.
В следующем примере показано, как вернуть первые индексы местоположения в найденной большой матрице. Было бы тривиально расширять эту функцию, чтобы вернуть массив найденных местоположений, если это намерение.
import numpy as np
def find_submatrix(a, b):
""" Searches the first instance at which 'b' is a submatrix of 'a', iterates
rows first. Returns the indexes of a at which 'b' was found, or None if
'b' is not contained within 'a'"""
a_rows=a.shape[0]
a_cols=a.shape[1]
b_rows=b.shape[0]
b_cols=b.shape[1]
row_diff = a_rows - b_rows
col_diff = a_cols - b_cols
for idx_row in np.arange(row_diff):
for idx_col in np.arange(col_diff):
row_indexes = [idx + idx_row for idx in np.arange(b_rows)]
col_indexes = [idx + idx_col for idx in np.arange(b_cols)]
submatrix_indexes = np.ix_(row_indexes, col_indexes)
a_submatrix = a[submatrix_indexes]
are_equal = np.allclose(a_submatrix, b) # allclose is used for floating point numbers, if they
# are close while comparing, they are considered equal.
# Useful if your matrices come from operations that produce
# floating point numbers.
# You might want to fine tune the parameters to allclose()
if (are_equal):
return[idx_col, idx_row]
return None
Используя вышеприведенную функцию, вы можете запустить следующий пример:
large_mtx = np.array([[1, 2, 3, 7, 4, 2, 6],
[4, 5, 6, 2, 1, 3, 11],
[10, 4, 2, 1, 3, 7, 6],
[4, 2, 1, 3, 7, 6, -3],
[5, 6, 2, 1, 3, 11, -1],
[0, 0, -1, 5, 4, -1, 2],
[10, 4, 2, 1, 3, 7, 6],
[10, 4, 2, 1, 3, 7, 6]
])
# Example 1: An intersection at column 2 and row 1 of large_mtx
small_mtx_1 = np.array([[4, 2], [2,1]])
intersect = find_submatrix(large_mtx, small_mtx_1)
print "Example 1, intersection (col,row): " + str(intersect)
# Example 2: No intersection
small_mtx_2 = np.array([[-14, 2], [2,1]])
intersect = find_submatrix(large_mtx, small_mtx_2)
print "Example 2, intersection (col,row): " + str(intersect)
Что бы напечатать:
Example 1, intersection: [1, 2] Example 2, intersection: None