[Algorytmy]Dziwne pomiary wydajności sita Erastotenesa

[Borneq]

Zrobiłem według opisu:

Kod: Zaznacz cały

void sito()
{
	int sqrtSize = sqrtl(SIZE);
	for (int i = 2; i <= sqrtSize; i++)
	{
		if (tab[i])
			for (int j = 2 * i; j < SIZE; j += i)
				tab[j] = false;
	}
}

Mierzyłem czas VC++,64 bit, 3.6 GHz:

Kod: Zaznacz cały

100 tys - 0.000128 s
1 mln - 0.0022 s
10 mln - 0.124 s
100 mln - 1.67 s
1000 mln - 20.4 s
2000 mln - 43.2 s.

Rośnie szybciej niż \(\displaystyle{ n \cdot log(n) \cdot log(log(n))}\)
Ale teraz zmierzyłem ilość obrotów wewnętrznej pętli gdzie następuje powiększanie j oraz zerowanie tablicy:

Kod: Zaznacz cały

100 tys - 202152
1 mln - 2197837
10 mln - 23492026
100 mln - 248304140
1000 mln - 2599964546

Teraz rośnie znacznie wolniej niż ze wzoru, raczej jak \(\displaystyle{ n \cdot log(log(n))}\)
Czyżby każde pole było wykreślane tylko 2 razy?
I czy oznacza że dla dużych tablic mamy jakiś kolosalne zwolnienie czasu? Między 1 mln i 10 mln na przykład..

Wiem : dla miliona nawet gdy zadeklarowałem pamięć przez new() mogło całość trzymać w cache, a potem już nie trzymało. Tym niemniej rośnie znacznie wolniej niż z podanego wzoru w Wikipedii i średnio 2 do 2.5 wykreślenia.

[kalwi]

Źle to zrobiłeś. Ten kod powinien wyglądać tak:

Kod: Zaznacz cały

void sito()
{
	bool tab[SIZE];
	for(int i = 0; i < SIZE; ++i)
		tab[i] = true;
   	int sqrtSize = sqrtl(SIZE);
   	for (int i = 2; i <= sqrtSize; ++i)
   	{
        if (tab[i])
        	for (int j = i * i; j <= SIZE; j += i)
            	tab[j] = false;
   }
}

Szczególnie zwróć uwagę na linijkę 10.

Hmm, post się dziwnie wyświetla, inaczej niż go napisałem (tj ten kod). Złe wcięcia są trochę.

[Borneq]

Czyli startuje od \(\displaystyle{ j^2}\)? Będzie jeszcze szybszy, coś wzór się nie zgadza. Tylko spowalnia gdy tablica nie mieści się w cache.

[kalwi]

Kod: Zaznacz cały

 int j = i * i

Nie wiem, gdzie tu widzisz \(\displaystyle{ j^2}\).

Kod: Zaznacz cały

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>

void sito(long long int);

int main()
{
    sito(1);           //1
    sito(10);          //10
    sito(100);         //100
    sito(1000);        //1k
    sito(10000);       //10k
    sito(100000);      //100k
    sito(1000000);     //1kk
    sito(10000000);    //10kk
    sito(100000000);   //100kk

    return 0;
}

void sito(long long int SIZE)
{
   clock_t t1, t2;

   bool *tab = malloc(SIZE * sizeof(bool));

   for(long long int i = 0; i < SIZE; ++i)
      tab[i] = true;

   int sqrtSize = sqrtl(SIZE);
   t1 = clock();

   for (long long int i = 2; i <= sqrtSize; ++i)
   {
      if (tab[i])
          for (long long int j = i * i; j <= SIZE; j += i)
               tab[j] = false;
   }

   t2 = clock();
   double diff1 = ((double)t2-(double)t1);
   float seconds = diff1 / CLOCKS_PER_SEC;

   if(SIZE < 1000000)
      printf("%lld:			 %f s
", SIZE, seconds);
   else
      printf("%lld:		 %f s
", SIZE, seconds);
   free(tab);
}

Mi coś takiego wyszło z tym poprawionym kodem:

Kod: Zaznacz cały

1:			 0.000002 s
10:			         0.000001 s
100:			         0.000000 s
1000:			 0.000004 s
10000:			 0.000041 s
100000:			 0.000607 s
1000000:		         0.010702 s
10000000:		 0.139599 s
100000000:		 1.797401 s

Cholerne formatowanie, w edycji wyświetla się prawidłowo (na konsoli również).
Zauważ, że w tym programie nie jest zliczana ilość czasu poświęcona na zaalokowanie i wyczyszczenie pamięci, pierwsze 3 wyniki można uznać za pomijalne.
Złożoność algorytmu sita Eratostenesa powinna być około \(\displaystyle{ O\left( n\log\log n\right)}\) i jeśli się nie mylę to co napisałem właśnie do tego zbiega.

[Borneq]

Powinno być

for (long long int j = i * i; j < SIZE; j += i)

zamiast

j <= SIZE

. U mnie dwa czasy ostatnie są podobne, natomiast wcześniejsze są zerowe, widać clock() ma mniejszą rozdzielczość. Zmieniłem na chrono

Kod: Zaznacz cały

#include <chrono>
using namespace std;

class stoper
{
public:
	chrono::time_point<chrono::high_resolution_clock> a, b;
	void start() { a = chrono::high_resolution_clock::now(); }
	void stop() { b = chrono::high_resolution_clock::now(); }
	double duration()
	{
		chrono::duration<double> elapsed_seconds = b - a;
		return elapsed_seconds.count();
	}
};
stoper st;
st.start();
st.stop();
printf("%lld:			 %f s
", SIZE, st.duration());

Dało:

Kod: Zaznacz cały

1:                       0.000000 s
10:                      0.000000 s
100:                     0.000000 s
1000:                    0.000001 s
10000:                   0.000007 s
100000:                  0.000140 s
1000000:                 0.002279 s
10000000:                0.123146 s
100000000:               1.564427 s

Dla mniejszych jeszcze większe przyśpieszenie z powodu cache. Jest jak piszesz, złożoność \(\displaystyle{ n \cdot log (log (n))}\), inna niż podaje Wikipedia

[kalwi]

Powinno być

for (long long int j = i * i; j < SIZE; j += i)

zamiast

j <= SIZE

.

Z wiki:
\(\displaystyle{ \text{for i } := 2, 3, 4, \text{ ..., nie więcej niż } \sqrt{n} \\
\qquad\text{if} \ A = \text{ true}: \\
\qquad \qquad\text{for }j := i^2, i^2+i, i^2+2i, ..., \text{ nie więcej niż n} : \\
\qquad \qquad \qquad A[j] := \text{ false}}\)

Także dla mnie nie więcej niż to jest tożsame z \(\displaystyle{ \le}\)

Jest jak piszesz, złożoność \(\displaystyle{ n \cdot log (log (n))}\), inna niż podaje Wikipedia

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity

W drugim zdaniu jest dokładnie taka złożoność napisana.

[Borneq]

Także dla mnie nie więcej niż to jest tożsame z \(\displaystyle{ \le}\)

W takim razi trzeba przydzielać o 1 większą tablicę, bo zwykle dla n przydziela się liczby o 0 do n-1.

W drugim zdaniu jest dokładnie taka złożoność napisana.

W polskiej Wiki bez komentarzy jest napisana złożoność binarna gzie dodatkowo liczy się długość liczby.