Функция пика в последовательности - оптимизировать код для ускорения его работы - 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;
}

Объяснение кода листинга программы

  1. Входные данные функции: nel - количество элементов в последовательности; less - функция, сравнивающая два элемента последовательности и возвращающая значение типа int (меньше, равно или больше).
  2. Создаются три переменные: l - левая граница текущего интервала; r - правая граница текущего интервала; m - середина текущего интервала.
  3. Начинается цикл, который продолжается до тех пор, пока левая граница интервала меньше правой.
  4. Вычисляется значение переменной m как сумма делителей на 2 от l и r.
  5. Если элемент с индексом m меньше следующего за ним элемента (m + 1), то правая граница интервала уменьшается на 1.
  6. Если элемент с индексом m больше предыдущего элемента (m - 1), то левая граница интервала увеличивается на 1.
  7. Если элемент с индексом m равен элементам с индексами m-1 и m+1, то функция возвращает значение m.
  8. Если после цикла значение переменной l остается меньше значения r, то функция возвращает значение l.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 4 из 5
Похожие ответы