On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:

[...]

> Im Moment sind es zwei unterschiedlich geartete Fragen:
> 1)
> 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