LINUX.ORG.RU

Почему 1 алгоритм работает в 100-200 раз быстрее другого.


0

1

Сумма делителей числа. Помогите разложить на элементарные комманды. Алгоритм 1

public static int summ_of_del2(int num) {
        int summ = 0;
        int max_del = num;
        int cur_del = 2;
        while (cur_del < max_del) {
            if (num % cur_del == 0) {
                max_del = num / cur_del;
                summ += cur_del;
                summ += max_del;
            }
            cur_del++;
        }
        summ = summ + 1;
        return summ;
    }
Алгоритм 2:
    public static int summ_of_del3(int num) {
        int summ = 0;
        int m = (int) Math.sqrt(num);
        int tmp;
        for (int k=2; k <= m; ++k) {
            if (num % k==0) {
                summ += k;
                tmp = num / k;
                if (k != tmp) {
                    summ += tmp;
                }
            }
        }

        return summ;

    }


а какой быстрее? первый?

по идее если много делителей то например оно на 10 шагу может в 10 раз сократить перебор :) и так далее.

olegsov
()
Ответ на: комментарий от olegsov

Куда в первый алгоритм добавлять корень? Там другое условие выхода. Количество циклов они проходят абсолютно одинаковое. Жду знающих людей. А работает быстрее второй алгоритм.

vsrmis
() автор топика

Как собирал программу? Ключи тоже покажи.

Zodd ★★★★★
()
Ответ на: комментарий от vsrmis

Количество циклов они проходят абсолютно одинаковое

Нет, не одинаковое: http://codepad.org/T9Edvohe

Почему?
Второй алгоритм всегда перебирает sqrt(num) делителей.

Первый алгоритм перебирает N >= sqrt(num) делителей, т.к.

cur_del >= num / previous_del

верно, только если cur_del >= sqrt(num).

Кроме того, в худшем случае первый алгоритм переберет num делителей.

user_2190
()

вот ты перебираешь все возможные делители начиная с 2.

при этом для каждого найденного делителя ты находишь еще один делитель БОЛЬШЕ найденного делителя.

дойдя до корня, ты уже не нейдешь тех делителей, которые ты не нашел до этого, ибо они все будут больше их парного делителя, а их ты уже перебрал.

следовательно нет смысла идти дальше корня.

второй алгоритм это учитывает.

а первый алгоритм устанавливает верхний предел, который ВСЕГДА выше корня до того как ты дойдешь корня. то есть это бессмысленно.

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

насчет разницы в 100-200 раз - очевидно — если взять простое число более 200**2, то первый будет перебирать вообще все варианты, а второй только до корня, то есть более чем в 200 раз меньше.

olegsov
()
Ответ на: комментарий от user_2190

Спасибо, понятно. Да действительно не учёл это.

vsrmis
() автор топика
Ответ на: комментарий от olegsov

вывод - второй алгоритм глупый

Согласен :) Только вы, наверное, имели в виду первый.

user_2190
()
Ответ на: комментарий от Zodd

Собери с оптимизацией -02 и будет одинаково.

С каких пор компиляторы стали умнее программиста, что умеют заменить

int cur_del = 2;
на
int cur_del = (int) Math.sqrt(num);
?

Dragon59 ★★
()
Ответ на: комментарий от Dragon59

Я к тому, что такая большая разница должна уменьшится.

Хотя сейчас проверил — у меня не получается разница в 100-200 раз. ТС как замерял?

Zodd ★★★★★
()

Почему 1 алгоритм работает в 100-200 раз быстрее другого.

Потому что это разные алгоритмы. Ваш К.О.

P.s. прежде чем сравнивать скорость - проверьте корректность :)

MKuznetsov ★★★★★
()
Ответ на: комментарий от vsrmis

работает быстрее второй алгоритм.

подозреваю unroll-loops. объяснить не могу :/

aol ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.