Array vergrößern

[Zwergpintscher]

Ich muss für die aktuelle Programmieraufgabe von Informatik I Daten in ein Array schreiben, jedoch weiß ich nicht, welche Menge Elemente benötigt werden, wenn ich das Array anlege.

Also muss mein Array erweiterbar sein, mit jedem neuen Element also um eins wachsen.

Ich habe mir nun folgendes überlegt: Ich erzeuge mir ein Array der Größe 1, in das ich das erste Element speichere. Bei jedem weiteren Durchlauf erzeuge ich ein Array der Länge altesArray.length+1 und kopiere das eine Array in das andere.

Jedoch scheint mir das in Bezug auf Laufzeit/Speicherplatz nicht sonderlich gut. Gibt es eine andere/bessere Möglichkeit?

ArrayList etc dürfen wir NICHT benutzen ;(

 

[bygones]

wenn du davon ausgehen kannst. dass so und so mehrmals der Array erweitert wird kannst du natuerlich auch einen anderen Faktor als 1 nehmen....

 

[Zwergpintscher]

wenn du davon ausgehen kannst. dass so und so mehrmals der Array erweitert wird kannst du natuerlich auch einen anderen Faktor als 1 nehmen....

Naja, jedoch kann es sein, dass nur ein Element ins Array soll, es kann aber auch sein, das 20.000 Elemente sein sollen (eigentlich weiß ich ja, dass 4480 Elemente rein sollen, nur laut unseren Übungsleitern soll das ganze auch für mehr/weniger Elemente funktionieren )!

 

[Leroy42]

Arrays kann man nicht vergrößern!

Aber anstatt dein Ansatz, nur jeweils in ein um ein Element
größeres Array zu kopieren ist wirklich ineffizient.

Bastele dir doch deine eigene kleine Klasse die sich
an ArrayList orientiert.

Sie sollte eine Instanzvariable size enthalten die die aktuell
zu verwendende Größe des intern verwalteten Arrays angibt,
bei jeder Erweiterung die Größe des internen Arrays verdoppelt
und zum Beispiel mit einer initialen Größe des internen Arrays von 10 ausgeht!

 

[Der Müde Joe]

ArrayList macht so:

default 16
wenn zu klein: verdoppeln (Arraycopy)

kannst auch eine init grösse wählen.
wenn zu klein: verdoppeln

Die Spezialfälle darfst du gerne im Source angucken ;-)

 

[Zwergpintscher]

Hmm... klingt gar nicht so verkehrt die Idee (bis auf die Tatsache, dass es sicherlich viel Arbeit ist^^). Werde mir jetzt gleich mal die Klasse ArrayList anschauen und gucken, was die so tolles kann bzw was ich davon brauch und nachprogrammieren muss =)

 

[sayang]

Ich denke mal (oder besser: ich hoffe mal), den Aufgabenstellern ist schon bewusst, dass es bessere Möglichkeiten einer "verlängerbaren" linearen Datenstruktur gibt. "Informatik I" klingt für mich eher danach, dass der Schwerpunkt hier auf der Übung des Array-Handlings an sich und der Übung im Umgang mit simplen Konstrukten wie for-Schleifen o.ä. liegt. Wenn ich Zwergpintscher beim Wort nehme, sollen die Elemente in ein "Array" - also nicht in eine List oder Map oder Table oder sonstwas - geschrieben werden.

Insofern ist der Ansatz ja nicht verkehrt, wenn auch ineffizient.
Ich würde vielleicht ein Array mit 1000 Feldern anlegen und auch immer wieder um 1000 vergrößern.
Nachdem das letzte Element in das Array gelegt wurde, würde ich dann die Länge des Arrays wieder soweit verkleinern, dass die Anzahl der Felder genau der Anzahl der Elemente entspricht.

Klar kann man die Verwaltung dieses Arrays in eine eigene Klasse schreiben - man muss nur eben in dieser Klasse ein Array als Datenstruktur benutzen.

Lg
sayang

 

[Leroy42]

Klar kann man die Verwaltung dieses Arrays in eine eigene Klasse schreiben - man muss nur eben in dieser Klasse ein Array als Datenstruktur benutzen.

Sach' ich doch: eine eigene Klasse, die sich an ArrayList orientiert

 

[Zwergpintscher]

Ja, es geht darum, dass wir uns selber mit den Datenstrukturen auseinandersetzen und nicht einfach ArrayList nehmen.
Ne andere Möglichkeit wäre auch eine verkettete Liste, die man implementieren könnte, allerdings mochte ich damals die Übungen mit den Listen schon nicht und will deswegen erstmal das mit nem Array zu machen- zumal anschließend die Elemente sortiert werden sollen und ich (als Java-Anfänger) denke, dass es einfacher ist den Sortier-Algorithmus für Arrays umzusetzen als für eine verkettete Liste

 

[Der Müde Joe]

>dass es bessere Möglichkeiten einer "verlängerbaren" linearen Datenstruktur gibt.

und wenn du jetzt den Blickpunkt auf RandomAccess richten würdest ;-)

 

[Leroy42]

...und ich (...) denke, dass es einfacher ist den Sortier-Algorithmus für Arrays umzusetzen als für eine verkettete Liste

Da hast du völlig recht!

 

[Zwergpintscher]

So, ich habs jetzt einfach gemacht, dass ich das Array immer vergrößer Sicher keine optimale Lösung, aber läuft einwandfrei und ging am schnellsten!

Danke allen für die Tips

 

[Leroy42]

dass ich das Array immer vergrößer

Noch einmal: Arrays kann man in Java (und ich glaube auch in jeder
anderen Programmiersprache) nicht vergrößern. :autsch:

 

[Zwergpintscher]

Ja, aber man folgendes kann man machen:

	//Kopiert ein Array in ein neues Array, welches ein Element groesser ist
	public static Int[] arrayCopyGroesser(Int[] alt)	{
		Int[] neu = new Int[alt.length+1];
		
		for (int i=0; i<alt.length; i++)	{
			neu[i]=alt[i];
		}
		
		return neu;
	}//ENDE arrayCopyGroesser

 

[Ark]

Ich antworte mal nur auf den Code hier, kenne das umgebende Problem nicht.

Wenn ich richtig informiert bin, verdoppelt z.B. ein StringBuilder seine Kapazität, wenn die alte überschritten wird. Ich denke, das hat etwas mit der Komplexität zu tun. Bei sukzessivem Anhängen einzelner Zeichen wächst so die Kapazität exponentiell, während diese Vergrößerung selbst nur noch logarithmisch oft (<-- mir fällt dafür gerade kein besserer Ausdruck ein) vorgenommen wird. Betrachtet man beide Umstände zusammen, ergibt sich so nur etwa linearer Aufwand. Da aber das Umkopieren nur noch logarithmisch oft geschieht, wird dieses zu noch erträglichem, wenn nicht sogar vernachlässigbarem Aufwand, während die gerade beschriebene Variante, ein Array nur um ein einziges Element "wachsen" zu lassen, zu (halb-)quadratischer Komplexität führt.

Ark

 

[Leroy42]

während diese Vergrößerung selbst nur noch logarithmisch oft (<-- mir fällt dafür gerade kein besserer Ausdruck ein) vorgenommen wird.

Wie wär's mit linear oft.

(oder doch gleich quasi-linear oft )