Ein paar Performance Fragen

Hallo ihr da drausen,

1. kennt jemand eine Implementierung mit der man mit so wenig Zeitaufwand
wie möglich ein Array rotieren lassen kann

also Beispiel: int arr[] = {1,2,3,4,5};

rotLeft(1,arr);

ergibt dann arr = [2,3,4,5,1];

gibt es dann schon funktionen oder operatoren in c? wie ">>" z.B. ??

CStoll

Konkrete Funktionen zum Rotieren gibt es nicht, das müsstest du selber schreiben. Eine recht schnelle (und platzsparende) Lösung wäre:

spiegele die ersten k Elemente
spiegele die letzten n-k Elemente
spiegele das komplette Array

(und das Spiegeln bekommst du jeweils mit einer Schleife:

for(i=start,j=ende;i<j;++i,--j)
  swap(arr+i,arr+j);

Undertaker

CStoll schrieb:

Eine recht schnelle (und platzsparende) Lösung wäre:

spiegele die ersten k Elemente

spiegele die letzten n-k Elemente

spiegele das komplette Array

(und das Spiegeln bekommst du jeweils mit einer Schleife:
for(i=start,j=ende;i<j;++i,--j)
  swap(arr+i,arr+j);

schnell und platzsparend? gegenüber was denn?

CStoll

Alternativen, die mir noch einfallen würden wären:

- kopiere die hinteren n-k Elemente an den Anfang eines zweiten Arrays
kopiere die vorderen k Elemente dahinter
kopiere alles zurück ins Ursprungsarray

(dürfte etwas schneller sein, braucht aber massiv zusätzlichen Speicherplatz)

- rotiere k-mal um ein Feld (dazu jedes Mal das erste Element zwischenspeichern, alle anderen Elemente ein Feld nach vorne kopieren und das gespeicherte Element ans Ende hängen)

(ist vom Platzverbrauch vergleichbar mit obiger Lösung, aber deutlich langsamer)

Aber wenn du eine noch bessere Möglichkeit kennst, ein Array zu rotieren - ich bin ganz Ohr.

Wenn das Ding groß ist und der eigentliche Zugriff darauf nicht extremst schnell sein muss oder die Länge gar Mod Zweierpotenz ist, kann man überlegen erst gar nicht zu rotieren, sondern einen index einfach mod-inkrementieren.

also momentan mach ich das so:

void shiftLeft(BYTE *bits, BYTE shiftCount, BYTE bitsLength)
{
	BYTE copy[bitsLength];
	int i,j;

	//#ifdef DEBUG
	//printf("shiftLeft\n");
	//printBin("Org",bits,1,bitsLength);
	//#endif

	// original Bitfolge kopieren
	memcpy(copy, bits, bitsLength);

	// Shiften	
	for(i = 0; i < bitsLength; i++)
	{
		int newPos = (i + shiftCount);

		if(newPos > (bitsLength - 1))		bits[i] = copy[newPos - bitsLength];
		else 														bits[i] = copy[newPos];							
	}	
	//#ifdef DEBUG
	//printBin("Shift",bits,1,bitsLength);
	//#endif
}

eure Vorschläge sind mir nicht ganz klar aber ich denk mal drüber nach.
Welche Nachteile würde mein Implementierung denn haben?

CStoll

Der Hauptnachteil deiner Lösung ist, daß du damit zusätzlichen Speicher (für copy[]) benötigst, je nach Größe kann das einiges kosten. (technisch entspricht der Ansatz der ersten Metohde, die ich als mögliche Alternativen dort oben erwähnt hatte).

Ohne zusätzlichen Speicher kommst du mit der erstgenannten Variante aus:

void reverse(BYTE* bits, int count)
{
  BYTE tmp;
  int i,j;
  for(i=0,j=count-1 ; i<j ; ++i,--j)
  {
    tmp = bits[i];
    bits[i] = bits[j];
    bits[j] = tmp;
  }
}

void shift(BYTE* bits, int count, int len)
{
  reverse(bits,count);
  reverse(bits+count,len-count);
  reverse(bits,len);
}

Wobei Tim's Lösung wohl für (sehr) große Arrays besser ist: du kopierst gar nichts um, sondern notierst dir nur die (reale) Startposition des Arrays - das i-te Element erreichst du bei Bedarf an Position arr[(i+start)%len] .

Also das Feld ist umgenau zu sein hat das Feld 64 Einträge.

Wichtig ist mir dabei mehr die Geschwindigkeit aber der Speicherbedarf sollte auch nicht überhand nehmen.

Das mit der Extrafunktion fänd ich tu much und mach die Sache auch noch langsamer oder.

Bemerkung das ganze läuft später auf eine 24Mhz/8Mhz Prozessor.

Die Lösung von Tim is zwar flott kann ich aber so in meinem Algorithmus nicht verwenden da die nachfolgenden Prozeduren nix von dem shiften mitbekommen.

CStoll

Veritas696 schrieb:

Also das Feld ist umgenau zu sein hat das Feld 64 Einträge.

Wichtig ist mir dabei mehr die Geschwindigkeit aber der Speicherbedarf sollte auch nicht überhand nehmen.

Das mit der Extrafunktion fänd ich tu much und mach die Sache auch noch langsamer oder.

Nicht wesentlich. Und wenn es dir besser gefällt, kannst du die drei Schleifen auch direkt in deine Funktion reinpacken

Btw, hast du vorher überprüft, ob das Array-rotieren wirklich der Engpass bei deinem Programm ist? Nicht daß du gerade versuchst, eine absolut unwichtige Ecke des Programms zu optimieren.

Die Lösung von Tim is zwar flott kann ich aber so in meinem Algorithmus nicht verwenden da die nachfolgenden Prozeduren nix von dem shiften mitbekommen.

Das Problem kannst du umgehen, indem du die nachfolgenden Prozeduren entsprechend umstellst

genau genommen, muss das ganze Programm so schnell wie möglich ablaufen und#
da geh ich grad mal alle Ecken durch

weitere Frage:

typedef unsigned char BYTE;
void conv2Bin(BYTE *inputField,BYTE *binField,BYTE length)
{
  int i,j;
  int binIndex = 0;

  for(i = 0; i < length; i++)   	// jedes BYTE des Blocks durchgehen
  {
    for(j = 0; j < 8; j++)        		//jedes Bit eines Bytes anschauen
   {
     // wenn Bit an Stelle j -> 0 dann 0 in binField eintragen
     if((inputField[i] & (128 >> j)/*BINCONV[j]*/) == 0) 
       binField[binIndex++] = 0;
     else   						  
       binField[binIndex++] = 1;			
   }
  }		
}

was lässt sich hieran noch optimieren oder ändern.

Beschreibung:
Die Funktion wandelt ein "Bytearray" in ein "BitArray" um
Bsp: aus
aus inputField -> [0x01, 0x05, 0xF0]
wird
binField = [0,0,0,0,0,0,0,1,
0,0,0,0,0,1,0,1,
1,1,1,1,0,0,0,0]

CStoll

Veritas696 schrieb:

genau genommen, muss das ganze Programm so schnell wie möglich ablaufen und#
da geh ich grad mal alle Ecken durch

Falscher Ansatz: Bevor du beginnst zu optimieren, solltest du herausfinden, welche Programmteile wirklich kritisch sind (und welche besonders oft durchlaufen werden). Dort sind dann die Stellen, wo es sich wirklich lohnt zu optimieren.

also die conv2Bin Funktion wird am häufigsten durchlaufen.

Ich denke mein Programm ist schon recht schnell, benutze
kaum Bibliotheksfunktionen außer 1 2 mal memcpy,
arbeite auf indizierten Arrays wo ich schnell an die gewünschten Stellen
komme, arbeite viel mit "<<" und ">>" anstatt Multiplikationen und Divisionen.

Deswegen schau ich mir ja jetzt grad solche Funktionen an die öfters benutzt
werden und vielleicht durch Profis wie auch noch effizienter werden können.

CStoll

Hmm, die if()-Abfrage da drin kannst du auf jeden Fall kürzen zu:

binField[binIndex++] = (inputField[i] & (128 >> j)/*BINCONV[j]*/) == 0);

(keine Ahnung, ob der Compiler intelligent genug ist, sowas von selber zu optimieren).

(btw, und Bibliotheksfunktionen sind in vielen Fällen wesentlich besser optimiert als du das jemals mit handgeschriebenem Code hinbekommen kannst)

hm, stimmt! gute idee werd ich einfach mal machen, wer traut schon seinem Compiler

Klar sind Bibpliotheksfunktionen sehr gut optimiert, wollt ich nicht abstreiten :p aber für die Sachen die ich da mache gibts eh keine geeigneten Funktionen für.

Was sollte man denn noch alles aus performace-Technischen Grunden beachten.
vorallem auf einem langsamen Prozessor?

binField[binIndex++] = ((inputField[i] & (128 >> j)) == 0);

funktioniert irgendwie nicht, bekomm da andere Ergebnisse raus

CStoll

Also auf der Ebene einzelner Funktionen bleibt wohl nur Mikro-Optimierung (Ersparnis einzelner Taktzyklen). Wenn du echt etwas an Leistung herausholen willst, müsstest du vermutlich dein gesamtes System umbauen. Das geht dann z.B. in die Richtung "Lazy Evaluation" (siehe Tim's Lösung zum Array-Rotieren) oder Verwendung anderer Basisalgorithmen (der Umstieg von BubbleSort auf QuickSort kann in manchen Fällen schon einiges ausmachen - gerade wenn du oft große Datenmengen sortieren mußt).

Undertaker

Veritas696 schrieb:

Beschreibung:
Die Funktion wandelt ein "Bytearray" in ein "BitArray" um
Bsp: aus
aus inputField -> [0x01, 0x05, 0xF0]
wird
binField = [0,0,0,0,0,0,0,1,
0,0,0,0,0,1,0,1,
1,1,1,1,0,0,0,0]

wofür brauchst du das?
ich habe so den verdacht, dass du auf diese funktion komplett verzichten kannst...

binField[binIndex++] = !((inputField[i] & (128 >> j)) == 0);

musste noch invertiert werden aber funzt auch nicht wirklich

@Undertaker: brauch das damit ich die einzelnen Bits Permutieren kann mit entsprechenden Matrizen.

@CStoll: na das würde zu weit führen, und sortieren muss ich auch nix.

Geht im großen und ganzen ums Bitknipsen(Permutieren, expandieren, XOR etc.)

P.S: na bald wisst ihr wohl auch was ich hier eigentlich tue

Undertaker

Veritas696 schrieb:

@Undertaker: brauch das damit ich die einzelnen Bits Permutieren kann mit entsprechenden Matrizen.

kannst du nicht das bit zu dem zeitpunkt rausholen, wenn du's brauchst?
dann könntest du auf die umwandlung verzichten...
z.b. so:

// Helper function to read one bit from array
int GetBit (unsigned char *array, unsigned int pos) 
{
  unsigned int bytepos = pos>>3;
  unsigned int bit = 7 - (pos - (bytepos<<3));
  return !!(array[bytepos] & (1<<bit)); 
}

die funktion gibt 1 zurück, wenn das bit in 'array' an stelle 'pos' gesetzt ist, sonst 0

CStoll

Veritas696 schrieb:

@CStoll: na das würde zu weit führen, und sortieren muss ich auch nix.

Ja, das war nur ein Beispiel (da ich deine Zielstellung nicht kannte, vermutlich ein schlechtes).

Geht im großen und ganzen ums Bitknipsen(Permutieren, expandieren, XOR etc.)

Da ist es wesentlich Platz- (und meistens auch zeit-)sparender, die Bits nicht auf Vorrat auseinanderzunehmen, sondern erst bei Bedarf genau die Bits herauszuziehen, mit denen du rechnen willst.