[linux C]пройтись маленьким двумерным массивом по большому двумерному
ничего не понял. можешь поподробнее написать? и причём тут линукс?
какой размер минора?
какая операция? больше, меньше, равно, сумма квадратов\модулей разностей?
какие элементы в матрице?
какая операция? больше, меньше, равно, сумма квадратов\модулей разностей?
какие элементы в матрице?
большая матрица например 100x100 элементов, маленькая например 4х4 элемента. надо маленькой пройтись по большой поэлементно. как бы поводить по сетке. мож либа какая есть. хотя щас проспался, думаю что поживей пойдет. пока несообразил как грамотнее будет сделать
Просто так поводить, или нужно что-нибудь определить ?
А загвоздка-то в чём? Берёшь imho и сравниваешь в цикле. Если скорость не нужна, то в лоб. Если нужна, то как при поиске в строке сравнивай сначала последний элемент [3][3] - быстрее дело пойдёт по идее, смещаться можно будет не на 1. Накатай алгоритм типа поиска в строке Боуера и Мура. Вирта можно глянуть.
сравнивай сначала последний элемент [3][3] - быстрее дело пойдёт по идее, смещаться можно будет не на 1Почему?
решение в лоб
N на M - большая матрица
n на m - маленькая
из маленькой делаем строку n*m
идем по каждому элементу от 1 до M - m + 1 => 1 до N-n+1 и составляем на нем строку размера n*m и сравниваем строки
под строкой в данном случае понимается просто массив элементов
N на M - большая матрица
n на m - маленькая
из маленькой делаем строку n*m
идем по каждому элементу от 1 до M - m + 1 => 1 до N-n+1 и составляем на нем строку размера n*m и сравниваем строки
под строкой в данном случае понимается просто массив элементов
Сложность решения как была M*N, так и остаётся, а сложность алгоритма возрастает по сравнению с обычным перебором
Пусть алгоритм должен вовзращать true, если удалось пройтись маленькой матрицей по большой и все сравнения давали true, иначе false.
Если бы требовалось смещаться каждый раз на 1, то это бы означало, что
1. все элементы матрицы m*n равны между собой, иначе алгоритм возвращает false
2. Раз все элементы m*n равны между собой, равны А, то требуется лишь проверить, что все элементы матрицы M*N равны А
Так что смещение по-любому должно быть на n по y и m по x.
Ничего алгоритмически лучше переборного алгоритма здесь не придумаешь.
Если бы требовалось смещаться каждый раз на 1, то это бы означало, что
1. все элементы матрицы m*n равны между собой, иначе алгоритм возвращает false
2. Раз все элементы m*n равны между собой, равны А, то требуется лишь проверить, что все элементы матрицы M*N равны А
Так что смещение по-любому должно быть на n по y и m по x.
Ничего алгоритмически лучше переборного алгоритма здесь не придумаешь.
ё-маё, ну напиши что надо то!
строгое равенство?
какие элементы? байты?
строгое равенство?
какие элементы? байты?
да уж сам написал, ошибся в индексе только, долбался два дня. но все равно народ спасибо! =)
Допустим у тебя большой массив - это битмап - абсолютно чёрный квадрат Малевича размером 11 на 11, а ты должен проверить нет ли там подмассива 4 на 4 абсолютно белого.
Тогда для проверки, что его там нет достаточно будет сравнить сначала элемент большого массива [3][3] (начальный элемент это [0][0]) c последним элементом [3][3] маленького (w - белый цвет) - потом обнаружив там B (чёрный цвет) смещаемся на 4 по горизонтали и опять сравниваем с элементом [3][3] маленького т.д.
За 4 сравнения обнаруживаем, что
w w w w
w w w w
w w w w
w w w w
никак не влезет в
? означает неизвестно что (мы не проверяли, что там в этом элементе).
Если ты начнёшь с элемента [0][0] сравнивать подряд, то тебе понадобится 8*8=64 сравнения для установления того же факта, пока весь угол не проверишь один элемент за другим
Если малый массив не из одних w, то сначала индекс строится на сколько смещаться при обнаружении одного из его подэлементов в большом массиве. Если один и тот же большой массив сканируется разными маленькими многократно, то наверное что-то по большому можно заранее посчитать, например, если в большом массиве w встречается в 2 местах, а в маленьком w есть, то вокруг этих 2 мест в большом массиве только и стоит копать.
Книжку Вирта глянь, главу про поиск. Вообще для двумерного поиска в общем случае задача нетривиальная, наверное нет в литературе. А может уж есть. Если кто знает - киньте ссылку для общего развития.
Тогда для проверки, что его там нет достаточно будет сравнить сначала элемент большого массива [3][3] (начальный элемент это [0][0]) c последним элементом [3][3] маленького (w - белый цвет) - потом обнаружив там B (чёрный цвет) смещаемся на 4 по горизонтали и опять сравниваем с элементом [3][3] маленького т.д.
За 4 сравнения обнаруживаем, что
w w w w
w w w w
w w w w
w w w w
никак не влезет в
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? B ? ? ? B ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? B ? ? ? B ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? означает неизвестно что (мы не проверяли, что там в этом элементе).
Если ты начнёшь с элемента [0][0] сравнивать подряд, то тебе понадобится 8*8=64 сравнения для установления того же факта, пока весь угол не проверишь один элемент за другим
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
B B B B B B B B ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
Если малый массив не из одних w, то сначала индекс строится на сколько смещаться при обнаружении одного из его подэлементов в большом массиве. Если один и тот же большой массив сканируется разными маленькими многократно, то наверное что-то по большому можно заранее посчитать, например, если в большом массиве w встречается в 2 местах, а в маленьком w есть, то вокруг этих 2 мест в большом массиве только и стоит копать.
Книжку Вирта глянь, главу про поиск. Вообще для двумерного поиска в общем случае задача нетривиальная, наверное нет в литературе. А может уж есть. Если кто знает - киньте ссылку для общего развития.
Оставить комментарий
Barbie29
на предмет поэлементного сравнения. может кто делал такую штуку или гденнить мож готовая библиотека есть? у меня чето лыжи не едут седня под утро =(