Моя проблема очень проста, но я еще не нашел эффективной реализации.

Предположим, есть матрица A, подобная этой:

0 0 0 0 0 0 0
4 4 2 2 2 0 0
4 4 2 2 2 0 0
0 0 2 2 2 1 1
0 0 0 0 0 1 1

Теперь я хочу найти в этой матрице все начальные позиции прямоугольных областей заданного размера. Область - это подмножество A, где все числа одинаковы.

Допустим, ширина = 2 и высота = 3. Есть 3 области, которые имеют этот размер:

2 2   2 2   0 0
2 2   2 2   0 0
2 2   2 2   0 0

Результатом вызова функции будет список начальных позиций (x, y, начиная с 0) этих областей.

List((2,1),(3,1),(5,0))

Ниже представлена ​​моя текущая реализация. «Области» здесь называются «поверхностями».

case class Dimension2D(width: Int, height: Int)
case class Position2D(x: Int, y: Int)

def findFlatSurfaces(matrix: Array[Array[Int]], surfaceSize: Dimension2D): List[Position2D] = {

    val matrixWidth = matrix.length
    val matrixHeight = matrix(0).length
    var resultPositions: List[Position2D] = Nil

    for (y <- 0 to matrixHeight - surfaceSize.height) {
        var x = 0
        while (x <= matrixWidth - surfaceSize.width) {
            val topLeft = matrix(x)(y)
            val topRight = matrix(x + surfaceSize.width - 1)(y)
            val bottomLeft = matrix(x)(y + surfaceSize.height - 1)
            val bottomRight = matrix(x + surfaceSize.width - 1)(y + surfaceSize.height - 1)
            // investigate further if corners are equal
            if (topLeft == bottomLeft && topLeft == topRight && topLeft == bottomRight) {
                breakable {
                    for (sx <- x until x + surfaceSize.width;
                         sy <- y until y + surfaceSize.height) {
                        if (matrix(sx)(sy) != topLeft) {
                            x = if (x == sx) sx + 1 else sx 
                            break
                        }
                    }
                    // found one!       
                    resultPositions ::= Position2D(x, y)
                    x += 1
                }
            } else if (topRight != bottomRight) {
                // can skip x a bit as there won't be a valid match in current row in this area
                x += surfaceSize.width 
            } else {
                x += 1
            }
        }   
    }
    return resultPositions
}

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

Спасибо, что подумал об этом! Я рад видеть ваши предложения или решения :)

РЕДАКТИРОВАТЬ: Размеры матрицы в моем приложении варьируются от 300x300 до 3000x3000 приблизительно. Кроме того, алгоритм будет вызываться только один раз для той же матрицы. Причина в том, что впоследствии матрица всегда будет изменяться (примерно 1-20%).

РЕЗУЛЬТАТЫ

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

Во-первых, необработанные результаты с использованием Scala 2. 8 и jdk 1.6.0_23. Алгоритмы выполнялись несколько сотен раз в рамках решения конкретной прикладной задачи. «Продолжительность» обозначает общее время, необходимое до завершения работы алгоритма приложения (конечно, без запуска jvm и т. Д.). Моя машина - это процессор Core 2 Duo с тактовой частотой 2,8 ГГц, 2 ядра и 2 ГБ памяти, JVM было передано -Xmx800M.

ВАЖНОЕ ПРИМЕЧАНИЕ: Я думаю, что мои настройки теста не совсем справедливы для параллельных алгоритмов, подобных алгоритму из Даниэль. Это потому, что приложение уже выполняет вычисления в многопоточности. Таким образом, результаты здесь, вероятно, показывают только скорость, эквивалентную однопоточной.

Размер матрицы 233x587:

                  duration | JVM memory | avg CPU utilization
original O(n^4) | 3000s      30M          100%  
original/-server| 840s       270M         100%
Nikita O(n^2)   | 5-6s       34M          70-80%
Nikita/-server  | 1-2s       300M         100%
Kevin/-server   | 7400s      800M         96-98%
Kevin/-server** | 4900s      800M         96-99%
Daniel/-server  | 240s       360M         96-99%

** с @specialized, чтобы сделать универсальные шаблоны быстрее , избегая стирания типа

Размер матрицы 2000x3000:

                  duration | JVM memory | avg CPU utilization
original O(n^4) | too long   100M         100%  
Nikita O(n^2)   | 150s       760M         70%
Nikita/-server  | 295s (!)   780M         100%
Kevin/-server   | too long, didn't try

Во-первых, небольшая заметка о памяти. Параметр -server JVM использует значительно больше памяти, что дает больше оптимизаций и в целом более быстрое выполнение. Как видно из 2-й таблицы, алгоритм Никиты работает медленнее с параметром -server, что, очевидно, связано с превышением лимита памяти. Я предполагаю, что это также замедляет алгоритм Кевина даже для небольшой матрицы, поскольку функциональный подход в любом случае использует гораздо больше памяти. Чтобы устранить фактор памяти, я также попробовал один раз с матрицей 50x50, а затем у Кевина потребовалось 5 секунд, а у Никиты - 0 секунд (ну, почти 0). Так что в любом случае он все равно медленнее, и не только из-за памяти.

Как вы можете видеть из чисел, я, очевидно, буду использовать алгоритм Никиты, потому что он чертовски быстрый, а это абсолютно необходимо в моем случае. Как указал Даниэль, его также можно легко распараллелить. алгоритмы как ответы, но я должен выбрать один. В заголовке моего вопроса было написано «наиболее эффективно», и один из них является самым быстрым в императивном, а другой - в функциональном стиле. Хотя этот вопрос помечен как Scala, я выбрал императивный алгоритм Никиты, так как разница между 2 и 240 по-прежнему слишком велика, и я не могу ее принять. Я уверен, что разницу еще можно немного уменьшить, есть идеи?

Итак, большое вам всем спасибо! Хотя я пока не буду использовать функциональные алгоритмы , у меня появилось много нового понимания Scala, и я думаю, что постепенно я начинаю понимать все функциональное безумие и его потенциал. (конечно, даже без особого функционального программирования Scala гораздо приятнее, чем Java ... еще одна причина изучить его)