pagination-problem / tree_structure

0 stars 0 forks source link

Redis #16

Closed laowantong closed 4 years ago

laowantong commented 4 years ago

@SarahMinich Pour t'aider voici un premier jet d'une version Redis pour Python:

class HashAdderRedis(HashAdder):
    def __init__(self, params):
        redis = __import__("redis").StrictRedis
        self.store = redis(host="localhost", port=6379, db=3)
        HashAdder.__init__(self, params)

    def cleanup_states(self):
        self.store.flushdb()

    def add_state(self, w1, w2, i1, i2):
        key = bytes((int(w1 // self.delta), int(w2 // self.delta), i1, i2))
        if not self.store.exists(key) or (w1, w2) < tuple(self.store.get(key)[:2]):
            self.store.set(key, bytes((w1, w2, i1, i2)))

    def get_states(self):
        return sorted((tuple(value) for value in self.store.mget(self.store.scan_iter())))

Pour faciliter les conversions, je passe par le type Python bytes. Cela limite bien sûr les valeurs des éléments du quadruplet entre 0 et 255, donc ça ne marche pas tel quel sur les instances les plus fournies. Et il faut éviter d'utiliser -1 pour dénoter le dernier élément.

laowantong commented 4 years ago

En 3d8691c, au lieu de coder l'absence de tuile dans un bin par -1 (qui référençait commodément la dernière colonne de la matrice des coûts), je la code par l'entier positif tile_count (je ne peux pas prendre tile_count - 1, qui est déjà l'index de la dernière tuile). Du coup, je dois dupliquer la dernière colonne de la matrice des coûts.

laowantong commented 4 years ago

J'ai ajouté l'implémentation du backend Redis dans le master (78f23ee), en relevant la limite à 65535 pour les membres du quadruplet représentant un état. J'utilise une version curryfiée des fonctions pack() et unpack() de la bibliothèque struct, qui comme par hasard est prévue pour l'interfaçage avec le langage C. Le codage et le décodage des états, la modélisation Redis et les commandes Redis restent donc valables pour ta future version en C.

À noter qu'en l'état, le recours à Redis dégrade fortement les performances du programme Python. Mais si toute la boucle est écrite en C, ces étapes de codage et de décodage n'interviendront qu'à l'entrée et à la sortie, et je pense que ça compensera. Redis est extrêmement rapide.

L'alternative, comme je l'ai dit, est d'utiliser une bibliothèque C de dictionnaires ou de matrices creuses. Même dans ce cas, le travail que j'ai fait pour le codage et le décodage des états reste valable.

laowantong commented 4 years ago

En désactivant la persistance de Redis (21a843d), je gagne 25 % en temps d'exécution par rapport à la version précédente.