Оптимизация кода C

Предположим, у нас есть массив чисел, скажем, {1,2,3}, и мы хотим выровнять числа за наименьшее количество возможных оборотов; где определение "поворота" выглядит следующим образом:

В свою очередь, вам нужно зафиксировать значение одного из элементов как есть, и увеличить каждое другое число на 1.

Учитывая, например. уже упоминалось - A={1,2,3}, цель состоит в том, чтобы выровнять их. Что я уже сделал, так это сформулировал логику, т.е. метод использования минимального числа ходов состоит в выборе максимального числа в каждом повороте.

Итерация 1: удерживайте A[2]=3. Массив в конце итерации => {2,3,3}

Итерация 2: удерживайте A[2]=3. Массив в конце итерации => {3,4,3}

Итерация 3: удерживайте A[1]=4. Массив в конце итерации => {4,4,4}

Итак, число пройденных оборотов = 3

Код, который я написал, выглядит следующим образом:

#include<iostream>
#include<stdio.h>

int findMax(int *a,int n)
{
    int i,max;
    max=1;
    for(i=2;i<=n;i++)
    {
        if(a[i]>a[max])
        {
            max=i;
        }     

    }
    return max;
}

int equality(int *a,int n)
{
    int i;
    for(i=1;i<n;i++)
    {
        if(a[i]!=a[i+1]) return 0;
    }
    return 1;
}

int main()
{
    int a[100],i,count,t,posn_max,n,ip=0;
    scanf("%d",&t);
    while(ip<t)
    {
        count=0;
        scanf("%d",&n);

        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        while(equality(a,n)==0)
        {
            posn_max=findMax(a,n);

            for(i=1;i<=n;i++)
            {
                if(i!=posn_max)
                {
                    a[i]=a[i]+1;
                }
            }
            count++;

        }
        printf("%d\n",count);
        ip++;
    }
    return 0;
}

Это дает мне правильный ответ, который мне нужен. Но я хочу оптимизировать его дальше.

Мое ограничение по времени составляет 1,0 с. Но сайт судьи говорит мне, что мой код занимает 1,01 с. Может кто-нибудь мне помочь?

Насколько я вижу, я использовал операторы scanf/printf по сравнению с cout/cin, чтобы оптимизировать часть ввода / вывода. Но что еще я должен делать лучше?

Источник

5 ответов

Решение

В вашем алгоритме вы увеличиваете все числа в ожидании максимума.

Если вы делаете это наоборот, уменьшая максимум и оставляя остальные числа, результат должен быть таким же (но с гораздо меньшими операциями с памятью / массивом)!

Чтобы сделать это еще быстрее, вы можете полностью избавиться от операций с памятью (как это было предложено также Ивайлом Странджевым): найдите минимальное число и, исходя из идеи выше (уменьшая числа вместо увеличения), вы знаете, сколько уменьшений требуется для уменьшения все числа к этому минимальному числу. Итак, после нахождения минимума вам понадобится одна петля для расчета количества витков.

Возьми свой пример {1,2,3}

  • Минимум 1
  • Количество оборотов: (1-1)+(2-1)+(3-1) = 0 + 1 + 2 = 3

Если вы действительно сообразительны, вы можете рассчитать количество оборотов непосредственно при вводе чисел и отслеживании текущего минимального числа... Попробуйте!;)

Источник

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

Источник

Помимо других комментариев, если я правильно понял, и ваш код немного слишком медленный, вот две оптимизации, которые должны вам помочь.

Во-первых, вы можете объединить равенства () и findMax() и сканировать только один раз в массиве вместо вашего текущего наихудшего случая (дважды).

Во-вторых, вы можете разделить петлю "увеличения" на две части (ниже и выше максимальной позиции). Это устранит усилие, чтобы проверить положение в петле.

Источник

1) Попробуйте развернуть петли 2) Можете ли вы использовать SIMD инструкцию? Это действительно ускорит этот код

Источник

Я мог бы printf в отдельном потоке, так как это операция ввода-вывода и намного медленнее, чем ваши вычисления.

Это также не требует сложного управления, например, очередь производитель-потребитель, так как вы передаете только упорядоченные числа от 0 до последнего count,

Вот псевдокод:

    volatile int m_count = 0;
    volatile bool isExit = false;

    void ParallelPrint()
    {
        int currCount = 0;

        while (!isExit)
        {
            while (currCount < m_count)
            {
                currCount++;
                printf("%d\n", currCount);
            }

            Sleep(0); // just content switch
        }
    }

Откройте ветку перед scanf("%d",&t); (Я думаю, это время инициализации не считается), и закрыть поток по isExit = true; до возвращения из вашего Main(),

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