Home>

python : How to speed up polynomial hash calculation

Computing a polynomial hash on the string s. My solution (Horner's method):

base= int(input())
mod= int(input())
s= input()
first_expr= ord(s[0]) * base + ord(s[1])
for i in range(2, len(s)):
    first_expr= first_expr * base + ord(s[i])
print(first_expr % mod)
# 123 |
# 100003 |=> 6080
# hash |

How can I speed up this solution?

Give a link to the testing system.

Stanislav Volodarskiy2022-01-30 07:40:57
python python-3.x
  • Answer # 1

    Module (%) must be called in a loop. Your algorithm now has quadratic complexity. Number of digitsfirst_exprgrows in proportion to the length of the string. Arithmetic operations with it are correspondingly slowed down. This is imperceptible on short lines, but on long lines it will not be good.

    def phash(base, mod, s):
    h= 0
    for c in s:
        h= (h * base + ord(c)) % mod
    return h
base= int(input())
mod= int(input())
s= input()
print(phash(base, mod, s))

    understood thanks. Your solution is indeed faster, but still fails on some tests

    Came Up2022-01-29 23:34:20
  • Answer # 2

    Module (%) must be called in a loop. Your algorithm now has quadratic complexity. Number of digitsfirst_exprgrows in proportion to the length of the string. Arithmetic operations with it are correspondingly slowed down. This is imperceptible on short lines, but on long lines it will not be good.

    def phash(base, mod, s):
    h= 0
    for c in s:
        h= (h * base + ord(c)) % mod
    return h
base= int(input())
mod= int(input())
s= input()
print(phash(base, mod, s))

    understood thanks. Your solution is indeed faster, but still fails on some tests

    Came Up2022-01-29 23:34:20