[...] montre comment les branches permettent de facilement se tirer du problème dans devoir sortir une artillerie telle que SAT.
Il est complet à tous points... Il est extrêmement rapide : il ne fait jouer que les paquets nécessaires. ... Il est incroyablement simple
Ces phrases m'ont un peu surpris. Ton solveur fait peut être ~250 lignes, mais comme ça a déjà été remarqué plus haut, le problème de gestion des dépendances est NP-complet et ton solveur.. loin d'être "complet".
D'autre part, le solveur implémenté dans ZYpp est basé sur le solveur open-source MiniSAT (http://minisat.se/ ) qui fait dans les 600 lignes. Pas mal pour un solveur complet qui s'affranchit de l'exponentialité des solutions possible avec le nombre de paquets disponibles.
Enfin, tu sous entends que le solveur d'openSUSE nécessite de chargé la base de données en mémoire avant de pouvoir effectuer les calculs de dépendances et que ceci ralenti considérablement sa vitesse.
Ce n'est pas exactement vrai, puisque en pratique on voit que l'utilisation d'une BDD binaire (que tu sembles aussi utiliser) est foudroyant à l'exécution. Il ne faut que quelques millisecondes pour lire la base de données entière et ce n'est en tout cas pas un "bottleneck".
Using a data dictionary approach to store and retrieve package and dependency information. A new solv format was created, which stores a repository as a string dictionary, a relation dictionary and then all package dependencies. Reading and merging multiple solv repositories takes just some milliseconds.
Là où les choses peuvent être améliorées est la vitesse de création des équivalents binaires des méta-données des dépôts, par exemple, en les générant à la volée directement sur le serveur, et pas après téléchargement des md-data par le client.
A noter aussi que Apt, Yum et URPMI sont incomplets et utilisent plutôt des méthodes heuristiques. A ma connaissance, le seul PM non expérimental qui utilise un algo "avancé" de type SAT et est possiblement complet est Smart.
Sinon, j'aime bien tes journaux/concepts, y'a de bonne idées mais je pense qu'un peu plus de modestie serait un plus concernant ta crédibilité.
# SAT, une artillerie lourde ?
Posté par Spyhawk . En réponse au journal Résolution des dépendances par système de branches. Évalué à 7.
Il est complet à tous points... Il est extrêmement rapide : il ne fait jouer que les paquets nécessaires. ... Il est incroyablement simple
Ces phrases m'ont un peu surpris. Ton solveur fait peut être ~250 lignes, mais comme ça a déjà été remarqué plus haut, le problème de gestion des dépendances est NP-complet et ton solveur.. loin d'être "complet".
D'autre part, le solveur implémenté dans ZYpp est basé sur le solveur open-source MiniSAT (http://minisat.se/ ) qui fait dans les 600 lignes. Pas mal pour un solveur complet qui s'affranchit de l'exponentialité des solutions possible avec le nombre de paquets disponibles.
Enfin, tu sous entends que le solveur d'openSUSE nécessite de chargé la base de données en mémoire avant de pouvoir effectuer les calculs de dépendances et que ceci ralenti considérablement sa vitesse.
Ce n'est pas exactement vrai, puisque en pratique on voit que l'utilisation d'une BDD binaire (que tu sembles aussi utiliser) est foudroyant à l'exécution. Il ne faut que quelques millisecondes pour lire la base de données entière et ce n'est en tout cas pas un "bottleneck".
Using a data dictionary approach to store and retrieve package and dependency information. A new solv format was created, which stores a repository as a string dictionary, a relation dictionary and then all package dependencies. Reading and merging multiple solv repositories takes just some milliseconds.
Là où les choses peuvent être améliorées est la vitesse de création des équivalents binaires des méta-données des dépôts, par exemple, en les générant à la volée directement sur le serveur, et pas après téléchargement des md-data par le client.
A noter aussi que Apt, Yum et URPMI sont incomplets et utilisent plutôt des méthodes heuristiques. A ma connaissance, le seul PM non expérimental qui utilise un algo "avancé" de type SAT et est possiblement complet est Smart.
Sinon, j'aime bien tes journaux/concepts, y'a de bonne idées mais je pense qu'un peu plus de modestie serait un plus concernant ta crédibilité.
http://en.wikipedia.org/wiki/ZYpp