Есть массив ( вмоем случае трехмерный, но не в этом суть). В нем необходимо найти определенное количество минимальных элементов (процент). И обнулить их.
Как это можно сделать с минимальными затратами ресурсов?

Массив в моем случае 512*512*3 of double.

Вероятно надо использовать сортировку и потом уже отбор и обнуление. Причем часть методов сортировки позволяют не доводить сортировку до конца (достаточно отобрать требуемый процент минимальных либо максимальных), к тому же в зависимости от заданного процента более эффективно сортировать с бОльших либо с мЕньших...
PS. Несколько проще, если все элементы - заведомо положительные.

Нет, элементы есть и отрицательные. И вообщето необходимо обнулять не минимальные, а ближайшие к нулю по модулю.

Я бы сделал так:

1. По проценту вичисляешь сколько элементов будет в новом массиве
t = (процент/100)*512*512*3
2. Создаешь массив x (double) этого размера
3. Записываешь туда первые t чисел
4. сортируешь x по порядку уменьшения
6. n=0, t++
6. если t+n число меньше самого большого (первого в массиве), то заменяешь это число t+n-ым числом
4. сортируешь x по порядку уменьшения (методом: менять местами рядом стоящие элементы массива, пока x[y] < x[y+1])
8. n++
9. продолжаешь в 6.

По массиву 512*512*3 надо идти не в цикле по принципу [x][y][z], а прибавляя к указателю 8 (если не ошибаюсь).

HalkaR

Цитата

необходимо обнулять не минимальные, а ближайшие к нулю по модулю.

т.е. фактически сортировать надо не элементы массива, а их абс. величины. впрочем пофиг.

cardinal

Цитата

По проценту вычисляешь сколько элементов будет в новом массиве t = (процент/100)*512*512*3

если процент более 50 - то брать есссно 100-процент... (above) - т.о. наибольшее время поиска таким методом - при процент около 50...

HalkaR
на такого размера массиве прекрасно работает quicksort. Размер массива - порядка 6 Мб, не разговор... впрочем если нет проблем по памяти, лучше имхо использовать сортировку двоичным деревом... см. http://algolist.manual.ru/sort/faq/q7.php и http://algolist.manual.ru/sort/faq/q8.php

Находишь элемент который занимает место на 10 проценте(10 месте из 100) все остальные делишь+умножаешь на него.

2Cardinal

Цитата

6. если t+n число меньше самого большого (первого в массиве), то заменяешь это число t+n-ым числом

Алтернатива: путём бинарного поиска находим "место" елемента t+n в массиве x.
Потом сдвигаем весь массив влево (если слева большие числа). пункт 7 тогда отпадает..

2Akina
Обычный инженерный подход - исползовать 100% работающую компоненту (сортировку). Но возможность использования сортировки думаю была всем понятна с самого начала.

Алгоритмом однако является именно то, что предложил Cardinal.


Это сообщение отредактировал(а) sergej.z - 22.4.2004, 00:25

sergej.z

Цитата

Алгоритмом однако является именно то, что предложил Cardinal.

Осмелюcь возразить - речь идет об ОПТИМАЛЬНОМ РЕШЕНИИ задачи. Алгоритм cardinal, вне всякого сомнения, решает именно нужную задачу - но заведомо неоптимально... o(n*n) и o(n*Log(n)) - вещи суть разные...

Цитата

если процент более 50 - то брать есссно 100-процент... (above) - т.о. наибольшее время поиска таким методом - при процент около 50...

Akina, это правильное замечание.

Цитата

Алгоритм cardinal, вне всякого сомнения, решает именно нужную задачу - но заведомо неоптимально... o(n*n) и o(n*Log(n)) - вещи суть разные...

Насчет этого подумаем...

Попробуем все.

Ну тогда и думать не надо. HalkaR нам потом все, что ему profiler сказал, расскажет

Быстрая сортировка очень хорошо показала себя. Для массива порядка 512*512*3 элементов of double время сортировки несколько секунд.

Кардинал, твой алгоритм хорош, но больше всего времени отнимает пункт 4, поскольку я нашел хороший метод сортировки разница между твоим алгоритмом и чистой быстрой сортировкой очень маленькая (с секундомером не стоял, но мелочь).

Вобщем я взял почти неизменный алгоритм с algolist.

НО.

Код

typedef double item;       /* Тип сортируемых элементов */ typedef int tblIndex;   /* Тип ключей, по которым сортируем */ tblIndex partition(double *a, tblIndex lb, tblIndex ub) {     item t, pivot;    tblIndex i, j, p;   /**********************************    *  разделение массива a[lb..ub]  *    **********************************/    /* Выбираем центр - pivot */    p = lb + ((ub - lb)>>1);    pivot = a[p];    a[p] = a[lb];    /* сортируем lb+1..ub относительно центра */    i = lb+1;    j = ub;    while (1) {        while (i < j && compGT(pivot, a[i])) i++;        while (j >= i && compGT(a[j], pivot)) j--;        if (i >= j) break;        t = a[i];        a[i] = a[j];        a[j] = t;        j--; i++;    }    /* центр в a[j] */    a[lb] = a[j];    a[j] = pivot;    return j; } void quickSort(double *a, tblIndex lb, tblIndex ub) {    tblIndex m;   /**************************    *  сортируем  a[lb..ub]  *    **************************/    while (lb < ub) {        /* разделение пополам */        m = partition (a, lb, ub);        /* Уменьшаем требования к памяти:    */        /*  меньший сегмент сортируем первым */        if (m - lb <= ub - m) {            quickSort(a, lb, m - 1);            lb = m + 1;        } else {            quickSort(a, m + 1, ub);            ub = m - 1;        }    } }

Вот функция сравнения

Код

bool compGT(double a, double b){return (a<b);}

Но мне нужно отсортировать по модулю.

Код

bool compGT(double a, double b){return (abs(a)<abs(b));}

В результате получается кривоватая сортировка. Я чегото не понимаю?

Код

while (1) {       while (i < j && compGT(pivot, a[i])) i++;       while (j >= i && compGT(a[j], pivot)) j--;       if (i >= j) break;       t = a[i];       a[i] = a[j];       a[j] = t;       j--; i++;   }

Это бы на asm переписать надо. compGT по крайней мере надо сделать inline.

Цитата

В результате получается кривоватая сортировка

Это примерно как?

quickSort это конечно жорошо, но... как бы так cказать... Плохо вобщем Тут и quickSort рекурсивно вызывается и фунция функцию погоняет. Я думаю, что если все таки написать как я предложил, то будет быстрее. Если у тебя что-то осталось от того, что ты уже написал, то покажи, может чего можно подправить.

Не намного быстрее. Выигрыш в пару секунд мне сейчас не так важен, как достаточно простой код. Сортировку все равно не выкинешь.

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

Цитата

Цитата В результате получается кривоватая сортировка Это примерно как?

Вобщем массив сортируется. Т.е. в начале нули, потом побольше, побольше, но

Код

0.5 0.5 -0.75 0 -0.5 0 0 0.5 0 0 0 0 0 0 0.5 0.5 0 0 0 0 0.5 0 0 0 0 0 0.5 0.5 0

B это в том случае если

Код

bool compGT(double a, double b){return (abs(a)<abs(b));}

или в этом случае:

Код

bool compGT(double a, double b){return (a<b);}

тоже?
А inline попробовал? Время ты profiler'ом мереешь или секундомером?

Это в первом случае.
Во втором все нормально.

Время замеряю на глаз - мне разница в долях секунды не важна.

Странно...

А если функцию

Код

bool compGT(double a, double b){return (abs(a)<abs(b));}

переписать в

Код

bool compGT(double a, double b) {   bool cmpr;   cmpr = abs(a) < abs(b);   return cmpr; }

бесполезно

Ну что-то я ничего не понимаю. Ты же сам как бы подтвердил, что проблема именно в abs. Значит дело вот в этой функции... Вот нонсенс...

... О, доперло! Пиши так:

Код

bool compGT(double a, double b){return (fabs(a)<fabs(b));}

У тебя же double, а не int - соответственно fabs, а не abs

cardinal , СПАСИБО!!!!!!!!!!