problém : eratostenovo sito

[wedro]

a k tomu nasobku:(musim polopate lebo dakomu nedochadza)
takze mame pole cisel, zoberieme dvojku a vymazeme vsetky nasobky dvojky... ostane 2,3,5,7,9,...
zoberem trojku a vymazem 3.nasobok, 5.nasobok, 7.nasobok,...
zoberem patku a vymazem 5.nasobok, 7.nasobok, 11.nasobok,...
atd. comprende?

asi som stale trubka, ale ako to chces robit ? do akej datovej struktury to chces dat? hashmapa ?
plus budme megalomani, spracuvavas cislo 100 000:
vezmes 2, 50 000x poodstranujes nasobok 2ky
vezmes 3, 33 333x poodstranujes nasobok 3ky
vezmes 5, 20 000x poodstranujes nasobok 5ky ?
...

majme napriklad list integerov. zoberem prvy integer (list.get(i)->dajme tomu sme vo fore) a vymazem jeho nasobok s druhym integerom v liste (list.remove(list.get(i)*list.get(j)->j zacina od i).t.j.:mazem iba nasobky prvočisel ktore este su v liste.
sice mam dva fory ale kratšie.

[galen]

hmm...
takze pri 10 000 000 cislach,
najdem prvocisla eratosom za nejakych 6200 ms, na 1.7GHz procaku ...
inicializacia pola (usporiadana hashmapa, koli dalsiemu processingu): 2800 ms

*zaciatok editu*
na PC z podpisu to inicializuje pole: 2800 ms
preratava ho: 5250 ms
takze celkovo cca 8s
*koniec editu*

celkova inicializacia teda zhruba 10s

nasledne si program vypyta:
vstup

a vramci milisekund da vystup

PS: treba nastavit JVM parametre, aby mala dost pamate, pri 10 000 000 je 500M malo, s 1000M to slape, nepozeral som kolko to zere, parametre pre JVM su: -Xmn200M -Xms1000M -Xmx1000M
eclipseProject si viete stiahnut tu: http://frix.fri.utc.sk/~kubij/eratosSito.zip

[galen]

majme napriklad list integerov. zoberem prvy integer (list.get(i)->dajme tomu sme vo fore) a vymazem jeho nasobok s druhym integerom v liste (list.remove(list.get(i)*list.get(j)->j zacina od i).t.j.:mazem iba nasobky prvočisel ktore este su v liste.
sice mam dva fory ale kratšie.

ja vcelku chapem, ako funguje list ...
mas tam cisla:
2,3,4,5,6,7,8,9

problem zacina vtedy, ked zmazes ktorekolvek cislo, teda napriklad 4:
2,3,5,6,7,8,9
lebo na indexe 3, nemas cislo 4, ale cislo 5, a teda, ak budes chciet mazat cislo z indexu 5 (logicka postupnost), zmazes cislo 7, co je prvocislo, a vonkoncom to nieje cislo 6, ktore si chcel zmazat...

sa ti rozsype kompletne indexacia po odmazani

[wedro]

ja vcelku chapem, ako funguje list ...
mas tam cisla:
2,3,4,5,6,7,8,9

problem zacina vtedy, ked zmazes ktorekolvek cislo, teda napriklad 4:
2,3,5,6,7,8,9
lebo na indexe 3, nemas cislo 4, ale cislo 5, a teda, ak budes chciet mazat cislo z indexu 5 (logicka postupnost), zmazes cislo 7, co je prvocislo, a vonkoncom to nieje cislo 6, ktore si chcel zmazat...

sa ti rozsype kompletne indexacia po odmazani

tak ja nepotrebujem vediet na akom indexe je dane cislo. a prikaz list.remove(cislo) ti zmaze ten prvok v zozname a nie cislo na indexe=cislo.

[galen]

tak ja nepotrebujem vediet na akom indexe je dane cislo. a prikaz list.remove(cislo) ti zmaze ten prvok v zozname a nie cislo na indexe=cislo.

tym padom, odmazavanie N cisiel ma zlozitost: O(n*n)
lebo najdenie cisla v neusporiadanom liste ma narocnost O(n)...

[pEpinko]

inicializacia pola (usporiadana hashmapa, koli dalsiemu processingu): 2800 ms

Otazka: Naco je tam hashmapa? Nestaci obycajne pole s 10M intami?

[galen]

inicializacia pola (usporiadana hashmapa, koli dalsiemu processingu): 2800 ms

Otazka: Naco je tam hashmapa? Nestaci obycajne pole s 10M intami?

nestaci, lebo:
obycajne pole s 10M intami musis pokazde prechadzat cele
to ze ci je cislo oznacene za prvocislo, prides az na konkretnom policku ... ked ho pristupis ...
takze musis n*n prebehnut cele pole, kym ho cele sprocessujes
a nasledne este Nkrat, kym dostanes zvysne prvocisla

Ak pouzijes dynamicku strukturu (list, hash), sice to budes musiet processovat n*n, ale N sa kazdym odstranenim prvku zmensi.
takze namiesto 10M zaznamov v konecnom dosledku budes prehladavat mozno 1/10...

na ukor pocetnosti prvkov pola vsak prichadza overhead s pristupovanim na ich prvky,
zatial co v beznom "array" pristupujes o(1), lebo vies ktory konkretny prvok,
tu, vzhladom na pouzitu strukturu o(n), log(n), pripadne idealny stav hashmapy o(1) pre kazdy prvok, ktory budes seekovat

podotykam, ze moja usporiadana hash-mapa (key set) bola usporiadana podla poradia prvkov, v akom boli do nej vkladane, nie na zaklade ich ciselnej hodnoty (kedze som tam daval rad radom cisla od najm. po najv. tak je to v tomto pripade identicke vysledkom)
nemusi tak hashmapa vyvazovat keySet, pri kazdom vkladani, na zaklade hodnoty kluca...

takze vkladanie do hashmapy bolo rychle - o(1)
seek na zaklade hash, tiez rychly, idealne o(1), kedze sa vsak jedna o Integer, dovolim si tvrdit, ze sa to tomu velmi priblizuje
remove prvkov uz sice mohol pokulhavat, nakolko boli odstranovane prvky z ktorehokolvek miesta, ale prinajhorsom to bolo o(n)

moznou experimentaciou s pouzitou datovou strukturou by sa mozno dal dosiahnut lepsi vysledok,
dovolim si vsak tvrdit, ze LIST lepsi urcite nebude, nakolko:
vkladanie o(1)
hladanie o(n)
odstranenie o(n)

mozno nejaky sortedList, ale tam by som povedal, ze zlozitosti ukonov pojdu zhruba O(log(n))

[pEpinko]

nestaci, lebo:
obycajne pole s 10M intami musis pokazde prechadzat cele
to ze ci je cislo oznacene za prvocislo, prides az na konkretnom policku ... ked ho pristupis ...
takze musis n*n prebehnut cele pole, kym ho cele sprocessujes
a nasledne este Nkrat, kym dostanes zvysne prvocisla

Parkrat som si to cele precital ale nejak mi to nejde do hlavy. Vytvorenie zoznamu s prvocilami pomocou sita je urcite aspon O(n(logn)(loglogn)) (zdroj wiki), neviem nakolko je to vysledok presnych poctov a nakolko efektivnej implementacie, ale trivialna implementacia je urcite O(sqrt(N)*N) to je vidiet dost lahko. S polom som to mal na mysli asi takto:

Kód: Vybrať všetko

    
for (int i = 0; i < SIZE; i++)
        arr[i] = i;
    arr[0] = -1;
    arr[1] = -1;
    for (int i = 2; i * i < SIZE; i++)
    {
        if (arr[i] != -1)
        {
            int n = 2;
            while ((i * n) < SIZE)
            {
                arr[i * n] = -1;
                n++;
            }
        }
    }

Potom este pole predpripravim jednym prejdenim na dotazy typu pocet prvocisel od A do B, co ma stoji O(n).

Kód: Vybrať všetko

    int n = 0;
    for (int i = 0; i < SIZE; i++)
    {
        if (arr[i] != -1)
            n++;
        arr[i] = n;
    }

Vsetky dotazy na pocet prvocisel v intervale viem teraz vyhodnotit v O(1).

Dokopy, majme N cisel a M dotazov na intervaly.

O(sito) + O(n) + O(1)*M

Kedze sito trva urcite viac ako O(n), mame

O(sito) + M*O(1), nejak pochybujem ze sa dostanes pod tuto hranicu s pouzitim lubovolnej struktury.

(cele vytvorenie a spracovanie pola mi to v C trvalo 1,75sekundy, skusil by som to aj v jave, ale nemam ju rad a nemam ani SDK )

[wedro]

Kód: Vybrať všetko

for (int i = 0; i < SIZE; i++)
        arr[i] = i;
    arr[0] = -1;
    arr[1] = -1;
    for (int i = 2; i * i < SIZE; i++)
    {
        if (arr[i] != -1)
        {
            int n = 2;
            while ((i * n) < SIZE)
            {
                arr[i * n] = -1;
                n++;
            }
        }
    }

da sa zjednodušit na:
for (int i = 0; i < SIZE; i++)
arr = i;
arr[0] = -1;
arr[1] = -1;
for (int i = 2; i * i < SIZE; i++)
{
if (arr != -1)
{
int n = i;
while ((i * n) < SIZE)
{
if(arr[n]!=-1)
arr[i * n] = -1;
n++;
}
}
}

[galen]

ocividne overhad so spravou pola je omnoho vacsi, ako pri priamom pristupe prachsprosteho pola ...

potom dostavam cas:
Init data in: 47
Parsed in: 703
Countup in: 47

tzn: inicializacia prvotneho pola 47ms
rozparsovanie identickym kodom, ako pouzivas ty: 703 ms
a finalne napocitanie prvocisiel, do toho pola, ktore sa pristupuje O(1): 47 ms

taaakze som lama

[pEpinko]

da sa zjednodušit na:...

Diky, usetrilo to 0,4 sekundy priblizne.

[zwARO]

pri studiu som nasiel toto ak to niekto chce

Kód: Vybrať všetko

#include<stdio.h>
int main()
{



int pole[1000];
int i, k;
for( i = 0; i < 1000; i++)
pole[i] = 1;

pole[0] = 0;
pole[1] = 0;

for( i = 0; i < 1000; i++)
{
/* ak je to prvocislo, vypisat a nasobky vynulovat */
	if (pole[i] == 1)
	{
		printf("%d\n",i);

/* najmensi nasobok i-cka je dvojnasobok, preto od
neho zacneme nulovat. Budeme pridavat i a nulovat
dalsie nasobky kym je index mensi ako 1000 */
			for( k = 2*i; k < 1000; k = k + i )
			pole[k] = 0;
		}
}

getchar();
return 0;
}

[kami_sama]

Kód: Vybrať všetko

for (int i = 0; i < SIZE; i++)
        arr[i] = i;
    arr[0] = -1;
    arr[1] = -1;
    for (int i = 2; i * i < SIZE; i++)
    {
        if (arr[i] != -1)
        {
            int n = 2;
            while ((i * n) < SIZE)
            {
                arr[i * n] = -1;
                n++;
            }
        }
    }

da sa zjednodušit na:
for (int i = 0; i < SIZE; i++)
arr = i;
arr[0] = -1;
arr[1] = -1;
for (int i = 2; i * i < SIZE; i++)
{
if (arr != -1)
{
int n = i;
while ((i * n) < SIZE)
{
if(arr[n]!=-1)
arr[i * n] = -1;
n++;
}
}
}

nemal by si vytvarat premenne priamo v cykle. spomaluje to cely algoritmus. tiez nepomaha efektivite nasobenie. moja verzia algoritmu je nasledovny:

Kód: Vybrať všetko

		long start = System.currentTimeMillis();
		boolean [] p = new boolean [MAX];
		int [] primes = new int [MAX];
		int i, counter = 0;
		
		p[0] = false;
		p[1] = false;
		p[2] = true;
		primes[counter] = 2;
		primes[++counter] = 3;
		for (i = 3; i < MAX; i += 2)
			p[i] = true;
		
		long init = System.currentTimeMillis();
		
		while(primes[counter] * primes[counter] < MAX){
			
			for (i = primes[counter]*3; i < MAX; i+=(primes[counter] + primes[counter))
				p[i] = false;
			
			i = primes[counter]+1;
			
			while (!p[i]) i++;
			
			primes[++counter] = i;
		}
		
		for (i = primes[counter]+2; i < MAX; i+=2)
			if (p[i])
				primes[++counter]=i;
		
		long end = System.currentTimeMillis();
		System.out.println("Init:\t"+(init-start));
		System.out.println("Alg:\t"+(end-init));
		System.out.println("Total:\t"+(end-start));

s vypismi okolo:
Init: 55
Alg: 183
Total: 238
samozrejme hodnoty su v ms.