Am 03.08.2017 um 13:53 schrieb tomas@tuxteam.de:
On Thu, Aug 03, 2017 at 11:57:43AM +0200, ul@openlilylib.org wrote:
Am 2017-08-02 11:19, schrieb tomas@tuxteam.de:
[...]
Zu Modulo musst Du hier lediglich wissen: das ist der Rest der Division einer Zahl durch eine andere. Meistens (die Konventionen variieren aber!) nimmt man den *positiven* Rest:
5 mod 7 == 5 21 mod 7 == 0 -1 mod 7 == 6 (*)
(*) immer die Doku konsultieren :-)
Die Rechenarten ergeben sich daraus:
(a + b) mod c == (a mod c + b mod c) mod c (a*b) mod c == ( (a mod c) * (b mod c) ) mod c
Es loht sich vielleicht (Verständnis ist oft Vertrautwerden), wenn Du Dir die Exponentiation mal genauer anguckst.
Danke, jetzt hat es klick gemacht. Ich hatte nie so recht verstanden, wieso man bei einzelnen Operanden Modulo machen kann, ohne das Ergebnis zu verfälschen. Natürlich ist es sonnenklar (nur ich stand auf dem Schlauch), dass man das nur dann machen kann, wenn man für das Ergebnis auch den Modulo berechnet.
Jetzt ist mir auch klar, warum (a^b) mod c = ((a mod c)^b) mod c ist, und dass man damit immense große Zahlen vermeiden kann, wenn man hinterher sowieso wieder nur am Modulo interessiert ist.
- Hashing
Das Konzept von Hash-Funktionen und Hash-Chains ist mir im Kurs klar geworden. Die Mathematik von guten Hash-Funktionen dagegen nicht.
Das liegt daran, dass nicht genau definiert ist, was eine gute Hashfunktion ist.
Ich habe mich wahrscheinlich nicht klar genug ausgedrückt. Dass ich zum jetzigen Zeitpunkt nicht erwarten kann, mir selber für gegebene Datenstrukturen geeignete Hashfunktionen auszudenken, ist mir schon klar. Aber ich hatte auch noch große Schwierigkeiten, den Ausführungen über die im Kurs vorgegebenen Funktionen zu folgen.
Im wesentlichen ist eine Hashfunktion eine Funktion, die "grosse Datenklumpen" auf "kleine Datenklumpen" abbildet, meistens, weil letztere leichter zu handhaben sind. Abgesehen davon will man meist, dass zwei unterschiedliche Datenklumpen unterschiedliche Hashwerte besitzen (wenn nicht, nennt sich das eine Kollision: die iist natürlich nicht immer zu vermeiden: gehen wir von z.B. Datenklumpen von 10MB aus und hashen wir sie auf 100 Bit "runter", dann müssen sich im Schnitt 10^5 grosse Klumpen auf einem Hash treffen. Doof.
D.h. wir wollen das "typische", "praktisch vorkommende" Datenklumpen "nicht zu oft" kollidieren. Und da fängt die schwarze Magie an :-)
Abgesehen davon gibt es noch spezialisierte Hashfunktionen, die bestimmte Eigenschaften haben:
- perfect hashing: nie eine Kollision (wie geht das denn?). Das geht dann, wenn die Ausgangsmenge der grossen Klumpen im Voraus bekannt ist. Man knetet die Hashfunktion so lange, bis man eine bekommt, die (für diese Menge) nicht kollidiert. Anwendung findet das z.B. in der Menge der Schlüsselworte einer Sprache. Mach mal "man gperf" :-)
(kleiner Scherz. Natürlich weiß ich, wie ich im Internet Manpages für nicht installierte Programme finde. Sehr interessant!)
- similarity hashing Man will, dass die Hashes von ähnlichen Klumpen auch ähnlich sind (was auch immer ähnlich sei: z.B. Dokumente mit vielen ähnlichen Wörtern sollen auf Bitwürste abgebildet werden, die sich in wenigen Bits unterscheiden). Gut für Dokumenten- und Bildersuche
Interessant. Im Kurs lag der Schwerpunkt eher darauf, diesen Fall möglichst zu vermeiden, um das Risiko von Kollisionen zu minimieren. Also: kleine Unterschiede in den Eingangsdaten sollten möglichst große und statistisch möglichst gleichmäßig verteilte Ergebnisse produzieren.
Eine weitere Kategorie, über die im Kurs gesprochen wurde, waren "Universelle Familien von Hash-Funktionen", die nicht perfekt sind, aber für zwei unterschiedliche Eingabewerte eine Kollisionswahrscheinlichkeit von höchstens 1/m (m = Größe der Hash-Tabelle) haben. https://en.wikipedia.org/wiki/Universal_hashing
[...]
Herzliche Grüße Urs
_______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
