[JAVA] Vorrei vedere ad occhio la differenza tra binaysearch e una ricerca lineare..

[luxorl]

Ciao,
volevo vedere ad occhio come la ricerca lineare su un vettore ordinato sia notevolmente più lenta di una binarysearch sullo stesso vettore. Ovviamente mi servirebbe un mega vettore per vedere questa differenza... io avevo provato a fare questo main:


public static void main(String args[]){
int v[]=new int[10000000];
for(int i=0;i<10000000;i++)
v[i]=i;
int x=Console.readInt("Numero da cercare: ");
int r=Lineare(v,x);
System.out.println("Posizione: "+r);

}


Ma ancora sono pochi gli elementi da controllare per vedere la differenza ad occhio nudo, e se aumento ancora la dimensione del vettore ho un OutOfMemoryError: Java Heap Space..

Come potrei fare?
Poi come posso inserire nel programma (sia nella ricerca binaria sia in quella lineare) un cronometro per avere un risultato preciso di quanto ci mettono?

[cionci]

Conta le iterazioni invece di usare il tempo...

Ogni volta che fai un contronto per vedere se l'elemento su cui sei posizionato è quello che cercavi incrementi di 1 un contatore... Al teremine del programma stampi il contatore...

[wisher]

oppure se vuoi vedere a occhio fai eseguire la ricerca un migliaio di volte e non una sola...
cmq ti consiglio di contare le iterazioni

[luxorl]

Conta le iterazioni invece di usare il tempo...

Ogni volta che fai un contronto per vedere se l'elemento su cui sei posizionato è quello che cercavi incrementi di 1 un contatore... Al teremine del programma stampi il contatore...

Vabè ma così avrei un risultato quasi "scontato" il numero di confronti che fa la ricerca lineare sarà pari alla posizione in cui si trova l'elemento cercato.

Io vorrei lanciare prima la ricerca binaria e poi la ricerca lineare sulla stessa istanza e fargli cercare l'ultimo elemento.. e vorrei in qualche modo vedere ad occhio nudo la ricerca lineare soffrire e quella binaria farcela in un paio di secondi :)

Ma un modo per far fare la ricerca su un mega vettore molto più grande di 10'000'000 celle non c'è?

[luxorl]

oppure se vuoi vedere a occhio fai eseguire la ricerca un migliaio di volte e non una sola...
cmq ti consiglio di contare le iterazioni

Ora provo a far eseguire la ricerca un migliaio di volte... :)

[^TiGeRShArK^]

per aumentare la dimensione del vettore basta aumentare la dimensione massima dell heap space allocata dalla java VM.
L'opzione è la seguente:

-Xmxn
Specify the maximum size, in bytes, of the memory allocation pool. This value must a multiple of 1024 greater than 2MB. Append the letter k or K to indicate kilobytes, or m or M to indicate megabytes. The default value is 64MB. Examples:

-Xmx83886080
-Xmx81920k
-Xmx80m

[luxorl]

Ora provo a far eseguire la ricerca un migliaio di volte... :)

Fantastico anche ripetendo la ricerca 10000000 volte con la binaria ci metto 3 o 4 secondi!!
Mentre la lineare già ripetendola solo 1000 volte ci mette un 40-45 secondi!! :D

[luxorl]

per aumentare la dimensione del vettore basta aumentare la dimensione massima dell heap space allocata dalla java VM.
L'opzione è la seguente:

Da eseguire dove? :stordita:

[^TiGeRShArK^]

è tra le opzioni della VM java..
quando lanci java.exe in pratica....