Hallo Tomás,
Am 29.07.2017 um 23:45 schrieb tomas@tuxteam.de:
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,
stimmt. Ich glaube, hier sieht man, wie ich schwimme. Ich war eigentlich von Varianten mit deutlich mehr %-Operationen ausgegangen und hatte dann gedacht, dass diese vielleicht unnötig Zeit kosten. Wahrscheinlich habe ich da dann in die falsche Richtung "verbessert" - eben, weil ich die Sache nicht völlig durchschaue.
Vielen Dank für deine Überlegungen und Ausführungen, die mich hoffentlich in eine bessere Richtung lenken - allerdings nicht mehr heute Abend, da ist mir das doch zu kompliziert. Ein Mentor hat im Forum übrigens geschrieben, dass sich alle, die Probleme mit der Laufzeit haben, sich mal "Schnelleres Modulo" (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem) anschauen sollten.
Ich melde mich, falls es weitere Erkenntnisse gibt. HG Urs
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 _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug