Есть ли инструмент / решение для программирования цикла, где условие проверяется только каждые X итераций?

Например: у меня есть функция, состоящая из цикла while (этот проверяет простые числа)

function isprime(int number){
int i=2;
int max= (int) sqrt(number)+1;
   while(i<max){
       if(number%i==0){
          return 0;
       }
       i++;
   }
return 1;
}

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

(Быстрый пример 1: Если "число" равно 1009, это будет проверка условия while 30 раз, 30 операций для индекса и 29*2 операций для условия if. Это 118 операций)

Я понимаю, что я могу просто вырезать и вставить в условие while, и индекс будет проходить максимум, что приводит к дополнительным операциям, не искажая возвращаемое значение. Так что, если я обрежу все, начиная с "если..." до "i++;" и вставьте его три (или n) раза, проверяя, что условие while будет занимать только 1/10 (или 1/(1+3n) операций), создавая максимум +2*3(или +(n-1))*3) ненужные операции.

(Быстрый пример 2: если "число" равно 1009, это будет означать проверку условия while 11 раз, 33 операции для индекса и 33*2 операции для условия if. Это 100 операций, на 13 меньше)

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

Есть ли инструмент (или метод, который мне не хватает), чтобы сделать это для меня, но держит код ясно и легко изменить?

Заранее спасибо!

Источник

2 ответа

Решение

Ваш вопрос немного неясен.

Во-первых, вы можете немного изменить свой алгоритм; например, увеличение на 2, а не на 1 (поскольку каждое простое число выше 2 является нечетным).

Затем, когда попросили оптимизировать (например, с g++ -Wall -O2), компилятор обычно выполняет некоторую циклическую развертку, как если бы он "копировал" (и постоянно свернул) тело цикла несколько раз.

С GCC вы можете помочь оптимизатору, например, используя __builtin_expect, например, с

#ifdef __GNUC__
#define MY_UNLIKELY(P) __builtin_expect((P),0)
#else
#define MY_UNLIKELY(P) (P)
#endif

и тогда вы будете кодировать

 if(MY_UNLIKELY(number%i==0))
   return 0;

Наконец, ручная оптимизация вашего кода может не стоить боли, вам следует протестировать. ( Кэш процессора очень важен сегодня, поэтому слишком большое развертывание может замедлить код, см. Также __builtin_prefetch в GCC и это).

Вы также можете рассмотреть возможности метапрограммирования и многоэтапного программирования; в таких языках, как Meta Ocaml или Common Lisp, метапрограммирование означает гораздо больше, чем C++11 template вещи. Вы могли бы рассмотреть возможность создания кода C во время выполнения (тогда dlopen или используя библиотеки JIT-компиляции, такие как libjit (например, сделать частичную оценку). Читайте также блог Дж. Питрата о мета-комбинаторном поиске и вики-страницу на eval. Моя система MELT показывает, что эти методы могут (болезненно) использоваться в связи с C++ (MELT генерирует код C++ во время выполнения, поэтому выполняйте метапрограммирование таким образом).

Источник

Существует странный фрагмент под названием "Устройство Даффа", который применим к случаю, когда вы заранее знаете, сколько итераций должно произойти.

Например, предположим, у вас есть этот цикл:

for (size_t i = 0; i != max; ++i) {
    call(i);
}

С устройством Даффа вы можете преобразовать его, чтобы проверять только каждые 4 итерации, например так:

size_t i = 0;

switch (max % 4) {
case 0: do { call(i++);
case 3:      call(i++);
case 2:      call(i++);
case 1:      call(i++);
           } while (i != max);
}

Таким образом, он сочетает ручное развертывание с компенсацией того факта, что количество итераций может не быть кратным числу раз, которое вы развернули. Здесь есть больше объяснений.

Хотя лично я бы посоветовал использовать немного более четкий формат:

// Adjust "max" to a multiple of N:
size_t const adjusted_max = (max + N - 1) / N * N;
size_t const leftover_max = max - adjusted_max;

for (size_t i = 0; i != adjusted_max; i += N) {
    call(i);
    call(i);
    // N times
}

switch (leftover_max) {
case N-1: call(adjusted_max + N - 1);
case N-2: call(adjusted_max + N -2);
...
case 1  : call(adjusted_max);
case 0  : ;
}

Обратите внимание, что вы можете обработать остаток до или после, это не имеет значения.

При этом Loop Unrolling является базовой оптимизацией компилятора; поэтому, прежде чем использовать такую ​​странную реализацию, проверьте, не будет ли ваш компилятор делать это за вас...

Источник
Другие вопросы по тегам