Функция пика в последовательности - оптимизировать код для ускорения его работы - C (СИ)
Формулировка задачи:
Я написала функцию для поиска пика, но программа выполняется примерно 14 сек. Как возможно оптимизировать функцию unsigned long peak(unsigned long nel, int (*less)(unsigned long i, unsigned long j)), чтобы программа выполнялась за 1 сек.
Вот мой код:
#include <stdio.h> int less(unsigned long i, unsigned long j) { if (i == j) return 0; if (i < j) { if (j <= 11241155978086311589UL) return 1; if (i >= 11241155978086311589UL) return 0; return (11241155978086311589UL-i) < (j-11241155978086311589UL); } if (i <= 11241155978086311589UL) return 0; if (j >= 11241155978086311589UL) return 1; return (11241155978086311589UL-j) < (i-11241155978086311589UL); } unsigned long peak(unsigned long nel, int (*less)(unsigned long i, unsigned long j)) { int i,r,b; for (i=0;i<nel-1;i++) { b=i++; r=less(b,i); if (r != 1) break; b=i--; } return i-1; } int main(int argc, char **argv) { unsigned long i = peak(13356955260197607378UL, less); if (i == 11241155978086311589UL) { printf("CORRECT\n"); } else { /* Если функция peak работает правильно, сюда никогда не будет передано управление! */ printf("WRONG\n"); } return 0; }
Решение задачи: «Функция пика в последовательности - оптимизировать код для ускорения его работы»
textual
Листинг программы
unsigned long fast_peak(unsigned long nel, int (*less)(unsigned long i, unsigned long j)) { unsigned long l = 0, r = nel - 1, m; for (;l < r;) { m = (l / 2 + r / 2); if (less(m, m + 1)) { l = m + 1; } else if (less(m, m - 1)) { r = m - 1; } else { return m; } } return l; }
Объяснение кода листинга программы
- Входные данные функции: nel - количество элементов в последовательности; less - функция, сравнивающая два элемента последовательности и возвращающая значение типа int (меньше, равно или больше).
- Создаются три переменные: l - левая граница текущего интервала; r - правая граница текущего интервала; m - середина текущего интервала.
- Начинается цикл, который продолжается до тех пор, пока левая граница интервала меньше правой.
- Вычисляется значение переменной m как сумма делителей на 2 от l и r.
- Если элемент с индексом m меньше следующего за ним элемента (m + 1), то правая граница интервала уменьшается на 1.
- Если элемент с индексом m больше предыдущего элемента (m - 1), то левая граница интервала увеличивается на 1.
- Если элемент с индексом m равен элементам с индексами m-1 и m+1, то функция возвращает значение m.
- Если после цикла значение переменной l остается меньше значения r, то функция возвращает значение l.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д