21-03-2005 04:08 Программистское
Дан двухмерный квадратны массив short'ов (src). Нужно получить второй двухмерный квадратный массив short'ов (dst), так что dst[i][j] = average(src[i-1][j-1]...src[i+1][j+1]). Реально составить такой алгоритм, чтоб он делал это за один проход каждого элемента в src? (т.е. O(n) с константой 1)
Комментарии:
cpcat
21-03-2005 14:57
Дневник • Хочухи • Профиль
В случае src[0][0] считать src[i-1][j-1] за src[0][0] или за src[max(i)][max(j)]?
флудер-неудачник
А что означает в average(src[i-1][j-1]...src[i+1][j+1]) многоточие?
cpcat
Если в углу, то усреднять 4 поля. Т.е. это доска, а не глобус
MIK
означает усреднять все поля вокруг (всего 9)
Если в углу, то усреднять 4 поля. Т.е. это доска, а не глобус
MIK
означает усреднять все поля вокруг (всего 9)
Камрад
Э... Вообще-то, что бы ты ни делал, будет O(n^2).
Задача стоит в том, чтобы любой ценой обойтись единственным обращением к каждому элементу, или в том, чтобы посчитать быстрее?
Задача стоит в том, чтобы любой ценой обойтись единственным обращением к каждому элементу, или в том, чтобы посчитать быстрее?
Anafay
Well, I consider the total number of elements to be n, not the size of the square.
To count faster. Actually we are already done with it
But the only thing we came up with was that for each element in the destination array we only needed to access 3 elements in the source array, while data for 6 other elements is available from the previous calcucation.
So for element (25,25) we already found the sum of elements (24,24), (24,25), (24,26) , (25,24), (25,25), (25,26) and we only need (26,24) , (26,25) and (26,26). So the total time is in general case would be 3*n.
Well, I consider the total number of elements to be n, not the size of the square.
To count faster. Actually we are already done with it
But the only thing we came up with was that for each element in the destination array we only needed to access 3 elements in the source array, while data for 6 other elements is available from the previous calcucation.So for element (25,25) we already found the sum of elements (24,24), (24,25), (24,26) , (25,24), (25,25), (25,26) and we only need (26,24) , (26,25) and (26,26). So the total time is in general case would be 3*n.
Камрад
Xirax
А тебе надо, чтобы еще меньше было обращений к src? IMHO, с запретом на чтение dst и с запретом на явные или завуалированные хранилища не выйдет.
А тебе надо, чтобы еще меньше было обращений к src? IMHO, с запретом на чтение dst и с запретом на явные или завуалированные хранилища не выйдет.
Anafay
Нету таких запретов :-/
Только src нельзя менять
Нету таких запретов :-/
Только src нельзя менять
Камрад
Xirax
Тогда просто помести dst[i,j]=avg(src[i-1,j],src[i,j],src[i+1,j]) - это один проход по каждому src[i,j]
А потом сделай то же самое внутри dst, по j и без всяких ограничений на количество обращений, которое будет опять же по одному к каждому dst[i,j] на чтение :gigi:
Вариант ( издевательский :gigi:) - сделай временный массив tmp, скопируй в него src и обращайся, сколько угодно к tmp :D
Тогда просто помести dst[i,j]=avg(src[i-1,j],src[i,j],src[i+1,j]) - это один проход по каждому src[i,j]
А потом сделай то же самое внутри dst, по j и без всяких ограничений на количество обращений, которое будет опять же по одному к каждому dst[i,j] на чтение :gigi:
Вариант ( издевательский :gigi:) - сделай временный массив tmp, скопируй в него src и обращайся, сколько угодно к tmp :D