[Projet solveur SAT] Débuter avec python.

Bonjour à tous.

Je suis en train de réaliser un solveur SAT en Python. J'ai choisi ce langage parce que je ne le connaissais pas et que c'était l’occasion de l'apprendre. Mais vu que c'est un nouveau langage pour moi, j'ouvre ce topic pour mes questions de débutants.

N'hésiter pas à me conseiller d'autre façon de faire (tant sur la syntaxe que sur l'algorithmique lorsque je posterai du code) et de me dire comment faire au mieux.

1. Alors pour commencer, je n'arrive pas à copier un itérateur. J'ai essayer tout et n'importe quoi (v = iter(a), copy.copy(v), puis new(v), copy(v) et j'en passe des meilleurs). Comment faire ? [Résolu, solution : tee()]
   
2. J'ai un fichier avec une formule et pour le moment, l'intégralité de la formule est copié dans une variable que je parcours avec l'itérateur. Je dois aller en avant et parfois revenir en arrière (j'ai appris que les itérateurs ne pouvaient pas aller en sens inverse dans Python, pour autant qu'on ne l'implémente pas. D'où mon désir de "sauvegarder" l'itérateur à la question 1. De plus n'y a t'il pas d'autre moyen d'optimiser l'accès au fichier avec un itérateur sans passer par la variable temporaire contenant la formule ?
   
3. Ensuite, j'ai 3 fichiers (main.py, a.py, constants.py), main.py inclu a.py et a.py inclu constants.py. Malgré tout, a.py ne peut pas utiliser les constantes déclarées dans constants.py (simplement de la forme A=1). J'ai essayé d'inclure avec import constants ou encore from constants import *. Sans succès. edit
   Solution

Merci beaucoup pour votre aide.

1)

Code:

---

1 2 3 4 5 6

>>> liste = [12, 5, 9] >>> liste, copy_liste = iter(liste), iter(liste) >>> liste <list_iterator object at 0x02F1F6D0> >>> copy_liste <list_iterator object at 0x02F54890>

---

2)

Si on peut revenir en arrière avec les indices

Code:

---

1 2 3 4 5 6 7 8

>>> liste = [12, 5, 9] >>> for i, j in enumerate(liste): if i != 0: print(liste[i-1])     12 5

---

3)

Si constants.py inclus tous les autres modules, vous n'incluez logiquement pas constants.py dans a.py par exemple.

Code:

---

1 2 3

from a import *   print(var_du_module_a)

---

Merci pour votre réponse. Je me suis très certainement mal exprimé mais je n'ai pas trouvé de solutions dans votre message.

1) En fait je veux copier un itérateur à partir d'un itérateur.

2) C'est des indices donc pas un itérateur à proprement parler il me semble ? Je dispose juste d'une variable "a" qui est un itérateur sur un objet (à la limite on ne sait pas lequel).

3) constants.py n'inclus aucun fichiers. En fait, Main.py inclus a.py qui inclus constants.py. Et dans a.py, je ne peux pas accéder aux variables déclarées dans constants.py.

1) ça change rien

Code:

---

1 2	iterator = iter(liste) iterator_copy = iterator

---

2) Ok, là ton problème peut se résoudre à l'aide d'un itérateur bidirectionnel

Voir doc officielle

3)

Citation:

---

constants.py n'inclus aucun fichiers. En fait, Main.py inclus a.py qui inclus constants.py. Et dans a.py, je ne peux pas accéder aux variables déclarées dans constants.py.

---

Bizarre

1) Malheureusement mes tests n'indiquent pas ce comportement, je pense que l'opérateur "=" fait une copie "par référence" (si c'est le terme utilisé dans le jargon Pÿthon). Preuve :

Code:

---

1 2 3 4 5 6

v = "A" a = iter(v) b = a c = a.next() print b.next()

---

et le résultat :

Code:

---

1 2 3

print b.next() StopIteration

---

Ce qui veut dire que l'incrémentation de l'itérateur "a" à également incrémenté "b".

2) L'itérateur que vous me montrez dans la doc permet de parcourir la séquence en sens inverse. Ce n'est pas bidirectionnelle vu qu'on ne peut pas faire de .next(), puis l'instant d'après revenir sur nos pas. (Ou alors je n'ai pas compris l'exemple).

3) :(

Citation:

---

2) L'itérateur que vous me montrez dans la doc permet de parcourir la séquence en sens inverse. Ce n'est pas bidirectionnelle vu qu'on ne peut pas faire de .next(), puis l'instant d'après revenir sur nos pas. (Ou alors je n'ai pas compris l'exemple).

---

euh... là faut me donner un exemple car je suis perdu, à part avec l'indexation, je ne vois pas comment tu pourrais revenir en arrière.

Après tu as la possibilté de parcourir une liste de façon circulaire, mais je ne pense pas que se soit cela que tu souhaites.

Citation:

---

1) Malheureusement mes tests n'indiquent pas ce comportement, je pense que l'opérateur "=" fait une copie "par référence" (si c'est le terme utilisé dans le jargon Pÿthon). Preuve :

---

Le module itertools et la méthode tee() vous permettra de créer le nombre d'itérateur que vous souhaitez si j'ai bien compris.

Pour la copie d'itérable (je suis en version 3 python pour le test),

Code:

---

1 2 3

l, m = [iter(elt) for elt in tee(['a', 'b', 'c'], 2)] print(next(l)) print(next(m))

---

Réunissons la question 1 et 2.

Exemple simple : un parcours d'une séquence de caractère. On veut s'arrêter AVANT le prochain espace. Pour détecter cette espace on est obligé de faire iterator.next() == whitespace. Mais après le .next() nous avons été un pas trop loin. D'où la nécessité de vouloir revenir un pas en arrière.

En utilisant les itérateurs je veux modéliser un "flux".

EDIT : Je viens de voir votre dernier message. Effectivement "tee" marche. Merci.
Malgré tout, je doute que ça soit la meilleure solution à mon problème, il s'agit peut-être plus d'un problème de conception alors.

Le plus simple aurait un exemple d'entrée sortie, mais bon...

Code:

---

1 2 3

>>> ch = 'abc def' >>> ch.split() ['abc', 'def']

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

>>> ch = 'abc def' >>> ch = iter(ch) >>> while True: c = next(ch) if c == ' ': break print(c)     a b c

---

Code:

---

1 2 3 4 5 6 7 8 9

>>> for i in 'abc def': if i == ' ': break else: print(i)     a b c

---

Merci pour ces exemples intéressants. Néanmoins la condition "lorsqu'on trouve un espace" était juste un exemple et peut éventuellement être plus compliqué.

J'ai édité mon premier message avec une simplification du problème #3 que je vous remet ici :

Le problème est encore plus simple que cela. J'ai ces deux fichiers :

test.py

Code:

---

1 2 3 4 5 6 7 8 9 10

import s import os import sys   def main(args): print GLOBAL_B   if __name__ == '__main__': main(sys.argv)

---

s.py

Code:

---

1 2	GLOBAL_B = 1

---

Et l'erreur suivante à l'interprétation :

Code:

---

1 2 3 4 5 6 7

Traceback (most recent call last): File "test.py", line 10, in <module> main(sys.argv) File "test.py", line 7, in main print GLOBAL_B NameError: global name 'GLOBAL_B' is not defined

---

Citation:

---

Merci pour ces exemples intéressants. Néanmoins la condition "lorsqu'on trouve un espace" était juste un exemple et peut éventuellement être plus compliqué.

---

Mais s'adapte évidemment ;)

Code:

---

1 2	def main(args): print s.GLOBAL_B

---

Pour la question 2, cherches-tu à faire un parseur (analyseur syntaxique)? Les expressions régulières (module re dans Python) pourraient être utile dans ce cas.

Arf j'ai pas vu, il a édité, j'ai proposé une seule solution, en l'occurence

Code:

---

print s.GLOBAL_B

---

surtout car c'est la solution conseillé, d'importer de cette façon

Code:

---

import mon_module

---

Ou alors une autre

Code:

---

from s import GLOBAL_B

---

Mais surtout pas

Code:

---

from mon_module import *

---

@fred1599 : Pourquoi la dernière solution n'est-elle pas acceptable ? (Je suppose que c'est pour éviter les conflits de nom, dans ce cas, quand est-il du fait qu'on est sur que ce nom de constante ne ré-apparaitra pas ?).

@dividee : Je vais commencer par le début. N'hésitez pas à commenter ou me contredire sur certains points qui vous semblerais faux.

Le but est d'analyser une formule dans un fichier. La première étape est de construire un arbre de syntaxe. J'ai décidé que pour rendre l'application plus propre je passerais par un module "Lexer". Il se construit grâce à un itérateur représentant le flux de donnée devant être analysé et, par le biais d'une méthode, renvoie des "Token", classe encapsulant une constante entière représentant un certain caractère (par exemple "/\" (ET logique) représenté par la valeur "1"). Ceci dans le but de dissocié l'interprétation graphique/syntaxique de l'interprétation sémantique de ce symbole. Le parser reçoit donc des Tokens et construira l'arbre syntaxique grâce à eux. C'est également lui qui sera chargé de construire la structure de donnée qui sera utilisée par la suite.

Donc une expression régulière ne conviendra pas pour ces raisons (confirmez svp.) :

1. Trop lente par rapport à un module spécialisé (j'accuse la généricité du module "re").
2. Ne permet pas de renvoyer une abstraction comme le "Token".
3. Donc un module "Lexer" serait quand même nécessaire.
4. Mais pour être utile, l'expression régulière devrait analyser l'entièreté de la formule d'abord. Donc on ne peut pas construire notre arbre de syntaxe en une seule passe.

Merci pour vos réponses.

Citation:

---

Pourquoi la dernière solution n'est-elle pas acceptable ?

---

Réponse:

Citation:

---

Je suppose que c'est pour éviter les conflits de nom

---

exact!

Citation:

---

quand est-il du fait qu'on est sur que ce nom de constante ne ré-apparaitra pas ?

---

Euh... Pas dis que j'ai compris, mais si tu as le nom du module et la constante à la suite, il y a peu de chance de retrouver la même constante.

Rien ne t'empêche de nommer tes modules d'un autre nom

Code:

---

1 2	import s as module_s print(module_s.GLOBAL_B)

---

A vrai dire, je trouve lourd d'importer exactement ce que j'utilise (from XX import bla,bla,bla,...) et lourd aussi de devoir préfixer chaque constantes par le nom de son module. Enfin je vais surement opter pour la première solution.

Sinon c'est toujours intéressant de savoir qu'on peut renommer des modules merci ;)

La 1ère solution et la dernière (renommer ton module) sont identiques.:)

A moins que je me trompe, lorsqu'on fait "from XX import z", on peut accéder à 'z' sans préfixe.

J'ai également une question sur les itérateurs. A part avec la méthode "next()" il n'est pas possible d'accéder à la valeur actuellement pointée par l'itérateur ?

Exemple :

Code:

---

1 2 3

v = "abc" a = iter(v) # Je veux la lettre 'a' mais sans avancer l'itérateur sur 'b'

---

Citation:

---

A moins que je me trompe, lorsqu'on fait "from XX import z", on peut accéder à 'z' sans préfixe.

---

La première méthode était

Code:

---

import s

---

Citation:

---

J'ai également une question sur les itérateurs. A part avec la méthode "next()" il n'est pas possible d'accéder à la valeur actuellement pointée par l'itérateur ?

---

Si

Code:

---

1 2	for i in v: print(i)

---

Code:

---

print('\n'.join([i for i in v]))

---

Code:

---

1 2	for i, j in enumerate(v): print('index {0} : lettre {1}'.format(i, j))

---

Citation:

---

Envoyé par fred1599

Si

Code:

---

1 2	for i in v: print(i)

---

Code:

---

print('\n'.join([i for i in v]))

---

Code:

---

1 2	for i, j in enumerate(v): print('index {0} : lettre {1}'.format(i, j))

---

---

Ben non, que ce soit avec for ou enumerate, tu consommes l’itérateur*! :mouarf:

N’y a pas de miracle, un itérateur par construction, ne fournit que next()… Si tu veux bosser sur les éléments n-1, n, n+1, tu peux soit les «*mettre en cache*» (garder les x derniers éléments lus), soit, si ce n’est pas assez souple, convertir l’itérateur un liste, ou mieux (si tu n’a pas besoin de le modifier), en tuple, puis d’utiliser enumerate…

En tout cas, je ne vois pas d’autre solution –*et s’il s’agit simplement d’interprêter une fonction, convertir l’itérateur en liste ou tuple ne devrait vraiment pas être un problème*!

Citation:

---

Ben non, que ce soit avec for ou enumerate, tu consommes l’itérateur

---

En effet je n'avais pas compris la question de cette façon là. En fait il veut avoir une autre méthode que next() pour son itérateur, et il y en a pas d'autres.

Bien vu mont29 :ccool:

Citation:

---

Envoyé par Trademark

Le but est d'analyser une formule dans un fichier. La première étape est de construire un arbre de syntaxe. J'ai décidé que pour rendre l'application plus propre je passerais par un module "Lexer". Il se construit grâce à un itérateur représentant le flux de donnée devant être analysé et, par le biais d'une méthode, renvoie des "Token", classe encapsulant une constante entière représentant un certain caractère (par exemple "/\" (ET logique) représenté par la valeur "1"). Ceci dans le but de dissocié l'interprétation graphique/syntaxique de l'interprétation sémantique de ce symbole. Le parser reçoit donc des Tokens et construira l'arbre syntaxique grâce à eux. C'est également lui qui sera chargé de construire la structure de donnée qui sera utilisée par la suite.

Donc une expression régulière ne conviendra pas pour ces raisons (confirmez svp.) :

1. Trop lente par rapport à un module spécialisé (j'accuse la généricité du module "re").
2. Ne permet pas de renvoyer une abstraction comme le "Token".
3. Donc un module "Lexer" serait quand même nécessaire.
4. Mais pour être utile, l'expression régulière devrait analyser l'entièreté de la formule d'abord. Donc on ne peut pas construire notre arbre de syntaxe en une seule passe.

Merci pour vos réponses.

---

C'est tout de même souvent des expressions régulières qui sont utilisées pour des "lexer" un peu complexes, comme par exemple dans (f)lex.

Mais si tu pars sur ce chemin, pourquoi réinventer la roue et ne pas utiliser une bibliothèque de parsing ? Il y en a déjà plein en Python (voir ici par exemple).

Pourquoi les performances du lexer/parser sont si importantes ? Le problème SAT est NP-complet, il me semble. Pour des formules un peu complexes, le temps de calcul sera de toute façon dominé par le solveur...

Alors effectivement il existe des bibliothèques, je m'en doutais. Et il existe déjà même des solveurs qui sont déjà 100 fois plus performant que ce que je ne ferai jamais. Je pense que si j'avais voulu faire un solveur à titre professionnel, je l'aurais fait en C++ ou, dans une moindre mesure, dans un langage compilé.

Le but de l'exercice est de concevoir un solveur de A à Z et d'en comprendre le fonctionnement. Pour avoir une application correcte, j'essaye toujours d'explorer toutes les possibilités et de faire au mieux, même pour les détails.

Votre commentaire me fait penser à un article lu sur ce forum. Selon l'auteur, les enseignements JAVA ne sont pas à la hauteur et l'élève fait toujours n'importe quoi quand il doit aller en entreprise. Ça on le sait bien, l'école et le monde professionnel sont très différents. Il conseillait donc aux professeurs d'apprendre aux élèves à utiliser directement les api de java. Et c'est là qu'il rejoint votre commentaire. Je trouve cette attitude dégradante envers l'informatique car c'est avant tout une science à part entière. En mathématique, les élèves doivent démontrer des formules, pourtant c'est déjà fait. En littérature, les élèves doivent écrire des dissertations sur des sujets ressassés des centaines de fois. Et bien en informatique, les élèves doivent concevoir du code qui a déjà été conçu par mille autres avant. Le but de cette manœuvre, aussi pénible puisse-telle vous paraitre, est, je pense, indispensable. Ceci permet d'acquérir les fondements logiques de la programmation. De plus, les choix de conception devant être fait par l'élève lui seront bénéfiques plus tard lorsque dans d'autres projets il sera confronté à des problèmes similaires. Pour finir ce monologue, il me semble qu'on utilise beaucoup mieux des outils dont on comprend les rouages internes (sans ça, il peut souvent arriver qu'on se demande pourquoi un tel choix a été fait. Par exemple, l'invalidation d'un itérateur après une suppression).

Néanmoins, merci pour vos commentaires qui m'ont été utiles. J'espère que vous comprenez mon point de vue.

Je suis d'accord sur le principe que tu défends. Je me suis trompé sur tes objectifs. Je pensais que l'objectif était d'expérimenter avec un solveur SAT.

L'avantage d'un langage comme Python, c'est de pouvoir prototyper rapidement une solution. Pour l'apprentissage, cela permet aussi de se concentrer sur le problème sans devoir trop se préoccuper de certains détails, importants mais non directement liés au problème.

Pour donner un exemple, on peut implémenter l'algorithme de recherche des plus courts chemin de Dijkstra en une dizaine de lignes, grâce à la richesse des structures de données en Python. Pour cela, on utilise, par exemple le type de données set (ensemble). L'implémentation efficace de ce type de données est, en soi, plus complexe que l'implémentation de l'algorithme de Dijkstra qui l'utilise, mais constitue un détail si le but est la recherche des plus courts chemins dans un graphe. De même, la démonstration mathématique de l'algo de Dijkstra n'oblige pas à redémontrer depuis le début la théorie des ensembles...

Ecrire un parser efficace en Python est louable, mais c'est une tâche plus ardue, il me semble, que d'écrire un solveur SAT.

Je ne prône pas la spécialisation de l'enseignement de la programmation sur un petit nombre de librairies utilisées en entreprise, mais je pense tout de même que choisir une librairie adaptée à ses besoins est une compétence qui peut avoir sa place dans un cursus...

On est bien d'accord dividee 8-)

Je ne reviens pas sur ce topic pour ne dire que ça mais pour un problème d'inclusion.

Le dossier du projet est composé entre autre de

Code:

---

1 2 3 4 5

+src |- librairie.py +test |- fichier_test.py

---

Le fichier_test ne trouve pas la librairie et malgré que j'ai fait : sys.path.append("../src/librairie.py") sys.path.append("../src") dans fichier_test.py.

Quelle est la solution à mon problème ?

Ce serait pas plutôt sys.path.append("../src")*? Le path contient des dossiers où chercher les fichiers, pas directement des fichiers…

Je ne sais pas pourquoi j'ai marqué ça dans le message :aie:. Dans mon code j'ai bien fait :

Code:

---

sys.path.append("../src")

---

Mais ça ne marche pas.

La notion de répertoire courant n'est pas très bien adaptée aux environnements fenêtrés modernes... Quand tu lances fichier_test.py, rien ne garantit que le répertoire courant est celui qui contient le fichier.
Il vaut mieux référencer explicitement __file__, comme ceci:

Code:

---

os.path.abspath(os.path.join(os.path.dirname(__file__), '..', 'src'))

---