[C] (assoziative) Arrays

G

Grinch

Well-known member
ID: 53444
L
30 April 2006
51
2
Nabend zusammen,
bin mal wieder etwas am leichten C programmieren und suche eine elegante Lösung für folgendes Problem:
Ich will eine kleine Netzwerkstatistik machen und zu diesem Zweck werte ich mit WinPcap bestimmte TCP Pakete aus. In manchen Paketen stehen eine ID und ein Beschreibungsstring, in anderen nur die ID.
Nun hab ich mir ein struct gebastelt, dass mehr oder weniger so aussieht
{
unsigned int id,
unsigned char beschreibung[50],
unsigned long long int in,
unsigned long long int out
}

Also, wenn ein Paket mit beiden Informationen ankommt, wird solch ein Variablentyp neu angelegt und in id und beschreibung die entsprechenden Werte geschrieben.

Jetzt hab ich davon sagen wir mal 1000 Stück im Speicher liegen und ein Paket kommt rein, das nur die ID bereithält und irgendwelche andern Daten. Nun muss ich den entsprechenden Eintrag raussuchen, der diese ID hat und dann die Paketlänge zu in oder out (je nachdem obs ein eingehendes oder ausgehendes Paket ist) hinzuaddieren.

Wie finde ich möglichst elegant diesen Eintrag? Bis jetzt hab ich halt ne Variable mit der Anzahl der Einträge und durchlaufe jedesmal eine forschleife von 0 bis zu dieser Anzahl und überprüfe ob beim gerade gewählten Eintrag die id übereinstimmt. Da es jedoch eine Menge Einträge sind und noch mehr Pakete pro Sekunde durch die Leitung flutschen (das Tool soll mal einen Hochleistungsfileserver überwachen) kostet das ja ne Menge Rechenleistung, nehme ich mal an.

Kann ich irgendwie anders auf die Einträge zugreifen, als mit einer fortlaufenden Nummer? bspw eintrag[id] wobei id dann eben die id des Pakets ist (möglich sind ids zwischen 0 und 65535, also einfach 65536 Einträge gleich zu erstellen fällt schon mal weg, ich würde gerne nur soviele wie nötig haben)?

Programmiert/Compiliert wird mit VC++ 6.0
 
Ne for-Schleife ist eigentlich ne gute Lösung dafür und viel Rechenleistung braucht die auch nicht (In PC-Spielen wird teilweise auch durch schleifen mit mehreren tausend Einträgen gelaufen, und man bekommt dennoch seine 70fps).
Ist halt immer die Wahl zwischen Performance und Speicherverbrauch.
 
wenn du das Array nach der ID sortieren lässt, musst du ja nur log2_1000 (ca 10) Durchgänge machen.
Mitte des Arrays aussuchen wenn die ID kleiner ist als das aktuelle Element, die Mitte vom Anfang bis zur der letzten Stelle nehmen, das solange machen bis man die ID erreicht hat.

Beispiel:
1
4
6
7
8
9
10

z.B. suchst du die 6
er nimmt die Mitte also 7
die 6 ist aber kleiner also nimmt er die Mitte von
1
4
6
7
also 4, das aber ist zu groß also nimmt er davon die 2. Hälfte
6
7 und nimmt die Mitte also 6. => fertig.
Also so wie z.B. Indexe bei Datenbanken.

MfG respawner
 
Hm, die Idee ist super, ich denke das werde ich doch morgen gleich mal einbauen... da die Wahrscheinlichkeit eh hoch ist, dass mehrere Pakete hintereinander die gleiche ID haben könnte ich mir die letztverwendete ja auch noch merken und damit noch mal etwas Performance rauskitzeln.
Im Moment ist das eh noch alles theoretisch, da ich den Datentransfer kaum simulieren kann, aber es kommt halt irgendwo wirklich auf jeden Befehl an, denn der Server soll ja nebenher noch was anderes machen als Pakete zu analysieren und daraus bunte Statistiken zu generieren ;)

Wenn jemand noch andere oder bessere Ansätze hat, nur her damit :biggrin:
 
@respawner:
Das dauert dann aber trodtzdem länger, als wenn er das array einfach einmal durchläuft. Zum einen muss er das Array ja einmal durchlaufen, um es zu sortieren und zum anderen muss er dann noch das richtige Element suchen. Dann kann er doch lieber gleich suchen und sich das sortieren sparen.
 
Cyclon schrieb:
@respawner:
Das dauert dann aber trodtzdem länger, als wenn er das array einfach einmal durchläuft. Zum einen muss er das Array ja einmal durchlaufen, um es zu sortieren und zum anderen muss er dann noch das richtige Element suchen. Dann kann er doch lieber gleich suchen und sich das sortieren sparen.
Zum Vergrößern anklicken....
kommt halt drauf an wie das Verhältnis lesen-schreiben ist
sortiert werden muss ja nur ein einziges mal. Wenn etwas hinzugefügt wird muss man suchen (log(n)) und es dort einfügen (Bei einer Liste müssen ja nur 2 Zeiger verändert werden). So bleibt das Ding immer sortiert. Beim Lesen hat man wieder log(n). Wenn man ein festes Array nimmt müsste man natürlich ständig neu sortieren was beim schreiben sehr langsam wird. Aber ich nehme an, das Listen verwendet werden.

OK, stimmt das lesen von Listen ist recht aufwendig.

MfG respawner
 
Zuletzt bearbeitet:
Da ich heute noch mit nem andern Problem zu kämpfen hatte hab ich das sortieren noch nicht drin. Bisher siehts so aus:
mein_datentyp *verbindungen[65536];
u_short anzahl=0;

hinzufügen:
verbindungen[anzahl]=malloc(sizeof(mein_datentyp));
anzahl++;

suchen:
for(i=0;i<anzahl;i++) if(verbindungen->id==gesuchte_id) return i;

entfernen:
free(verbindungen);
for(++i;i<anzahl;i++)
verbindungen[i-1]=verbindungen;
anzahl--;


Zum sortieren müsste ich eigentlich nur die hinzufügen dahingehend ändern, dass er noch schaut wo er es einfügen muss und dann alle größeren zeiger ein element nach hinten schiebt (praktisch das entfernen rückwärts).

Das Verhältnis von hinzufügen/entfernen zu suchen hängt davon ab, wieviel derjenige hoch oder runterlädt mit einer Verbindung. Aber Grundsätzlich dürfte das Verhältnis jenseits der 1:1000 liegen. Also der Geschwindigkeitsfokus liegt klar auf der Suchfunktion.

Wie üblich bin ich für weitere Verbesserungsvorschläge oder Hinweise auf Fehler jeglicher Art sehr dankbar.


Ach ja, vielleicht noch wegen den Listen. Ich hab ja heute erst mit dem Speichern der Daten angefangen, hatte also das mit dem sortieren schon im Hinterkopf, kam nur nicht mehr ganz dazu es einzupflegen. Daher dachte ich mir, mit nem Zeigerarray ist es nachher erheblich schneller, da ich ja direkt auf die mitte mit Anzahl/2 zugreifen kann, bei einer Liste müsste ich die Liste ja mehrfach durchlaufen, da kann ich gleich meine for-schleife behalten ;)
Ausserdem ist die Vorgabe ja ein Einsatz auf nem Hochleistungsserver, der über mehrere GB an RAM verfügt, da kommts auf die 65000 Zeiger nicht an und jeder Listeneintrag würde ja auch noch mal 1 oder 2 Zeiger mehr brauchen, bei >1000 Einträgen hat man da schon wieder ein paar kB weniger Speicherersparnis im Vergleich zum Array ;)
Oder denke ich da falsch?

Bin ja noch Azubi und das ist im Prinzip mein erstes richtiges C Programm (leider lernt man in der Berufsschule nur noch Java, aber mir persönlich gefällt C besser, daher versuche ich mich mit C an der Aufgabe :)).
Also rückt raus die Tipps und Tricks :p
 
Zuletzt bearbeitet:
Hallo Grinch, (edit) nicht hetzen, schreibe ja gerade was :D (/edit). Wenn Du Visual C++ hast, müßtest Du über C++ eigentlich eine Klasse wie Hashtable oder hash_map zur Verfügung haben. Aber hier ein Tipp für die Programmierung in C.

Es mag vielleicht Overhead sein, wegen ganzzahligen Keys gleich Hashtables aufzubauen. Aber ich glaube, wenn Du so ein Konzept hier einsetzst, dann hast Du es in C auch für die nächste Problemstellung parat.

Näheres über Hashtables in C findest Du unter der folgenden Referenz dank der University of Cambridge. Der Code ist unter BSD-Lizenzbestimmungen zur Verfügung gestellt.

C Hash Table (Klick)

Die dort beschriebenen Hashtables können beliebige Keys enthalten, sofern diese über Referenzen aufgebaut werden, weil die entsprechenden Stellen als (void *) deklariert sind. Dasselbe gilt für die Values - in Deinem Fall wären das Deine struct-Instanzen, die dann als (struct *) aufzubauen wären.
 
puh, schwere Kost.. Aber Danke, ich werde mir das aber auf jedenfall mal näher anschauen. Leider hab ich zuhause kein VC++, so dass das Umsetzen noch etwas warten muss.

Aber mir ist grad noch was eingefallen, und zwar hat das Problem von heut morgen ja auch mit dem Problem hier zu tun: Und zwar hab ich festgestellt, dass diese ID nicht so einmalig ist, wie sie beschrieben wurde. Sie ist nur zusammen mit der UID einmalig. Bei meinem Ansatz oben ist das nicht weiter tragisch, das struct um einen u_short erweitert und das suchen ebenfalls auf if(verbindungen->id==id && verbindungen->uid == uid) erweitert und fertig war die Sache. Da die meisten User nie mehr als 5 Verbindungen oder so offen haben werden ist das aber wohl nicht so tragisch, dann würde ich nach der id sortieren und dann einfach alle einträge mit der id durchlaufen und die uid suchen. Mal schauen wie sich das mit Hashtables oder Listen lösen lässt...

So wies aussieht wird das ganze komplizierter als ich mir das vorgestellt hab ;)
 
hmm, ich weiß nicht ob ich jetzt nen denkfehler habe, aber...

du reservierst ein array für 65536 einträge, und packst es von unten voll mit deinen einträgen also z.b. so?

arr[0] = obj:id:1223
arr[1] = obj:id:345
arr[2] = obj:id:6732
...


wobei die id dein verbindung angibt. und nun möchtest du das schnell sortieren und schnell suchen?

dann würd ich das einfach so speichern:
arr[1223] = obj:id:1223
und so weiter...

suchaufwand und sortieraufwand gleich null...
 
Thomas schrieb:
dann würd ich das einfach so speichern:
arr[1223] = obj:id:1223
und so weiter...
Zum Vergrößern anklicken....
Das wäre wirklich das Einfachste, aber das geht leider nur bedingt, da die ID nicht einmalig ist.
Es ist in etwa so:
User 1 verbindet sich. => uid = 1;
User 1 macht eine Verbindung auf => id=1;
User 1 macht noch ne Verbindung auf id=2;
User 2 verbindet sich => uid=2;
User 2 macht ne Verbindug auf => id=1;
User 1 macht ne Verbindung auf => id=3;
User 2 macht ne Verbindung auf => id=2;
(hier sind die jetzt durchnummeriert, in der Realität aber nicht. es stehen 16-bit für uid und id zur verfügung)
Also das heisst, dass ich praktisch für jeden User das Array mit 65536 Einträgen bräuchte (obwohl davon nur ein Bruchteil genutzt wird) und dann noch mal 65536 Einträge für die uid.. also 2^32 Einträge, und das is selbst wenns nur Pointer sind etwas viel wie ich finde ;)
Daher ist mein aktueller Ansatz: Es stehen insgesamt 65536 Verbindungen zur Verfügung (wenns mehr sind fliegen die ältesten raus, aber dazu wird es denke ich nicht kommen). Und für jede Verbindung speicher ich die uid, und die verbindungsid. Das Array der Verbindungen ist nach der uid,id sortiert (wird beim Hinzufügen und Entfernen der Einträge erledigt). und dann nach respawners methode (also das binary search) das array durchquälen.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben