Ответ 1

Поиск первого ненулевого значения работает только тогда, когда сигнал симметричен и не содержит вращения. Рассмотрим следующий пример, заимствованный из Интернета (ноль = синий, макс = красный), обратите внимание, что первое ненулевое значение находится где-то в верхнем правом углу:

_{(источник: mathworks.com)}

Возможно, вы захотите взглянуть на градиентный спуск. Общий алгоритм определен для непрерывных функций (ваш дискретный), но вы все равно можете его использовать.

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

Некоторые свойства:

• Как правило, быстрее, чем полный поиск (итерация всей матрицы)
• Чем больше пространство поиска (матрица), тем быстрее оно сравнительно с исчерпывающим поиском.
• Вы по-прежнему в порядке, даже когда сигнал не симметричен и не центрирован (сначала ненулевое значение выровнено с максимальным значением), вы можете обрабатывать более сложные сигналы!
• Тот же метод можно использовать для одномерных сигналов или масштабирования до n-измерений (что довольно круто, если подумать, и весьма полезно:])

Ограничения:

• Он может колебаться вечно, не сходясь к значению, особенно в дискретной функции, вам нужно обработать этот случай в своем коде.
• Вам не гарантированно найти глобальный максимум (его можно поймать в локальном, есть способы преодоления этого)
• Вам нужно либо интерполировать свою функцию (не все, всего несколько ячеек, это не сложно, я бы не использовал линейную интерполяцию) или внести некоторые изменения в алгоритм (вычисление градиента в дискретной функции по сравнению с непрерывной один, не сложно)

Это может быть излишним для вас, это может быть уместно, я не знаю, вы не предоставляете больше подробностей, но, возможно, стоит взглянуть на это. Обратите внимание, что существует целое семейство алгоритмов, с множеством вариаций и оптимизаций. Посмотрите сначала статью в Википедии;)

Ответ 2

Вероятно, вы не сможете избежать сканирования всей матрицы в худшем случае, но вы можете сократить время выполнения в среднем случае, сканируя при постепенном увеличении разрешения.

Итак, например, вы начнете с отбора проб на некотором (произвольно выбранном) большом расстоянии, оставив вам две возможности:

• вы либо нашли точку с ненулевым значением → , тогда вы можете использовать какую-либо другую технику для "дома" локально на пике по мере необходимости (например, "подъем градиента", как упоминалось в некоторых из другие ответы)

• ваш поиск оказывается пустым → это означает, что разрешение сканирования было слишком большим, волна "провалилась сквозь трещины". Тогда ваш алгоритм уменьшит разрешение (скажем, уменьшив его в два раза) и запустив другое сканирование (если это будет сделано умно, вы можете даже пропустить те точки, которые вы уже выбрали в предыдущем прогоне), только более мелкозернистый

Таким образом, вы продолжаете сканировать постепенно меньшие разрешения, пока не найдете то, что ищете - первые несколько "грубых" сканирований будут быстрее, но имеют меньшие шансы на успех, но (в зависимости от некоторых факторов, как размер полной матрицы по сравнению с размером "всплесков" ), вы в среднем получите хороший шанс найти цель, прежде чем вам придется уменьшить разрешение достаточно далеко, чтобы сканировать весь матричный элемент на -элементное.

Чтобы проиллюстрировать:

Первое сканирование:

#-------#-------
----------------
----------------
----------------
----------------
----------------
----------------
----------------
#-------#-------
----------------
----------------
----------------
----------------
----------------
----------------
----------------

Второе сканирование:

o---#---o---#---
----------------
----------------
----------------
#---#---#---#---
----------------
----------------
----------------
o---#---o---#---
----------------
----------------
----------------
#---#---#---#---
----------------
----------------
----------------

Третье сканирование:

o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------

И так далее (с '#', являющимся вновь сэмплированными ячейками, и 'o' - это ранее отобранные ячейки, которые можно пропустить)...

Ответ 3

Сначала разбиваем всю матрицу на 7x7 малые матрицы, так как перекрытия между матрицами минимизируются.

Разделив матрицу на маленькие матрицы, перейдите или произвольно выберите некоторые точки каждой малой матрицы, чтобы проверить, существуют ли ненулевые значения.

Если вы найдете ненулевые значения из малой матрицы, найдите # из этого ненулевого значения.

Ответ 4

Проведите матрицу от 0,0 до тех пор, пока вы не нажмете ненулевое значение.

Как только вы нажмете ненулевое значение, посмотрите на верхний, правый, нижний, левые соседи, чтобы найти самый большой (если их больше одного, просто выберите один из них).

Затем сделайте то же самое снова на самой большой, которую вы просто выберите, посмотрите на своих 4 соседей и найдите самую большую, пока не нажмете #.

Ответ 5

Если окружающий шаблон всегда один и тот же, поэтому в зависимости от значений соседних элементов и первого ненулевого числа, с которым мы сталкиваемся, мы всегда можем предсказать правильное положение пятна # в течение O (1).

 First non zero element-->| 1 | 1 | 2 |
                        0 | 1 | 4 | 9 |
                        1 | 2 | 9 | # |

Например, если первое ненулевое число равно 1, а правый - 1, down - 1, а справа - нижняя диагональ 4, поэтому # находится в (i + 2, j + 2) с ( i, j) - позиция текущего элемента.

Ответ 6

Предполагая, что шаблон всегда один и тот же, вы хотите проверить каждые пять ячеек в каждом направлении, начиная с [2][2], пока не найдете что-то ненулевое. Таким образом, вы проверите [2][2], [2][7], [2][12], ..., [7][2], [7][7], [7][12], ..., [12][2], ... и т.д.

Как только вы найдете одну из этих ячеек с ненулевым значением, вы можете просто проверить своих соседей и соседей своих соседей, чтобы найти символ #.

Это O(n^2), это лучшее, что вы можете сделать, потому что вам не удастся проверить ячейки O(n^2).

Ответ 7

Другим возможным подходом является итерация по ячейкам до тех пор, пока не будет найдено первое ненулевое число. Поскольку это ненулевое число, как гарантируется, находится в том же столбце, что и центр волны, применительно к свойствам волны, мы можем просто прокрутить колонку до тех пор, пока не найдем точку, в которой образец aba (9#9 в примерном случае), где значение b будет центром волны.

Предположения:

• В матрице существует полная волна, так что присутствуют самые дальней удаленные волны, позволяющие найти первое ненулевое число.
• Центральное значение уникально в той мере, в какой оно не равно другим значениям в одном столбце, иначе алгоритм найдет одно из центральных окружающих значений как центр.

код:

// iterate through cells
for (int y = 0; y < matrix.length; y++) {
    for (int x = 0; x < matrix[0].length; x++) {
        if (matrix[y][x] > 0) { // first non-zero value, in this case at point 3,3
            int cellCurr = 0;
            int cellOnePrev = 0;
            int cellTwoPrev = 0;
            for (; y < matrix.length; y++) { // iterate down rest of column
                cellCurr = matrix[y][x];
                if (cellCurr == cellTwoPrev) { // aba pattern found, center is b
                    System.out.println("found " + cellOnePrev + " at " + x + "," + (y - 1));
                    return;
                }
                // update necessary values
                cellTwoPrev = cellOnePrev;
                cellOnePrev = cellCurr;
            }
        }
    }
}

Вывод для примера с 10 вместо #:

found 10 at 3,6

Ответ 8

В соответствии с редактированием основное намерение состоит в том, чтобы найти первую ненулевую запись. Это имеет смысл. Как только вы это обнаружите, вы можете тривиально использовать метод градиента-подъема, чтобы найти максимальное значение: просто переходите от текущей записи к соседнему с самым высоким значением на каждом шаге, пока не достигнете вершины.

Однако некоторые важные важные детали отсутствуют. Например, может быть важно знать форму волны. В исходном вопросе, похоже, есть какая-то гауссовая форма. Может ли это быть более "плоским"? То есть, может ли такое же максимальное значение заставлять область большего матрицы заполняться ненулевыми элементами?

Ключевой момент здесь - для первой, тривиальной оптимизации - знать диаметр области, содержащей ненулевые записи. Если вы знаете, что диаметр области с ненулевыми элементами составляет, например, n, тогда вы можете пересечь матрицу с размером шага n-1 и быть уверенным, что вы не пропустите волну.

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

Но для тривиального поиска (независимо от размера шага 1 или n-1) могут быть решения, которые влияют на общую производительность. Наиболее заметно: эффекты кеширования. Вот пример, который помещает "волны" в матрицы разных размеров. (Заметим, что для простоты "волны" на самом деле прямоугольны, основанные на морской окрестности записи с максимальным значением).

Он ищет первую ненулевую запись, используя три метода:

• findNonZeroSimpleA: пробегает только матрицу, основная колонка
• findNonZeroSimpleB: просто пробегает матрицу, строка main
• findNonZeroSkipping: просто пробегает матрицу, майор столбца, с размером шага n-1

Это не "тест"

Это дает лишь приблизительное представление о различиях в производительности. Некоторые результаты для моего ПК (не говоря уже о настройке, потому что это не тест): для матрицы 8000x8000 с максимальным значением 10, расположенным на (6000,6000), время работы для трех подходов составляет

• findNonZeroSimpleA: 28.783 ms
• findNonZeroSimpleB 831.323 ms
• findNonZeroSkipping 2.203 ms

Как вы можете видеть, наибольшая разница подразумевается порядком обхода (просто поменяв две строки - обязательно используйте правильный здесь!). Подход "пропуская" уменьшает время работы примерно на коэффициент, соответствующий размеру волны. (Результат может быть искажен и здесь, опять же из-за эффектов кеширования, когда размер волны "большой", но, к счастью, это именно те случаи, когда пропущенный подход был бы особенно полезен).

import java.awt.Point;

public class WaveMatrixTest
{
    public static void main(String[] args)
    {
        //basicTest();
        speedTest();
    }

    private static void basicTest()
    {
        int size = 30;
        int maxValue = 10;
        int array[][] = new int[size][size];
        placeValue(array, maxValue, 15, 15);
        System.out.println(toString2D(array));
    }

    private static void speedTest()
    {
        int maxValue = 10;
        int runs = 10;
        for (int size=2000; size<=8000; size*=2)
        {
            for (int run=0; run<runs; run++)
            {
                int x = size/2+size/4;
                int y = size/2+size/4;
                runTestSimpleA(size, maxValue, x, y);
                runTestSimpleB(size, maxValue, x, y);
                runTestSkipping(size, maxValue, x, y);
            }
        }

    }

    private static void runTestSimpleA(int size, int maxValue, int x, int y)
    {
        int array[][] = new int[size][size];
        placeValue(array, maxValue, x, y);

        long before = System.nanoTime();
        Point p = findNonZeroSimpleA(array, maxValue);
        long after = System.nanoTime();

        System.out.printf("SimpleA,  size %5d max at %5d,%5d took %.3f ms, result %s\n",
            size, x, y, (after-before)/1e6, p);
    }

    private static void runTestSimpleB(int size, int maxValue, int x, int y)
    {
        int array[][] = new int[size][size];
        placeValue(array, maxValue, x, y);

        long before = System.nanoTime();
        Point p = findNonZeroSimpleB(array, maxValue);
        long after = System.nanoTime();

        System.out.printf("SimpleB,  size %5d max at %5d,%5d took %.3f ms, result %s\n",
            size, x, y, (after-before)/1e6, p);
    }

    private static void runTestSkipping(int size, int maxValue, int x, int y)
    {
        int array[][] = new int[size][size];
        placeValue(array, maxValue, x, y);

        long before = System.nanoTime();
        Point p = findNonZeroSkipping(array, maxValue);
        long after = System.nanoTime();

        System.out.printf("Skipping, size %5d max at %5d,%5d took %.3f ms, result %s\n",
            size, x, y, (after-before)/1e6, p);
    }

    private static void placeValue(int array[][], int maxValue, int x, int y)
    {
        int sizeX = array.length;
        int sizeY = array[0].length;
        int n = maxValue;
        for (int dx=-n; dx<=n; dx++)
        {
            for (int dy=-n; dy<=n; dy++)
            {
                int cx = x+dx;
                int cy = y+dy;
                if (cx >= 0 && cx < sizeX &&
                    cy >= 0 && cy < sizeY)
                {
                    int v = maxValue - Math.max(Math.abs(dx), Math.abs(dy));
                    array[cx][cy] = v;
                }
            }
        }
    }

    private static Point findNonZeroSimpleA(int array[][], int maxValue)
    {
        int sizeX = array.length;
        int sizeY = array[0].length;
        for (int x=0; x<sizeX; x++)
        {
            for (int y=0; y<sizeY; y++)
            {
                if (array[x][y] != 0)
                {
                    return new Point(x,y);
                }
            }
        }
        return null;
    }

    private static Point findNonZeroSimpleB(int array[][], int maxValue)
    {
        int sizeX = array.length;
        int sizeY = array[0].length;
        for (int y=0; y<sizeY; y++)
        {
            for (int x=0; x<sizeX; x++)
            {
                if (array[x][y] != 0)
                {
                    return new Point(x,y);
                }
            }
        }
        return null;
    }

    private static Point findNonZeroSkipping(int array[][], int maxValue)
    {
        int size = maxValue * 2 - 1;
        int sizeX = array.length;
        int sizeY = array[0].length;
        for (int x=0; x<sizeX; x+=size)
        {
            for (int y=0; y<sizeY; y+=size)
            {
                if (array[x][y] != 0)
                {
                    return new Point(x,y);
                }
            }
        }
        return null;
    }


    private static String toString2D(int array[][])
    {
        StringBuilder sb = new StringBuilder();
        int sizeX = array.length;
        int sizeY = array[0].length;
        for (int x=0; x<sizeX; x++)
        {
            for (int y=0; y<sizeY; y++)
            {
                sb.append(String.format("%3d", array[x][y]));
            }
            sb.append("\n");
        }
        return sb.toString();
    }

}

Ответ 9

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

СЛУЧАЙ I. Зона, пораженная волной, велика по сравнению со всей областью

Мой совет: путешествовать по диагонали.

Вы должны начать с угла и двигаться по диагонали, пока не достигнете первого ненулевого значения. После этого перемещается система.

CASE II Область, затронутая волной, мала по сравнению со всей областью

Мой совет: играть в шахматы.

Вы должны начать с угла и двигаться, как на шахматной доске (см. пример)

Сделайте это, пока не достигнете первого ненулевого значения. И здесь меняется система путешествий.

После достижения нулевого значения сделайте это: проверьте все 8 (на самом деле 5 достаточно, вам не нужно проверять из угла, который вы пришли, однако эта второстепенная вещь может быть трудно реализовать) окружающие области и перейти к самому большому стоимость. Повторяйте такой шаг, пока не найдете #.

Ответ 10

Поскольку нет заданий на запись, я бы использовал несколько потоков, чтобы сначала найти ненулевой номер, а затем найти # с одним потоком. Если матрица достаточно велика, чтобы отменить более низкую производительность обработки потоков, это будет работать лучше, чем однопоточный.

• Разделить матрицу в нескольких областях
• Найти ненулевое число последовательно или произвольно
• Как только любое ненулевое число найдено, остановите все потоки
• Найти # с одним потоком с правильным алгоритмом

Ответ 11

Предполагая, что вы знаете границы области, поиск первой ненулевой точки должен немного походить на игровой броненосец, за исключением того, что вы знаете, что цель имеет ширину и высоту, что является преимуществом. Учитывая тот факт, что вы не знаете размер ненулевой части волны, начните с предположения, что он большой и продвинется к предположению о меньшем размере.

Если длина равна 1x1, начните с тестирования 0.33x0.33, 0.33x0.66, 0.66x0.33 и 0.66x0.66. Если вы не нашли, уменьшите размер шага до 0,33/2 и повторите тест до тех пор, пока на корабль не попадет множество точек. Сложная часть начинается, когда вы нашли первую точку, так как никакая соседняя точка не обязательно имеет более высокое значение, поэтому в этом случае вам придется повторить первый шаг, ища что-то большее, чем ваш текущий уровень. Предыдущий набор обращений определяет новую область, на которую нужно смотреть. Если соседняя точка имеет более высокий уровень, вы, очевидно, двигаетесь туда.

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

Ответ 12

Вы можете пойти следующим образом:

Сначала найдите самый большой номер. в матрице, а затем перейдите к расположению этого max no. в матрице и, наконец, проверка соседей решит проблему поиска #.

a = max(matrix)
[r,c] = find(matrix == a)

тогда проверьте для соседей с r +/- 1 и c +/- 1, и u найдет #.