Challenge 22

[Patrick_35]

Bonjour

 

Je propose à petit challenge pour tous niveaux.

Ceux qui se considèrent comme débutant peuvent déjà proposer leurs solutions.

Ceux qui se considèrent comme d'un niveau intermédiaire pourront proposer leur solution à partir de mercredi.

Et pour les autres, à partir de jeudi.

 

Le but, serait à partir d'une liste, d'en extraire le début, la fin ou remplacer un élément d'une liste.

 

Un exemple

(setq lst  '((1 "a") (2 "b") (1 "a") (1 "a") (5 "e") (3 "c")))

(deb_pat lst 3) --> ((1 "a") (2 "b") (1 "a"))
(fin_pat lst 3) --> ((1 "a") (1 "a") (5 "e") (3 "c"))
(sub_pat lst '(9 "i") 3) --> ((1 "a") (2 "b") (1 "a") (9 "i") (5 "e") (3 "c"))

 

Un test du Benchmark sera fait sur toutes les propositions afin de déterminer le vainqueur pour la routine la plus rapide.

 

A vous neurones ;)

 

@+

[bseb67]

Salut patrick_35!

 

Juste une petite question:

pour la fonction sub, on doit utiliser deb et fin?

[Patrick_35]

Salut

 

Tu fais ce que tu veux, le but étant de trouver la routine la plus rapide.

 

@+

[(gile)]

Salut,

 

le but étant de trouver la routine la plus rapide

 

J'ai fait quelques essais de benchmark, suivant les routines les résultats peuvent être influencés par la longueur de la liste et la valeur de l'indice (placé vers le début ou la fin de la liste).

Doit-on prendre comme référence la liste que tu donnes, ou une liste plus longue ?

 

[Patrick_35]

Si tu as ou trois type de liste pour faire un test objectif, donne les.

 

@+

[(gile)]

Ta liste est très bien, avec ses doublons, pour mettre les routines au point et tester leurs fonctionnement.

 

Pour des benchmarks, on peut aussi l'utiliser comme liste courte.

Pour une liste plus longue 100 éléments, on peut faire :

(setq lst100 nil n 100) 
(repeat 100 (setq lst100 (cons (setq n (1- n)) lst100)))

et tester :

(deb lst100 5) (deb lst100 50) (deb lst100 95)

 

 

 

[Edité le 8/7/2008 par (gile)]

[Bred]

Salut Patrick et (gile),

(gile), dans ta construction de liste tu as taper trop vite : c'est lst1 et non lst.

 

Pour être sûr d'avoir bien compris l'énoncé, sommes nous d'accord pour le résultat ?

 

(deb_pat lst 5) -> (0 1 2 3 4)

(deb_pat lst 50) -> (0 1 2 3 4 5 ..... 47 48 49)

(deb_pat lst 95) -> (0 1 2 3 4 5 .... 91 92 93 94)

 

et pour les autres :

 

ex :

(fin_pat lst 3) -> (2 3 4 5 6 7 ..... 97 98 99)

 

(sub_pat lst "A" 3) -> (0 1 2 "A" 4 5 6 7 ..... 97 98 99)

[Patrick_35]

Tu as bien compris Bred

 

Apparemment, les débutants se bousculent pas :(

 

ps : j'ai nommé mes routines ..._pat afin de pouvoir les différencier avec les différents intervenants

pps : J'ai modifié GEF car la gestion de l'affichage ne me convenait pas.

 

@+

[Arcasdk]

Cela aurait été avec plaisir mais malheureusement j'ai pas mal de boulot ces temps ci. Je me rattraperais au challenge 23.

[Bred]

Apparemment, les débutants se bousculent pas

Moi, les codes que j'ai pondus ils sont à un niveau +/- débutant...

et j'avoue ne pas avoir d'idée pour les rendre plus "perfectionné"....

[lili2006]

Bonjour à toutes et tous,

 

pps : J'ai modifié GEF car la gestion de l'affichage ne me convenait pas.

 

Quel perfectionniste !

 

Apparemment, les débutants se bousculent pas

 

Désolé, mais même à ce stade, cela reste du chinois pour moi, plus aucun document de référence,...

 

Bref, faut vraiment s'y mettre !

[(gile)]

(gile), dans ta construction de liste tu as taper trop vite : c'est lst1 et non lst.

 

Bien vu Bred, c'était pour voir si tu suivais ;)

 

J'ai modifié le message avec lst100, on peut faire de la même manière lst10 ou lst1000.

Je rappelle toutefois que la liste de Patrick_35 se prête mieux à la mise au point des routines, une fois qu'elle retourne les bons résultat on peut faire de benchmarks avec des listes plus ou moins longues.

[Patrick_35]

Je me rattraperais au challenge 23

Les challenges pour débutants ne sont pas si fréquents.

 

Moi, les codes que j'ai pondus ils sont à un niveau +/- débutant...

A voir ton petit dernier, je t'aurais plutôt classé parmi ceux qui donneront leur solution jeudi.

 

Quel perfectionniste !

C'est souvent dans le détail que l'on fait la différence ;)

 

@+

[Bred]

Salut,

bon, on est jeudi, je poste mes codes, et ça tombe bien que je sois le premier parce qu'ils ne sont pas du tous élaborés... (et puis je suis allez un peu vite) :

 

; Début de liste jusqu'au n'ème élément de la liste
(defun deb_Bred (lst n / l)
 (repeat n
   (setq l (append l (list (nth 0 lst)))
  lst (cdr lst)))
 l
)

 

; Fin de liste partir du n'ème élément de la liste
(defun fin_Bred (lst n / l i)
 (repeat (- (setq i (length lst)) (1- n))
   (setq l (cons (nth  (setq i (1- i)) lst) l)
  n (1+ n)))
 l
)

 

; insert un élément après le n'ème élément de la liste
(defun sub_Bred (lst lst-I n)
 (append (deb_Bred lst n) (list lst-I) (fin_Bred lst (+ n 2)))
)

 

[Edité le 10/7/2008 par Bred]

[Patrick_35]

Salut Bred

 

Bravo pour les lisps.

 

Juste une remarque

(append (deb_pat lst n) (list lst-I) (fin_pat lst (+ n 2)))

En

(append (deb_Bred lst n) (list lst-I) (fin_Bred lst (+ n 2)))

serait plus approprié ;)

 

@+

[Bred]

merci, en effet, ENCORE une étourderie.... :mad2:

décidément, faut que je sois plus attentif en ce moment....

[Matt666]

Aaaah J'avais pas vuuu !!!

:o :( :( :mad: :mad: :mad:

 

Grmbl. Vivement le challenge 23 !! ;)

 

Bravo Bred ! :D

[Patrick_35]

Il n'est pas trop tard Matt ;)

Je donne mes lisps vers midi

 

@+

[Patrick_35]

Comme promis, voici ma contribution

 

(defun deb_pat1(lst n)
 (vl-remove-if '(lambda(x) (< (setq n (1- n)) 0)) lst)
)

 

(defun deb_pat2(lst n / i res)
 (setq i -1)
 (repeat n
   (setq res (cons (nth (setq i (1+ i)) lst) res))
 )
 (reverse res)
)

 

(defun fin_pat1(lst n)
 (vl-remove-if '(lambda(x) (> (setq n (1- n)) 0)) lst)
)

 

(defun fin_pat2(lst n / i res)
 (setq i -1
lst (reverse lst)
 )
 (repeat (1+ (- (length lst) n))
   (setq res (cons (nth (setq i (1+ i)) lst) res))
 )
)

 

(defun sub_pat1(lst rpl n)
 (setq n (1+ n))
 (mapcar '(lambda(x) (if (zerop (setq n (1- n))) rpl x)) lst)
)

 

(defun sub_pat2(lst rpl n)
 (append (deb_pat2 lst n) (list rpl) (fin_pat2 lst (+ n 2)))
)

 

J'attends ce soir pour afficher les tests avec le benchmark

 

@+

[walterkrunch]

Une solution un peu bê-bête, simple et simplette.. qui ne marche que sur les listes sans doublons :

 

 
(setq deb (vl-remove-if-not '(lambda(x) (<=(vl-position x lst) index )) lst))
(setq fin (vl-remove-if-not '(lambda(x) (>(vl-position x lst) index )) lst))

 

Ok elle n'a qu'1 mérite, celui d'être brève..

[Patrick_35]

Merci walterkrunch.

C'est toujours interessant à savoir :)

Et si tu as une liste sans doublon, regarde la fonction member.

 

 

 

 

 

Le test du Benchmark

 

Une première liste

(setq lst1 '((1 "a") (2 "b") (1 "a") (1 "a") (5 "e") (3 "c")))

 

Une seconde

(setq n 100)
(repeat n (setq lst2 (cons (setq n (1- n)) lst2)))

 

(benchmark (list '(deb_bred lst1 3) '(deb_pat1 lst1 3) '(deb_pat2 lst1 3)))

Elapsed milliseconds / relative speed for 16384 iteration(s):

 

(DEB_PAT2 LST1 3).....1156 / 2.57 <fastest>

(DEB_BRED LST1 3).....1203 / 2.47

(DEB_PAT1 LST1 3).....2969 / 1 <slowest>

(benchmark (list '(fin_bred lst1 3) '(fin_pat1 lst1 3) '(fin_pat2 lst1 3)))

Elapsed milliseconds / relative speed for 16384 iteration(s):

 

(FIN_BRED LST1 3).....1172 / 2.48 <fastest>

(FIN_PAT2 LST1 3).....1172 / 2.48

(FIN_PAT1 LST1 3).....2907 / 1 <slowest>

(benchmark (list '(sub_bred lst1 '(9 "i") 3) '(sub_pat1 lst1 '(9 "i") 3) '(sub_pat2 lst1 '(9 "i") 3)))

Elapsed milliseconds / relative speed for 16384 iteration(s):

 

(SUB_PAT2 LST1 (QUOTE (9 "i")) 3).....1375 / 1.1 <fastest>

(SUB_BRED LST1 (QUOTE (9 "i")) 3).....1406 / 1.08

(SUB_PAT1 LST1 (QUOTE (9 "i")) 3).....1516 / 1 <slowest>

 

(benchmark (list '(deb_bred lst2 40) '(deb_pat1 lst2 40) '(deb_pat2 lst2 40)))

Elapsed milliseconds / relative speed for 8192 iteration(s):

 

(DEB_PAT2 LST2 40).....1110 / 3.38 <fastest>

(DEB_PAT1 LST2 40).....2547 / 1.47

(DEB_BRED LST2 40).....3750 / 1 <slowest>

(benchmark (list '(fin_bred lst2 40) '(fin_pat1 lst2 40) '(fin_pat2 lst2 40)))

Elapsed milliseconds / relative speed for 4096 iteration(s):

 

(FIN_PAT1 LST2 40).....1281 / 1.6 <fastest>

(FIN_PAT2 LST2 40).....2032 / 1.01

(FIN_BRED LST2 40).....2047 / 1 <slowest>

(benchmark (list '(sub_bred lst2 "az" 40) '(sub_pat1 lst2 "az" 40) '(sub_pat2 lst2 "az" 40)))

Elapsed milliseconds / relative speed for 4096 iteration(s):

 

(SUB_PAT1 LST2 "az" 40).....1078 / 4.06 <fastest>

(SUB_PAT2 LST2 "az" 40).....2719 / 1.61

(SUB_BRED LST2 "az" 40).....4375 / 1 <slowest>

 

En attendant la suite :)

 

@+

[Bred]

Ben tiens, c'est marrant...

Je m'étais refusé d'utiliser "reverse" car je pensais que cette fonction pouvais être "lente", et au vu de ton Deb_Pat2, ça dépote sec !!!!.. :o

[Patrick_35]

Il y avait une une discutions au sujet de cons, append et reverse et ce qui en ressortait est qu'il valait mieux faire plusieurs cons et à la fin un reverse que plusieurs append

Une histoire d'empilement de la liste. Un cons ajoute alors qu'un append refait la liste si ma mémoire est bonne

 

@+

[(gile)]

Salut,

 

Je n'ai pas pu répondre plus tôt,

 

Voilà ce que j'avais fait (d'abord des fonctioncs récursives (c'est ce qui me vient souvent en premier à l'esprit, puis des formes itératives pour essayer d'être plus rapide.

 

(defun deb_gile1 (lst ind)
 (if (    (cons (car lst) (deb_gile1 (cdr lst) (1- ind)))
 )
)

(defun deb_gile2 (lst ind / ret)
 (while (    (setq ret (cons (car lst) ret)
  ind (1- ind)
  lst (cdr lst)
   )
 )
 (reverse ret)
) 

 

(defun fin_gile1	(lst ind)
 (if (    (fin_gile1 (cdr lst) (1- ind))
   lst
 )
)

(defun fin_gile2 (lst ind)
 (while (    (setq ind (1- ind)
  lst (cdr lst)
   )
 )
) 

 

(defun sub_gile1	(lst ele ind)
 (if (zerop ind) ; (or (zerop ind) (null lst))
   (cons ele (cdr lst))
   (cons (car lst) (sub_gile1 (cdr lst) ele (1- ind)))
 )
)

(defun sub_gile2 (lst ele ind / ret)
 (while (    (setq ret (cons (car lst) ret)
  ind (1- ind)
  lst (cdr lst)
   )
 )
 (append (reverse ret) (cons ele (cdr lst)))
) 

[(gile)]

Le même benchmark en ajoutant mes contributions:

 

_$ (benchmark (list '(deb_bred lst1 3) '(deb_pat1 lst1 3) '(deb_pat2 lst1 3) '(deb_gile1 lst1 3) '(deb_gile2 lst1 3)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

 

(DEB_GILE1 LST1 3).....1078 / 2.51

(DEB_GILE2 LST1 3).....1078 / 2.51

(DEB_PAT2 LST1 3)......1172 / 2.31

(DEB_BRED LST1 3)......1250 / 2.16

(DEB_PAT1 LST1 3)......2703 / 1.00

 

_$ (benchmark (list '(fin_bred lst1 3) '(fin_pat1 lst1 3) '(fin_pat2 lst1 3) '(fin_gile1 lst1 3) '(fin_gile2 lst1 3)))

Benchmarking ...................Elapsed milliseconds / relative speed for 65536 iteration(s):

 

(FIN_GILE1 LST1 3).....2000 / 2.68

(FIN_GILE2 LST1 3).....2000 / 2.68

(FIN_PAT2 LST1 3)......2547 / 2.10

(FIN_BRED LST1 3)......2578 / 2.08

(FIN_PAT1 LST1 3)......5360 / 1.00

 

_$ (benchmark (list '(sub_bred lst1 '(9 "i") 3) '(sub_pat1 lst1 '(9 "i") 3) '(sub_pat2 lst1 '(9 "i") 3) '(sub_gile1 lst1 '(9 "i") 3) '(sub_gile2 lst1 '(9 "i") 3)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

 

(SUB_GILE1 LST1 (QUOTE (9 "i")) 3).....1172 / 1.41

(SUB_GILE2 LST1 (QUOTE (9 "i")) 3).....1234 / 1.34

(SUB_PAT1 LST1 (QUOTE (9 "i")) 3)......1328 / 1.25

(SUB_PAT2 LST1 (QUOTE (9 "i")) 3)......1594 / 1.04

(SUB_BRED LST1 (QUOTE (9 "i")) 3)......1657 / 1.00

 

_$ (benchmark (list '(deb_bred lst2 40) '(deb_pat1 lst2 40) '(deb_pat2 lst2 40) '(deb_gile1 lst2 40) '(deb_gile2 lst2 40)))

Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

 

(DEB_GILE2 LST2 40).....1281 / 2.06

(DEB_GILE1 LST2 40).....1360 / 1.94

(DEB_PAT2 LST2 40)......1562 / 1.69

(DEB_PAT1 LST2 40)......2235 / 1.18

(DEB_BRED LST2 40)......2640 / 1.00

 

_$ (benchmark (list '(fin_bred lst2 40) '(fin_pat1 lst2 40) '(fin_pat2 lst2 40) '(fin_gile1 lst2 40) '(fin_gile2 lst2 40)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

 

(FIN_GILE2 LST2 40).....1875 / 2.94

(FIN_GILE1 LST2 40).....2203 / 2.50

(FIN_PAT1 LST2 40)......4469 / 1.23

(FIN_PAT2 LST2 40)......4578 / 1.20

(FIN_BRED LST2 40)......5515 / 1.00

 

_$ (benchmark (list '(sub_bred lst2 "az" 40) '(sub_pat1 lst2 "az" 40) '(sub_pat2 lst2 "az" 40) '(sub_gile1 lst2 "az" 40) '(sub_gile2 lst2 "az" 40)))

Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

 

(SUB_GILE1 LST2 "az" 40).....1391 / 3.65

(SUB_GILE2 LST2 "az" 40).....1422 / 3.57

(SUB_PAT1 LST2 "az" 40)......1671 / 3.04

(SUB_PAT2 LST2 "az" 40)......3516 / 1.44

(SUB_BRED LST2 "az" 40)......5079 / 1.00

 

[Edité le 10/7/2008 par (gile)]