AutoLisp trier une liste avec index

**DrNitro** · 14/02/2013, 21h27

Salut,
j'ai un petit probleme pour trier une liste de nombres rééls sous autolisp
je suis partit sur un truc simple " google"
http://www.developpez.net/forums/d98...ste-n-element/
mais apparement en autolisp y'a pas les fonction du common lisp ! qui simplifie la vie
je planche dessus depuis un peu plus d'une heure
je m'arrache les cheveux mais je n'y arrive pas depuis que je les ait coupés

Alors on va partir sur un truc tres bourrin

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
; la liste d'exemle
(setq L (list  5 6 4 2 1 3))
 
; - on cherche l'element min de L et on enregistre son indice dans ListIndex
; - on enleve l'élément min de L  => comment faire
; - et on refait en boucle
; plus facile a dire qu'a faire
(setq Min (apply 'min L))  ; d'appres <a href="http://forums.augi.com/showthread.php?7808-Autolisp-List-Problem" target="_blank">http://forums.augi.com/showthread.ph...p-List-Problem</a>

mais j'essai de modifier celui là aussi en paralle
http://www.programcreek.com/2010/10/...ent-in-a-list/

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(defun get-min ( m l )
 
  (cond ((null (car l)) m)
        ((< (car l) m) (get-min (car l) (cdr l)))
        (t (get-min m  (cdr l))))
)

comment recuperer l'indice de l'élément

**DrNitro** · 14/02/2013, 21h35

Ah! tiens!
http://autocad.wikia.com/wiki/Nth-re...oLISP_function)
ça c'est super

**DrNitro** · 14/02/2013, 22h42

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(setq Lsort (vl-sort L '<) )         
   (foreach n Lsort
    (progn
       (setq index 0)
       (repeat (length L)
         (progn
            (if (eq n (nth index L))
               (setq ListIndex (Append ListIndex (list index)))
               )
            (setq index (1+ index))
            )
         );repeat
      )
      );

fo

**Patrick_35** · 15/02/2013, 17h09

Salut

Et cette solution ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(mapcar '(lambda(x)(vl-position x l)) (vl-sort l '<))

@+

**jack-ft** · 18/02/2013, 10h52

Bonjour, je ne comprends pas pourquoi tu ne peux pas utiliser directement la fonction vl-sort telle qu'elle est décrite dans la référence: vl-sort ???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
(setq L (list  5 6 4 2 1 3))
 
(setq L (vl-sort L '<))

Attention! La doc n'indique pas si la fonction est destructive!
Il faut donc tester sur un exemple, puis, le cas échéant, appliquer la fonction à une copie de la liste d'origine.

Oops! Je crois avoir compris: tu veux retourner l'ordre dans lequel se trouve ta liste d'origine, c'est-à-dire la liste des positions qu'ont ses éléments dans la version triée de la liste, c'est ça?
et je plussoie la proposition de Patrick

**Patrick_35** · 18/02/2013, 13h43

La fonction vl-sort est très puissante et permet de trier de plusieurs manières
En ordre croissant en utilisant directement la fonction < ou l'inverse avec > pour des listes simples
Ou par exemple sur les listes à deux éléments.
Un exemple sur le 2em élément d'une liste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(setq l '(("toto" 3) ("titi" 2) ("yoyo" 4) ("keke" 1)))
(vl-sort l '(lambda(a b)(< (cadr a) (cadr b))))

Ou encore sur le 1er puis sur le second si les 1er éléments sont les mêmes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
(setq l '(("toto" 3) ("titi" 2) ("toto" 4) ("titi" 1)))
(vl-sort l '(lambda(a b)(if (eq (car a) (car b))
			  (< (cadr a) (cadr b))
			  (< (car a) (car b))
			)
	   )
)

Pour moi, le fonction n'est pas destructive dans le sens ou il faut affecter une variable pour récuperer le résultat.

@+

**jack-ft** · 18/02/2013, 14h53

Envoyé par Patrick_35

Pour moi, le fonction n'est pas destructive dans le sens ou il faut affecter une variable pour récuperer le résultat.

[chipotage]
Ben non, ça marche pas du tout, ton raisonnement!

Si la fonction est purement fonctionnelle, il faut effectivement récupérer le résultat pour pouvoir l'utiliser, soit en le passant comme argument à une autre fonction, soit en le stockant quelque part, par exemple dans la 'cell value' d'une variable, sinon il est perdu.

Mais si la fonction est destructive, elle va réaffecter les cdr des différents cons, mais ne va certainement pas changer le lien entre le symbole et la cell value qui pointait sur le premier cons de la liste.
En conséquence, si le car de la liste était déjà le minimum, il est possible que la variable pointe dorénavant vers la liste triée (car pointant toujours vers le même premier cons), mais ce n'est pas certain (c'est très implementation-dependant).
En revanche, si le car de la liste ne pointait pas vers le minimum, il est très peu probable que la variable pointe maintenant vers la liste triée (car les diverses implémentations de 'sort' que j'ai pu observer jusqu'à présent manipulent exclusivement les cdr et jamais les car des cons).

Dans certains lisps où la fonction 'sort' est destructive, voici ce que l'on peut généralement obtenir:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
(setq l1 '(3 4 1 2))
(setq l0 l1)
(eq l0 l1)
=> t
(setq l2 (sort '< l1)) # ou (sort l1 '<) ou (sort l1 #'<) (sort l1 (function '<) (sort l1 (lambda (a b) (< a b))) etc.
=> (1 2 3 4)
l1
=> (3 4)
(eq l1 (cddr l2))
=> t
(eq l0 l1)
=> t

car le cdr de (last l1) a été remplacé par (cddr l1), lequel l1 a été remplacé par nil.

Un test pour vérifier la destructivité de sort consiste donc à regarder le contenu de l1 après appel de sort.

Pour la petite histoire, j'ai remarqué que beaucoup de "débutants" (ce que je n'applique à personne ici!) ont tendance à "craindre" ce qu'on appelle "effet de bord" et se méfient donc de fonctions comme 'sort' 'setf' 'rplaca' rplacd' 'pop' (CL) ou 'nextl' (Le_Lisp). Cette crainte est souvent amplifiée par la confusion entre effet de bord sur un symbole et effet de bord sur un cons:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
(setq l1 '(a b c d)) # effet de bord sur le symbole l1
(setq l0 l1) # effet de bord sur le symbole l0
(pop l1) # effet de bord sur le symbole l1
=> a
l1
=> (b c d)
l0
=> (a b c d)

Dans cet exemple, il n'y a pas eu d'effet de bord sur le symbole l0, pas plus qu'il n'y a eu le moindre effet de bord sur aucun cons. Il y a juste eu l'équivalent de:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(prog1 (car l1) (setq l1 (cdr l1))) # effet de bord sur le symbole l1

À noter que 'pop' doit être une fonction "spéciale" (macro, fexpr ou fsubr). Elle ne peut pas être écrite comme une fonction "normale" (évaluant ses arguments de manière habituelle) car elle doit recevoir le symbole lui-même et non sa celle value, afin de pouvoir le réaffecter, contrairement à 'sort' 'rplaca' 'rplacd' qui sont des fonctions normales.
[/chipotage]

**DrNitro** · 19/02/2013, 01h16

Envoyé par Patrick_35

Salut

Et cette solution ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(mapcar '(lambda(x)(vl-position x l)) (vl-sort l '<))

@+

Merci Patrick_35 C'est exactement ça je ne connaissait pas la fonction vl-position , et puis comme je debute je n'ai pas le reflex mapcar ou apply
c'est bien de ne pas se prendre la tete a gerer les boucles el les incrementations!

**Patrick_35** · 20/02/2013, 11h50

@jack-ft
Merci de tes explications, même si je n'ai pas tout compris et pu tester (lisp sur Autocad)
Mais une chose me surprend, si une fonction est destructive car elle fait un peu ce qu'elle veut (si j'ai bien compris), ce n'est pas un BUG du langage ?

@+

**jack-ft** · 20/02/2013, 18h21

Envoyé par Patrick_35

@jack-ft
Merci de tes explications, même si je n'ai pas tout compris et pu tester (lisp sur Autocad)
Mais une chose me surprend, si une fonction est destructive car elle fait un peu ce qu'elle veut (si j'ai bien compris), ce n'est pas un BUG du langage ?

@+

Ah ben non! Pas du tout!...

Sauf si on se place dans une vision purement fonctionnelle!

En fait, on dit qu'une fonction est destructive lorsqu'elle modifie les données reçues en entrée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
(setq l1 (list 'a 'c))
=> (a c)
(setq l2 l1)
=> (a c)
(rplaca l1 'b)
;; ou
(setf (car l1) 'b)
=> (b c)
l2
=> (b c) ;; !!!

La fonction 'rplaca' a écrit le symbole 'b dans la case 'car' de ce que désignait l1, modifiant ainsi le contenu de l1. Cette fonction DOIT faire cela: c'est sa raison de vivre!
Cette fonction n'est pas fonctionnelle dans le sens (en gros) où l'évaluation de l2 ne rend plus la même chose après le passage de rplaca sur l1.
Les fonctions intrinsèquement destructives sont indispensables pour gérer une forme de persistance (comme dans la programmation objet).

Une fonction comme 'sort' peut être fonctionnelle ou non. Sa raison de vivre n'est pas de modifier ce qu'elle reçoit, mais de rendre un résultat trié.
Si une implémentation de 'sort' décide de rendre une copie triée de la liste qu'elle reçoit, alors elle est fonctionnelle et il faut le dire dans la doc.
Si une implémentation de 'sort' décide d'utiliser exactement les cellules de la liste qu'elle reçoit en les modifiant pour rendre une liste triée, alors elle est destructive et il faut le dire dans la doc.

La version avec copie est plus lente et sollicite le GC (garbage collector, ramasse-miettes ou glanage des cellules), mais elle est non-destructive.
La version avec des rplacd est plus rapide et ne sollicite pas le GC, mais elle est destructive.

Lorsque je programmais des outils de composition et d'exécution musicale en temps réel, on faisait la chasse à tout ce qui faisait de l'allocation (comme cons, list, append etc.) car, si cela venait à déclencher le GC, la musique s'arrêtait complètement pendant 2 secondes

**DrNitro** · 21/02/2013, 18h45

par un souci indescriptible je veut savoir - comme c'est mon premier message sur ce site - comment on marque resolue !

**Patrick_35** · 22/02/2013, 11h45

@jack-ft
Ah ok, merci beaucoup
C'est bien ce que j'avais compris pour la fonction destructive, qu'elle modifiait les données d'entrées, mais pas tout à fait dans le sens que tu m'as indiqué.
C'est plus clair maintenant

@+