HASHING.md

Dogopher

Petites optimisations rigolotes pour le Hashing

Code pour le profiling

Nous utiliserons ce code pour le profiling de notre function de hashage.

import cProfile
import pstats

def profile_hashing(n=10**5):
    grid = HexGrid.random_state(100)
    for _ in range(n): 
        hash(grid)


cProfile.run("profile_hashing()", "hashing_profile")
p = pstats.Stats("hashing_profile")
p.sort_stats("cumtime").print_stats(10)

Candidats pour la fonction de hashage

Nous avons retenus deux canditats pour la fonction de hashage que nous décrivons ci-dessous.

Le builtin hash

L'implémentation la plus logique et la plus directe est d'utiliser le builtin hash de Python.

Le code

def __hash__(self) -> int:
    return self.grid.tobytes().__hash__()

Pour se faire nous avons néanmoins besoin de convertir la grille (qui est un numpy.ndarray) en une chaîne d'octets pour pouvoir calculer son hash.

Le résultat

Le graphe ci dessous répertorie les temps d'exécution:

Comme nous pouvons le voir, les résultats sont bons et largement suffisants pour notre utilisation, néanmoins, comme la compétition est sous contrainte de temps, nous pouvons mieux faire et gagner quelques secondes de temps de calcul sur la fonction de hashage.

La librairie xxhash

La librairie xxhash est une librairie de hashage performante qui propose des fonctions de hashage non-sécurisée (non-cryptographique) très rapides.

Comme nous utilisons le hashage exclusivement pour des accès à un dictionnaire, ce n'est pas dérangeant que nos fonctions soient non-cryptographiques.

• Référence: https://stackoverflow.com/a/75870138

Le code

def __hash__(self) -> int:
    return xxh32(self.grid).intdigest()

Ce code suppose que notre grille (qui est un numpy.ndarray) suit un layout de C-array, ce qu'il est possible de faire en utilisant numpy.ascontiguousarray lors de la création de la grille dans la classe HexGrid.

def __array_of_state(self, state: State) -> np.ndarray:
    # Code de __array_of_state
    return np.ascontiguousarray(array)

Le résultat

Le graphe ci dessous répertorie les temps d'exécution:

Soit un gain d'environs 7 secondes sur la méthode avec le builtin de Python sur une chaîne d'octets.