[Pytanie] Optymalizacja algorytmu

[encoreeFTW]

siema, co mozna zmienic w tym oto algorytmie aby wykonywal sie szybciej?

#include <iostream>

using namespace std;

int licz_dziel(int a);

int main()
{
	ios_base::sync_with_stdio(0);
	int a;
	cin>>a;
	cout<<licz_dziel(a);
	return 0;
}

int licz_dziel(int a)
{
	register int i = 2;
	int licznik = 2;
	for(;i<=(a/2)+1;i++)if(a%i==0)licznik++;
	return licznik;	
}

 

 

program ma za zadanie wypisywac liczbe wszystkich dzielnikow, ja sprawdzam od 2 do polowy liczby, licznik od poczatku to 2, bo 1 i liczba sa zawsze dzielnikami, program dziala, lecz na sprawdzaczce nie przechodzi 2 ostatnich prob ze wzgledu na za dlugi czas wykonania. jakies pomysly?

[Lesteross]

Pierwsza rzecz: w mądrej książce czytałem, iż kompilator wcale nie musi wstawiać zmiennej do rejestru, jeżeli użyjesz słowa kluczowego register, także nie masz pewności, że do zmiennej będzie szybszy dostęp. Dlatego lepiej tego słowa unikać, bo kompilator sam powinien dokonać optymalizacji.

 

Warto zmienić i++ na ++i, podobnie jak licznik++ . Z tego względu, iż w danym czasie nie robisz na nich konkretnie nic (w danej linijce), a operator postinkrementacji tworzy kopię inkrementowanego obiektu, co w jakimś stopniu przedłuża czas jego wykonywania. Możesz sprawdzić, czy to zadziała.

 

Jak mi się coś na myśl nasunie to ci powiem .

[encoreeFTW]

nic to nie dalo, nadal 2 ostatnie proby za wolne ;f

[Mordijc]

Zamiast cin i cout użyj scanf i printf, podobno są deko szybsze.

i<=(a/2)+1 zmień na i<(a/2)+2

[Lesteross]

Nie wiem, ogranicz licznik do shorta? Użyj printf-a? Przekaż parametr jako referencję?

 

A tak btw. co to za sprawdzaczka? Jakaś strona z takimi zadaniami? Kiedyś ktoś podał właśnie stronę z takimi zadaniami, tylko nie chce mi się pół forum przeglądać .

[encoreeFTW]

dalej za wolno

 

ta strona to tzw moodle, moja szkola ma serwer, i sprawdzaczke do zadan, ktore zadaje koles od inf

[IeMaster]

czy masz podany jakiś zakres tj maksmalną wartość danych wjeściowych ?

 

 

spróbuj to:

 

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    for (int i(0); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}

powinno by szybkie. Znalezione w google "find all diviors fast"

[Vesim]

http://msdn.microsoft.com/en-us/library/dd728073.aspx Jedynie

[Sopelek997]

Zamiast ograniczenia a/2 przyjmuj sqrt(a)

 

Dodatkowo, jeśli liczba jest nieparzysta to nie ma ona parzystych dzielników, możesz zrobić dwie wersje funkcji dla parzystych i nieparzystych