Оптимизация ввода / вывода (вывода) в коде C + цикл

Question

У меня есть код, который читает (10 ^ 5) int (s) из стандартного ввода, а затем, выполнив ##, выводит их на стандартный вывод.Я позаботился о части INPUT, используя "setvbuf" и читая строки с помощью "fgets_unlocked ()", а затем анализируя их, чтобы получить требуемые int (s).У меня есть 2 проблемы, с которыми я не могу разобраться:

1.) Поскольку я печатаю 5 миллионов мегапикселей на стандартном устройстве, это занимает много времени: ЕСТЬ ЛЮБОЙ СПОСОБ СНИЖЕНИЯ ЭТОГО (япопытался использовать fwrite (), но o / p печатает непечатаемые символы по причине , использующей fread для чтения в буфер int )

2.) После анализа ввода для int (s)скажем «х», я на самом деле нахожу «нет» делителей, выполнив% (mod) для «нет» в цикле (см. код ниже): Возможно, это также является причиной истечения срока действия моего кода: любые предложения по этому поводуулучшенный.Большое спасибо Это на самом деле проблема от http://www.codechef.com/problems/PD13

# include <stdio.h>
# define SIZE 32*1024
char buf[SIZE];

main(void)
{
int i=0,chk =0;
unsigned int j =0 ,div =0;
int a =0,num =0;
char ch;

setvbuf(stdin,(char*)NULL,_IOFBF,0);

scanf("%d",&chk);
while(getchar_unlocked() != '\n');
while((a = fread_unlocked(buf,1,SIZE,stdin)) >0)
{
    for(i=0;i<a;i++)
    {
        if(buf[i] != '\n')
        {
            num = (buf[i] - '0')+(10*num);
        }
        else
        if(buf[i] == '\n')
        {   
            div = 1;
            for(j=2;j<=(num/2);j++)
            {
                if((num%j) == 0)    // Prob 2
                {
                    div +=j;
                }
            }
            num = 0;
            printf("%d\n",div); // problem 1
        }       
    }
}
return 0;
 }

Answer 1

Версия 2, основанная на предложении @UmNyobe и @wildplasser (см. Комментарии выше) Выполнение кода заняло 0,12 секунды и 3,2 МБ памяти на онлайн-судье. Я сам проверил с 2 * 10 ^ 5 int (input) в диапазоне от 1 до 5 * 10 ^ 5, и выполнение заняло:

реальный 0m0,443s

пользователь 0m0,408s

sys 0m0.024s

** Пожалуйста, посмотрите, можно ли провести дополнительную оптимизацию.

* * 1010

Answer 2

Вы можете печатать намного быстрее, чем printf.

Посмотрите на itoa() или напишите свою собственную простую функцию, которая очень быстро преобразует целые числа в ascii.

Вот быстрый-н-грязныйверсия itoa, которая должна работать быстро для ваших целей:

char* custom_itoa(int i)
{
    static char output[24];  // 64-bit MAX_INT is 20 digits
    char* p = &output[23];

    for(*p--=0;i/=10;*p--=i%10+0x30);
    return ++p;    
}

обратите внимание, что эта функция имеет некоторые серьезные встроенные ограничения, в том числе:

• он не обрабатывает отрицательные числа
• в настоящее время он не обрабатывает числа больше 23 символов в десятичной форме.
• он по своей природе опасен для потоков.Не пытайтесь в многопоточной среде.
• возвращаемое значение будет повреждено при повторном вызове функции.

Я написал это исключительно для скорости, а не для безопасностиили удобство.

Answer 3

// Prob 2 Ваша проблема с biggesr сейчас ... Вы просто хотите узнать количество делителей?

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

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

n = a1^p1 * a1^p2 *... *an^pn

Тогда сумма делителей будет.

((a1^(p1+1) - 1)/(a1 - 1))*((a2^(p2+1) - 1)/(a2-1))*...*((an^(pn+1) - 1)/(an-1))

Чтобы понять, что у вас есть (для n = 8) 1+ 2 + 4 + 8 = 15 = (16 - 1)/(2 - 1)

Это значительно улучшит скорость, но целочисленная факторизация (то, что вы действительно делаете) действительно дорогая ...

Редактировать:

В вашей ссылке максимум 5000000, поэтому у вас есть максимум 700 простых чисел

Простой алгоритм декомпозиции

void primedecomp(int number, const int* primetable, int* primecount,
      int pos,int tablelen){
    while(pos < tablelen && number % primetable[pos] !=0 )
       pos++;

    if(pos == tablelen)
      return

     while(number % primetable[pos] ==0 ){
        number = number / primetable[pos];
        primecount[pos]++;
     }
     //number has been modified
     //too lazy to write a loop, so recursive call
     primedecomp(number,primetable,primecount, pos+1,tablelen);

}

РЕДАКТИРОВАТЬ : вместо подсчета вычислите a^(n+1), используя primepow = a; primepow = a*primepow;

Это будет намного чище в C ++ или Java, где у вас есть hashmap. В конце primecount содержит значения pi, о которых я говорил выше.

Даже если это выглядит страшно, вы создадите primetable только один раз. Теперь этот алгоритм запустить в худшем случае в O(tablelen), что составляет O(square root(Nmax)). ваш начальный цикл прошел в O(Nmax).