Pour les conflits je commence à penser qu'il est possible de faire une bonne distro qui ne les gère pas, en abandonnant au moins partiellement FHS (en:Filesystem_Hierarchy_Standard) et en utilisant des scripts de configuration des alternatives. La meilleure solution pour ce problème est, en cas d'alternatives conflictuelles, de ne fournir que le paquet que Je préfère.
Le problème de dépendances inverses étant coûteux, certaines sous-solutions pourraient-elles être précalculées côté serveur et/ou mises en cache côté client ?
On devrait pouvoir splitter le graphe des paquets en sous-graphes "intéressants" en ramenant toutes les versions d'un paquet à un nœud avec pour poids une fonction logarithmique sur le nombre de versions (O(n) sur le nombre de paquets), en le désorientant (O(n) sur le nombre de dépendances), en réduisant les chaînes isolées (conserver la longueur originale dans le poids des liens, O(n log n) sur le nombre de dépendances déversionnées il me semble), en calculant l'arbre couvrant minimal (en:Minimum_spanning_tree, à peu près linéaire d'après Wikipedia), puis en tronçonnant l'arbre comme un bourrin.
Il y a plusieurs techniques à essayer pour tronçonner, mais j'ai le sentiment qu'on aurait facilement de jolis sous-graphes dans lesquels précalculer.
De toute façon je suis définitivement moins bon que les gens qui bossent là-dessus et n'y pense que vaguement dans le bus, mais j'avais envie de le raconter ;)
Pour revenir à ton outil steckdenis, fais gaffe à ce que tu veux calculer à chaque opération : nombre d'entre elles sont des mises à jour.
Or à chaque mise à jour on "désinstalle" la version actuelle et "installe" la nouvelle. Et "souvent" il "suffit" de vérifier que ça n'impacte personne.
Bref l'opération la plus courante est peu coûteuse dans le cas général, essaye de conserver cette propriété !
Il y a un super algo en O(n) basé sur une fable de La Fontaine ([http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algor(...)]) pour résoudre parfaitement le problème des dépendances inverses. J'ai un prototype de preuve en 50 caractères de Brainfuck en tête mais pas la place dans la marge pour le reproduire !
[^] # Re: Bravo
Posté par Pierre Carrier . En réponse au journal Résolution des dépendances par système de branches. Évalué à 2.
Le problème de dépendances inverses étant coûteux, certaines sous-solutions pourraient-elles être précalculées côté serveur et/ou mises en cache côté client ?
On devrait pouvoir splitter le graphe des paquets en sous-graphes "intéressants" en ramenant toutes les versions d'un paquet à un nœud avec pour poids une fonction logarithmique sur le nombre de versions (O(n) sur le nombre de paquets), en le désorientant (O(n) sur le nombre de dépendances), en réduisant les chaînes isolées (conserver la longueur originale dans le poids des liens, O(n log n) sur le nombre de dépendances déversionnées il me semble), en calculant l'arbre couvrant minimal (en:Minimum_spanning_tree, à peu près linéaire d'après Wikipedia), puis en tronçonnant l'arbre comme un bourrin.
Il y a plusieurs techniques à essayer pour tronçonner, mais j'ai le sentiment qu'on aurait facilement de jolis sous-graphes dans lesquels précalculer.
De toute façon je suis définitivement moins bon que les gens qui bossent là-dessus et n'y pense que vaguement dans le bus, mais j'avais envie de le raconter ;)
Pour revenir à ton outil steckdenis, fais gaffe à ce que tu veux calculer à chaque opération : nombre d'entre elles sont des mises à jour.
Or à chaque mise à jour on "désinstalle" la version actuelle et "installe" la nouvelle. Et "souvent" il "suffit" de vérifier que ça n'impacte personne.
Bref l'opération la plus courante est peu coûteuse dans le cas général, essaye de conserver cette propriété !
Il y a un super algo en O(n) basé sur une fable de La Fontaine ([http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algor(...)]) pour résoudre parfaitement le problème des dépendances inverses. J'ai un prototype de preuve en 50 caractères de Brainfuck en tête mais pas la place dans la marge pour le reproduire !