Croissement de liste

[bigsyke]

Bonjour à toutes et a tous :)

 

Avant tout je voudrais remercier une fois de plus tout ceux qui font vivre ce forum, prenne sur leur temps pour se pencher sur nos petits problèmes et partage leur savoir.

 

Voici mon petit souci:

 

Je dispose de 2 listes (lstptx et lstpty) correspondant a des coordonnées de point

 

 

Commande: !lstptx

((X1 Y1 Z1) (X2 Y2 Z2) (Xn Yn Zn))

 

 

Commande: !lstpty

((X’1 Y’1 Z’1) (X’2 Y’2 Z’2) (X’n Y’n Z’n))

 

 

Le but est de créer une nouvelle liste qui donnerait cela :

 

Commande: !lstpt

((X1 Y’1 Z’1) (X1 Y’2 Z’2) (X1 Y’n Z’n)……(X2 Y’1 Z’1) (X2 Y’2 Z’2) (X2 Y’n Z’n)...)

 

 

 

Je pense bien a certaine piste mais elle me donne l’impression de tuer une mouche avec un marteau…

[(gile)]

Salut,

 

Vite fait, s'il ne s'agit que de combiner les X de la première liste avec les (Y Z) de la seconde :

 

(defun foo (l1 l2)
 (apply
   'append
   (mapcar
     '(lambda (p1)
 (mapcar '(lambda (p2) (cons (car p1) (cdr p2))) l2)
      )
     l1
   )
 )
)

 

S'il s'agit de combiner chacune des coordonnées (X Y Z) des points de la première liste avec tous les points de la seconde :

 

(defun bar (l1 l2)
 (apply
   'append
   (mapcar
     '(lambda (p1)
 (apply
   'append
   (mapcar
     '(lambda (p2)
	(mapcar '(lambda (x1 x2) (subst x1 x2 p2)) p1 p2)
      )
     l2
   )
 )
      )
     l1
   )
 )
)

[bigsyke]

Merci beaucoup Gile!

 

La solution en (foo l1 l2) est exactement ce que je cherchais :) :) :)

 

J'avoue que j'ai encore quelques lacunes dans la manipulation des listes...surtout avec mapcar et lambda (comme par hasard <img src='http://cadxp.com/public/style_emoticons/<#EMO_DIR#>/laugh.gif' class='bbc_emoticon' alt=':(rires forts):' /> )

J'étais personnellement partie sur quelque chose de plus lourd a coup de nth ou de foreach que je maitrise mieux.

 

Merci encore pour ton aide Gile ;)

[Patrick_35]

J'avoue que j'ai encore quelques lacunes dans la manipulation des listes...surtout avec mapcar et lambda

Salut

 

La fonction lambda définit une fonction anonyme

La fonction mapcar fonctionne comme une boucle foreach sauf que l'argument est une fonction et retourne le résultat

 

Par exemple, ajouter 1 aux chiffres de la liste '(2 3 4 5)

(mapcar '1+ '(2 3 4 5))

Peut aussi s'écrire

(mapcar '(lambda(x) (1+ x)) '(2 3 4 5))

 

@+

[(gile)]

J'avoue que j'ai encore quelques lacunes dans la manipulation des listes...surtout avec mapcar et lambda

 

L'intérêt de mapcar est que cette fonction retourne directement un liste, ce qui bien le but ici.

Mais on peut aussi utiliser foreach pour construire une nouvelle liste :

 

(defun foo (l1 l2 / lst)
 (foreach p1 l1
   (foreach p2	l2
     (setq lst (cons (cons (car p1) (cdr p2)) lst))
   )
 )
 (reverse lst)
)

[VDH-Bruno]

Bonsoir,

 

J'avoue que j'ai encore quelques lacunes dans la manipulation des listes...surtout avec mapcar et lambda

Pour compléter et détailler la réponse de Patrick_35, un lien =>

Les fonctions passées comme argument

 

Et toujours avec mapcar , une légère optimisation possible de la fonction foo proposé par (gile) dans le cas ou tu aurais de nombreux points à traiter.

 

(defun foo (l1 l2)
 (setq	l1 (mapcar 'car l1)
l2 (mapcar 'cdr l2)
 )
 (apply
   'append
   (mapcar
     '(lambda (x1)
 (mapcar '(lambda (yz2) (cons x1 yz2)) l2)
      )
     l1
   )
 )
)

 

A+

[Patrick_35]

Bonsoir,

 

 

Pour compléter et détailler la réponse de Patrick_35, un lien =>

Les fonctions passées comme argument

 

Et toujours avec mapcar , une légère optimisation possible de la fonction foo proposé par (gile) dans le cas ou tu aurais de nombreux points à traiter.

 

(defun foo (l1 l2)
 (setq	l1 (mapcar 'car l1)
l2 (mapcar 'cdr l2)
 )
 (apply
   'append
   (mapcar
     '(lambda (x1)
 (mapcar '(lambda (yz2) (cons x1 yz2)) l2)
      )
     l1
   )
 )
)

 

A+

Salut

 

je ne suis pas certain car tu ajoutes quand même deux boucles.

 

@+

[VDH-Bruno]

Salut,

je ne suis pas certain car tu ajoutes quand même deux boucles.

Même si la modif en ajoutant 2 boucles supplémentaires avec mapcar est plus un clin d'œil d'encouragement adressé bigsyke sur ce sujet.

 

Tu penses bien qu'avant de reprendre des lignes de codes derrière (gile), j'ai pesé mes mots en parlant de "légère optimisation" dans le cas de "nombreux points" ;) .

 

Donc si on veut tenter de quantifier le terme de nombreux points, pour positionner un curseur il faut avoir en tête la valeur d'accroissement de la liste final soit:

(longueur de la liste L1) x (longueur de la liste L2) = (longueur de la liste résultat)

 

Dans le premier code la fonction (car p1) est multiplié par le nombre d'élément présent dans L2 et la fonction (cdr p2) est multiplié par le nombre d'élément présent dans L1.

 

Dans la seconde version de foo, les car de L1 et les cdr de L2 sont mémorisé au début du code pour être réutilisé par la suite dans le corps de la fonction, les car et cdr sont traité au moyen de la fonction mapcar qui est effectivement une boucle que l'on pourrais éventuellement réécrire comme ceci :

(defun bv:mapcar (f l)
 (if l  (cons ((eval f) (car l)) (bv:mapcar f (cdr l)))))

Si on considère que les fonctions ont un coup sensiblement équivalent, pour mémoriser un car dans L1 ou un cdr dans L2, cela coute environ un if, cons, eval , car, bv:mapcar, cdr soit grosso modo 6 opérations.

 

En conclusion les expressions (mapcar 'car l1) et (mapcar 'cdr l2) doivent être gagnante dès que les listes L1 et L2 ont plus de 6 éléments, donc dans le cas où la liste résultante contient au moins 7x7 éléments, résultat qui se retrouve au Benchmark.

 

A+ Bruno

(Ps: l'optimisation reste très légère car elle est rapporté à l'ensemble de la fonctions foo et porte sur des fonctions lisp très peu couteuse que sont car et cdr..)

[Patrick_35]

(longueur de la liste L1) x (longueur de la liste L2) = (longueur de la liste résultat)

Oui

 

Dans le premier code la fonction (car p1) est multiplié par le nombre d'élément présent dans L2 et la fonction (cdr p2) est multiplié par le nombre d'élément présent dans L1.

Heu oui, mais pour moi (car p1) = L1 et (cdr p2) = L2 en nombre d'éléments. Je ne vois pas trop où tu veux en venir ?

 

Dans la seconde version de foo, les car de L1 et les cdr de L2 sont mémorisé au début du code pour être réutilisé par la suite dans le corps de la fonction

Oui, mais le gain entre les boucles au début pour ne conserver que le nécessaire et un car et cdr dans les mapcar reste à démontrer.

 

Si on considère que les fonctions ont un coup sensiblement équivalent, pour mémoriser un car dans L1 ou un cdr dans L2, cela coute environ un if, cons, eval , car, bv:mapcar, cdr soit grosso modo 6 opérations.

Je ne suis pas certain car tu fais une boucle pour ne retenir que le car de L1 et une autre pour le cdr de L2 alors que dans la première version, tu la fais directement dans la boucle.

Dans un sens comme dans l'autre, tu as besoin d'un car sur L1 et d'un cdr sur L2. Alors un gain avec les deux mapcar supplémentaires ?

 

@+

[VDH-Bruno]

Re,

 

Oui

 

Le premier oui me rassure, mais vraisemblablement pour le reste je me suis très mal exprimé, je revoie ma copie et tente une approche plus lispienne que littéral, en proposant une autre factorisation de l'expression car dans foo, factorisation plus juste et certainement plus parlante…

(defun foo1 (l1 l2)
 (apply
   'append
   (mapcar
     '(lambda (p1)
        (setq p1 (car p1))
        (mapcar '(lambda (p2) (cons p1 (cdr p2))) l2)
      )
     l1
   )
 )
)

Ecrit comme cela on voit mieux l'optimisation du (car p1) dans foo1 qui est appliqué à chaque élément de L1 et est valable pour tous les éléments de L2 qui suivent.

 

 

Maintenant pour factoriser le cdr, il faut le faire en amont de la boucle sur L1:

(defun foo2 (l1 l2)
 (setq l2 (mapcar 'cdr l2))
 (apply 'append
        (mapcar '(lambda (p1) (setq p1 (car p1)) (mapcar '(lambda (p2) (cons p1 p2)) l2)) l1)
 )
)

La fonction cdr est appliquée à tous les éléments de L2, et est valable pour tous les éléments de L1.

 

 

Alors que dans la fonction foo d'origine les fonctions car et cdr ne sont plus dépendants dans leurs appels aux nombres d'éléments présents dans les listes L1 et L2, leurs nombres d'appels est directement lié aux nombres d'élément contenue dans la liste résultat LR = L1 x L2.

 

Le nombre d'éléments contenus dans la liste résultat étant multiplicatif, il croit plus vite que le nombre d'appel contenu dans l'expression suivante qui est additif malgré le coût amené par mapcar:

(setq	l1 (mapcar 'car l1)
l2 (mapcar 'cdr l2)
 )

 

A+

(Ps: Pas sûr d'avoir été plus clair sur ce coup-là, tout cela restant très anecdotique)

[Patrick_35]

Si si, je n'avais pas compris la démarche. Je suis d'accord que cela reste anecdotique et que le gain est plus que négligeable, mais il est toujours intéressant de débattre sur ces sujets.

Donc pour résumer, tu "mémorises" les résultats afin d'éviter d'aller les chercher dans chaque boucle, ce qui peut faire un gain potentiel en fonction d'un nombre minimum d'éléments pour compenser les deux mapcar

 

Oki et merci

 

@+

[VDH-Bruno]

Donc pour résumer, tu "mémorises" les résultats afin d'éviter d'aller les chercher dans chaque boucle, ce qui peut faire un gain potentiel en fonction d'un nombre minimum d'éléments pour compenser les deux mapcar

Ouais, as te lire je m'aperçois que je me débrouille mieux en lisp qu'à l'écrit, si seulement j'avais formulé ma réponse comme la tienne, on aurait tous 2 gagné notre temps <_< .

Oui, ces débats sont toujours intéressant ;)

 

A+