-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
[...]
Im Moment sind es zwei unterschiedlich geartete Fragen:
Bei der Aufgabe, Substrings zu hashen, komme ich einfach nicht über einen Testfall hinweg, bei dem der Algorithmus zu lange braucht. Hier muss es entweder eine Optimierung geben, die ich nicht gefunden habe (z.B. dass unnötig String-Kopien erzeugt werden oder es eine unnötige Schleife gibt) oder einen Sonderfall, der meinen Algorithmus in die Ecke (bzw. in einen Kreis) treibt): https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues/3
Ich vermisse einige Moduli (%) in precompute_hashes. Z.B. muss
y = self._rn_dx ** p_len
eine ziemlich grosse Zahl sein, bei einem mässig (~100) langem Pattern (im Assignment faseln die von bis 10^5), selbst wenn _rn_dx so klein ist wie bei Dir (2) (was ich ein wenig bedrohlich finde, ich weiss nicht, wie sich das auf das Kollissionsverhalten des Hashes auswirkt).
Python kommt mit grossen Zahlen zwar klar, aber sie sind teuer (auf meiner Gurke kippt die Zeit bei mir von 0.8 auf über 4 (Sekunden):
for i in range(60, 100, 1):
... def f(): ... return 2**i ... timeit.timeit(f) ... print(i) ... 0.8464090824127197 60 0.8901400566101074 61 0.8901631832122803 62 4.829195976257324 63 3.9598159790039062 64 4.131256103515625 65
Da sieht man auch, wieviele Bits sich Python bei einem 64 bit-System als tag bits reserviert, nämlich 3. Ab 2^62 muss Python die Maschinenintegers verlassen und "lange Integers" nehmen. Schick aber langsam.
Vielleicht ist eine Exponentiation in der Schleife, mit Modulo dazwischen richtig. Ganz luxuriös wäre "modular exponentiation" [1], aber ich glaube, die Fussgängermethode wird ausreichen (ein erster Test bei mir liefert: eher nicht -- uh, oh):
def mexp(x, y):
... e = x ... for i in range(1, y, 1): ... e = (e*x) % 1000000009 ... return e ...
mexp(2, 6)
64
def f():
... return mexp(17, 100) ...
timeit.timeit(f)
27.922509908676147
Entweder übersehe ich etwas, oder es braucht tatsächlich [1].
Ganz fies wird, wenn Du das "unmodulierte" y weiter unten für jedes Character in der Schleife nimmst: dann muss Python jedes einfache Integer in ein "fettes" verwandeln...
So viel kriege ich noch heute Abend zusammen.
Fazit: teste Dein Programm mit richtig langen Strings (pattern length 100 oder so).
lg - -- t