Как уменьшить повторное использование оператора % для более быстрого выполнения в C

avatar
Arbaz
9 августа 2021 в 04:09
163
4
0

Это код -

for (i = 1; i<=1000000 ; i++ ) {
      for ( j = 1; j<= 1000000; j++ ) {
         for ( k = 1; k<= 1000000; k++ ) {   
             if (i % j == k && j%k == 0) 
                  count++;
          }
      }
}

или лучше сократить любую операцию %, которая выполняется до миллиона раз в любой программе??

редактировать- извините , инициализируется 0, скажем, i = 1 ok!

теперь, если я уменьшу третий цикл как ответ @darshan, тогда оба первых && второй цикл может выполняться до N раз

, а также вычисляет % , n*n раз. ex- 2021 mod 2022 , затем 2021 mod 2023 .........и так далее

итак, мой вопрос - модуль % в два раза (а может и больше) тяжелее по сравнению с +, - так что здесь можно реализовать любую другую логику ?? который является альтернативой для этого вопроса. и дает тот же ответ, что и эта логика..

Большое спасибо за компетентные комментарии и помощь-

Вопрос:

3 целых числа (A,B,C) считаются особыми, если они удовлетворяют следующие свойства для данного целого числа N :

A mod B=C
B mod C=0
1≤A,B,C≤N 

Мне так любопытно, есть ли какое-либо другое умнейшее решение, которое может значительно уменьшить временную сложность.

Источник
Nathan Pierson
9 августа 2021 в 04:15
3

Вы также можете изменить порядок самых внутренних циклов, чтобы j увеличивалось на k за раз вместо 1 за раз. Почти наверняка есть какой-то теоретико-числовой способ вычислить это количество, которое намного быстрее, чем O (n ^ 3), хотя это может не иметь большого значения.

cup
9 августа 2021 в 04:18
0

Начните цикл j с i и начните цикл k с j.

risingStark
9 августа 2021 в 04:18
0

Эта программа никогда не перестанет выполняться. Это O (n ^ 3), а n слишком велико. Почитайте про временную сложность. Какой изначальный вопрос?

paddy
9 августа 2021 в 04:23
9

Никого не беспокоит очевидное деление на ноль в этом коде?

Nathan Pierson
9 августа 2021 в 04:24
0

На самом деле, расширяя мой комментарий выше, мы можем еще больше изменить порядок циклов - сделать i самым внутренним циклом, начиная с k и каждый раз увеличивая на j. Затем при каждом выполнении внутреннего цикла мы можем безоговорочно увеличивать count, и теперь, чтобы получить фактический ответ, нам просто нужно вычислить длину каждого цикла.

sweenish
9 августа 2021 в 04:27
2

@risingStark Есть большая разница между «никогда не останавливаться» и «долго ждать». Хорошо сформированный код O (n ^ 3) завершится.

Retired Ninja
9 августа 2021 в 04:28
4

@paddy Деление на ноль значительно сокращает время выполнения.

risingStark
9 августа 2021 в 04:35
0

@sweenish Я согласен, но вы поняли. Я не знаю, просто подсознательно преувеличиваю, может быть, потому что я регулярно практикую конкурентное кодирование, и от одного взгляда на O(n^3) у меня побежали мурашки.

Yakk - Adam Nevraumont
9 августа 2021 в 04:47
0

@swee 10 ^ 18 циклов занимает около 10 ^ 9 секунд или порядка 30 лет. Так что нет, большой разницы нет; среднее время до отказа почти любой компьютерной системы намного меньше (отключение питания, отказ оперативной памяти и т. д.).

Jeremy Friesner
9 августа 2021 в 04:57
0

Первое, что я бы сделал, это закомментировал бы самое внутреннее, если полностью, и измерил бы, сколько времени занимает программа без вызовов оператора %. Это дало бы вам верхнюю границу/сценарий наилучшего случая для производительности (при условии, что это не позволяет компилятору заменить всю программу возвратом константы времени компиляции, конечно)

Daniel Langr
9 августа 2021 в 06:17
0

@JeremyFriesner Если вы удалите if, компилятор, скорее всего, оптимизирует все циклы в одно добавление: godbolt.org/z/xPhcdfjeq.

Jeremy Friesner
9 августа 2021 в 06:30
0

@DanielLangr да, именно об этом была моя скобка. И действительно умный оптимизатор мог бы сделать это даже при наличии if, поскольку в программе нет ничего, что нельзя было бы вычислить во время компиляции.

Clifford
9 августа 2021 в 07:10
0

Здесь нет реального оправдания тегу [embedded] или даже C++17, если уж на то пошло.

Lundin
9 августа 2021 в 07:53
0

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

Arbaz
9 августа 2021 в 12:31
0

@Yakk-AdamNevraumont да, согласен. это не просто 10 или 100. Что, если мы представим N как десятки миллионов. я должен пытаться заменить арифметику каждый раз, в основном */% в каждом решении, чтобы увидеть, насколько это может повлиять на временную сложность.

Clifford
9 августа 2021 в 13:29
0

@Arbaz: Возможно, но проблемы с производительностью не уникальны ни для одного из них, и это может просто сузить вашу аудиторию. Дело в том, что в этом вопросе нет ничего особенного для встроенных систем. Удаление циклически инвариантных выражений из вычисления в цикле является фундаментальным принципом.

sweenish
9 августа 2021 в 15:32
0

@Yakk-AdamNevraumont Если я предполагаю, что одно ядро ​​​​4 ГГц сойдет с ума, я получу 8 лет. Так как он сможет выполнять 4*10^9 инструкций в секунду. Если моя математика исключает что-то важное, дайте мне знать. Во всяком случае, я говорил вообще об общем утверждении. Я не одобряю крайне неэффективный код.

Yakk - Adam Nevraumont
9 августа 2021 в 15:37
0

@sweenish У вас есть сравнение циклов, приращение и т. Д .; Я предполагаю 1 итерацию короткого цикла каждые 10^-9 секунд, т.е. 4-6 циклов на цикл. На практике да, вы можете отказаться от SIMD или чего-то подобного и повысить пропускную способность, но даже в этом случае фактор скромный. Я хочу сказать, что неэффективный алгоритм с большим размером входных данных эквивалентен «навсегда», потому что среднее время до отказа оборудования не так уж велико, если вы говорите об алгоритмах O (n ^ 3) или хуже.

Craig Estey
9 августа 2021 в 19:32
0

Я голосую за повторное открытие, потому что пример самодостаточен, и есть четкие ответы на его упрощение и повышение скорости. Это/было бы поучительно для других, потому что [хорошие] ответы говорят о рефакторинге алгоритма. (т. е.) Не все ускорения являются просто настройками, но иногда требуется переписывание.

Ответы (4)

avatar
Marek R
11 августа 2021 в 14:05
0

Просто измените порядок индексации и рассчитайте A на основе ограничений:

void findAllSpecial(int N, void (*f)(int A, int B, int C))
{
    // 1 ≤ A,B,C ≤ N 
    for (int C = 1; C < N; ++C) {
        // B mod C = 0 
        for (int B = C; B < N; B += C) {
            // A mod B = C
            for (int A = C; A < N; A += B) {
                f(A, B, C);
            }
        }
    }
}

Без деления не бесполезно if только для циклов и операций сложения.

avatar
Michael Veksler
9 августа 2021 в 12:37
1

Во-первых, ваш код имеет неопределенное поведение из-за деления на ноль: когда k равно нулю, тогда j%k не определено, поэтому я предполагаю, что все ваши циклы должны начинаться с 1, а не 0.

Обычно операторы % и / выполняются намного медленнее, чем любая другая операция. Можно избавиться от большинства вызовов операторов % в вашем коде, выполнив несколько простых шагов.

Во-первых, посмотрите на строку if:

if (i % j == k && j%k == 0)

i % j == k имеет очень строгое ограничение по сравнению с k, что играет вам на руку. Это означает, что перебирать k вообще бессмысленно, так как есть только одно значение k, удовлетворяющее этому условию.

for (i = 1; i<=1000000 ; i++ ) {
      for ( j = 1; j<= 1000000; j++ ) {
         k = i % j;
         // Constrain k to the range of the original loop.
         if (k <= 1000000 && k > 0 && j%k == 0)
                  count++;
      }
}

Чтобы избавиться от "i % j", переключите цикл. Это изменение возможно, так как на этот код влияет только то, какие комбинации i,j проверяются, а не в том порядке, в котором они вводятся.

for ( j = 1; j<= 1000000; j++ ) {
      for (i = 1; i<=1000000 ; i++ ) {
         k = i % j;
         // Constrain k to the range of the original loop.
         if (k <= 1000000 && k > 0 && j%k == 0)
                  count++;
      }
}

Здесь легко наблюдать за тем, как ведет себя k, и использовать это для итерации k напрямую без итерации i и, таким образом, избавления от i%j. k выполняет итерацию от 1 до j-1, а затем делает это снова и снова. Итак, все, что нам нужно сделать, это перебрать k непосредственно в цикле i. Обратите внимание, что i%j вместо j == 1 всегда равно 0, а поскольку k==0 не удовлетворяет условию if, мы можем безопасно начать с j=2, пропустив <3390999>2103324

for ( j = 2; j<= 1000000; j++ ) {
      for (i = 1, k=1; i<=1000000 ; i++, k++ ) {
         if (k == j)
            k = 0;
         // Constrain k to the range of the original loop.
         if (k <= 1000000 && k > 0 && j%k == 0)
                  count++;
      }
}

По-прежнему бесполезно повторно запускать j%k для одних и тех же значений j,k (помните, что k повторяется несколько раз во внутреннем цикле). Например, для j=3 значения i и k идут {1,1}, {2,2}, {3,0}, {4,1}, {5,2},{6,0},... {n*3, 0}, {n*3+1, 1}, {n*3+2, 2},... (для любого значения n в диапазоне 0 < n <= (1000000-2)/3).

Значения за пределами n= floor((1000000-2)/3)== 333332 сложны — давайте посмотрим. Для этого значения n, i=333332*3=999996 и k=0, поэтому последняя итерация {i,k}: {n*3,0},{n*3+1,1},{n*3+2, 2} становится {999996, 0}, {999997, 1}, {999998, 2}. Вам действительно не нужно перебирать все эти значения n, так как каждое из них делает одно и то же. Все, что вам нужно сделать, это запустить его только один раз и умножить на количество допустимых значений n (в данном случае это 999996+1 — добавление 1 для включения n=0).

Поскольку это не охватывает все элементы, необходимо продолжить остальные значения: {999999, 0}, {1000000, 1}. Обратите внимание, что в отличие от других итераций здесь нет третьего значения, так как оно установило бы i вне допустимого диапазона.

for (int j = 2; j<= 1000000; j++ ) {
      if (j % 1000 == 0) std::cout << std::setprecision(2) << (double)j*100/1000000 << "%  \r" << std::flush;
      int innerCount = 0;
      for (int k=1; k<j ; k++ ) {
         if (j%k == 0)
             innerCount++;
      }
      int innerLoopRepeats = 1000000/j;
      count += innerCount * innerLoopRepeats;
      // complete the remainder:
      for (int k=1, i= j * innerLoopRepeats+1; i <= 1000000 ; k++, i++ ) {
         if (j%k == 0)
             count++;
      }

}

Это по-прежнему очень медленно, но, по крайней мере, выполняется менее чем за день. Можно получить дальнейшее ускорение, используя важное свойство делимости. Рассмотрим первый внутренний цикл (это почти то же самое для второго внутреннего цикла), и обратите внимание, что он выполняет много избыточной работы и делает это дорого. А именно, если j%k==0, это означает, что k делит j и существует пара K такая, что pairK*k==j. Пара k вычисляется тривиально:pairK=j/k.

Очевидно, что для k > sqrt(j) существует пара K < sqrt(j). Это означает, что любое k > sqrt(j) может быть извлечено просто путем сканирования всех k < sqrt(j). Эта функция позволяет вам перебрать только квадратный корень из всех интересных значений k. Поиск только значений sqrt(j) дает огромный прирост производительности, и вся программа может завершиться за считанные секунды.

Вот вид второго внутреннего цикла:

      // complete the remainder:
      for (int k=1, i= j * innerLoopRepeats+1; i <= 1000000 && k*k <= j; k++, i++ ) {
         if (j%k == 0)
         {
             count++;
             int pairI = j * innerLoopRepeats + j / k;
             if (pairI != i && pairI <= 1000000) {
                    count++;
             }
         }
      }

Первый внутренний цикл должен пройти аналогичное преобразование.

avatar
HARSH MITTAL
9 августа 2021 в 04:49
-1

Ниже приведена очевидная оптимизация: Третий цикл с «k» действительно не нужен, так как уже есть отображение «многие в один» из (I, j) -> k

Из кода я понял, что вы хотите вычислить количество пар (i,j) так, что (i%j) является коэффициентом j. Это правильно или я что-то упустил?

Arbaz
9 августа 2021 в 12:55
0

как вы получили такую ​​пару i,j,k, что i%j=k и j%k=0

avatar
Darshan V
9 августа 2021 в 04:49
1

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

for(i = 0; i<=1000000 ; i++ ) 
     for( j = 0; j<= 1000000; j++ ) 
     {
          a = i%j;
          for( k = 0; k <= j; k++ )   
             if (a == k && j%k == 0) 
                  count++;
      }

Мы поместили a = i%j во второй цикл, потому что нет необходимости вычислять его каждый раз при изменении k, так как он независим от k и для условия j%k == 0, чтобы быть правдой, k должно быть <= j, следовательно, измените ограничения цикла

Frank
9 августа 2021 в 12:23
0

Вы уверены, что это на самом деле делает код быстрее? Поднятие a из внутреннего цикла — это то, что я ожидаю от компилятора. Показательный пример: clang создает точно такую ​​же сборку: gcc.godbolt.org/z/aE5jvEdW1.

Arbaz
9 августа 2021 в 12:40
0

да, я понял. Но хотя логика такая же, как и при вычислении%, она не может сократить мое время более чем на 0,00143 секунды за 10 ^ 5. мое время выполнения составляет 0,512 ~ и занимает столько же, сколько 0,51111

Frank
9 августа 2021 в 12:51
0

@Arbaz «логика такая же, как вычисление%» Не совсем так. Это изменение действительно удаляет МНОГО вызовов %. Причина, по которой скорость одинакова, заключается в том, что это изменение уже было сделано за вас компилятором в вашем исходном коде.

Clifford
9 августа 2021 в 13:38
1

@Frank Да, если вы примените -O3, инвариант цикла будет оптимизирован. На самом деле это не честный тест фундаментальной временной сложности написанного кода, а тест оптимизатора. Тот факт, что оптимизатор может спасти вас от неэффективного кода, не означает, что вы должны писать преднамеренно неэффективный код.

Clifford
9 августа 2021 в 13:42
0

При выражении, как указано выше, кажется, что внутренний цикл (k) можно полностью исключить, поскольку ничего не происходит, кроме как a == k. Весь внутренний цикл может быть ограничен: if(j % (i%j) == 0 ) count++ ;