nicht angemeldet
Hi,
Ich meinte die häufigsten 65000 Suchbegriffe, das sind ja die Fachbegriffe.
Soviele werden das insgesamt kaum sein, vemutlich nur ein paar Tausend, wenn überhaupt, die signifikant oft nachgefragt wurden. 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. Wenn die Postingfrequenz weiter in die Höhe schnellt vielleicht sogar noch öfter am Tag. Auf die gleiche Frage bekommst Du also am Montag eine andere Antwort als am Dienstag; oder am Mittwoch oder am Donnerstag oder ...
eher nicht, ich finde die alte Suche aktuell schon performant genug.
Wenn wirklich jeder vorher erstmal suchen würde, der hier eine Frage stellt, wäre sie schon jetzt am Ende. Sie war überhaupt nicht für solch einen Andrang vorgesehen. Das sie überhaupt so lange durchgehalten hat, läßt einen den Hut vor dem Programmierer ziehen!
(Der wäre dann aber getrennt von DB und Frontend, könnte also ein Drittanbieter einbauen. Du vielleicht?)
Ähm könnte ich, aber ich bin sicher die DB hat selbst konfigurierbare cachingfeatures die aus Projektsicht favorisiert würden.
Nicht rausreden, machen. Wenn's dann nach sorgfältiger Prüfung für zu leicht befunden wurde - tja, dann hast Du eben im schlimmstem Fall eine schöne Fingerübung hinter Dir. Und das ist schließlich nichts Schlechtes!
Ich glaube Christian hat Dich einfach mißverstanden. Du meintest die normale Kollisionsbehandlung durch Mehrfachhashing, oder?
wenn Mehrfachhashing genestete Hashes sind, ja!
Als "genestet" kann man die eigentlich nicht unbedingt beschreiben? Aber gut, ich erklär's einfach mal in groben Zügen und Du sagst dann, ob Du genau das gemeint hast oder nicht:
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
Um ein anderes unbelegtes Loch zu finden kann ich verschiedene Algorithmen anwenden: mehr oder weniger willkürlich nach links und rechts schauen, ob es da 'was Leeres gibt, oder völlig zufällig ein Loch auswählen. Mehrfachhashing nutzt die letztgenannte Methode, in dem sie einfach einen zweiten Hash ansetzt. Wird von der ersten Hashfunktion für die Eingabe "foo" das Loch 22 ausgewählt, wird von der zweiten Hashfunktion vielleicht das Loch 44 ausgegeben.
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?
OK, angenommen ich nehme eine für die deutsche Sprache gute Hashfkt die 32 Bit zB \xABCD liefert.
Das sind nur 16 Bit. Aber egal, ich weiß, was Du meinst.
Wenn ich die oberen 16 bits \xAB nehme könnte ich locker eine Tabelle im RAM adressieren.
Kommt auf die Architektur und das OS an. Normalerweise sind aber 32 bzw 64 Bit dazu nötig. Aber auch hier: egal, ich weiß, was Du meinst.
Von dort könnte ich nun eine weitere Tabelle die auf der Platte liegt referenzieren die ich mit den unteren 16 bit \xCD ansprechen ohne eine neue Hashfkt zu nehmen.
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. Noch ein Problem: die Hashfunktion müßte bijektiv sein bzw Du müßtest den Suchbegriff mitgeben.
In der RAM-Tabelle könnte dann auch in jeder Zelle, - quasi als Caching - die wichtigsten/häufigsten Schlüssel aus der Platten-Tabelle liegen, um einen teuren Zugriff zu vermeiden.
Nein, das bringt nur 0,0000irgendwas% plus oder minus Gewinn. Ein Caching müßte schon vollständig sein.
Gut jetzt sage ich, was hindert mich daran die untere Tabelle zu verkleinern um Speichereffizient zu sein. Angenommen es sind nur y Einträge enthalten, mit 2^(x-1)< y <2^x", dann kann ich auch eine Tabelle mit 2^x Einträgen nehmen wobei die oberen x Bits von \xCD der Schlüssel wären, und die Werte der "unteren" Bits auf die oberen Zellen projeziert werden. Ohne zu viele uneffektive Kollisionen da die ursprüngliche Hashfkt ja bereits gut war.
"Obere" und "untere" Bits heißen auch "most signifcant bit(s)" respektive "least significant bit(s)" und das nicht ohne Grund. Du kannst so einen Hash nicht einfach in der Mitte teilen, das haut einfach nicht hin. Die Entropie des Hashwertes steckt im gesammtem Hashwert, Teile davon sind höchst unterschiedlich "zufällig". Sieht man am besten mit einem LKG-Zufallsgenerator.
---snip--- #ifndef _ISOC99_SOURCE #define _ISOC99_SOURCE #endif
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <limits.h> #include <time.h>
static uint32_t seed;
/* linearer Kongruenzgenerator. Marke: Standard */ static uint32_t lkg( uint32_t a, uint32_t b, uint32_t N){ uint32_t result=0; result = (seed * a + b) % N; seed = result; return result; }
static uint32_t zufall(){
uint32_t ret1 = 0UL; uint32_t ret2 = 0UL;
uint32_t ret = 0UL;
uint8_t *p = NULL;
/* Da wir in eineme Durchlauf nur 16 Bit erhalten, lassen wir das 2x laufen. 32 Bit pro Anfrage sollte eine Zufallsfunktion schon mindestens liefern./ for(int i = 0; i < 2;i++){ / Zwei aufeinanderfolgende Zahlen der Folge erzeugen. / ret1 = lkg((uint32_t)397204094UL,(uint32_t)0UL,(uint32_t)2147483647UL); ret2 = lkg((uint32_t)397204094UL,(uint32_t)0UL,(uint32_t)2147483647UL); / Alle umdrehen nützt nicht viel, da die beiden mittleren Oktets auch nicht sonderlich "gut" sind. p = (uint8_t*)&ret1; for(int i = 0;i < (int)sizeof(uint32_t);i++){ tmp <<= 8; tmp |= p; p++; } ret1 = tmp;/ /* Also nur die äußeren Oktets bei der ersten Zahl austauschen. / p = (uint8_t)&ret1; *p ^= *(p+3); *(p+3) ^= *p; *p ^= (p+3); / Beide Zahlen exklusiv verodern. Durch das Umdrehen oben ist das Resultat Endianess unabhängig falls wir nicht gerade auf einer PDP-11 sitzen.
Zahl = 0x11223344 Little Endian = 0x11223344 Big Endian = 0x44332211 PDP-11 = 0x22114433
Das Problem ist bei LKGs, das die erzeugten Zahlen in Richtung LSB immer schlechter werden. Durch das XOR und das Umdrehen sind aber zumindest die beiden äußeren Oktets gleich "gut".*/ ret1 ^= ret2;
/* Füllen des Returnwertes von rechts nach links */ p = (uint8_t *)&ret1;
ret <<= i*8; ret |= *p; ret <<= 8; ret |= (p+3); } return ret; } static void seed_lkg( uint32_t i){ / normalerweise kommen hier ein paar Tests die sind aber schon in main() */ seed = i; }
int main(int argc, char **argv){
uint32_t tmp = 0UL; unsigned long count = 0, i = 0;
unsigned char *p = NULL;
seed_lkg((uint32_t)time(NULL)); if(argc > 1){ if((count = strtol(argv[1], (char **)NULL, 10)) >= ULONG_MAX/2){ fprintf(stderr,"Bitte nicht mehr als %lu, danke.\n",ULONG_MAX/2-1); exit(EXIT_FAILURE); } } else count = 1024;
for(;i<count;i++){ tmp = zufall(); p = (unsigned char )&tmp; printf("%c%c%c%c",(p+3),(p+2),(p+1),*p ); } exit(EXIT_SUCCESS); } ---snap--- (Bin jetzt zu faul, auch noch Optionsparsing einzubauen. Einfach oben einmal mit und einmal ohne Bitjuggling arbeiten (einfach auskomentieren)) Tests der Ausgabe (mit Ent bzw DIEHARD und eine LCG-crack, aber sowas gibt's tatsächlich online?) mit Bitjuggling ergaben gute Werte. Unerwarteterweise keine Wiederholung nach 2^32 Zyklen! (Ich hatte aber auch nicht mehr Platz auf der Platte als für 2^32+3 Zyklen, kann durchaus sein, das sich das einen später wiederholt hat) Wenn man nicht bloß die Bytes austauscht sondern die Bits selber gut durchschüttelt, sollte das Ergebniss noch etwas besser aussehen. Mit dem Standard-LKG entsprachen die Tests dann aber wieder voll und ganz den Erwartungen. Bevor irgendjemand Unsinn damit anstellt: das ist kein kryptographisch sicherer Pseudo-Zufallsgenerator! Auch wenn er äußerlich so aussieht.
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.
Knackpunkt wäre es also eine gute Hashfkt mit 32 Bit für die Selfsprache zu finden. Oder irre ich mich?
Du suchst also die perfekte Welle^WHashfunktion? Glaube nicht, das Dir das viel nützt. Das meine ich wörtlich: ich glaube nicht, das es viel nützt. Der Aufwand steht in rein gar keinem Verhältnis zum Nutzen. Selbst so "Kleinigkeiten" wie eine Rechtschreibprfüng ("Meinten sie 'Rechtschreibprüfung'"?) ist schwierig zu implementieren, sehr schwierig. Hier haut dann wieder der extrem große Umfang der Eingabemenge in's Kontor. 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. Ein Cache, der die Ergebnisse der häufigst gesuchten Begriffe vorhält (die erste Seite vielleicht sogar komplett) wäre natürlich nicht schlecht. Aber es würde wahrscheinlich auch nix rausreißen. Deshalb erstmal die Suche sorgfältig und ohne große Spielereien aufbauen und stabil bekommen. Wer dann noch Lust und Zeit hat, kann sich ja daran versuchen.
so short
Christoph Zurnieden