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.

Einsteiger

@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.

DirkB

@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;

Einsteiger

@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.

Schlangenmensch

@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

DirkB

@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.

DocShoe

@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:

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

hustbaer

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.

Einsteiger

@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

Wutz

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

Einsteiger

@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.

hustbaer

@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.)