Challenge 2

[(gile)]

Un autre challenge,

 

Inclure une liste dans une autre à une position donnée.

 

Exemple : inclure '("d" "e" "f") dans '("a" "b" "c" "g" "h" "i") entre le"c" et le "g".

 

(inc-lst '("d" "e" "f") '("a" "b" "c" "g" "h" "i") 3)

ou

(inc-lst '("d" "e" "f") '("a" "b" "c" "g" "h" "i") "c")

 

doit retourner ("a" "b" "c" "d" "e" "f" "g" "h" "i")

 

Désolé, le coup est parti tout seul...

 

[Edité le 17/5/2007 par (gile)]

[Didier-AD]

Youpee

cette fois ci je suis le premier à répondre

 

Euh ! C'était quoi la question ?

[Patrick_35]

Salut

Le "c" est unique ?

 

ps: j'attend un peu et si c'est oui, je posterai une réponse demain

[Bred]

un truc basique pour (inc-lst '("d" "e" "f") '("a" "b" "c" "g" "h" "i") "c") :

 

(defun inc-lst (lst-R lst s / a b lst-F)
(setq a (reverse (member s (reverse lst)))
     b (cdr (member s lst))
     lst-F (append a (append lst-R b)))
lst-F
 )

 

le même que ci-dessus en le "compilant"

 

(defun inc-lst (lst-R lst s)
(append
 (reverse (member s (reverse lst)))
 (append lst-R (cdr (member s lst))))
 )

 

Ah ben tient, un truc qui fonctionne avec (inc-lst '("d" "e" "f") '("a" "b" "c" "g" "h" "i") "c") et (inc-lst '("d" "e" "f") '("a" "b" "c" "g" "h" "i") 3)

 

(defun inc-lst (lst-R lst s / s)
 (if (equal (type s) 'INT)
   (setq s (nth (1- s) lst))
   )
(append
 (reverse (member s (reverse lst)))
 (append lst-R (cdr (member s lst))))
 )

 

[Edité le 17/5/2007 par Bred]

[(gile)]

Le "c" est unique ?

 

Non, c'est un exemple pour donner la position, on peut prendre "g" ou 3 comme je disais.

 

Personnellement je préfère 3 qui donne une position précise même en cas de doublon dans la liste "d'accueil", mais je pense que c'est bien de laisser ouvert à plus de solutions.

 

super Bred :D

 

[Edité le 17/5/2007 par (gile)]

[Didier-AD]

Euh !

il parait que Reverse sur des listes longues çà prend du temps alors, sans Reverse juste pour le Fun

 
(defun inc-lst (LstR Lst s / pos genereserie)
 (defun genereserie ( debut fin  / l n)
   (setq l (list fin) n fin)
   (while (>= (setq n (1- n)) debut)
     (setq l (cons n l))
   )
   l
 )
 (if (/= 'INT (type s))
   (setq pos  (- (length Lst) (length (member s Lst))))
   (setq pos (1- s))
 )
 (append
   (mapcar '(lambda (n) (nth n Lst))  (genereserie 0 pos))
   LstR
   (mapcar '(lambda (n) (nth n Lst))  (genereserie (1+ pos) (1- (length Lst))))
 )
)

 

 

[(gile)]

l parait que Reverse sur des listes longues çà prend du temps

 

Il semblerait que ce soit plutôt append qui soit à éviter avec les listes longues, voir cette discussion.

[ElpanovEvgeniy]

Salut :)

 

(defun inc-lst (new old pos)
;; (inc-lst new old pos)
(cond ((not (equal (type pos) 'INT)) (inc-lst new old (1+ (vl-position pos old))))
      ((> pos 0) (cons (car old) (inc-lst new (cdr old) (1- pos))))
      (t (append new old))
) ;_  cond
) 

 

 

[(gile)]

Super Evgeniy :D

 

Je donne ma solution, elle ressemble à celle d'Evgeniy en utilisant 'repeat' au lieu d'une forme récursive.

 

(defun Inc-Lst1	(inc lst pos / temp)
 (or (= (type pos) 'INT)
     (setq pos (1+ (vl-position ele lst)))
 )
 (repeat pos
   (setq temp (cons (car lst) temp)
  lst  (cdr lst)
   )
 )
 (append (reverse temp) inc lst)
) 

 

D'après mes tests, c'est la solution de Bred la plus rapide, bravo ;)

[ElpanovEvgeniy]

:)

(defun inc-lst2 (new old pos)
(or (= (type pos) 'INT) (setq pos (1+ (vl-position pos old))))
(apply 'append
       (mapcar '(lambda (x)
                 (setq pos (1- pos))
                 (if (= -1 pos)
                  (append new (list x))
                  (list x)
                 ) ;_  if
                ) ;_  lambda
               old
       ) ;_  mapcar
) ;_  apply
) 

[Didier-AD]

 

Il semblerait que ce soit plutôt append qui soit à éviter avec les listes longues, voir cette discussion.

 

Je crois qu'il faut comparer ce qui est comparable

une liste c'est une suite d'éléments ; d'un point de vue informatique c'est ce qu'on appelle une liste chainée : chaque élément pointe sur son suivant.

 

Comment fonctionne CONS

CONS crée un élément et établit la relation entre cet élément son suivant c'est à dire la liste ; c'est donc très rapide admettons que celà prend une unité de temps

 

Comment fonctionne APPEND

APPEND doit commencer par trouver le dernier élément de la liste puis expliquer à cet élément qu'il a un suivant ; il est évident que celà prend plus de temps que CONS car pour trouver le dernier élément de la liste il faut "descendre" cette liste depuis son origine en admettant que descendre d'un élément à son suivant correspond à une unité de temps la durée d'un APPEND c'est donc N+1 unité de temps (avec N la longueur de la liste d'origine)

 

Donc pas de problème si on compare CONS et APPEND, c'est CONS qui gagne et plus la liste est longue plus c'est flagrant. mais le résultat n'est pas le même ; si on veut le même résultat il faut utiliser REVERSE deux fois

 

 

Comment fonctionne REVERSE

REVERSE commence d'abord par trouver la fin de la liste (N unité de temps) puis construit une liste à l'envers donc effectue N fois CONS, en quelque sorte on a donc une durée égale à 2N unité de temps (N pour descendre jusqu'au dernier et N fois CONS)

 

ainsi donc

 1-) (cons 11 '(1 2 3 4 5 6 7 8 9 10)) prend [b]1 unité [/b]de temps mais la liste est dans le désordre
2-) (append '(1 2 3 4 5 6 7 8 9 10) (list 11)) prendrait [b]11 unités [/b]de temps
3-) (reverse (cons 11 (reverse '(1 2 3 4 5 6 7 8 9 10))) prendrait 20+1+22 = [b]43 unités [/b] de temps

 

Alors, il faut faire comment

çà dépend de ce qu'on a à faire

- pour ajouter un élément à une liste dont l'ordre importe peu, il est évident qu'il faut utiliser CONS

- pour ajouter Un seul élément à la fin d'une liste il est préférable d'utiliser

 

 (append LaListe (list NouvelElement))

plutôt que

 (reverse (cons NouvelElement (reverse LaListe)))

 

- pour constituer une liste de N éléments (à partir d'un fichier par exemple) il vaut mieux utiliser une syntaxe du type

 
(repeat n
 (setq LaListe (cons ElementDependantDeN LaListe))
)
(setq LaListe (Reverse LaListe))

 

qui prendra 3N unités de temps

plutôt que

 
(repeat n
 (setq LaListe (append LaListe (list ElementDependantDeN)))
)

qui prendrait (N*(N+1))/ 2 unités de temps c'est à dire 1 + 2 + 3 + 4 +.....+N

 

Voilà, c'était ma contribution à la compréhension des listes

Bon WE à tous

 

 

 

 

 

[Edité le 18/5/2007 par Didier-AD]

[(gile)]

Merci Didier pour ce brillant exposé :)

[Patrick_35]

Moi qui voulait donner une solution, je m'incline devant ElpanovEvgeniy

 

Et merci à Didier pous son exposé

 

@+

 

[Edité le 18/5/2007 par Patrick_35]