Ciclo for per creazione di array enorme

[roby492]

Di nuovo qui, a chiedervi un suggerimento:-)

L'altro giorno mi avete aiutato a fare dei metodi per la ricerca binaria generica, ora per l'esercizio successivo devo 'cronometrare' i tempi del metodo iterativo e di quello ricorsivo.
Credo però che l'array sia troppo piccolo per mostrare dei tempi significativi, infatti esce sempre o quasi zero. Come posso creare un ciclo for che crei un array fino a che i tempi di ricerca si alzeranno? Ho anche dei dubbi che arrivi fino a 9999999, anche se stampo l'indice i e array.length mi dice che è 9999999, ma secondo me dovrebbe arrivare fino a 32000 e qualcosa, vero?

Il codice che ho scritto è il seguente:

public static void main(String []args)
	{	
		Integer[] cerca = new Integer[10];
		cerca[0]=10;
		int indiceRis=0;
		Integer[] array=new Integer[9999999];
		//int i;
		for(int i = 0 ; i < 9999999 ; i++)
		{
			array[i]=i;
			//System.out.println(i);
		}
		//System.out.println("ii"+i);
		OttoQuindici<Integer> OttoQuindici = new OttoQuindici<Integer>();
		long inizioIterativo=System.currentTimeMillis();
		indiceRis =OttoQuindici.binaria(array, cerca, Integer.class);
		long fineIterativo=System.currentTimeMillis();
		long tIterativo=fineIterativo-inizioIterativo;
		long inizioRicorsivo=System.currentTimeMillis();
		int indiceRis2 =-10;
		indiceRis2=OttoQuindici.binRicorsiva(array, cerca, 0, array.length ,Integer.class);
		long fineRicorsivo=System.currentTimeMillis();
		long tRicorsivo=fineRicorsivo-inizioRicorsivo;
		System.out.println("Inizio: "+inizioIterativo);
		System.out.println("Fine  : "+fineIterativo);
		System.out.println("Tempo Iterativo: "+tIterativo);
		System.out.println("Tempo Ricorsivo: "+tRicorsivo);
		if(indiceRis!=-1)
			System.out.println("Risultato:"+array[indiceRis2]);
		else
			System.out.println("Non trovato");
	}
	
	public int binRicorsiva(T[] elementi, T[] ricerca,int inferiore, int superiore ,Class<T> clazz) 
	{
		int meta=(inferiore+superiore)/2;
		System.out.println("hola");
		if(inferiore>superiore)
			return -1;
		else if (elementi[meta] == ricerca[0])
			return meta;
		else if (ricerca[0].compareTo(elementi[meta])>0)
			return binRicorsiva(elementi, ricerca, meta+1,superiore, clazz);
		else if (ricerca[0].compareTo(elementi[meta])<0)
			return binRicorsiva(elementi, ricerca, inferiore, meta-1, clazz);
			
		return -1;
	}

[gaetano123]

Nelle stupidate di Visual Basic di microsoft, integer arriva fino a 32767, ma nel caso di altri linguaggi più seri, arriva oltre i 2 miliardi.

[Kaamos]

L'indice è un int, che quindi arriva a 2^32-1 (valore contenuto anche nella costante Integer.MAX_VALUE). Dando un'occhiata ai primi risultati di Google sembrerebbe che la massima dimensione per un array sia il suddetto valore meno otto, e in effetti nelle librerie del linguaggio c'è qualcosa del genere, ad esempio nella classe ArrayList.
Tuttavia penso che occuperesti troppa memoria e riceveresti un errore ben prima di quel valore... ma ti basta provare, danni non ne fai.

P.S.: "altri linguaggi più seri" è un po' troppo semplificativo, non dipende sempre dal solo linguaggio. A meno che non siano seri neanche C e C++...

[roby492]

Ciao ragazzi, grazie delle risposte.

Allora, innanzitutto ho provato a compilare con un array di 99999999 e non da errore, ma un errore di memoria in esezione.

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at OttoSedici.main(OttoSedici.java:30)

Detto questo, sono certo che superi il 32000 fatidico perchè sto facendo girare il programma stampando i valori dell'indice i (ORA è a 400000).

Quindi, o il mio programma non funziona, cosa probabile, oppore il mio pc fa la ricerca binaria in troppo poco tempo, perchè il risultato che da è zero.
Il libro mi consiglia di misurare il tempo impiegato con System.currentTimeMillis();

Esiste qualcosa di più preciso? Oppure avete altri consigli da darmi? (ora i= 2000000 circa)

Grazieee!

[lolide]

Visto che l'operatore [] degli array accetta un int, puoi allocare un array grande max come il massimo numero rappresentabile da un int (Integer.MAX_VALUE). Cmq dicono che alcune JVM usano fino a 16 byte della memoria allocata di un array come spazio riservato (2 byte vengono usati anche per salvarsi la lunghezza dell'array allocato), quindi alla fine alloca Integer.MAX_VALUE - 8 per sicurezza

Poi ti da errore di memoria perchè la memoria heap per quell'applicazione e' poca.
Puoi aumentarla passando -XmsN (specificando in N il num di byte) alla riga di comando di esecuzione del programma (fai java --help nella console per vedere precisamente quale parametro passare)

Poi allocando un array di Integer allochi un array di puntatori quindi non a 32 ma a 64 bit (4byte).....
usa

int[] array = new int[Integer.MAX_VALUE - 8];

per allocare un array di int a 32 bit

Per calcolare il tempo in modo piu' preciso usa System.nanoTime()

[Kaamos]

Originariamente inviato da lolide
Visto che l'operatore [] degli array accetta un int, puoi allocare un array grande max come il massimo numero rappresentabile da un int (Integer.MAX_VALUE). Cmq dicono che alcune JVM usano fino a 16 byte della memoria allocata di un array come spazio riservato (2 byte vengono usati anche per salvarsi la lunghezza dell'array allocato), quindi alla fine alloca Integer.MAX_VALUE - 8 per sicurezza

Poi ti da errore di memoria perchè la memoria heap per quell'applicazione e' poca.
Puoi aumentarla passando -XmsN (specificando in N il num di byte) alla riga di comando di esecuzione del programma (fai java --help nella console per vedere precisamente quale parametro passare)

Poi allocando un array di Integer allochi un array di puntatori quindi non a 32 ma a 64 bit (4byte).....
usa

int[] array = new int[Integer.MAX_VALUE - 8];

per allocare un array di int a 32 bit

Per calcolare il tempo in modo piu' preciso usa System.nanoTime()

In realtà ne basterebbe anche uno di byte per la dimensione dell'array, anzi avanzerebbe pure un bit. Comunque gli indirizzi saranno a 32 o 64 bit a seconda del sistema, suppongo.
Però non so francamente nel dettaglio cosa contengano questi fatidici 32 byte da non utilizzare.

[roby492]

Grazie dei preziosi consigli.

Ho provato ad utilizzare Integer.MaxVALUE-8 ma ovviamenta dato di nuovo l'errore dovuto alla memoria.

Allora ho tentato l'aumento della memoria disponibile, passando quel parametro da linea di comando ma non ha funzionato.

Tuttavia, utilizzando System.nanoTime() ho avuto dei risultati (questa volta diversi da zero) e quindi posso ritenere l'esercizio completato.

L'importante per ora è che il metodo funzioni, che abbia verificato che la ricorsione in questo caso è il metodo più veloce e che possa passare a svolgere l'esercizio successivo.

So che questi discorsi sono alla base della programmazione, ma ritengo, forse sbaglio, di poterli assimilare e approfondire nel corso del tempo, in base alle problematiche che mi si porranno davanti.

Ciao e grazie ancora a tutti!

[Kaamos]

Originariamente inviato da roby492
Grazie dei preziosi consigli.

Ho provato ad utilizzare Integer.MaxVALUE-8 ma ovviamenta dato di nuovo l'errore dovuto alla memoria.

Allora ho tentato l'aumento della memoria disponibile, passando quel parametro da linea di comando ma non ha funzionato.

Tuttavia, utilizzando System.nanoTime() ho avuto dei risultati (questa volta diversi da zero) e quindi posso ritenere l'esercizio completato.

L'importante per ora è che il metodo funzioni, che abbia verificato che la ricorsione in questo caso è il metodo più veloce e che possa passare a svolgere l'esercizio successivo.

So che questi discorsi sono alla base della programmazione, ma ritengo, forse sbaglio, di poterli assimilare e approfondire nel corso del tempo, in base alle problematiche che mi si porranno davanti.

Ciao e grazie ancora a tutti!

Se vuoi utilizzare array con più elementi dovresti inizializzare un array di int anziché di Integer, questi ultimi sono oggetti e si portano appresso tutto il peso della loro classe, e quindi spazio in memoria (una volta inizializzati ovviamente).

Hai fatto un po' di prove? Mi sembra strano che la ricorsione sia più veloce dell'iterazione in questo caso...

[roby492]

Hai ragione, non funziona nulla! O meglio non sempre funziona...

I due metodi danno risultati uguali tipo sotto il valore cerca=100. Oltre questo numero il metodo binRicorsivo non da risultati e restituisce -1... Per questo vi chiedo di dare un'occhiata al codice, non me lo spiego proprio.

Tuttavia quando il metodo binricorsiva() riesce a trovare il valore, ci mette molto meno, però mi vengono a questo punto dei dubbi sul fatto che sia normale.

Infine, non posso usare i tipi primitivi perchè i due metodi accettano solo le classi involucro, poichè metodi generici (almeno così mi pare di aver capito).

Grazie ragazzi!

[Kaamos]

Originariamente inviato da roby492
Hai ragione, non funziona nulla! O meglio non sempre funziona...

I due metodi danno risultati uguali tipo sotto il valore cerca=100. Oltre questo numero il metodo binRicorsivo non da risultati e restituisce -1... Per questo vi chiedo di dare un'occhiata al codice, non me lo spiego proprio.

Tuttavia quando il metodo binricorsiva() riesce a trovare il valore, ci mette molto meno, però mi vengono a questo punto dei dubbi sul fatto che sia normale.

Infine, non posso usare i tipi primitivi perchè i due metodi accettano solo le classi involucro, poichè metodi generici (almeno così mi pare di aver capito).

Grazie ragazzi!

E' vero che i tipi generici possono essere solo oggetti e non dati primitivi, ma se il tuo scopo e' lavorare su un array grande fai tutto in un'unica classe e dichiara un array di int. Va bene essere il piu' generici possibili, ma questo non deve intaccare la funzionalita' del programma... a meno che non ci siano altre cose che non ci hai detto sul tuo programma.

Che per pochi numeri i tempi d'esecuzione s'equivalgano e' normale, ovviamente.

Secondo me, a meno di strani rigiri del compilatore o di qualcos'altro che mi sfugge, il metodo iterativo alla lunga dovrebbe essere piu' rapido... crea un caso pessimo: lancia il programma con l'opzione che ti ha suggerito l'altro utente dandogli piu' memoria possibile, istanzia un array di int di dimensione Integer.MAX_VALUE - 8 (lasciandolo vuoto cosi' si riempe di zeri) e fagli cercare un numero diverso da zero.

Inoltre per cercare di capire cosa succede, la soluzione e' sempre la solita: mettere nel codice delle stampe di debug che ti aiutino a capire cosa il tuo programma sta facendo. Potresti stampare ad esempio l'indice attuale e/o il numero contenuto, ad ogni iterazione (nel caso iterativo) o chiamata (nel caso ricorsivo).