Aller au contenu

Introduction décente à l'orienté objet ?

Yozz

Par Yozz,
dans Science et technologie

Messages recommandés

Nirvana

Nirvana

Posté
Posté

map sûr collection donnée applique une fonction à tous les éléments de la collection.

C'est la première partie de mapreduce si tu veux.

 

Merci. Par contre, j'ai "développé" le code pour ma propre compréhension et je bloque :

 

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Codage de deux entiers naturels vers un seul entier naturel

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]

# Définit la fonction codage (avec les arguments x et y)
codage = lambda x, y: (x + y + 1) * (x + y + 2) / 2 - x - 1

schema = list(map(lambda x: (x == 'R') and 'R' or suite.pop(0), schema)) #?????

def R(liste):

	a = liste[0]		# Premier élément de la liste
	b = -1				# ??????  <----
	reste = liste[1:]	# Toute la liste sauf le premier élément

	# Si le premier élément de la liste est une racine
	if liste[0] == 'R':
		a = (R(liste[1:]))[0]		# ??????  <----
		reste = (R(liste[1:]))[1]	# ??????  <----
	
	# Traitement du "reste" de la liste
	if reste:
		# Si le premier élément du reste de la liste est une racine
		if reste[0] == 'R':
			b = (R(reste[1:]))[0]		# ??????  <----
			reste = (R(reste[1:]))[1]	# ??????  <----
		else:
			b = reste[0]				# ?????? (-1 = reste[0] ?) <----
		return codage(a, , reste[1:]	# ??????  <----
	else:
		return a

resultat = R(schema)
print(resultat)

 

 

Lien vers le commentaire
Malky

Malky

Posté
Posté

Petit errata : dans le code plus haut à la ligne "return codage(a, B, reste[1:]" le 'b' est en minuscule sinon l'interpréteur ronchonne.

 

map(f, séquence) ça applique la fonction f a chaque élément de la séquence et ça retourne la séquence contenant les résultat de tous les appels à la fonction f

 

liste=[1, 2, 3, 4]

def f(x): return x+1

liste2=map(f, liste)

print(liste2)

 

>>> [2, 3, 4, 5]

 

Elle peut facilement être remplacée par une list comprehention, c'est même plus dans l'esprit python (map c'est un peu vieillot maintenant)

En list comprehension ça donne : 

 

schema=[(x=='R') and 'R' or suite.pop(0) for x in schema]

 

 

Je devrais avoir 1h ou 2 de libre cet aprèm', j'essaierai de poster qqs commentaires sur la fonction R() qui n'est pas évidente à lire. 

Lien vers le commentaire
Noob

Noob

Posté
Posté

Merci. J'aimerais me servir de ce code mais ça doit être trop concis pour moi. En l'état, je ne comprends pas son fonctionnement.

 

L'idée derrière c'est la programmation fonctionnelle, tu peux trouver des vidéos sympa sur le sujet sur coursera.

Le cours est donnée par Martin Odersky et il est vraiment très bien fichu, bon c'est du Scala, mais l'idée est la même. https://class.coursera.org/progfun-2012-001/class/index

Si jamais tu y arrives pas je peux te télécharger le cours et t'envoyer les vidéos si tu as besoin.

 

A titre personnel ça a été un vrai défi pour moi ce cours. J'ai très bien fini, mais j'ai mis pas mal de temps dedans pour rendre chaque TP.

Lien vers le commentaire
Malky

Malky

Posté
Posté

Bon, j'ai une bonne heure de dispo ça devrait suffire.

J'ai enlevé les fonctions lambda qui brouillent la lecture plus qu'autre chose, et on va voir ça ligne par ligne.

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]

Initialisation des variables d'entrée comme dans l'exemple
 

def codage(x, y): return (x+y+1)*(x+y+2)/2-x-1

Definition de la fonction codage, je l'ai juste raccourcie pour tenir sur une ligne en ajoutant le '-1' à la fin pour corriger le petit offset

schema=[(x=='R') and 'R' or suite.pop(0) for x in schema]

Les hostilités commencent ici : le fameux and/or trick pour faire tenir un if/then/else dans une expression, et la compréhension de liste. Si tu coupe le code à cet endroit là et que tu ajoutes un print(schema) tu verras le résultat de cette ligne : dans la liste 'schema', les 'f' sont maintenant remplacés par les nombres de la liste 'suite' dans le bon ordre.
Une compréhension de liste c'est la définition d'une liste de manière fonctionnelle, la forme générale c'est :
liste2=[f(x) for x in liste] avec f(x) qui représente une opération sur x.
Dans l'exemple de map() plus haut, tu peux aussi écrire :
 
liste=[1, 2, 3, 4]
liste2=[x+1 for x in liste]
print(liste2)
>>> [2, 3, 4, 5]
 
La syntaxe est assez claire, je définis une liste qui contient x+1 pour tout x appartenant à 'liste'.
Maintenant dans ce cas, l'opération sur x paraît beaucoup plus compliquée, mais en fait elle est assez simple : j'ai utilisé un comportement particulier des opérateurs 'and' et 'or' quand ils traitent autre chose que des booléens ainsi que la tendance générale des ordinateurs à être fainéants.
 
Pour simplifier on va écrire 'a and b or c', l'interpréteur va naturellement évaluer cette expression 'booléenne' de gauche à droite.
a est-il vrai ?
-> oui, donc il faut évaluer b pour connaître le résultat de 'a and b'
-> non, pas besoin d'évaluer b, a étant faux le résultat sera faux de toute façon.
ensuite, si 'a and b' est vrai il n'y a pas besoin d'évaluer c car le résultat 'vrai or c' est de toute façon vrai
si a ou b est faux, il faut évaluer c car c peut avoir une incidence sur le résultat
au final 'a and b or c' revient à écrire : 'if a then b else c' c'est un if/then/else raccourci
Mais en plus, python garde le type original des objets évalués : une string "pipi" vaut 'vrai' alors qu'une string "" (vide) vaut 'faux' sauf que les objets gardent leur type et leur valeur au travers des opérateur 'and' et 'or'.
Dans la ligne de code en question :
a -> (x=='R') <- booleen
b -> 'R' <- string
c -> suite.pop(0) <- nombre
Dans ce cas 'a and b or c' signifie : if (x=='R') then 'R' else suite.pop(0) pour tout x appartenant à la liste 'schema'
Le résultat est tout de suite visible : les 'R' restent des 'R', mais les 'f' (en fait tout ce qui n'est pas 'R') sont remplacés par le premier élément pris dans 'suite' et ainsi de... suite. 
Pourquoi and/or ? parce qu'on ne peut pas caser de if/then/else dans une expression, donc on ne peut pas non plus le caser dans une compréhension de liste.

def R(liste):
  a, b, reste=liste[0], -1, liste[1:]

On attaque R(). La première ligne est une assignation multiple :

a=liste[0]

b=-1

reste=liste[1:]

Là tu as correctement interprété les assignations, le b=-1 c'est juste pour instancier la variable (sinon il existe un cas ou b peut être utilisé sans avoir été défini), j'aurais tout autant pu écrire b="coucougnette farcie" la valeur n'a aucune importance.

J'assigne liste[0] à 'a' et juste après tu peux voir qu'il y a une autre assignation de a, mais qui est conditionnelle : si (juste après) liste[0] se révèle valoir 'R' la valeur de a va changer, en l'assignant dès le début à ligne[0] je donne sa valeur à a dans le cas où liste[0] n'est pas 'R'.

Pour 'reste' il s'agit aussi d'une assignation par défaut : tous les éléments de liste sauf le premier (qui est dans 'a')

  if liste[0]=='R': (a, reste)=R(liste[1:])

Si liste[0] est 'R', je fais une assignation multiple avec le resultat d'un autre appel à la fonction 'R'. Si tu regardes un peu plus bas, la fonction 'R' possède deux lignes 'return' : une pour tout le long du déroulement du code, qui renvoie deux valeurs : codage(a, b ) et reste[1:], et une autre pour la fin du code quand la liste d'origine est réduite à un nombre : le résultat final (return a).

Ici, on a pas encore fini de parcourir l'arbre donc R renvoie deux valeurs : un nombre et la partie de liste qui n'a pas encore été parcourue à ce moment là.

La liste 'reste' est assez troublante : elle est rendue nécessaire par le fait que si tu connais le fils de gauche de ton noeud courant (c'est l'élément suivant dans la liste), tu ne connais pas la position du fils de droite avant d'avoir parcouru tout le sous-arbre de gauche. D'où la nécessité de découper la fonction récursive en deux parties : une simple qui gère les fils de gauche au fur et à mesure qu'ils se présentent, et une autre pour gérer les fils de droite une fois que la gestion des fils de gauche te retourne la liste qui reste une fois que le sous-arbre de gauche a été parcouru. Le fait que R soit récursive te garanti que quand le premier appel récursif à R se termine, la liste 'reste' que la fonction retourne commence par le fils de droite de ton noeud de départ, et il en va de même pour tous les noeuds intermédiaires. C'est assez ignoble au niveau de l'occupation mémoire comme algo, mais ça marche de manière 'purement' récursive alors que si tu utilises des variables globales et des compteurs, tu auras au mieux quelque chose d'hybride itero-récursif.

Pour revenir au code : si le premier noeud rencontré est un 'R', on relance R sur le sous-arbre de gauche du noeud courant en l'explorant, à chaque fois, comme s'il s'agissait d'un arbre entier (avec d'autres noeuds et des fils de gauche et de droite).

  if reste:
    if reste[0]=='R': (b, reste)=R(reste[1:])
    else: b=reste[0]
    return codage(a, , reste[1:]
  else: return a

Là il y a une grosse partie de l'algo. 

On a d'abord une vérification : est-on à la fin de l'arbre ? Si c'est la cas, ça veut dire que l'invocation courante de R à été lancée avec une liste vide comme paramètre 'liste', donc je fais un check :

if reste:

   (il reste des noeuds à explorer)

else: return a    <- à ce moment là 'a' contient le résultat du tout dernier 'codage' une fois que la liste est réduite à deux nombre, et ne contient plus du tout de 'R'

 

S'il reste des noeuds à explorer :

 

if reste[0]=='R': (b, reste)=R(reste[1:])

On fait la même chose que pour 'a' plus haut : si le fils de droite du noeud courant est un 'R', on relance la machine sur le reste de la liste. Note bien que dans cet appel de 'R' le paramètre reste[1:] va devenir la variable 'liste' de cet appel récursif. De nouveau il s'agit d'une assignation multiple : 

b=codage(a, b ) <- les variables a et b d'un autre appel à la fonction!

et reste=le reste[1:] de l'autre appel également! 

En gros (c'est pas facile à expliquer en fait, ça risque de ne pas être facile à comprendre) la liste est 'grignotée' à chaque appel de fonction jusqu'à ce que les variables a et b dans l'instance de R contiennent tous les deux des nombres, auquel cas on peut enfin appliquer la fonction codage dessus, et retourner le résultat : 

 

else: b=reste[0]return codage(a, , reste[1:]

A cet endroit du code, il n'y a plus de 'R' : à chaque fois qu'on on a rencontré un on a relancé la fonction R récursivement sur le sous-arbre, à gauche ou a droite. On est donc sûrs que a et b contiennent bien un nombre : soit parce qu'il s'agit d'un fils 'final', soit parce que les appels récursifs à R ont ramenés le sous-arbre correspondant à un seul nombre. On peut donc appliquer codage à nos deux nombres et retourner le résultat de l'opération à l'appel à R au dessus (on 'remonte' dans l'arbre avec le résultat du sous-arbre), accompagné à chaque fois du reste de la liste qui n'a pas encore été explorée.

print(R(schema))

Et voilà, l'arbre est plié, il ne reste plus qu'un seul nombre : le résultat final de la fonction (du tout premier appel à R, donc)

 

La récursivité c'est pas simple, et le sujet en lui même rajoute de la complexité avec cette histoire de fils de droite.

J'aurais probablement du temps ce soir si tu as des questions (et il risque d'y en avoir, je n'ai pas l'impression d'avoir été limpide dans les explications)

D'ici là, si tu as accès à un interpréteur python, en mettant des print partout tu peux facilement avoir un aperçu de comment l'algo fonctionne (en particulier comment il grignote la liste jusqu'à la fin)

Lien vers le commentaire
0100011

0100011

Posté
Posté

 Expérimentalement la récursivité se comprend de manière non linéaire. Je vois ça tous les ans : il y a les étudiants qui n'ont pas eu le déclic (rien en 1h30 de TD) et ceux qui l'ont eu (tous les exos terminés en 7 min). Le temps d'acquisition de cette manière de réfléchir est une variable personnelle. Je ne sais pas si l'enseignant peut faire grand chose à part donner 15 manières différentes d'aborder la résolution. 

 

  Personnellement je vois ça, et je le présente, comme de la démonstration par récurrence mais en généralisant aux types inductifs et à l'envers : dans la démonstration par récurrence on monte (on cherche à passer de n à n+1 alors qu'en programmation on descend en se demandant comment passer de n+1 à n-1). 

Lien vers le commentaire
Malky

Malky

Posté
Posté

Bon a va arrêter les blagues (encore que c'est assez édifiant de voir la différence de lisibilité de deux codes qui font exactement la même chose, mais un seul des deux est propre)

Schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
Suite = [1, 2, 3, 4, 5]

def codage(x, y): return (x+y+1)*(x+y+2)/2-x-1

def traiteNoeud(schema, suite):
    if schema.pop(0)=='R': filsGauche=traiteNoeud(schema, suite)
    else: filsGauche=suite.pop(0)
    if schema:	
        if schema.pop(0)=='R': filsDroit=traiteNoeud(schema, suite)
        else: filsDroit=suite.pop(0)
        return codage(filsGauche, filsDroit)
    else: return filsGauche

print(traiteNoeud(Schema, Suite))

>>> 257394.0

 

C'est nettement plus lisible, non ?  :icon_wink:

Lien vers le commentaire
Nirvana

Nirvana

Posté
Posté

Bon a va arrêter les blagues (encore que c'est assez édifiant de voir la différence de lisibilité de deux codes qui font exactement la même chose, mais un seul des deux est propre)

Schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
Suite = [1, 2, 3, 4, 5]

def codage(x, y): return (x+y+1)*(x+y+2)/2-x-1

def traiteNoeud(schema, suite):
    if schema.pop(0)=='R': filsGauche=traiteNoeud(schema, suite)
    else: filsGauche=suite.pop(0)
    if schema:	
        if schema.pop(0)=='R': filsDroit=traiteNoeud(schema, suite)
        else: filsDroit=suite.pop(0)
        return codage(filsGauche, filsDroit)
    else: return filsGauche

print(traiteNoeud(Schema, Suite))

>>> 257394.0

 

C'est nettement plus lisible, non ?  :icon_wink:

 

Carrément. Désolé de ne pas avoir réagi plus vite (fatigue, tout ça), je poserai éventuellement mes questions en fin d'après-midi.

Lien vers le commentaire
Noob

Noob

Posté
Posté

 Expérimentalement la récursivité se comprend de manière non linéaire. Je vois ça tous les ans : il y a les étudiants qui n'ont pas eu le déclic (rien en 1h30 de TD) et ceux qui l'ont eu (tous les exos terminés en 7 min). Le temps d'acquisition de cette manière de réfléchir est une variable personnelle. Je ne sais pas si l'enseignant peut faire grand chose à part donner 15 manières différentes d'aborder la résolution. 

 

  Personnellement je vois ça, et je le présente, comme de la démonstration par récurrence mais en généralisant aux types inductifs et à l'envers : dans la démonstration par récurrence on monte (on cherche à passer de n à n+1 alors qu'en programmation on descend en se demandant comment passer de n+1 à n-1). 

 

Même constat, et pour le coup même si quelqu'un parmi eux à compris, ça se diffuse pas chez les autres.

Parce que au mieux il utilisera les expressions du prof au pire les sienne et là ça peut-être bordel dans la tête à tout le monde.

Lien vers le commentaire
Noob

Noob

Posté
Posté

Y'a un truc a comprendre pour la récusivité ? (a part qu'il faut s'en méfier sur les plateformes qui ne font pas de Tail Call Optimisation).

 

Le concept à la limite pourquoi pas, mais l'appliquer à un problème spécifique n'est pas toujours évident.

Par exemple en découvrant les tours de Hanoï je me souviens d'avoir été un peu ébloui par la solution.

Lien vers le commentaire
Malky

Malky

Posté
Posté

C'est la condition d'arrêt : la première invocation de la fonction prend le tout premier noeud comme fils gauche, mais n'a pas de fils droit (vu qu'au départ il n'y a qu'un seul noeud), donc après avoir traité le fils gauche il faut vérifier s'il reste des données à traiter dans le schema. Quand il n'y en a plus c'est que tu as traité tout l'arbre et que filsGauche contient le résultat final demandé.

Lien vers le commentaire
Nirvana

Nirvana

Posté
Posté

C'est la condition d'arrêt : la première invocation de la fonction prend le tout premier noeud comme fils gauche, mais n'a pas de fils droit (vu qu'au départ il n'y a qu'un seul noeud), donc après avoir traité le fils gauche il faut vérifier s'il reste des données à traiter dans le schema. Quand il n'y en a plus c'est que tu as traité tout l'arbre et que filsGauche contient le résultat final demandé.

 

Merci. Avec quelques "print" bien placés, on comprend beaucoup mieux.

Lien vers le commentaire
Rincevent

Rincevent

Posté
Posté

Y'a un truc a comprendre pour la récusivité ? (a part qu'il faut s'en méfier sur les plateformes qui ne font pas de Tail Call Optimisation).

Pareil. La récursivité n'est pas un problème conceptuel, c'est plus souvent un problème de "putain je me suis planté sur la condition de remontée", mais ça c'est de l'essai-erreur, avec de la pratique ça devrait rentrer. Disons que c'est plusfacile à faire sur un dos d'enveloppe, mais qu'une fois codé il faut quand même tester avec soin. Comme pour tout code, en fait.
Lien vers le commentaire
0100011

0100011

Posté
Posté

Prolog c'est de la programmation logique. C'est déclaratif dans un certain sens comme la programmation fonctionnelle. L'idée est de décrire logiquement son problème sous forme de clauses de Horn et de lancer la résolution dessus pour trouver les valeurs qui satisfont le problème. C'est joli mais ça ne sert que pour les programmes qu'on ne sait pas programmer :)

Lien vers le commentaire
0100011

0100011

Posté
Posté

Ca peut avoir son intérêt quand on n'a pas d'idée précise d'algorithme pour résoudre un problème. Ca reste très expérimental d'un autre côté ça permet de développer des maquettes à vitesse record. 

Lien vers le commentaire
  • 3 weeks later...
  • 1 month later...
POE

POE

Posté
Posté

Je ne sais pas si c'est le fil adéquat : je me demande le temps qu'il faut pour apprendre à faire un programme simple (pas un jeu avec animation et musique) sous Androïd. J'aimerais bien programmer une petite application simple et voir si ça tourne. Qui connait le bouzin ?

Lien vers le commentaire
Noob

Noob

Posté
Posté

Je ne sais pas si c'est le fil adéquat : je me demande le temps qu'il faut pour apprendre à faire un programme simple (pas un jeu avec animation et musique) sous Androïd. J'aimerais bien programmer une petite application simple et voir si ça tourne. Qui connait le bouzin ?

 

Déjà fait et déjà encadré des petits jeunes qui voulaient apprendre.

Si tu veux tu peux me contacter par mp.

J'ai fait essentiellement des jeux avec eux, mais disons que c'est toujours le même principe.

Lien vers le commentaire
  • 2 months later...
L'affreux

L'affreux

Posté
Posté

Une critique de l'objet : Why should I have written ZeroMQ in C, not C++ (part I) puis part II. La deuxième partie est discutable mais je suis sensible à la critique des exceptions de la première partie. En PHP j'hésite souvent entre renvoyer FALSE ou lever une exception. Je trouve qu'une exception n'est pas toujours pratique pour signaler une erreur maitrisée. Par exemple lors d'un problème d'accès réseau, si on veut réessayer trois fois avant de s'avouer vaincu, un code à base d'exception est verbeux et moche. En revanche les exceptions sont idéales pour signaler un état anormal, c-à-d un bug interne ou externe au programme impliquant l'arrêt du traitement.

Lien vers le commentaire

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant
Aller sur la liste des sujets
×
×
  • Créer...