Datem im Array effektiv neu anordnen



  • Hallo Leute,

    ich habe hier ein Struktur-Array das ich neu anordnen möchte. Leider fehlt mir noch der zündened Gedanke wie ich das sinnvoll und effektiv hinbekomme, da die Struktur aus ca. 10000 oder mehr Elementen besteht.

    vorher			nachher
    
    Eintrag[0][-]		Eintrag[5][+]
    Eintrag[1][-]		Eintrag[6][+]
    Eintrag[2][-]		Eintrag[0][-]
    Eintrag[3][-]		Eintrag[1][-]
    Eintrag[4][-]		Eintrag[2][-]
    Eintrag[5][+]		Eintrag[10][+]
    Eintrag[6][+]		Eintrag[3][-]
    Eintrag[7][-]		Eintrag[4][-]
    Eintrag[8][-]		Eintrag[13][+]
    Eintrag[9][-]		Eintrag[7][-]
    Eintrag[10][+]		Eintrag[8][-]
    Eintrag[11][-]		Eintrag[9][-]
    Eintrag[12][-]		Eintrag[11][-]
    Eintrag[13][+]		Eintrag[12][-]
    Eintrag[14][-]		Eintrag[14][-]
    Eintrag[15][-]		Eintrag[15][-]
    Eintrag[16][-]		Eintrag[16][-]
    Eintrag[17][-]		Eintrag[17][-]
    Eintrag[18][-]		Eintrag[18][-]
    Eintrag[19][-]		Eintrag[19][-]
    

    Die linke Seite ist die Ausgangssituation, die mit [+] markierten Elemente sollen nach oben verschoben werden. Jedoch soll beim Verschieben die Anzahl der Lücken erhalten beleiben. Hat jemand eine Idee wie man das umsetzen kann?



  • Was sind den "Lücken"? Und was heißt "nach oben verschoben"? Ein Position? An´s Ende?



  • @DocShoe sagte in Datem im Array effektiv neu anordnen:

    Was sind den "Lücken"? Und was heißt "nach oben verschoben"? Ein Position? An´s Ende?

    Mit Lücken meine ich die Elemente die mit "[-]" gekennzeichnet sind, z.B. zwischen [6] und [10] sind vorher 3 Elemente mit "[-]" (7,8,9) und nach dem nach oben verschieben ebenfalls 3 Elemente mit "[-]" (0,1,2) d.h. der Abstand zwischen [6] und [10] beträgt vorher wie nachher immer noch (wie gewünscht) 4 Elemente.
    Ich hab mal vorher und nachher eingefügt, ich hoffe es ist dann besser verständlich. Eintrag[5] wird von Position 5, ganz nach oben auf Position 0 verschoben, alle restliche Einträge mit [+] "folgen" ihm mit unverändertem Abstand zueinander.
    [+] = BOOL ist_markiert = true;
    "[-]" = BOOL ist_markiert = false;



  • Wenn ich dich richtig verstanden habe möchtest du eigentlich alle Elemente vor dem ersten zu verschiebenden Element löschen und den Rest in der Reihenfolge und Abstand behalten, richtig?



  • @DocShoe ich glaube löschen möchte er nicht.
    Jede zusammenhängende Gruppe, deren Elemente mit einem Plus markiert sind, soll um die Größe der davor stehenden zusammenhängenden Gruppe an Elementen, die mit einem minus markiert sind, nach oben verschoben werden.



  • @Schlangenmensch sagte in Datem im Array effektiv neu anordnen:

    ich glaube löschen möchte er nicht.
    Jede zusammenhängende Gruppe, deren Elemente mit einem Plus markiert sind, soll um die Größe der davor stehenden zusammenhängenden Gruppe an Elementen, die mit einem minus markiert sind, nach oben verschoben werden.

    Stimmt nur bedingt, die erste "Lücke" 0 bis 5 gibt an um wieviel alle markierten Elemente nach oben geschoben werden. Hier mal mein Code der eben nicht effektive ist:

    	int		first_id = 0;
    
    	while(Element[0].ist_markiert == false){
    		element_t	Element_tmp;
    		BOOL		first_id_found = false;
    
    		for(i = first_id; i < anzahl_elemente; i++){
    			if(Element[i].ist_markiert == true){
    				if(first_id_found == false){
    					first_id_found = true;
    					first_id = (i-1);					//bein nächsten Durchlauf fangen wir da an wo sich das erste markierte Element befindet
    				} 
    				memcpy(&Element_tmp, &Element[i-1], sizeof(element_t));	
    				memcpy(&Element[i-1], &Element[i], sizeof(element_t));
    				memcpy(&Element[i], &Element_tmp, sizeof(element_t));
    			}
    		}
    	}
    
    


  • Gibt da so eine Funktion in der C Bibliothek namens quicksort.



  • @Einsteiger zum kopieren von einem Element brauchst du kein memcpy (da fehlen auch ein paar &)

    Wenn du längere Sequenzen verschieben willst musst du (wegen möglicher überlappung) auch memmove nehmen.



  • It's a rotate? Mit ForwardIt als element_t* und einem swap wie oben sollte es auch in C gehen.



  • @DirkB sagte in Datem im Array effektiv neu anordnen:

    zum kopieren von einem Element brauchst du kein memcpy (da fehlen auch ein paar &)
    Wenn du längere Sequenzen verschieben willst musst du (wegen möglicher überlappung) auch memmove nehmen.

    Ja da hast du recht, Code abtippen birgt halt mögliche Fehlerquellen. memmove ist bekannt, aber meiner Meinung nach in diesem Fall nicht notwendig.

    @TGGC sagte in Datem im Array effektiv neu anordnen:

    Gibt da so eine Funktion in der C Bibliothek namens quicksort.

    quicksort ist bekannt, aber ich wüsset nicht was ich in die callback Funktion als Vergleicher reinschreiben sollte, was ist dein Vorschlag?

    Hier noch eine kurze Erklärung was ich mit effektiv meine: Rechenzeit sparen ist wichtig, Belegung von Arbeitsspeicher ist unwichtig. D.h. wenn für die Lösung zusätzliche Variablen in die Struktur eingefügt werden müssten, dann ist das OK. Wenn ein identisches Struktur-Array als Hilfsstruktur notwendig ist, dann ist das auch ok.

    @manni66 sagte in Datem im Array effektiv neu anordnen:

    It's a rotate? Mit ForwardIt als element_t* und einem swap wie oben sollte es auch in C gehen.

    rotate kenne ich nicht. Das werde ich mir mal anschauen, Danke.



  • @Einsteiger sagte in Datem im Array effektiv neu anordnen:

    Ja da hast du recht, Code abtippen birgt halt mögliche Fehlerquellen.

    Darum ja auch Copy&Paste.

    memmove ist bekannt, aber meiner Meinung nach in diesem Fall nicht notwendig.

    Habe ich auch nicht behauptet. Aber memcpy ist hier auch nicht nötig.
    tmp = a[i-1]; a[i-1]=a[i]; a[i]= tmp;



  • @DirkB sagte in Datem im Array effektiv neu anordnen:

    tmp = a[i-1]; a[i-1]=a[i]; a[i]= tmp;

    Bist du sicher dass das funktioniert? Ich habe gedacht das würde nur gehen wenn die Elemente Pointer wären.
    Aber eigentlich bin ich auf der Suche nach eine besseren Algorithmus, nicht an Feintuning an dem hier geposteten Code. Wie gesagt der Code funktioniert bei mir, die Ausgabe entspricht exakt dem erwarteten Ergebinss, nicht jedoch die dafür benötigte Rechenzeit.



  • @Einsteiger Wenn es um Optimierung geht, muss man natürlich fragen, bei welchen Daten brauchst du wie lange, wie hast du das gemessen, auf welchem System und mit welchen Compiler Einstellungen.

    Als Bonus: Testdaten und Compilierfähiges Programm bereit stellen, dann kann man selber rumspielen 😉



  • @Einsteiger sagte in Datem im Array effektiv neu anordnen:

    Bist du sicher dass das funktioniert?

    Ja.

    Ich habe gedacht das würde nur gehen wenn die Elemente Pointer wären.

    Du kennst das wohl nur aus der swap-Funktion.

    Der Compiler erkennt an dem Code, dass du zwei Elemente vertauschen möchtest und kann das optimieren - im besten Fall zu einem swap-Opcode.
    Ob das bei den drei memcpy-Aufrufen auch erkannt wird, kann ich nicht sagen.



  • @Einsteiger sagte in Datem im Array effektiv neu anordnen:
    ... nicht jedoch die dafür benötigte Rechenzeit.

    Wie lange dauert das denn konkret (bei wie vielen Elementen)?

    Mal sehen, ob ich dich jetzt richtig verstanden habe:
    Du möchtest alle mit + markierten Elemente an den Anfang der List schieben, wobei alle zusammenhängenden + eine Gruppe ergeben. Zwischen den Gruppen gibt es nicht-markierte Elemente, die zum Auffüllen der Plätze zwischen den Gruppen benutzt werden, damit zwischen den verschobenen Gruppe die Anzahl der nicht-markierten Elemente gleich bleibt?

    Wenn du sagst, dass Speicherplatz egal ist kann man die Liste vllt besser neu aufbauen und dabei so vorgehen:

    1. neue Liste mit der gleichen Anzahl der Elemente erzeugen
    2. Index des ersten nicht-markierten Elements finden (in deinem Beispiel 0)
    3. Index und Länge der nächsten Gruppe finden (in deinem Beispiel: 5,2 )
    4. ab Gruppe 2: Abstand zur vorherigen Gruppe bestimmen und neue Liste mit unbenutzten nicht-markierten Elementen auffüllen
    5. Gruppe an die neue Liste anhängen, weiter bei 4
    6. wenn es keine weitere Gruppe mehr gibt die alte Liste bis zu Ende durchlaufen und die bisher nicht benutzten nicht-markierten Elemente anhängen


  • Einfach und vermutlich schnell genug:

    • Ermittle die Position des ersten (+) Elements im originalen Array. Wenn es keins gibt oder die Position 0 ist bist du fertig.
    • Mach ein neues Array mit gleicher Grösse.
    • Kopiere alles ab der ermittelten Position an den Anfang des neuen Arrays.
    • Füll den freigebliebenen Rest im neuen Array mit (-) Markierungen auf (beliebiger Wert).
    • Geh über das neue Array drüber und ersetze alle (-) Elemente. D.h. wenn du auf ein (-) Element triffst dann überschreibst du es mit dem nächsten (-) Element im originalen Array.
    • Kopier das neue Array über das alte drüber

    Das ist O(N), besser wird's nicht. Linear könnte man es vermutlich noch etwas schneller machen, aber ich glaube dass es vermutlich so reicht. Denn jede Optimierung würde den Code vermutlich komplizierter machen.



  • @hustbaer sagte in Datem im Array effektiv neu anordnen:

    Das ist O(N), besser wird's nicht. Linear könnte man es vermutlich noch etwas schneller machen, aber ich glaube dass es vermutlich so reicht. Denn jede Optimierung würde den Code vermutlich komplizierter machen.

    So sieht's aus! Genau so geht's, danke für die Hilfe hustbaer. Das hatte ich mit besserem Algorithmus gemeint. Hier ein kurzer Benchmark:

    Anzahl Elemente		mein alter Code		Lösungsvorschlag hustbaer
    
    10.000		=	0,109s			0,000s
    25.000		=	0,710s			0,001s
    50.000		=	2,727s			0,001s
    100.000		=	12,102s			0,002s
    200.000		=	81,477s			0,002s
    500.000		=	zu lange		0,011s
    1.000.000	=	zu lange		0,022s
    
    mit s = Sekunden
    
    


  • https://onlinegdb.com/HJ8StpBO8
    O(N-startindex-anzahlmarkiert)



  • @Wutz sagte in Datem im Array effektiv neu anordnen:

    https://onlinegdb.com/HJ8StpBO8

    Danke, interessanter Code, da muss ich genau kucken, der ist ziemlich kompakt geschrieben.



  • @Wutz sagte in Datem im Array effektiv neu anordnen:

    https://onlinegdb.com/HJ8StpBO8
    O(N-startindex-anzahlmarkiert)

    Völliger Schwachsinn.
    (EDIT: Also die Behauptung dass es O(N-startindex-anzahlmarkiert) wäre. Der Code ist kein Schwachsinn soweit ich erkennen kann, nur total unleserlich formatiert. Und halt genau so O(N) wie alles andere mit dem man dieses Problem korrekt lösen kann O(N) sein muss - besser geht einfach nicht.O(x) ohne weitere Angaben wird allgemein so verstanden dass man jede Operation zählt. D.h. memcpy mit X Bytes muss auch als X Operationen gezählt werden. Und eine Schleife die Y durchläufe macht als Y Operationen, egal wie wenig diese Schleife tut. Sonst könnte ich auch schreiben mein Vorschlag ist O(1). Und wenn dann jemand meint das wäre nicht richtig sag ich einfach "ach, ich hab gemeint O(1) für die Anzahl dynamischer Speicheranforderungen". Schwachsinn.)


Log in to reply