nicht angemeldet
Hi,
Aber wahrscheinlich macht alleine schon ein Cache der letzten Abfragen einer Session auch sehr viel sinn, weil die Querys eines Nutzers oft sukzessive wachsen.
Was für eine Session?
Es wäre auch nicht günstig, ausgerechnet die letzten Abfragen einer solchen Session zu cachen, da sie gegen Ende hin meistens immer feiner werden, spezialisierter also. Caching lohnt aber nur, wenn das Gecachte auch oft verlangt wird. Eine Spezialabfrage mit Datum, Autor und Phrase, wenn ich das mal etwas übertreiben darf, kommt aber eher selten vor, ein Caching würde nur Platz verschwenden.
Aber das ist ja auch nicht das Problem, das Ärgernis liegt darin, das da täglich verschieden drauf geantwortet werden muß, denn täglich wird das Archiv geupdated.
Wieso, es reicht doch die Referenz auf die Liste der Postings eines Begriffes zu cachen, schließlich müssen diese wowieso ständig geupdatet werden...
Ja, genau und darin würde auch eine Gelegenheit zur Optimierung liegen: eine gut passende Strategie zum Indexupdate zu finden. Was Du cachen möchtest liegt aber bereits komplett im RAM und muß nicht weiter optimiert werden. Meine Wortliste hat 1.549.146 Einträge (zwar lowercase, aber aus 3 Sprachen und dazu noch den üblichen Verdächtigen) und ist gerade mal knapp 18 MiB groß. Alles in eine luxuriöse DB-Tabelle gepackt macht rund 100-150 MiB. Das ist nicht sonderlich viel.
Vermutlich denke ich mal wieder zu sehr in meinem Modell, da Daniela keine Listen von Referenzen baut.
Weiß man nicht, bevor man's nicht gesehen hat.
Ja aber man muss für eine Zukunftsprognose den Postinganstieg in Relation mit dem Mooreschem Gesetz sehen. Und ich sehe mittlerweile eine Abflachung der Archivkurve.
So sah das nach den ersten drei Jahren auch aus. Geht man davon aus, ist in diesem Jahr eine Steigerung um das Viereinhalbfache im Vergleich zu 2004 zu erwarten.
Das sie überhaupt so lange durchgehalten hat, läßt einen den Hut vor dem Programmierer ziehen!
Dito :) BTW auch an die Programmierer der RegExp die als hocheffektive Automaten realisiert wurden.
Du warst nie im Perlcode, oder?
Aber solltest Du auch eigentlich direkten Kontakt vermeiden, zumindest zum Altem. Mein Augenzucken und die grauen Strähnen im Bart habe ich erst seitdem.
Ich halte es aus Projektsicht nicht für sinnvoll Technologien zu mischen, der Ansatz über eine DB zu gehen ist schon vom Total Cost of Ownership her korrekt, insbesondere bei der Wartung hochspezialisierter Algorithmen.
"Nu' hann 'sch Kopping!"[1], wie der Rheinländer bei solchen Anhäufungen sinnfreier Buzzwords gerne zu sagen pflegt.
Laß es bitte. Danke.
Alleine was mir zu denken gibt, sind die Probleme aus den Hardwareanforderungen. Mein Credo ist es das der Algo der Maschine anzupassen sein muss und nicht umgekehrt...
Dann sag' das mal Microsoft.
Nein, mittlerweile ist Hardware deutlich billiger geworden als Arbeitszeit. Es sieht zwar so aus, als ob da Änderungen gesucht würden, aber im Augenblick ist es noch so.
Wenn beim Hashing eine Kollision stattfindet kann man da grundsätzlich auf zwei verschiedene Arten drangehen:
- ein anderes unbelegtes Loch suchen
- alles in ein Loch quetschen
Letzteres, hatte auch bereits den Fachbegriff "Offenes Hashing" dafür refrenziert http://de.wikipedia.org/wiki/Hash-Funktion#Offenes_Hashing
aber das geht in diesem Thread auch schon mal verloren.
Hier geht nix verloren, hier wird _alles_ archiviert.
Es sei denn, es ginge mal etwas verloren.
Wenn Du also 2) meintest, dann habe ich Dich wohl mißverstanden. Allerdings verstehe ich Dein Begehr dann gar nicht mehr, das macht bei 2) doch rein gar keinen Sinn? Ja, ist eigentlich sogar kontraproduktiv?
Die unmengen an Hashfkt habe ich schon als Bottleneck erkannt, bin davon ausgegangen dass sie einfach nur selten gebraucht werden.
Warum gehst Du davon aus?
weil ich zum sekundären Hash die Information zur Hashfkt mit ablegen muss, das kann mitunter teuer werden.
Und die werden dann nur selten gebraucht, weil sie teuer sind? Nein, so ganz verstehe ich es noch nicht.
Teuer wäre es auch nicht, da es durchaus Methoden gäbe, viele verschieden Hashfunktionen aufgrund eines kurzen Seeds zu bauen.
Aber ich glaube, so langsam komme ich dahinter:
Du möchtest also gerne die sonst üblichen Linked Lists, die bei der Methode 2) entstehen durch eine weitere Hashtabelle ersetzen. Und wenn es bei dieser dann Kollisionen gibt, wiederum eine Hashtabelle anstatt einer Linked List nehmen und das ad finitum acerbum?
Nä, das wäre ja völlig beklopft, das kann's wohl doch nicht gewesen sein?
Damit hättest Du dann rein theoretisch 2^16*2^16 = 2^(16+16) = 2^32 Eintragsmöglichkeiten. Nix gewonnen. Eher etwas verloren, denn die Tabelle im Ram ist doppelt so groß, wie Du vermutest, also bleiben am Ende nur noch 2^31 Eintragsmöglichkeiten mit nutzbaren Daten über.
wieso ist die Tabelle im RAM doppelt so groß wie vermutet?
Du erzeugst einen Pointer auf eine Stelle im RAM in der _was_ ist? Ein weiterer Pointer? Wohin? Auf eine Stelle auf der Platte? Wozu dann der Umweg? Es ist also schon etwas mehr Information nötig, diesen Umweg plausibel zu machen. Z.B. etwas Metainformation. Und 16 Bit + 1 Bit sind 17 Bit. Kleinste Größe auf den heute üblichen Architekturen sind 32/64 Bit, also ist die Tabelle doppelt so groß wie vermutet bzw ganz überflüssig.
Im übrigen ist 16 nur ne Hausnummer die korrigiert werden kann.
Hilft hier auch nicht mehr.
Noch ein Problem: die Hashfunktion müßte bijektiv sein bzw Du müßtest den Suchbegriff mitgeben.
Hä? Für einen Hash brauche ich den Suchbegriff doch immer, um auf Kollision zu checken, oder?
Nein, warum das denn?
Ein Caching müßte schon vollständig sein.
Was meinst du mit vollständig? Wenn ich erst einen extra Cache
durchsuche ist das eine Suche mehr, die jedesmal zu buche
schlägt. Bei dieser Methode fällt der Cachewert während der einen Suche selbst quasi als Abfallprodukt an.
Ähm .. nein, so meinte ich das nicht:
Die Information im Cache sollte vollständig sein, z.B. die erste Seite einer Suche nach dem Wort XYZ. Welche Worte gecached werden sollen kann eine empirische Untersuchung über die Häufigkeit der Suchen ermitteln, wieviel liegt am freiem Plattenplatz. Diese Seite ist am besten schon fertig formatiert und gzipped, "ready to go" sozusagen. Ob etwas gecached ist sagt Dir ein Bloomfilter. Dieser Bloomfilter kann sogar per Javascript in die Formularseite eingebunden werden, sodaß für jeden Sucher, der JS eingeschaltet hat dieser Vorgang auf dem Server schonmal überflüssig wird, er bekommt die Antwort "ist gecached | nicht gecached" schon frei Haus geliefert.
"Obere" und "untere" Bits heißen auch "most signifcant bit(s)" respektive "least significant bit(s)" und das nicht ohne Grund.
Grummel, letztendlich ist es egal wieviele und welche Bits ich für die eine RAM-Tabelle nehme. Wir haben einen 32 dimensionalen Würfel den wir beliebig drehen und projezieren können.
Nein, eben nicht. Das ist ja eines der Probleme auf das Du stößt, wenn Du Hashe so willkürlich teilst: die Verteilung der einzelnen Teile entspricht nicht Deinen Wünschen und Vorstellungen. Besonders wenn die Hashtabellen gut gefüllt sind beginnt der Ärger.
Die Hashfkt soll es aber erlauben.
Ja, damit hättest Du dann aber fast schon kryptographisch sichere Hashfunktionen, soviel Aufwand wäre es, jedes Bit mit möglichst gleichem Entropiewert zu belegen.
Jetzt mal ein theoretischer Ansatz, hätte ich einen idealen Zufallsgenerator (z.B. Schrödingers Katze ;)
Da reicht schon thermisches Rauschen. Deine Soundkarte ist da gerne behilflich. Aber selbst da hast Du Ärger mit der Entropieverteilung. Die AD-Wandler der gängigen Soundkarten sind nunmal nicht so sonderlich und Du hast schwer zu kämpfen, daraus etwas gutes zu machen.
mit dem ich die Werte der Hashfkt einmal ermittle und in eine Tabelle schriebe -ohne Duplikate-, dann hätte diese Fkt so ziemlich die gewünschte Eigenschaft über alle Bits zufälig zu sein.
Das, was Pearson vorschlug, ja.
OK, theoretisch, aber über ne rekursive Definition muss sich doch sowas basteln lassen, oder !?!
Wenn etwas rekursiv ist, ist es automatisch nicht mehr zufällig. Du meinst also etwas anderes, was bitte?
Sieht man am besten mit einem LKG-Zufallsgenerator.
[...]
och bitte, die Source einer ungeeigneten Hashfkt schließt aber nicht die Existenz einer geigneten aus.
Das war ein Beipiel, um Dir den Unterschied zwischen MSB und LSB sichtbar zu machen, mehr nicht.
(Sorry, bis ich den Code durchgearbeit habe, inklusive Theorie, ist der Thread im Archiv, deswegen später mehr ...)
Nein, der hier landet so schnell nicht im Archiv, das glaube ich weniger. Der dürfte noch bis zm Wochenende oder zumindest kurz davor hier rumliegen.
Wenn ihn keiner rausschmeißt heißt das natürlich, aber _das_ würde mich dann doch ein wenig wundern.
Mit anderen Worten, wenn die ursprüngliche Hashfkt mit 32 Bit eine gute Verteilung hat, dann eigentlich auch eine abgeleitete Hashfkt mit weggestrichenen Bits.
Nein, eben nicht, siehe oben.
OK allgemein nicht ...
Ich weiß nicht, ob RMD160, SHA1 o.ä. kryptographisch sichere Hashfunktionen eine Ausnahme darstellen, glaube es aber eher nicht.
Perfekt ist wohl zuviel verlangt, eine die die Eigenschaften der Sprache nutzt wäre schon nett.
Eigenschaft der Eingangsprache: Strings variabler Länge.
Wenn Du jetzt noch _irgendeine_ weitere Eigenschaft findest, die sich in eine Hashfunktion integrieren läßt?
Du könntest natürlich auch mit n-grammen arbeiten. Dann arbeitest Du aber nicht nur mit riesigen Mengen, die Du erstmal mit ein paar Regeln (welchen Regeln?) kleiner bekommen mußt, dazu kommt noch, das die Worte jedesmal gesplittet werden müssen.
Ok jetzt mal wieder ne Idee ins blaue: Man zerlegt ein Wort in seine ersten 2 Silben und den Rest.
Was sind Silben, was ist Rest?
Für den Anfangsteil berechnet man einen möglichst kompakten Code C wie bei Huffman
über die Silbenwahrscheinlichkeit, sodass möglichst viele Bits für die Codierung des Restes verbleiben (wäre bikjektiv). Den Rest codiert man mittels einer adequaten Hashfkt H1.
Meinst Du nicht auch, das Du in der Zeit, wo Du das alles berechnest auch einfach die DB gefragt haben könntest?
Sinnvolle Optimierungen sind von der Idee her stets einfach, ansonsten meist Mikrooptimierung.
Die Implementation selber kann dann durchaus etwas komplexer sein. Beipiel Komprimierung: Die Idee war, das englischer Text viele Redundanzen enthält (7-Bit Encodierung bei Binärarchitekturen usw) und die doch entfernt werden könnten, die Implementation von Huffman war dann zwar etwas komplexer, aber auch allgemeiner.
... ahh essen ruft ...
Schwein gehabt, was?
so short
Christoph Zurnieden
[1] Zu deutsch: "Nun habe ich Kopfweh!"