Задача:
Дан двумерный массив 1000 x 1000, нужно разделить его на квадраты по 4 элемента в каждом. Из каждой четверки нужно выбрать максимальный и на основе этих элементов получить новый массив, затем полученный массив нужно также обработать. Эти действия повторяются до тех пор, пока не останется всего один элемент в массиве.

Как можно оптимизировать задачу????

прежде чем оптимизировать, нужно иметь хотя бы
один алгоритм решения :) ты на чем остановился ?

да и, кстати, как массив то представлен ?
строка за строкой подряд ? и какой размер элементов, DWORD, BYTE ?

Задачу моджно оптимизировать:
1. по скорости
2. по размеру

:)

Задача нерешаемая, т. к. размер массива должен быть степенью двойки (Array[2^n][2^n]), иначе один элемент никогда не останется
Если же задача будет соответствовать этому условию, тогда просто ищи наибольший элемент массива

Loger прав. Решение для задачи с приведенными условиями настолько очевидно, что я плачу :))))))

HeDiN

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

В условии задачи отсутствует конечная цель.
Непонятно, что нужно получить - один элемент в массиве или все промежуточные массивы.
Как её можно решить исходя из этого?
Не понятно так же, как будет делиться этот массив на четвёрки.
Например, можно ввести дробные индексы и округлять их при доступе к элементам (перекрывающиеся квадраты)
Или принять, что элементы выходящие за пределы равны 0.
Если по условию нужно разделить, то можно разделить :).


ЗЫ
Если это прикол, то что он делает в A&O..

Нет, это не прикол.
Я не верно выразился. Оптимизировать пока нечего. Был у меня код, но он на Delphi, а перевести эго на асм руки не доходят. Про размер вы правы, я просто цифры округлил, на самом деле размер это не самое важно (можно эго привести к нужному, заполнив нулями недостающую область). Оптимизация должна быть по скорости это однозначно.
И еще одна маленькая не точность - выбирать нужно минимальный элемент.
Loger смысл ты понял, но мне нужны все промежуточные результаты. Т.е. массивы образуют своего рода пирамиду, где в основании лежит исходный массив, а вершиной является наименьший элемент этого массива.
S_T_A_S_ массив двумерный и индексы целые числа (в Delphi было, во всяком случае, так).
Для наглядности можете посмотреть архив, там картинка, по которой все станет понятно (я надеюсь).

Никто не знает что за глюк? При правке сообщения нельзя добавить аттач

200561445__img.rar

Поскольку оптимизировать пока нечего, наверное, стоит определиться с основами алгоритма.
Формат хранения какой? Как написАл Funbitили его можно менять?

Я так понял, что полученные массивы должны быть оптимизированны для дальнейшего использования..
то есть данная выборка не самое узкое место в программе.
Если это так, то есть ли смысл оптимизировать это.
Проблема в том, что на первом проходе предётся обработать 5Мб памяти, на втором 1,25..
Только с третьего-четвёртого прохода оба массива будут помещаться в кеш и появится(?) смысл оптимизировать сами команды.

При обычном хранении данных imho лучше попробовать так -
берём четвёрку, выбираем один элемент, запоминаем.
Повторяем для 3х четвёрок рядом.
Из полученной четвёрки опять выбираем один, так же ищем ещё три.
И т.д.
Возможно, так уменьшится нагрузка на кеш, по сравнению с перебором всего первого массива, затем второго..
Хотя может и нет - надо же проверять :).

Реализация на C такая
void DivideArray(long * lpInputArray,long * lpOutputArray,unsigned long outputSize){
for (unsigned long i=0,i<outputSize;i++){
for (unsigned long j=0;j<outputSize;j++){
lpOutputArray[i,j]=MIN(MIN(lpInputArray[i*2][j*2],lpInputArray[i*2+ 1][j*2]),MIN(lpInputArray[i*2][j*2+1],lpInputArray[i*2+1][j*2+1]))
}
}
}

Ну и где тут оптимизация, если цикл в цикле?
И что такое MIN?

#define MIN(a,b) ((a>b)?b:a)
А оптимизация зависит от
1. Типа данных, которыми заполнен массив
2. Наборов используемых инструкций
3. По скорости или по размеру

Переписать для одного счётчика не проблема

void DivideArray(long * lpInputArray,long * lpOutputArray,unsigned long outputSize)
{ 
for (unsigned long i=0,i<(outputSize*outputSize);i++)
{ 
lpOutputArray[i]=MIN(MIN(lpInputArray[(i/outputSize)*outputSize*4
+(i%o utputSize)*2],lpInputArray[(i/outputSize)*outputSize*4
+(i%outputSize)* 2+1]),MIN(lpInputArray[(i/outputSize)*outputSize*4
+(i%outputSize)*2
+ou tputSize*2],lpInputArray[(i/outputSize)*outputSize*4+(i%outputSize)*2
 
+ outputSize*2+1])) 
} 
}

Только вот будет ли от этого понятней?

Переписать для одного счётчика не проблема

В данном случае, что в лоб, что по лбу.
Не вижу разницы между:

for (unsigned long i=0,i<outputSize;i++){ 
for (unsigned long j=0;j<outputSize;j++){ 

и

i<(outputSize*outputSize);

Если outputSize - константа или степень 2, разница есть

В чем она?