Suchfunktion optimieren?
-
Bitte ein Bit schrieb:
Oder kennt jemand ein STL-Pendant (ohne Templates), welche die gängigen Container-Klassen implementiert ?
z.b. das: http://home.gna.org/gdsl/
-
fricky schrieb:
Bitte ein Bit schrieb:
Oder kennt jemand ein STL-Pendant (ohne Templates), welche die gängigen Container-Klassen implementiert ?
z.b. das: http://home.gna.org/gdsl/
Boa, was für ein unsicherer Frickelhaufen...
-
Tachyon schrieb:
Boa, was für ein unsicherer Frickelhaufen...
was speziell meinst du? sind doch überall asserts drin.
-
Die Typsicherheit...
-
Tachyon schrieb:
Die Typsicherheit...
was gefällt dir nicht? vielleicht gdsl_element_t, der ein void* ist? was würdest du besser machen?
-
fricky schrieb:
Tachyon schrieb:
Die Typsicherheit...
was gefällt dir nicht? vielleicht gdsl_element_t, der ein void* ist? was würdest du besser machen?
C++ Templates benutzen.
Wenn ich mich auf einer derart hohe Abstraktionsebene begebe, dass ich generische Container benötige, würde ich eine andere Sprache wählen.
-
wenn ich mich nicht irre, wurde hier die binäre suche, bzw. die halbierungssuche noch nicht erwähnt. das bringt auch schon ernome laufzeitverkürzungen.
-
Tachyon schrieb:
C++ Templates benutzen.
geht nicht in C. ausserdem blasen templates, wenn man nicht aufpasst, das executable ganz schön auf.
Tachyon schrieb:
Wenn ich mich auf einer derart hohe Abstraktionsebene begebe, dass ich generische Container benötige, würde ich eine andere Sprache wählen.
du kannst ja ein grafisches tool nehmen, dass dir aus abstrakten modellen den C-code generiert.
aber in C braucht man eigentlich selten was generisches und wenn man's doch braucht, dann ist so 'ne lib da oben^^ doch nicht schlecht.
-
BorisDieKlinge schrieb:
falls es doch vorkommen würde, das 2 identische ID für unterschiedliche string existieren, müsste ich den string nach gefundener HashID sicherheitshalber nochmal vergleichen denk ich;)
Genau deshalb habe ich die map einen int-Wert auf einen String-Array abbilden lassen - ich hatte auch mal geschaut, zu einem Hashwert gab's sogar immer ~10000 Strings.
ljlöjlk schrieb:
wenn ich mich nicht irre, wurde hier die binäre suche, bzw. die halbierungssuche noch nicht erwähnt. das bringt auch schon ernome laufzeitverkürzungen.
Bitte ein Bit schrieb:
An Badestrand:
Gelle die STL ist doch schön ? Da sind so viele Dinge / Datenstrukturen drin welche man in vielen Fällen gut gebrauchen kann. Und wenn man sich die interne Datenstrukturen von Sets (ich vermute auch mal die Maps) anschaut, kommt man schnell zu Bäumen.Oh ja, ich merke auch immer wieder (voller Freude), wie bequem doch so einiges ist
-
"binäre halbierungssuche" ERKÄRUNG BITTE bin wissenhunrig;)
-
http://de.wikipedia.org/wiki/Binäre_Suche schrieb:
Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.
Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.
Die Länge des Suchbereiches wird von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf 1 Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.
-
BorisDieKlinge schrieb:
"binäre halbierungssuche" ERKÄRUNG BITTE bin wissenhunrig;)
also, entweder binäre suche oder halbierungssuche. zwei begriffe, die das gleiche meinen.
-
Nehmen wir mal ein Beispiel: Wir haben die folgende Liste von Schlüsseln von Datenobjekten (Hash Werte, Numerische Werte oder was auch immer)
1 4 5 7 8 9 10Wir suchen die 8. Anfangs startet man die Suche über dem kompletten Bereich 1-10. Das mittlere Element ist 7 und ist kleiner als 8. Also wird die Suche im Bereich 8-10 fortgesetzt. Wäre das mittlere Element größer, würde man im Bereich 1-5 weitersuchen. Das mittlere Element von dem neuen Bereich ist 9 und kleiner als 8 und somit wird die Suche auf dem Bereich 8-8 fortgesetzt. Das folgende mittelere Element ist 8 und entspricht dem gesuchten Element.
Dieses Vorgehen lässt sich grafisch darstellen, in Form einer Baum-Datenstrukur.
7 / \ 4 9 / \ / \ 1 5 8 10Will man ein Element in dieser Liste suchen, muss man erst mit der 7 vergleichen. Ist das gesuchte Element kleiner, muss man das Element mit der 4 vergeleichen, sonst mit der 9, ...
Vorraussetzung für die binäre Suche ist, dass die Liste sortiert ist. Deswegen ist das Einfügen eines Elements nicht so einfach, weil man die Sortierung bewahren muss um die binäre Suche auszuführen können.
-
danke, binärbaum bzw, suche ist mir bekannt
das worte "halbierungssuche" kannte ich net^^