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
--
ul@openlilylib.org
https://openlilylib.org
http://lilypondblog.org