Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
<div align='center'>
<img src=https://gitlab.utc.fr/uploads/-/system/project/avatar/14278/dogopher.png alt="logo" width=90 height=90 />
<h1>Dogopher</h1>
<p>Petites optimisations rigolotes pour le Hashing</p>
</div>
## Code pour le profiling
Nous utiliserons ce code pour le profiling de notre function de hashage.
```python
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
```python
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:
<div align="center">
<img src="images/hash_builtin.png" alt="Résultat des performances de la méthode builtin">
</div>
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
```python
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`.
```python
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:
<div align="center">
<img src="images/hash_xxhash.png" alt="Résultat des performances de la méthode xxhash">
</div>
Soit un gain d'environs 7 secondes sur la méthode avec le builtin de Python sur une chaîne d'octets.