Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork33.7k
Closed
Description
In both 3.10 and 3.11, hashing a small fraction is 20x slower than for a decimal. For fractions with large denominators, it is slower still.
We could sacrifice the space for one slot to cache the hash value:
__slots__ = ('_numerator', '_denominator', '_hash')def __hash__(self): try: return self._hash except AttributeError: self.hash = ... # current code goes here return self._hashAnother approach would be to have a single, size limited cache for the computation:
def __hash__(self): @lru_cache(maxsize=1 << 16) def current_code(numerator, denominator): try: dinv = pow(denominator, -1, _PyHASH_MODULUS) except ValueError: # ValueError means there is no modular inverse. hash_ = _PyHASH_INF else: hash_ = hash(hash(abs(numerator)) * dinv) result = hash_ if numerator >= 0 else -hash_ return -2 if result == -1 else result return current_code(self._numerator, self._denominator)Example of code that would benefit:
@lru_cache(maxsize=100_000)def pabs(n: Fraction | int) -> Fraction: "P-adic absolute value" ...for x, y in product(pool, repeat=2): # pool is a set of fractions used as test values assert (pabs(x)==0) == (x==0) # |x|=0 if and only if x=0 assert pabs(x * y) == pabs(x) * pabs(y) # |xy| = |x||y| assert pabs(x + y) <= pabs(x) + pabs(y) # |x + y| ≤ |x| + |y| (Triangle Inequality) assert pabs(x + y) <= max(pabs(x), pabs(y)) # Strong triangle inequality assert pabs(x) == pabs(y) or pabs(x + y) == max(pabs(x), pabs(y)) # Lemma 2.1: If |x| ≠ |y|, |x+y| = max{|x|, |y|}