ArrayList bei großen Zahlen langsam?

[Guest]

Hi,

folgender Code:

public void run(){
		ArrayList<Zahl> liste = new ArrayList<Zahl>(10000000);
		
		for(int i=0;i<10000000;i++){
			liste.add(new Zahl(i,0));
		}		
	}

	
	class Zahl{
		public int z;
		public int counter;
		public Zahl(int z, int counter){
			this.z = z;
			this.counter = counter;
		}
	}

Ab ca. 900000 wirds wahnsinnig langsam, dh. der Code läuft bei mir nun schon seit einer halben Stunde. Was mache ich falsch?

 

[Murray]

Läuft Dein Programm denn wirklich noch, oder ist ein OutOfMemoryError aufgetreten?

 

[Landei]

Wenn das interne Array von ArrayList "überläuft", wird in ein neues kopiert, was heftig werden kann. Wenn du von vornherein weißt, wie groß deine ArrayList wird, kannst du die erwartete Größe schon im Konstruktor angeben, das spart Zeit.

Wenn du nur "sequentiell" mit der Liste arbeiten willst (also z.B. kein get(index) oder so brauchst) wäre LinkedList eventuell eine schnellere Alternative.

Was du machst, sieht aus, als möchtest du die Häufigkeit von Zahlen ermitteln. Wenn dem so ist, bietet sich eine Map<Integer, Integer> an (z.B. HashMap), bei der die Zahl der key, und die Häufigkeit der value ist.

 

[SlaterB]

public class Test
{


    public static void main(String args[])
        throws Exception
    {
        ArrayList<Zahl> liste = new ArrayList<Zahl>(10000000);

        long time = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++)
        {
            liste.add(new Zahl(i, 0));
            if ((i+1) % 500000 == 0)
            {
                System.out.println("i+1: " + (i+1) + ", time: " + (System.currentTimeMillis() - time));
            }
        }

    }


}
---

Ausgabe:

i+1: 500000, time: 188
i+1: 1000000, time: 281
i+1: 1500000, time: 328
i+1: 2000000, time: 672
i+1: 2500000, time: 828
i+1: 3000000, time: 906
i+1: 3500000, time: 985
i+1: 4000000, time: 1078
i+1: 4500000, time: 1156
i+1: 5000000, time: 1813
i+1: 5500000, time: 1844
i+1: 6000000, time: 2078
i+1: 6500000, time: 2203
i+1: 7000000, time: 2235
i+1: 7500000, time: 2344
i+1: 8000000, time: 2375
i+1: 8500000, time: 2485
i+1: 9000000, time: 2594
i+1: 9500000, time: 2625
i+1: 10000000, time: 2750

insgesamt also nur 3 Sekunden, bekommst du bei dir Zwischenausgaben? (evtl. Intervall auf 100.000 oder niedriger setzen)

den Speicher musste ich auch hochsetzen

--------

> Wenn das interne Array von ArrayList "überläuft", wird in ein neues kopiert, was heftig werden kann

nur 30 mal oder so, dauert nicht wirklich lange,
zudem ist hier die Größe initial vorgegeben,
läßt man sie weg, dauert mein Beispielprogramm 4.4 Sekunden statt 2.7

> wäre LinkedList eine schnellere Alternative

LinkedList ist deutlich aufwendiger,
in meinem obigen Programm über 8 Sekunden statt 2.7

LinkedList ist beim sequentiellen Durchlauf besser + Löschen/ Einfügen am Anfang/ in der Mitte,
der Aufwand für Aufbau in Reihenfolge ist höher, ebenso der Speicherbedarf


(edit: hab mein Programm noch etwas korrigiert, die Sekundenangaben ändern sich dadurch etwas)

 

[Gast]

Hi,

den heap space hatte ich auch vergrößert.

jetzt klappts aber mit ähnlichen zeiten wie bei dir slaterb. Versteh ich nicht.

 

[Murray]

@Slater: das Programm hat bei mir (JDK 1.6.0_10, Win XP, Default-Heap-Größe) einen OutOfMemoryError verursacht, daher der Hinweis.

Mit ein paar zusätzlichen Ausgaben sieht man auch, wie die Garbage-Collection sich zwar eifrig bemüht, im Endeffekt aber doch scheitert:

   import java.util.ArrayList;
   
   public class Zahl{
      public int z;
      public int counter;
      public Zahl(int z, int counter){
         this.z = z;
         this.counter = counter;
      }
      
      public static void main( String[] args){
        ArrayList<Zahl> liste = new ArrayList<Zahl>(10000000);
        
        long t0 = System.currentTimeMillis(); 
        Runtime rt = Runtime.getRuntime();
        for(int i=0;i<10000000;i++){
      	  if ( ((i % 10000) == 0) || (rt.freeMemory() < 10000)) {
      	 	  System.out.println( "i: " + i + " " + (System.currentTimeMillis()-t0) + "ms " + rt.freeMemory() + "/" + rt.maxMemory());
      	  }
          liste.add(new Zahl(i,0));
        }      
     }
   }

 

[Soi]

Wie kann es eigentlich zu der Speicherknappheit mitten in der Schleife kommen: Es wurde ja eine initiale Größe angegeben? Was bewirkt denn:

new ArrayList<Temperatur>(10000000);

wirklich? Ein 10 Millionen Elemente langes Array scheint ja nicht direkt angelegt zu werden.

 

[xerberuz]

Wie kann es eigentlich zu der Speicherknappheit mitten in der Schleife kommen: Es wurde ja eine initiale Größe angegeben? Was bewirkt denn:

new ArrayList<Temperatur>(10000000);

wirklich? Ein 10 Millionen Elemente langes Array scheint ja nicht direkt angelegt zu werden.

Nein. Es legt eine Array mit 10000000 Referenzen an. Die eigentlichen Objekte entstehen erst in der Schleife.

 

[SlaterB]

das Array ist leer 10.000.000 x 4 Bytes groß, um die 40 MB, was noch in den Standard-Speicher von 64 MB reinpasst,

wenn du aber noch 10 Mio. Objekte anlegst von jeweils 20 Byte oder so, dann ist Ende im Gelände

 

[Guest]

was noch in den Standard-Speicher von 64 MB reinpasst

vorausgesetzt wir sprechen von dem Einsatz der Sun VM unter Windows

 

[SlaterB]

vorausgesetzt, die Steckdose bringt 220 Volt und die Sonne geht morgen wieder auf :bae: