Elemente in Array einfügen

Herakles

Herakles

Profifragensteller
Moin!

Ich möchte mit einer Schleife über ein Array Bytes an bestimmten Stellen einfügen.

Außer mit memmove kommt mir aber keine Idee, das zu realisieren. Auf memmove möchte ich aufgrund von Performanceproblemen bei einem bestimmten Prozessor gern verzichten. Und am Liebsten soll das alles mit nur einem Array klappen, also kein Zusammenkopieren eines zweiten Arrays benötigen.

Hat jemand eine tolle Idee, wie ich das realisieren kann? Ein Link genügt mir auch.

Ich programmiere in C, Pseudocode würde mir aber auch helfen.

Viele Grüße
Herakles
 
Für eine ordentliche Antwort sind das nicht genug Informationen. Beschreibe die Datenstrukturen, Quell- und Zieldaten.
 
So sieht's bislang aus:

Code: 
void escapes_einfuegen( uint8_t *Pdaten, uint8_t anzahl_daten, uint8_t *laenge ) {
	uint8_t i;
	
	for( i=0; i < anzahl_daten; i++ ) {
		if( (Pdaten[i] == ESC) || (Pdaten[i] == END) ) {
			// Verschiebe das aktuelle Byte um eins nach hinten, um ein zusaetzliches
			// Byte einfuegen zu koennen
			memmove( &Pdaten[i+1], &Pdaten[i], anzahl_daten - i );
			// Ersetze das aktuelle Byte mit dem Escape-Byte
			if( Pdaten[i] == ESC ) Pdaten[i] = ESC_ESC;
			else if( Pdaten[i] == END ) Pdaten[i] = ESC_END;
			(*laenge)++;
			i++;
		}
	}
}

Und nun suche ich etwas, das das memmove wegrationalisiert. :)

Herakles
 
Das ist eine ziemlich undankbare Aufgabe, da wirst du nichts schnelleres als memmove finden.

Du hast 2 möglichkeiten. Entweder du nimmst einen 2. Array in Kauf oder du machst das verschieben effizienter (die verschiebungen auf das Nötige reduzieren). Da gibt es mehrere Möglichkeiten je nachdem ob du mehr Speicher oder Rechenzeit sparen willst.
 
So ist das komplexitätsmäßig Wahnsinn: O(n^2)
Daher erst einmal drüberlaufen und zählen, wie viele Bytes eingefügt werden müssen. Daraus berechnen, wo das letzte Byte eingefügt wird und als Zeiger merken.
Danach ein zweites mal drüber und zwar diesmal rückwärts und dabei Bytes kopieren und einfügen.
Per Konstruktion kann der Zielzeiger den Quellzeiger nicht überholen.
Das ganze sieht dann etwa so aus:
Code: 
u1* const end = daten + anzahl;
u1*       dst = end;
for (u1 const* i = daten; i != end; ++i) {
  if (*i == ESC) ++dst;
}
for (u1* i = end; i != daten;) {
  u1 const d = *--dst = *--i;
  if (d == ESC) *--dst = ESC_ESC;
}
 
ich wuerde an deiner stelle vielleicht doch den weg mit einem zweiten array gehen:

Code: 
void einfuegen(char* array,int einfpos,char neuval)
void einfuegen(short* array,int einfpos,short neuval)
void einfuegen(int* array,int einfpos,int neuval)
void einfuegen(long long* array,int einfpos,long long neuval)
{
  int length;
  void* tmparray;

  length=sizeof(array)-einfpos*sizeof(array[0]);
  tmparray=malloc(length);
  memcpy(tmparray,&array[einfpos],length);
  tmparray[einfpos]=neuval;
  memcpy(&array[einfpos+1],tmparray,length-sizeof(array[0]));
  free(tmparray);
}
dieser code fuegt an der stelle einfpos das neue element neuval in array ein.
 
Statt bei jedem Einfügen einmal zu kopieren (was schon Wahnsinn ist) jeweils zweimal zu kopieren + malloc + free erscheint mir nicht eine Verbesserung zu sein.
Ich bezweifle, dass das memmove() per se das Problem ist, sondern vielmehr dass quadratisch viele Daten kopiert werden.
[edit]
Was mir gerade noch auffällt: sizeof(array) liefert /nicht/ die Größe der Reihung, denn array ist deklariert als Zeiger, daher bekommt man einfach nur die Größe des Zeigers (also üblicherweise 4 oder 8).
[/edit]
 
Zuletzt bearbeitet:
Tron, Dettus - wie gehabt tolle Ergebnisse hier bei bsdforen.de. Dank Euch beiden! Das wird mir weiterhelfen!

Ergebendst, Herakles
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben