Hallo, für die GetNext-Anfrage bei SNMP benötige ich eine Routine, welche mir die Object Identifier lexikografisch sortiert. Meine MIB besteht momentan aus einem Array aus Structs, in welchem auch die OIDs liegen: MIB[a].OID[b] a wählt hierbei das Managed Object aus. b gibt mir die Stelle der OID an. Für diejenigen die mit SNMP noch nichts zu tun hatten: Die OIDs einer MIB könnten beispielsweise folgendermaßen aussehen: MIB[0].OID[0] = 1 MIB[0].OID[1] = 3 MIB[0].OID[2] = 6 MIB[0].OID[3] = 1 MIB[0].OID[4] = 2 MIB[0].OID[5] = 1 MIB[0].OID[6] = 1 MIB[0].OID[7] = 1 MIB[0].OID[8] = 0 MIB[1].OID[0] = 1 MIB[1].OID[1] = 3 MIB[1].OID[2] = 6 MIB[1].OID[3] = 1 MIB[1].OID[4] = 2 MIB[1].OID[5] = 1 MIB[1].OID[6] = 5 MIB[1].OID[7] = 8 MIB[1].OID[8] = 0 MIB[2].OID[0] = 1 MIB[2].OID[1] = 3 MIB[2].OID[2] = 6 MIB[2].OID[3] = 1 MIB[2].OID[4] = 2 MIB[2].OID[5] = 1 MIB[2].OID[6] = 1 MIB[2].OID[7] = 3 MIB[2].OID[8] = 0 Nun sollen diese 3 Arrays lexikografisch sortiert werden, also am Ende soll rauskommen: 0, 2, 1 für die Reihenfolge MIB[0], MIB[2], MIB[1]. Wie kann ich dieses Sortieren ressourcenschonend in einen 8-Bit Mikrocontroller implementieren? Ich hoffe mein Problem wurde deutlich. Gruß, Thomas
heapsort(); wenn es in der avr-libc noch nicht enthalten ist, google nach heapsort.c.
Wenn ich das nun nicht komplett falsch verstanden habe sortiert mir heapsort(); aber nur die einzelnen Einträge eines Array. Ich möchte nun ja aber nicht den Inhalt meiner Arrays sortieren (dies ist ja eine Adresse die so bleiben soll). Stattdessen sind in meinem Programm einzelne Variablen in dieser Baumstruktur vorhanden und jede dieser Variable über eine gewisse Adresse (OID bzw. Pfad über die Zweige zum Blatt) adressiert. Bei einer GetNext-Anfrage springe ich nun an irgendeine Stelle in dieser Baumstruktur und muss von dort aus das nächste tieferliegende Objekt, also das nächste tieferliegende Blatt, finden. Ich hoffe das Problem wird nun klarer. Thomas
Die Funktion sortiert dir was du willst: ein Array von Strukturen (MIB[x]), ein Array von Pointern, ein Array von Indizes. Wie diese Arrayelemente verglichen werden bestimmst du, indem du heapsort() einen Pointer auf deine Vergleichsfunktion übergibst. Wenn du ein Array von Indizes sortieren willst sieht das ganze dann ungefähr so aus (Casts, "&" und "*" nach Bedarf hinzufügen):
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
Danach hast du in mib_order die lexikalische Reihenfolge stehen, und das dürfte ja reichen um weiterzukommen.
qsort() ist schon dabei, heapsort() noch nicht. Klingt wie eine lohnenswerte Ergänzung der Bibliothek. Andreas, kannst du die relativen Vor- und Nachteile beider Varianten kurz beschreiben?
Jörg Wunsch wrote: > Andreas, kannst du die > relativen Vor- und Nachteile beider Varianten kurz beschreiben? Nochmaliges lesen der FreeBSD-manpage beantwortet die Frage eigentlich schon: The heapsort() function [...] Its only advantage over qsort() is that it uses almost no additional memory; while qsort() does not allocate memory, it is implemented using recursion. Ja, ich denke, das werde ich mal mit in die avr-libc aufnehmen.
Gast
#606505
Gerade für µC-Anwendungen ist der Heapsort oft besser geeignet als der Quicksort. Zum einen, wie schon von Jörg geschrieben, wegen der günstigeren Speichernutzung (variabler Stackverbrauch wegen Rekursion ist bei kleinen Speichern ähnlich bäh wie malloc). Zum anderen ist der Worst-Case-Rechenaufwand beim Heapsort O(n log n), beim Quicksort O(n²). Im Mittel performt der Quicksort zwar trotzdem besser, aber bei Steuerungsanwendungen u. ä. zählt meist die maximal benötigte Zeit.