Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
alexus5
292 / 148 / 85
Регистрация: 07.01.2016
Сообщений: 394
Завершенные тесты: 4
1

подсчет соседей

08.10.2019, 20:20. Просмотров 814. Ответов 6
Метки нет (Все метки)

приветствую.
Задан двумерный массив объектов. Необходимо для каждого элемента посчитать количество соседей, удовлетворяющих определенному условию, в окрестности Мура порядка n. Хотелось бы узнать, существуют ли алгоритмы, выполняющие задачу за время, не зависящее от порядка окрестности подсчета?
C#
1
2
3
4
5
6
7
        /// <param name="values">Исходные значения</param>
        /// <param name="func">Условие</param>
        /// <param name="n">Порядок окрестности</param>
        static int[,] GetDensityMap2<T>(this T[,] values, Func<T, bool> func, int n)
        {
 
        }
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2019, 20:20
Ответы с готовыми решениями:

метод k ближайших соседей
дайте ссылку на литературу где описан это метод

Быстрый поиск k ближайших соседей
Имеется 10000 точек в 20-мерном пространстве. Распределены более менее равномерно. Нужно по...

Поиск соседей в изменяющихся точках
Доброго дня. Существует следующая задача: Есть много точек от нескольких десятков тысяч. Часть из...

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

подсчет числа "соседей" для всех двоичных наборов
помогите написать программу в ява: подсчет числа &quot;соседей&quot; для всех двоичных наборов, на которых...

6
VTsaregorodtsev
698 / 643 / 104
Регистрация: 19.02.2010
Сообщений: 2,311
08.10.2019, 20:51 2
Ну так число соседей зависит от порядка http://www.cyberforum.ru/cgi-bin/latex.cgi?n как http://www.cyberforum.ru/cgi-bin/latex.cgi?(2n+1)^2-1. И как в общем случае (не зная, что за условие Вам надо проверять) можно избавиться от проверки их всех?
0
Shamil1
Модератор
2341 / 1628 / 365
Регистрация: 26.03.2015
Сообщений: 5,936
09.10.2019, 01:10 3
Вроде бы, можно, если использовать горизонтальный вектор суммы вертикальных полосок высоты 2n+1.
1
Shamil1
Модератор
2341 / 1628 / 365
Регистрация: 26.03.2015
Сообщений: 5,936
09.10.2019, 13:43 4
Лучший ответ Сообщение было отмечено alexus5 как решение

Решение

Можно посчитать за время O(N), где N - количество элементов в матрице. То есть, асимптотика не зависит от n.

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

C#
1
2
3
4
5
6
7
8
9
// Получаем сумму для полоски из суммы для полоски на клетку выше, 
//     вычитая "лишнее" значение и добавляя "новое".
sums[i+n] += (func(values[i+n, j+n]) ? 1 : 0) - (func(values[i+n, j-n-1]) ? 1 : 0);
// Получаем сумму для квадрата из суммы для квадрата на клетку левее, 
//     вычитая "лишнюю" полоску и добавляя "новую".
res[i, j] = res[i - 1, j] + sums[i + n] - sums[i - n - 1];
// Получаем сумму для окрестности из суммы для квадрата, 
//     вычитая значение в центре
res[i-1,j] -= (func(values[i-1, j]) ? 1 : 0);
Только нужно корректно обработать граничные значения.

Например, так:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static int[,] GetDensityMap2<T>(T[,] values, Func<T, bool> func, int n)
{
    int len1 = values.GetLength(0);
    int len2 = values.GetLength(1);
 
    int GetCount(int i, int j) => 0 <= i && i < len1 && 0 <= j && j < len2 ? func(values[i, j]) ? 1 : 0 : 0;
 
    int[] sums = new int[len1];
    int GetSum(int i) => 0 <= i && i < len1 ? sums[i] : 0;
    void AddSum(int i, int value) { if (0 <= i && i < len1) sums[i] += value; }
 
    int[,] res = new int[len1, len2];
    int GetRes(int i, int j) => 0 <= i && i < len1 && 0 <= j && j < len2 ? res[i, j] : 0;
    void AddRes(int i, int j, int value) { if (i < len1 && 0 <= j && j < len2) res[i < 0 ? 0 : i, j] += value; }
 
    for (int j = -n; j < len2; j++)
    {
        for (int i = -n; i < len1; i++)
        {
            AddSum(i+n,  GetCount(i+n, j+n) - GetCount(i+n, j-n-1));
            AddRes(i, j, GetRes(i-1, j) + GetSum(i+n) - GetSum(i-n-1));
        }
        for (int i = 0; i < len1; i++)
        {
            AddRes(i, j, -GetCount(i, j));
        }
    }
    
    return res;
}
1
VTsaregorodtsev
698 / 643 / 104
Регистрация: 19.02.2010
Сообщений: 2,311
09.10.2019, 16:30 5
Shamil1, ну, это только для такой вырожденной функции func, которую ТС задал в стартовом посте.
Как только проверяемое условие начнёт использовать значение самогО элемента (центрального в окне) - всё.
0
Shamil1
Модератор
2341 / 1628 / 365
Регистрация: 26.03.2015
Сообщений: 5,936
09.10.2019, 19:15 6
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Как только проверяемое условие начнёт использовать значение самогО элемента (центрального в окне) - всё.
Согласен. Но ТС явно указал тип функции "Func<T, bool> func" - принимает один аргумент типа элемента и возвращает бул. То есть, за линейное время мы можем из исходной матрицы получить матрицу подсчитываемых значений.
0
alexus5
292 / 148 / 85
Регистрация: 07.01.2016
Сообщений: 394
Завершенные тесты: 4
09.10.2019, 19:23  [ТС] 7
Shamil1, оказывается, это возможно. спасибо за идею.
0
09.10.2019, 19:23
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2019, 19:23

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

Найти в массиве элементы, которые больше двух своих соседей по вертикали / горизонтали и при этом меньше двух других соседей
Помогите пожалуйста!!!задача на java решается находит в массиве A все элементы, которые...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.