unschöne schleifen.jemand ne bessere idee

[souly]

hallo,

habe folgendes problemchen oder besser anliegen.

hab mir einen algorithmus implementiert bei dem ich ein Eingabearray bekomme (unsortiert) und dann die n-größte zahl ermittelt, dabei wird das eingabearray in 3 weitere arrays aufgeteilt. eins in dem alle werte kleiner einem vergleichswert sind, eins für die, die exakt dem vergleichswert entsprechen und dann noch eins wo alles größer als der vergleichswert reinkommt.

klappt soweit wunderbar, nur was mich etwas stört, ich muss zuerst das gesamte array durchlaufen und die vergleichsopration auf <, > bzw. = durchführen und zählen wieviele werte für die 3 neuen arrays, in die das ganze aufgeteilt werden, soll jeweils hinein müssen.
dann erzeuge ich die 3 arrays anhand der ermittelten größen und lassen exakt die selbe vergleichsroutine nochma durchlaufen, nur das ich diesesmal die werte halt verschiebe, bzw kopiere.

Das ist natürlich doppelt-gemoppelt. Kann man das irgendwie kombinieren oder sich den zweiten durchlauf sparen? find das so sehr unschön

//Zählen wieviele Elemente in die 3 Mengen gehören
		int sizeL=0, sizeE=0, sizeG=0;
		
		for (int i=0; i < in.length; i++)
		{
			if (cmp.compare(in[i], in[rndDigit]) < 0)
				sizeL++;
			else if (cmp.compare(in[i], in[rndDigit]) == 0)
			 	sizeE++;
			else
				sizeG++;
		}
		
		//Hilfsarrays erstellen
		Object 	[] l = new Object [sizeL]; int lc = 0;
		Object	[] e = new Object [sizeE]; int ec = 0;
		Object	[] g = new Object [sizeG]; int gc = 0;
		
		//Eingangsarray in die Hilfsarrays verteilen gemäß Vergeichsschlüssel
		for (int i=0; i < in.length; i++)
		{
			if (cmp.compare(in[i], in[rndDigit]) < 0)
				l[lc++] = in[i];
			else if (cmp.compare(in[i], in[rndDigit]) == 0)
			 	e[ec++] = in[i];
			else
				g[gc++] = in[i];
		}

 

[Marco13]

Hm - man könnte statt Arrays einfach Listen nehmen (z.B. ArrayList) und die dann bei Bedarf am ende mit list.toArray in Arrays zurückverwandeln. Alternativ könnte man (je nachdem, worum es da geht) die Arrays am Anfang alle so groß machen, wie das hauptarray, und am ende die Daten umkopieren (und Arrays der passenden Größe). Muss man sich überlegen - letzteres sieht erstmal komisch aus, könnte aber "effizienter" sein als die Lösung mit der List.

 

[souly]

das ganze ist eine implementierung des randomized quick select algorithmus.

http://pine.cs.yale.edu/pinewiki/QuickSelect

hab mich jetzt mal so beholfen....sieht vom stil her schöner aus, aber ob es wirklich perfomanter ist.

ich kopiere jetzt nur noch 3x die arrays, anstatt die vergleichsoperation auszuführen....

		//Hilfsarrays erstellen
		Object 	[] l = new Object [in.length]; int lc = 0;
		Object	[] e = new Object [in.length]; int ec = 0;
		Object	[] g = new Object [in.length]; int gc = 0;
		
		//Eingangsarray in die Hilfsarrays verteilen gemäß Vergeichsschlüssel
		for (int i=0; i < in.length; i++)
		{
			if (cmp.compare(in[i], in[rndDigit]) < 0)
				l[lc++] = in[i];
			else if (cmp.compare(in[i], in[rndDigit]) == 0)
			 	e[ec++] = in[i];
			else
				g[gc++] = in[i];
		}
		
		//Umkopieren in Arrays mit passenden Längen
		Object [] x;
		x = new Object [lc];
		for (int i=0; i < lc; i++)
			x[i] = l[i];
		l = x;
		
		x = new Object[ec];
		for (int i=0; i < ec; i++)
			x[i] = e[i];
		e = x;
		
		x = new Object[gc];
		for (int i=0; i < gc; i++)
			x[i] = g[i];
		g = x;

 

[Marco13]

Ach so ja - bei "umkopieren" dachte ich eigentlich an drei Aufrufe von System.arraycopy - das macht zwar im Prinzip das gleiche, sieht aber deutlich hübscher aus 🙂

Wäre halt interessant zu wissen, um welche Arraygrößen es da geht. Wenn das ein Array mit 10 Millionen Einträgen ist, und man weiß z.B. das nur wenige (<10) Zahlen GLEICH der Zahl n sind, dann bräuchte man dafür keinen weiteren Array mit 10 Millionen Einträgen zu erstellen....

Wenn ich den Pseudocode aus dem Wiki richtig überflogen habe, wird das ganze ja Rekursiv aufgerufen - das sollte dann ggf. nicht alles mit neuen Arrays gemacht werden: Man könnte VIELLEICHT (das müßte man sich überlegen!) EINmal die großen Arrays erstellen, und die dann ALLE DREI der Methode übergeben. Bei den Rekursiven aufrufen würden die dann die Rollen tauschen... grob

void doit(int a[], int k)
{
    int temp0[] = new int[a.length];
    int temp1[] = new int[a.length];
    doit(a, temp0, temp1, k);
}

void doit(int a[], int temp0[], int temp[1], int k)
{
    verteileAuf(temp0);
    verteileAuf(temp1);
    ...
    if (bla)
    {
       // Rekursiver aufruf:
       doit(temp0, a, temp1, k) // Arrays a und temp0 tauschen die Rollen
    }
    else
    {
       // Rekursiver aufruf:
       doit(temp1, temp0, a, k) // Arrays a und temp1 tauschen die Rollen
    }

}

ist aber nur ein spontaner Gedanke - müßte man sich mal genauer überlegen.

 

[Gast]

denke ich werds so lassen, ich weis nämlich nicht genau ob es seitens des Aufgabenstellers ok ist vorgefertigte Routinen zum kopieren zu nehmen....auch wenn das was ich mache vermutich der selbe code ist, der dabei ausgeführt werden würde.

danke fürs mitdenken. dachte es gäb da einen direkten, besseren ansatz. dann lass ich es so....es läuft ja 🙂