Suchfunktion optimieren?

BorisDieKlinge

bool boFound=false;
	for(k=0; k< DB_COUNT && !boFound; k++,iRawID=k){
		for(l=0; l< acRawTag[k].iSize && !boFound ;l++,iTagID=l){		
			if(!strcmp(acRawTag[k].pDataStructure[l].acTagName,acTag))
				boFound=true;
		}
	}

hallo habe mehrer Tabellen an einträgen, wobei es eine haupttabelle gibt, welche wiederrum auf andere tabellen verweist sin denen gesucht wird (deswege 2 for-schleifen)

die strcmp funktion wird wohl am meisten zeit fressen.. was könnte man hier optimieren um schneller zu vergleichen?

wenn ich es so mache

if(!memcmp(acRawTag[k].pDataStructure[l].acTagName,acTag,strlen(acTag)))

geht ehr langsamer, weil das strlen wieder zeit frist..

was mir aufgefallen ist, das die erste suche in den tabel 25ms geht, wenn ich dann wieder neu beginne gehst unter <1ms.. ?? kann es sein das er sich durch die erste suche erst die tabellen im speicher anlegt?

Bitte ein Bit

Am strcmp kann man direkt nichts ändern, aber an der Suche an sich selbst, da du ja anscheinend nur feststellen willst, ob ein gewisser Eintrag vorhanden ist.

bool boFound=false;

for(k=0; k< DB_COUNT && !boFound; k++,iRawID=k)
{
  for(l=0; l< acRawTag[k].iSize && !boFound ;l++,iTagID=l)
  {       
    if(!strcmp(acRawTag[k].pDataStructure[l].acTagName,acTag))
    {
      boFound=true;
      goto stop
    }
  }
}

stop:

Alternativ kann man es ähnlich wie bei Google machen und B* Bäume verwenden. Oder wenn nur in Tabellen suchen musst, kannst du ja auch eine SQL Datenbank benutzen.

BorisDieKlinge

es sind keine Datenbank tabellen! mit tabellen meine ich statische structur arrays:

typedef {

.....

}STRUCTURE;

static STRUCTURE [] ={{....},{....}};

dein goto brauch ich ja nich, ich setzt ja ein flag wenn es gefunden wurde und springaus den schleifen....

Tachyon

Erklär doch mal, was Du genau willst. Vielleicht ist ja auch die Struktur nicht so wirklich optimal.

Bitte ein Bit

An BorisDieKlinge:
Ups, mit dem boFound hast du Recht.

BorisDieKlinge

an der eigentlich structur kann ich nicht ändern..wenn ich sie ändere, werden es genausviel iterationen bzw. vergleiche sein! Der Flaschenhals liegt an dem strcmp..

vll. merk ich mir bei jedem eintrag noch die länge des eintrags und versuchem mal memcmp... vll. ist das dann schneller..

Tachyon

BorisDieKlinge schrieb:

an der eigentlich structur kann ich nicht ändern..wenn ich sie ändere, werden es genausviel iterationen bzw. vergleiche sein! Der Flaschenhals liegt an dem strcmp..

vll. merk ich mir bei jedem eintrag noch die länge des eintrags und versuchem mal memcmp... vll. ist das dann schneller..

Naja, es gibt auch sortierte Baumstrukturen, wo bei jeder Iteration eine ganze Reihe von alternativen Pfaden wegfallen, wodurch die Suche ordentlich beschleunigt wird. Man kann also durch strukturänderungen schon ordentlich was ereichen.

BorisDieKlinge schrieb:

was mir aufgefallen ist, das die erste suche in den tabel 25ms geht, wenn ich dann wieder neu beginne gehst unter <1ms.. ?? kann es sein das er sich durch die erste suche erst die tabellen im speicher anlegt?

testest du das ganze etwa unter unter windoofs? wenn ja, dann brauchst du dich wegen der falschen messwerte nicht zu wundern. das OS mit multitasking, virtual memory und paging/caching etc. verhindern jede genaue messung.
wenn strcmp die bremse ist, dann such anders. erzeuge vorher eine eindeutige ID für jeden string und speichere diese sortiert ab usw.
btw, das mit dem flag ist doof. die goto-variante ist besser.

BorisDieKlinge

erzeuge vorher eine eindeutige ID für jeden string und speichere diese sortiert ab usw.

wie soll das funktionieren?

Tachyon

BorisDieKlinge schrieb:

erzeuge vorher eine eindeutige ID für jeden string und speichere diese sortiert ab usw.

wie soll das funktionieren?

Schon mal was von Hashing-Algorithmen gehört?

BorisDieKlinge schrieb:

erzeuge vorher eine eindeutige ID für jeden string und speichere diese sortiert ab usw.

wie soll das funktionieren?

ok, 'eindeutig' war etwas übertrieben, aber fast eindeutig, mit sogenannten hashwerten. dann brauchst du nur zwei integers zu vergleichen und nicht mehr mit strcmp die bytes einzeln absuchen.
http://www.cse.yorku.ca/~oz/hash.html

BorisDieKlinge

ist das sowas wie checksummenberechnung? durch nen algo. nen wert für nen string berechnen.. aber diese werte sind ja nich unbeding eindeutig;)

BorisDieKlinge schrieb:

aber diese werte sind ja nich unbeding eindeutig

aber fast. http://en.wikipedia.org/wiki/Hash_collision

BorisDieKlinge

@fricky: darf ich fragen wie lange du schon programmierst, und wie alt du bist?

BorisDieKlinge schrieb:

@fricky: darf ich fragen wie lange du schon programmierst, und wie alt du bist?

äääh ja, äääh nein, äääh wieso?

BorisDieKlinge

ja nur so, weil du es anscheinend drauf hast;)

mmh, und wenn Du vor dem strcmp einfach das erste byte prüfst?

char *str = "Hallo";
char *vgl = "welt";

if(str[0]==vgl[0]) {

if(strcmp(str,vgl)) {

}

}

Damit hast Du schonmal eine Menge strcmp rausgenommen. Wenn Du die ersten 2 Bytes testest, sind es noch weniger usw.

BorisDieKlinge schrieb:

ja nur so, weil du es anscheinend drauf hast

danke, aber das ist zuviel der ehre. den tip mit dem hashwert hätte dir jeder zweite, regelmässige forenuser hier geben können.

fdsfsafa schrieb:

mmh, und wenn Du vor dem strcmp einfach das erste byte prüfst?

strcmp wird wohl auch abbrechen, wenn das erste byte nicht stimmt. das spart höchstens den funktionsaufruf.

@boris: aber mach doch mal 'nen profilerlauf. vielleicht liegts ja gar nicht am strcmp.

BorisDieKlinge

nene, es an strcmp.. ist ja die einzigste funktion welche "was tut" der sind ja nur verschachtelte schleifen..1 Aber das zufrieden bist : Ohne strcmp oder memcmp geht im faktor 20 schneller..

nep

Naja an strcmp an sich liegt es aber nicht. Wenn du halt Strings verlgeichen musst, dann musst du Strings vergleichen, und das dauert eben.
Wie schon gesagt, du könntest über Hashing und dem Vergleichen der Hash-Werte bestimmt noch was rausholen an Performanz. Ansonsten wie auch schon gesagt, evtl. nochmal die ganzen Strukturen irgendwie umändern.

Bei strcmp wäre die einzigste Möglichkeit die ich sehe, dass du dir evtl. deine eigene strcmp-Funktion als Makro schreibst und da halt auf jede Sicherheitsüberprüfung verzichtest. Wobei ich glaube, dass das bei strcmp auch nicht anders ist und das schon hochperformant implementiert ist. Aber ka, ewig lang her, dass ich was mit C Funktionen gemacht hab
Und da bezweifle ich mal stark, dass du überhaupt nen Unterschied wirst messen können.