Forum: Knobelecke

Nur verwendet deine Lösung - zwar nicht von dir definierte - Klassen, also etwas was Du selbst ausgeschlossen hattest. Damit ist deine Lösung leider KEINE Lösung deiner Aufgabe. Die einzig mögliche Lösung ist wohl alles in eine byte aka char Array zu speichern. Nur warum sollte man das tun, wen man sich ebenso gut eine Struktur definieren kann.

Schau dir übrigens mal qsort und bsearch an, damit solltest Du auch bei der Arraylösung auf die Zeiten der map Implementierung kommen. Die normale C++ map gilt übrigens als ziemlich ineffizient, da Sie auf balancierten binär Bäumen aufsetzt, was auch der Grund ist warum du mit einmaligem qsort und folgenden bsearch aufrufen die gleichen Geschwindigkeitszuwächse erreichen kannst. Eine effizienter Implementierung findest Du in der C++11 er hash_map. Während der Zugriff in der map nämlich O(ld(n)) ist, ist er für die hash_map O(1).

 

Zitat:

Nur verwendet deine Lösung - zwar nicht von dir definierte - Klassen

Das hab ich jetzt erst nachgelesen. Und stimmt.
Das haette ich vielleicht vorher machen sollen, bzw die Aufgabestellung
klarer definieren.

Zitat:

Schau dir übrigens mal qsort und bsearch an, damit solltest Du auch bei der Arraylösung auf die Zeiten der map Implementierung kommen.

Ich glaube du hast nicht ganz verstanden, wie die Suche in der Liste erfolgt.
Wenn alles wirklich in einem char-Array (oder string-Array) abgelegt ist, dann hilft nur ein strcmp, oder ein .find(),
da die Information, nach welcher gesucht wird dann ein Teil des strings waere und so wie bsearch fuer mich aussieht,
kann es nur nach den gesamten Informationen, die in einem Element stehen suchen.
Somit wuerde diese Loesung garnichts bringen.

Selbst wenn man es in 2 Arrays speichern wuerde, dann wuerde zwar das eine Array (das mit den IP Adressen) zwar sortiert werden und darin wuerde auch dann die Funktion bsearch funktionieren.
Aber qsort kann wohl kein Array nach der Verknuepfung zu einem anderen Array genauso sortieren (also dass dann die Informationen des Arrays mit NextHop und Metrik immernoch zu den Positionen von dem Array mit den IP Adressen passt).

--
Physiker finden, Ingenieure erfinden.

 

Hi,

Zitat:

Ich glaube du hast nicht ganz verstanden, wie die Suche in der Liste erfolgt.
Wenn alles wirklich in einem char-Array (oder string-Array) abgelegt ist, dann hilft nur ein strcmp, oder ein .find(),
da die Information, nach welcher gesucht wird dann ein Teil des strings waere und so wie bsearch fuer mich aussieht,
kann es nur nach den gesamten Informationen, die in einem Element stehen suchen.
Somit wuerde diese Loesung garnichts bringen.

Selbst wenn man es in 2 Arrays speichern wuerde, dann wuerde zwar das eine Array (das mit den IP Adressen) zwar sortiert werden und darin wuerde auch dann die Funktion bsearch funktionieren.
Aber qsort kann wohl kein Array nach der Verknuepfung zu einem anderen Array genauso sortieren (also dass dann die Informationen des Arrays mit NextHop und Metrik immernoch zu den Positionen von dem Array mit den IP Adressen passt).

Wo ist den da jetzt das Problem? Du kannst das große Array doch in kleinere Blöcke einteilen. Da jeder Datensatz strukturell Gleich ist, kannst Du jeden Datensatz mit der GLEICHEN Anzahl - also etwa 42 - Zeichen kodieren. Was Du jetzt noch brauchst ist eine Ordnung, aber auch die ist kein Problem. Für die positiven Integer reicht es führende 0en und feste Stellenzahl zu verwenden, der double Wert ist - sofern man ihn nicht einfach auf einen Integer abbildet - etwas komplizierter, aber auch machbar. Im Ergebnis hat man dann einen Datenblock von je n Zeichen mit einer passenden Ordnung. Diesen kann man dann einmal mit qsort sortieren wobei eine Vergleichfunktion zum Einsatz kommt die den kommpletten Datensatz von n Zeichen vergleicht - möglich sind hier strncmp oder memcmp. Bei der Suche mit bsearch reicht es nur den IP - Quelle & Ziel - zu vergleichen. Allerdings muss man nach einem erfogreichen bsearch noch solange die Vorgänger sequentiell testen bis man die optimale Route - die erste in der Liste mit passenden IPs - gefunden hat.

Vorteil gegenüber deiner Variante ist dann sohgar noch, dass mehrere Routen zwischen zwei Hosts korrekt verarbeitet werden.