jak przyspieszyc rekurencje

Question

Witam, zastanawiam się dlaczego zadanie link nie wchodzi mi na 100%. Na komputerze dla najwiekszego testu liczby mi +/- 10s, natomiast na szkopule ledwo zmiescilem sie w czasie (tj. 19.98s / 20.00s)? Czy to przez rekurencje? A jak tak to jak to przyspieszyć? Dodam, ze oryginalne zadanie (z OIJ) robilem identycznym sposobem (tj. rekurencyjne "doklejanie" cyfr).

moj kod: link.

Tutaj dla porownania oryginalne zadanie: link oraz rozwiązanie: link.

Comments

Wydaje mi się, że nadużywasz funkcji pow. Szczególnie, że wywołujesz ją wielokrotnie z tymi samymi argumentami.

---

sprawdzalem, to nie tu lezy blad, byc moze po prostu szkopul ma jakis wolniejszy kompilator

Answer 1

Na samym cache'owaniu prim() można ściąć połowę czasu btw.

Ten pow(10, dl) faktycznie nie wygląda tam zbyt szczęśliwie, ale on sam raczej nie wprowadzi zbyt dużego laga.

Comments

tylko dlaczego oryginalne zadanie dla wartosci 10^18 dziala .2s a to tutaj ok 20 dla wartosci 10^6 razy mniejszych? musi byc jakies wytlumaczenie i to raczej nie przez prime() bo w tamtym zadaniu licze pierwszosc liczby w ten sam sposob

---

Oryginalne zadanie aż tak bardzo się nie rozgałęzia. Dla tych samych liczb testowych (1 1000000000000) w oryginalnym zadaniu będziesz mieć tak ze 300 wywołań rekDokl w sumie, gdzie w zmodyfikowanym to będzie około 32000.

---

nie bardzo rozumiem co to jest cachowanie i jak tego uzyc, ale moze sie przydac, wiec bylbym wdzieczny za pokazanie jak tego uzyc

---

Cache'owanie wyników to po prostu zapisywanie wyników po ich wyliczeniu do jakiejś struktury danych (np. unordered_map), a potem przy kolejnym wywołaniu funkcji przed przejściem do kosztownych obliczeń sprawdza się najpierw czy w tej "pamięci podręcznej" czasem wyniku już nie ma. Np.:

unordered_map<ull, int> prim_cache;

bool prim(ull x) {
        const auto cache = prim_cache.find(x);
        if (cache != prim_cache.end()) {
                return cache->second;
        }

        for (ull i = 2; i * i <= x; i ++) {
                if (x % i == 0) {
                        prim_cache[x] = 0;
                        return 0;
                }
        }
        prim_cache[x] = 1;
        return 1;
}

Można by jeszcze rzucić potem okiem na rozkład tych liczb w pamięci podręcznej. Może użycie sita Eratostenesa żeby trochę wypełnić pamięć podręczną dało by też jakiegoś boosta.

---

Zanim włączał bym memoizację (czyli cache), przyśpieszył bym sam algorytm sprawdzania liczby pierwszej. Daje to wg. moich pomiarów przyśpieszenie (co nie dziwne bo mniej pętli):

bool prim(ull x) {    
        if ((x == 2) or (x == 3)) {    
                return true;    
        }    
    
        if ((x <= 1) or ((x % 2) == 0) or ((x % 3) == 0)) {    
                return false;    
        }    
    
        for (auto i = 5ULL; i * i <= x; i += 6) {    
                if (((x % i) == 0) or ((x % (i + 2)) == 0)) {    
                        return false;    
                }    
        }    
    
        return true;    
}

Krótki test rozwiązania orig.:

$ time echo "1 10000000000" | ./prim 
2683
real	0m1,285s
user	0m1,285s
sys	0m0,001s

Po poprawce:

$ time echo "1 10000000000" | ./prim
2683
real    0m0,430s
user    0m0,423s
sys    0m0,008s

Teraz dodanie memoizacji (co nie jest raczej rozwiązaniem eleganckim w takich konkursach ale może dawać przyśpieszenie), która może wyglądać tak (proszę mnie poprawić jeśli jest jakaś niezręczność związana z wydajnością):

bool prim(ull x) {
	if ((x == 2) or (x == 3)) {
		return true;
	}

	if ((x <= 1) or ((x % 2) == 0) or ((x % 3) == 0)) {
		return false;
	}

	static unordered_map<ull, bool> prim_cache;
	const auto & cache = prim_cache.find(x);
	if (cache != prim_cache.end()) {
		return cache->second;
	}

	for (auto i = 5ULL; i * i <= x; i += 6) {
		if (((x % i) == 0) or ((x % (i + 2)) == 0)) {
			return prim_cache[x] = false;
		}
	}
	return prim_cache[x] = true;
}

I efekt:

$ time echo "1 10000000000" | ./prim
2683
real    0m0,320s
user    0m0,321s
sys    0m0,000s

No i wyszło ~ 4 x szybciej

A dalsze przyśpieszenie, zgadzam się.. Sito.