определение локальных максимумов

@Galina1810 · Регистрация: 22.09.2016

Студворк — интернет-сервис помощи студентам

Дана матрица NxM, размеры ограничены N<=10000 и M<=10000.
В каждую точку матрицы (элемент) нужно записать число, которое является максимумом в квадратике вокруг этой точки.
Сторона квадрата - D.
Пример для D=3:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{bmatrix}&7 &2 &1 &3 &3 \\ &9 &6 &6 &3 &6 \\&8 &7 &3 &9 &3 \\ &7 &7 &2 &8 &2 \\ &3 &1 &1 &8 &1 \end{bmatrix}$ -> $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{bmatrix}&9 &9 &6 &6 &6 \\&9 &9 &9 &9 &9 \\&9 &9 &9 &9 &9 \\&8 &8 &9 &9 &9 \\&7 &7 &8 &8 &8\end{bmatrix}$
Очевидное решение: перебор всех элементов в квадратике и нахождение максимума не подходит для больших N и M, и особенно для D

@Shamil1 · 22.09.2016, 17:56

Сообщение от Galina1810

перебор всех элементов в квадратике и нахождение максимума не подходит для больших N и M, и особенно для D

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

@Galina1810 · 22.09.2016, 18:51 **[ТС]**

Может быть есть какие-нибудь численные методы? через градиенты? или специальные маски? частные случаи? Проход в подматрице - это сложность О(n^2).

@Shamil1 · 22.09.2016, 19:58

Размер ответа - тоже О(n^2).

Для решения данной задачи хорошо использовать gpu.

@ProgJ · 24.09.2016, 08:57

Galina1810, можно обойтись без полного перебора
Нужно свести двумерную задачу к одномерной, и вместо N*M нахождений максимумов из 9 получим 2 раза по N*M нахождений максимумов из 3 (вместо 3*3 получим 3+3)
Будем отдельно преобразовывать каждую строку, находить максимум из 3-х. Получится промежуточная матрица, которую теперь нужно пройти по столбцам

@VTsaregorodtsev · 25.09.2016, 22:17

Сообщение от Shamil1

Вы можете немного уменьшить количество сложений

Скорее, не сложений - а сравнений и/или условных переходов.
Через использование ассемблерных команд cmov (для целочисленки) или maxps (для плавучки), через векторизацию расчётов (maxps - как раз оттуда). Но для векторизации нужно данные перестраивать - иначе чтение невыравненных данных займёт столько времени, что всё ускорение от simd-команд пропадёт.
В общем, под каждый конкретный размер d - можно вручную написать отдельную макс.эффективную функцию. А универсальный код для всех размеров d - может в разы проигрывать в скорости каждой такой специализированной реализации.

Ну и ProgJ правильно описАл самый лучший вариант - но там всё сказанное мной выше тоже работает.

@Galina1810 · 29.09.2016, 07:32 **[ТС]**

не совсем поняла о чем Вы. Есть элемент "6" с индексами [1,1]. Т.к. D==3, то я рассматриваю квадратик вокруг шестерки:
а точнее строки этого квадрата: 7,2,1 | 9,6,6 | 8,7,3. Выбираю максимум в каждой из строк: 7, 9, 8. Это уже получается полный перебор. Далее по Вашему алгоритму нужно сканировать по столбцам. Как же для данного элемента получить сложность 3+3 ?

@Shamil1 · 29.09.2016, 08:08

Сообщение от Galina1810

Выбираю максимум в каждой из строк: 7, 9, 8.

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

Добавлено через 1 минуту

Сообщение от Galina1810

Это уже получается полный перебор.

Асимптотика не улучшается. Те же O(n²).

@Galina1810 · 29.09.2016, 10:53 **[ТС]**

но если сдвинуться в координату [1,2] там где тоже элемент "6", то все мои найденные максимумы теряют силу, ведь они уже не входят в квадрат со стороной D==3 для данного элемента. И придется искать все максимумы заново. Можете, пожалуйста, объяснить за счет чего происходит экономия еще раз?

@ProgJ · 29.09.2016, 11:37

Galina1810, поиск максимума для матрицы 3*3, можно сделать в 2 этапа
1. найти максимум для каждой строки, получится вектор из 3-х элементов
2. найти максимум в этом векторе, получим число

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

@Shamil1 · 29.09.2016, 12:26

Исходная матрица

Промежуточная матрица
получена из исходной нахождением максимумов по строкам (по 3 сравнения на каждый элемент)

Ответ
получен из промежуточной матрицы нахождением максимумов по столбцам (по 3 сравнения на каждый элемент)

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

@Galina1810 0 / 0 / 0 Регистрация: 22.09.2016 Сообщений: 4

	определение локальных максимумов 22.09.2016, 17:22. Показов 2384. Ответов 10 Метки нет (Все метки) Дана матрица NxM, размеры ограничены N<=10000 и M<=10000. В каждую точку матрицы (элемент) нужно записать число, которое является максимумом в квадратике вокруг этой точки. Сторона квадрата - D. Пример для D=3: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{bmatrix}&7 &2 &1 &3 &3 \\ &9 &6 &6 &3 &6 \\&8 &7 &3 &9 &3 \\ &7 &7 &2 &8 &2 \\ &3 &1 &1 &8 &1 \end{bmatrix}$ -> $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{bmatrix}&9 &9 &6 &6 &6 \\&9 &9 &9 &9 &9 \\&9 &9 &9 &9 &9 \\&8 &8 &9 &9 &9 \\&7 &7 &8 &8 &8\end{bmatrix}$ Очевидное решение: перебор всех элементов в квадратике и нахождение максимума не подходит для больших N и M, и особенно для D 0

@Galina1810 0 / 0 / 0 Регистрация: 22.09.2016 Сообщений: 4
	22.09.2016, 18:51 [ТС]
	Может быть есть какие-нибудь численные методы? через градиенты? или специальные маски? частные случаи? Проход в подматрице - это сложность О(n^2). 0

@Shamil1 Модератор 3137 / 2284 / 469 Регистрация: 26.03.2015 Сообщений: 8,888
	22.09.2016, 19:58
	Размер ответа - тоже О(n^2). Для решения данной задачи хорошо использовать gpu. 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	24.09.2016, 08:57
	Galina1810, можно обойтись без полного перебора Нужно свести двумерную задачу к одномерной, и вместо NM нахождений максимумов из 9 получим 2 раза по NM нахождений максимумов из 3 (вместо 3*3 получим 3+3) Будем отдельно преобразовывать каждую строку, находить максимум из 3-х. Получится промежуточная матрица, которую теперь нужно пройти по столбцам 0

@Galina1810 0 / 0 / 0 Регистрация: 22.09.2016 Сообщений: 4
	29.09.2016, 07:32 [ТС]
	не совсем поняла о чем Вы. Есть элемент "6" с индексами [1,1]. Т.к. D==3, то я рассматриваю квадратик вокруг шестерки: а точнее строки этого квадрата: 7,2,1 \| 9,6,6 \| 8,7,3. Выбираю максимум в каждой из строк: 7, 9, 8. Это уже получается полный перебор. Далее по Вашему алгоритму нужно сканировать по столбцам. Как же для данного элемента получить сложность 3+3 ? 0

@Galina1810 0 / 0 / 0 Регистрация: 22.09.2016 Сообщений: 4
	29.09.2016, 10:53 [ТС]
	но если сдвинуться в координату [1,2] там где тоже элемент "6", то все мои найденные максимумы теряют силу, ведь они уже не входят в квадрат со стороной D==3 для данного элемента. И придется искать все максимумы заново. Можете, пожалуйста, объяснить за счет чего происходит экономия еще раз? 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	29.09.2016, 11:37
	Galina1810, поиск максимума для матрицы 33, можно сделать в 2 этапа 1. найти максимум для каждой строки, получится вектор из 3-х элементов 2. найти максимум в этом векторе, получим число Вы ищите максимум не одной матрицы, а разных. Некоторые из них пересекаются. Есть матрицы с одинаковыми строчками, максимумы для таких строчек можно вычислить один раз* 0

определение локальных максимумов

Решение