Zeiger Wettrennen

[Rolf B]

Hallo pl,

wir reden aktuell über Konzepte, da helfen Codebeispiele nicht so recht.

Du fragtest, ob ein Konstrukt sinnvoll ist, in dem eine lineare Liste mit mehreren Zeigern abgegrast wird, die unterschiedliche Teile der Liste bearbeiten. Antwort war: Ja, wenn es multithreaded ist. Sonst nicht. Damit wäre das Thema eigentlich erledigt.

Wenn der Code single-threaded ist, so die weitergehende Überlegung, könnte eine Aufteilung der Suche über mehrere Intervalle ggf. sogar kontraproduktiv sein, aus Überlegungen heraus, die auf die Prozessorarchitektur zurückgehen. Da sind wir aber im Bereich des Taktezählens, und das tut man erst wenn die letzten logischen Optimierungen ausgereizt sind. Ein Abgleiten deinerseits, mit mehreren Zeigern eine Schachtelung abzubilden, haben wir beiseitegelegt. Weil das nicht die Frage war.

Mehr oder weniger optimale Implementierungen linearer Listen bringen nur marginalen Nutzen. Ob nun einfach oder doppelt verkettet. Ob Du eine doppelt verkettete Liste brauchst oder nicht hängt von den Operationen ab die Du ausführen willst, aber für eine lineare Suche ist das unerheblich. Da sind die Algorithmen auf einfach und doppelt verketteten Listen gleich.

Und ich bin sicher, dass Du für Listen keine Codebeispiele brauchst, die findest Du reichlich bei deinem verehrten Niklaus Wirth.

Fazit bleibt immer noch: Eine echte Beschleunigung erhältst Du nur wenn Du die Liste durch was anderes ersetzt, so dass du eine rein sequenzielle Suche vermeiden kannst. Sprich: Brain statt Blech. Aber da hast Du abgewunken, weil dein Code eh schon so schnell ist.

Ob dieser Ersatz möglich ist, hängt von der Anwendung ab. Sind deine Suchabfragen so geartet, dass Du an Hand der Suchparameter das zu durchsuchende Intervall eingrenzen kannst? Das wäre bspw. der Fall wenn Du Einträge suchst die ein bestimmtes Präfix haben (Suche alle Schlüssel, die die mit "self" beginnen). Eine Suche nach allen Worten, die "self" enthalten, würdest Du damit nicht optimieren können, dafür bleibt nur die erschöpfende Suche. Suchst Du alle Einträge, deren Schlüssel nach dem letzten / mit self beginnt (also z.B. self*.html in allen Ordnern), würde Dir ein Suchindex helfen wo der Filename nach vorne gezogen ist.

Frage ist dann immer, wie man das in einer CGI Anwendung realisiert. Da lohnt es nicht, aufwändig Suchstrukturen aufzubauen, die nur einmal verwendet werden. Deswegen kam mein Vorschlag nach einer passenden Speicherung in der Datei, in der die zu durchsuchenden Daten liegen. Sprich: Du baust die Suchstruktur außerhalb des CGI-Programms auf und liest sie dort als Binary ein. Was dazu führt, dass Du im gespeicherten Binary keine Pointer verwenden kannst, sondern Offsets verwenden musst. Und es führt zur Überlegung, ob das segmentweise Lesen einer vergleichsweise kleinen Datei effizient ist. Das sind alles Kriterien, die je nach konkretem Fall zu unterschiedlichen Optimierungsergebnissen führen können. Den konkreten Fall kennst aber nur Du. Die Frage, ob die Mühe echten Mehrwert bringt, kannst auch nur Du beantworten.

Rolf