Długi okres działania programu (C++)

Question

Witam, robiąc zadanie napotkałem na problem długiego okresu wykonywania programu. Czy mógłby ktoś znaleźć błąd w moim kodzie i powiedzieć co zrobiłem nie tak? 

Plik tekstowy: http://wklej.org/id/3242835/

Mój program:

#include <iostream>
#include <fstream>

using namespace std;

long int czypierwsza(int liczba);

int main()
{
	fstream wejscie;
	wejscie.open("liczby.txt", ios::in);
	fstream wynik;
	wynik.open("wyniki_liczby.txt", ios::out);

	int licznik_czynniki = 0;
	int ilosc_liczb = 0;
	int liczba;

	while (wejscie >> liczba)
	{
		for (int i = 3; i <= liczba; i++)
		{
			if (czypierwsza(i) == true)
			{
				if (liczba % i == 0)
				{
					licznik_czynniki++;
					if (licznik_czynniki == 3)
						break;
				}
			}
		}
		ilosc_liczb++;
		licznik_czynniki = 0;
	}

	cout << "ilosc: " << ilosc_liczb << endl;

	//wynik << "Zadanie 1" << endl;
	//wynik << "Ilosc liczb: " << ilosc_liczb << endl;

	wejscie.close();
	wynik.close();
	system("PAUSE");
}

long int czypierwsza(int liczba)
{
	if (liczba < 2)
		return false;
	for (int j = 2; j * j <= liczba; j++)
		if (liczba % j == 0)
			return false;
	return true;
}

 

Answer 1

Przeanalizujmy złożoność obliczeniową twojego programu, zaczynając od tej funkcji

long int czypierwsza(int liczba)
{
    if (liczba < 2)
        return false;
    for (int j = 2; j * j <= liczba; j++)
        if (liczba % j == 0)
            return false;
    return true;
}

Najgorszy przypadek jest kiedy liczba jest pierwsza i będziesz musiał przejść ~sqrt(liczba) iteracji pętli.

Teraz ten kawałek kodu

while (wejscie >> liczba)
    {
        for (int i = 3; i <= liczba; i++)
        {
            if (czypierwsza(i) == true)
            {
                if (liczba % i == 0)
                {
                    licznik_czynniki++;
                    if (licznik_czynniki == 3)
                        break;
                }
            }
        }
        ilosc_liczb++;
        licznik_czynniki = 0;
    }

Pętla while wykona się maksymalnie 1000 razy wynika to z treści zadania, druga pętla wykona się pesymistycznie ~10^9 razy,  Każda iteracja pętli for kosztuje sqrt(liczba).

Łącząc to wszystko dostajemy 1000*10^9*sqrt(liczba) co można oszacować od góry jako 10^15.5 operacji. Procesor o częstotliwości 3GHz może policzyć 3*10^9 operacji na sekunde więc dostajesz ok 10^6.5/3 sekund to jest około 12 dni.

Podsumowując masz zły algorytm rozwiązania zadania. Możesz sobie poczytać o troche sprytniejszej implementacji sita erastotenesa tutaj, powinno to rozwiązać twoje problemy.

Answer 2

Mam wrażenie, że twój program nawet nie działa tak jak powinien. Czemu przerywasz pętlę kiedy liczba będzie miała 4 lub więcej czynników?  Jeżeli też dobrze widzę, to czemu liczysz wszystkie liczby? Chcesz sprawdzić, czy Egzaminatorzy rzeczywiście nie kłamali i umieścili 1000 liczb? :D

Drugie pytanie: co twój program na to, jakbyś mu podał liczbę np 30?

Comments

Przeczytaj zadanie ponownie.

---

No to mówię. Inkrementujesz licznik liczb na końcu while. Więc nie ważne co będziesz miał przed i tak go zwiększasz.

Na dodatek, nawet dalej podtrzymuję, że sprawdzasz czy liczba ma trzy lub więcej różne czynniki.

W złym miejscu masz sprawdzanie czy liczba ma 3 czynniki, w złym miejscu masz inkrementacje liczb których czynników pierwszych nieparzystych jest dokładnie 3.

Testowales ten kod dla jakichkolwiek danych testowych?

---

while (wejscie >> liczba)
	{
		for (int i = 3; i <= liczba; i++)
			if (czypierwsza(i) == true)
				if (liczba % i == 0)
				{
					licznik_czynniki++;
					if (licznik_czynniki == 3)
					{
						ilosc_liczb++;
						licznik_czynniki = 0;
						break;
					}	
				}
	}

Wydaje mi się, że warunek, w którym sprawdzam czy liczba ma trzy czynniki jest w dobrym miejscu.

---

Sprawdzasz już po wyjściu z fora.

A ilość czynników zerujesz bez względu na to czy ma trzy czy więcej lub mniej, na końcu lub początku pętli while.

---

A co do samej optymalizacji. Polecam użyć sita erastotensa (szukać czynników do sqrt(liczba)), wrzucić wszystkie czynniki pierwsze do vectora. Potem sprawdzasz czy liczba jest parzysta (jeżeli jest, to na starcie nie spełnia warunków "dokładnie trzech czynników z których każdy jest nieparzysty"). Jeżeli nie jest parzysta, to poszukujesz tych czynników do czasu aż:

a) Znajdziesz 4, jeżeli znajdziesz ich 4 to od razu zwracasz że nie ma dokładnie 3 dzielników

b) Przeiterujesz po wszystkich liczbach pierwszych które mogą być potencjalnymi czynnikami pierwszymi. Jeżeli na końcu okaże się że jest ich dokładnie 3, inkrementujesz licznik z liczbami o dokładnie 3 czynnikach pierwszych. Jeżeli nie ma ich 3, to nic nie robisz i ponawiasz sprawdzanie dla kolejnej liczby w pliku. Wykonujesz to do czasu, aż sprawdzisz wszystkie liczby w pliku.

 

Tak na szybko optymalizacja twojego programu.

---

while (wejscie >> liczba)
	{
		pierwiastek = sqrt(liczba);
		
		if (liczba % 2 == 0)
			continue;
		else
		{
			bool *tab = new bool[pierwiastek + 1];
			for (int i = 2; i <= pierwiastek; i++)
				tab[i] = 0;
			sito(tab, pierwiastek);

			for (int i = 2; i <= pierwiastek; i++)
				if (tab[i] == 0)
					if (liczba % i == 0)
					{
						licznik_czynniki++;
						if (licznik_czynniki > 3)
							break;
					}
			delete[] tab;
		}			

		if (licznik_czynniki == 3)
			ilosc_liczb++;

		licznik_czynniki = 0;
	}

Zastosowałem się do porad, program wykonuje się od razu, ale niestety wynik nie niepoprawny.

---

Jeszcze jako ciekawostkę dodam, że rozwiązanie zaproponowane przez CKE nie działa :) tzn. wykonywałoby się podobną ilość czasu co moje rozwiązanie na początku.