Challenge 22

Patrick_35 · le 7 juillet 2008

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 · le 7 juillet 2008

Salut patrick_35!

Juste une petite question:

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

Patrick_35 · le 7 juillet 2008

Salut

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

@+

(gile) · le 7 juillet 2008

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 · le 7 juillet 2008

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

@+

(gile) · le 7 juillet 2008

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 · le 8 juillet 2008

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 · le 8 juillet 2008

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 · le 8 juillet 2008

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

Bred · le 8 juillet 2008

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 · le 8 juillet 2008

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) · le 8 juillet 2008

(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 · le 8 juillet 2008

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 · le 10 juillet 2008

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 · le 10 juillet 2008

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 · le 10 juillet 2008

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

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

Matt666 · le 10 juillet 2008

Aaaah J'avais pas vuuu !!!

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

Grmbl. Vivement le challenge 23 !! ;)

Bravo Bred ! :D

Patrick_35 · le 10 juillet 2008

Il n'est pas trop tard Matt ;)

Je donne mes lisps vers midi

@+

Patrick_35 · le 10 juillet 2008

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 · le 10 juillet 2008

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 · le 10 juillet 2008

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 · le 10 juillet 2008

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 · le 10 juillet 2008

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) · le 10 juillet 2008

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 10 juillet 2008

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)]

Connexion

Challenge 22

Messages recommandés

Patrick_35

bseb67

Patrick_35

(gile)

Patrick_35

(gile)

Bred

Patrick_35

Arcasdk

Bred

lili2006

(gile)

Patrick_35

Bred

Patrick_35

Bred

Matt666

Patrick_35

Patrick_35

walterkrunch

Patrick_35

Bred

Patrick_35

(gile)

(gile)

Créer un compte ou se connecter pour commenter

Créer un compte

Se connecter

Forums

Naviguer

Activité

Information importante