Avis sur l'intérêt de LISP sur projet

**Nothus** · 01/02/2019, 10h58

Bonjour à tous,

Je vous soumets un problème d’opportunité : dans un cadre (semi) professionnel, je m’intéresse à un service d’authentification (qui est une partie d’un projet). Je pense que LISP serait un bon candidat pour l’écrire (en passant par SBCL).

Voici mes réflexions / la situation :
- LISP est éprouvé, « efficace » (en fonction du sens que l’on met derrière) et permet une compilation vers les principaux OS. Sa philosophie technique semble la plus « souple ».
- Dans mon cas, il serait un processus lancé comme enfant d’un autre (le principal – supervisant les autres – étant en Python). Mon processus programmé en LISP aurait un seul canal pour les commandes et un pour les résultat. Pour le processus parent, chaque requête d’identification dispose d’un numéro (aléatoire ou incrémentiel, peu importe : il doit être unique à un processus LISP à un moment donné). Ce numéro est retourné par LISP avec la réponse (identifiant trouvé / pas trouvé et éventuellement des droits associés ou un ).
- LISP se baserait sur un fichier à parcourir avec la liste des identifiants + mot de passé hashé + sel (et éventuellement des règles supplémentaires, en faisant des copies de sauvegarde régulières). Il garderait en RAM les correspondances par fréquence (par exemple, les nième derniers identifiants trouvés). Cette liste serait lue en priorité puis, si l’identifiant n’est pas trouvée, au sein du fichier d’identifiants source. L’intérêt étant de favoriser les accès les plus fréquents.
- Idéalement la configuration de ce « service » (tous les processus entre eux) évolue « à chaud » : ne pas à avoir à redémarrer les processus et prendre en compte des modifications dans le fonctionnement même du service d’identification ou d’optimisations diverses. J’ai cru comprendre que LISP était adapté à ce genre de problématique ?
- Mon programme LISP doit pouvoir gérer des règles parallèles à l’identification (par exemple une plage horaire d’autorisation ou d’interdiction de connexion).
- Mon fichier source d’identifiants fait une taille limite (une centaine de Mo a priori, comprenant toutes les règles associées à chaque compte). Davantage d’identifiants à stocker, provoquent le démarrage d’un nouveau processus LISP avec un fichier source d’identifiants supplémentaires. Les processus ne seront pas nécessairement sur la même machine.
- Le processus principal envoie les commandes d’ajout, de modification ou de suppression de comptes, modifie les règles, peut ajouter un « format » de règles. Pour l’identification, il envoie à tous les processus enfants LISP actifs, la même requête (et attend une réponse positive ou négative des processus enfants, pour décider si le couple identifiant et mot de passe hashé a été trouvé au moins une fois).

Vos avis et retours sur l’intérêt de LISP dans un tel cahier des charges me seraient très utiles.

Bonne journée à tous,

Julien.

**byjav** · 02/02/2019, 19h12

Bonjour !

Au niveau de la cryptographie, on a Ironclad : http://quickdocs.org/ironclad/ Si ça suffit, je suppose que le reste ne doit pas présenter de problèmes insurmontables. Lisp est en effet très approprié aux modifications « à chaud »; en plus, avec un serveur Swank en marche, il est très pratique de controller le processus en ligne. Peut-être qu’au cours de temps, Lisp même absorbera d’autres components du système. Ça doit être vraiment amusant, je suis jaloux.

**Nothus** · 04/02/2019, 22h13

Merci Byjav (et désolé pour le délai de retour).

Bon je suis heureux de voir que mon choix n'était pas tout à fait n'importe quoi

Je teste les outils que tu évoques. Merci pour les renseignements : je débute en LISP - je dois dire que c'est assez déroutant de "tout" faire sous la forme de listes (venant de Python, c'est même une révolution copernicienne). Mais une fois le plis pris, c'est finalement assez agréable à écrire et cela me semble très puissant pour <edit>conceptualiser et écrire</edit> certains traitements (par contre je partage pas ton enthousiasme de tout passer sous LISP, notamment la partie requêtage réseau).

J'ai noté que les fonctions d'union sur les listes étaient natives ; cf :
http://dept-info.labri.fr/~idurand/e...k/node122.html

Tu me confirmes que leur utilisation pose (pas trop) de difficultés sur un très grand nombre de listes ? Je t'avoue que c'est le point de performance qui m'intéresse, avec la possibilité d'avoir un bon langage pour des modifications à chaud.

Une dernière question (promis je te laisse en paix après) : j'ai noté que les typecases sont des macros (utilisés pour le paramètre de reste dans l'appel d'une fonction d'après mes découvertes). Quel en en est l'usage ? La documentation anglaise n'est pas très claire : "These macros allow the conditional execution of a body of forms in a clause that is selected by matching the test-key on the basis of its type." Cf :
http://aiweb.cs.washington.edu/resea...r/typecase.htm

En somme c'est un switch-case sur des clés... ?

Merci et bonne soirée !

**byjav** · 05/02/2019, 05h25

Je teste les outils que tu évoques. Merci pour les renseignements : je débute en LISP - je dois dire que c'est assez déroutant de "tout" faire sous la forme de listes (venant de Python, c'est même une révolution copernicienne). Mais une fois le plis pris, c'est finalement assez agréable à écrire et cela me semble très puissant pour <edit>conceptualiser et écrire</edit> certains traitements (par contre je partage pas ton enthousiasme de tout passer sous LISP, notamment la partie requêtage réseau).

Eh bien, les listes ne sont pas la seule option. On a tout un arsenal de types de données, y compris, naturellements, les tableaux (même multidimensionnels) et les tableaux associatifs (dits tables de hachage). Par exemple, je suppose que dans ton cas, on pourrait organiser le cache sous la forme d’un table de hachage. On peut toujours commencer avec les listes et ensuite, optimiser quelque chose en remplaçant les listes par un autre type de données. C’est facile si l’on utilise un API spécifique pour les données (c’est-à-dire, si l’on introduit l’abstraction des données).

Les listes sont très flexibles comme représentation de l’information. (Par exemple, on peut même programmer en utilisant seulement les listes.

) On peut avoir, par exemple, une variable globale comme

Code :

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

1
2
3
(defvar *utilisateurs* '((:id 1 :nom "François" :couleurs (:prefere :rouge
                                                           :yeux :bleu))
                         (:id 2 :nom "Marie" :enfants ("André" "Jean"))))

C’est facile à écrire, à lire, à manipuler. C’est la façon préférée de personnaliser Emacs.

Mais ça peut être pas trop efficace, surtout si la liste est longue. Alors, on peut la transformer avant d’utiliser. Par exemple, la façon naïve de trouver les informations correspondant à un ID donné, c’est

Code :

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

(find id *utilisateurs* :key (lambda (u) (getf u :id)))

Si cela est inefficace, j’écrie une fonction comme ça :

Code :

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

1
2
3
(defun id-finder (users)
  (lambda (id)
    (find id users :key (lambda (u) (getf u :id)))))

je « compile » ma liste

Code :

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

1
2
(defvar *id-finder*)
(setf *id-finder* (id-finder *utilisateurs*))

et maintenant,

Code :

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

(funcall *id-finder* 1)

doit être beaucoup plus efficace, parce que la liste n’est plus là. La liste s’est transformée dans le code machine de la fonction *id-finder*. Les fermetures sont encore une forme de représentation de l’information.

Voici une réalisation plus efficace de id-finder:

Code :

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

1
2
3
4
5
6
(defun id-finder (users)
  (let ((ht (make-hash-table)))
    (dolist (u users)
      (setf (gethash (getf u :id) ht) u))
    (lambda (id)
      (values (gethash id ht)))))

En « compilant » la liste, je la transforme d’abord en un table de hachage (ça se fait une fois seulement).

Donc, on peut écrire aisément un prototype et le perfectionner ensuite. Mais je dois noter que SBCL est très efficace en soi.

J'ai noté que les fonctions d'union sur les listes étaient natives ; cf :
http://dept-info.labri.fr/~idurand/e...k/node122.html

Il s’agit ici de l’union comme ensembles : (union '(1 2 3) '(2 3 4)) => (1 2 3 4). On a toute sorte d’opérations sur les listes. En effet, elles peuvent ètre relativement (!) inefficaces parce qu’elles ne modifient ses arguments. Par exemple, la seule façon d’ajouter la liste (1 2 3) à (2 3 4) sans rien modifier, c’est de faire une copie de (1 2 3). Pour cette raison, la fonction append copie ses arguments sauf le dernier. Donc, voilà une boucle inefficace:

Code :

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

1
2
3
(let ((list '()))
  (dotimes (i 1000000 list)
    (setf list (append list (list i)))))

parce qu’ici, tous les résultats intermédiaires deviennet miettes (quadratiques !). La liste, c’est tout simplement une suite de paires, et pour raisons d’efficacité, on doit travailler avec sa tête. C’est mieux :

Code :

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

1
2
3
(let ((list '()))
  (dotimes (i 1000000 (nreverse list))
    (push i list)))

Ou encore de la magie:

Code :

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

(loop for i below 1000000 collect i)

(personne ne sait qu’est-ce qui se passe, mais c’est super efficace).

Il y a aussi des fonctions « destructives » qui ont le droit de modifier ses arguments. Ses noms comportent la lettre N, comme nreverse. C’est vraiment dangereux. Par exemple:

Code :

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

1
2
3
4
5
(let ((a (list 1 2 3)))
  (let ((b (cons 0 a)))
    (setf (second a) -1)
    b))
(0 1 -1 3)

On a modifié la valeur de a, et on voit que la valeur de b est changé aussi. C’est parce que les listes partagent de la structure : nous avons obtenu la deuxième en ajoutant une paire à la première, donc les trois paires qui composent la première sont communes.

En plus, il est interdit de modifier des objets literals tels que les listes précédées de ' dans le texte du programme.

Donc, en théorie, les operations avec les listes peuvent être moins efficaces et produire des miettes. Mais je dois noter encore une fois que SBCL est très efficace en soi. Peut-être, le très grand nombre est encore acceptable.

En somme c'est un switch-case sur des clés... ?

C’est un switch-case sur les types. En voici un exemple très bête :

Code :

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

1
2
3
4
5
(defun foo (x)
  (typecase x
    (number (1+ x))
    (string (concatenate 'string x " !"))
    (t 'bar)))

En action :

Code :

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

1
2
3
4
5
6
CL-USER> (foo 3)
4
CL-USER> (foo "Salut")
"Salut !"
CL-USER> (foo (make-array 3 :initial-contents '(3 4 5)))
BAR

Je ne dis pas que c’est la meilleure façon d’écrire des fonctions polymorphes. Par exemple, CL possède une POO très avancée, ou bien... Ce n’était qu’un exemple. Bien sûr, on a le switch ordinaire aussi, il s’appelle case (avec les variants ecase et ccase ― ecase et etypecase signalent un erreur simple s’il n’a pas eu de bon candidat, alors que ccase et ctypecase signalent un erreur corrigible).

(promis je te laisse en paix après)

Va, ce n’est pas le forum le plus actif.

On pourrait discuter ou faire des révisions du code. Lisp est puissant et bien pensée, il y en a toute sorte d’outils de la métaprogrammation jusqu’aux chiffres romains, mais il n’est pas tout à fait sympatique pour les débutants.

À propos, je ne sais pas quel est ton setup, mais moi, je recommande Portacle https://portacle.github.io/ comme base. Il y a ceux qui ne savent pas qu’en Lisp, le développement est interactif. Ben, il est interactif et c’est important. Dans le future, le processus lancé par Python va charger et lancer le serveur swank et tu vas exécuter M-x slime-connect pour obtenir le même milieu interactif.

**Nothus** · 08/02/2019, 13h57

Merci pour l'ensemble de tes réponses ! J'ai commencé à ébauche la logique générale. Je mets la conversation en résolue... mais je pense que j'aurais probablement l'occasion de reposter ici même dans un prochain fil !

Encore une fois : merci !

**Nothus** · 17/02/2019, 10h59

Bonjour Byjav,

J'espère que tu vas bien. Je me permets de reposter ici compte tenu que c'est en lien avec tes premières réponses... de nouvelles questions sont apparues :
- tu parles de la compilation pour *id-finder* en utilisant l'imbrication de la liste et de la fonction dans une fonction tierce. D'où ma question : la bonne "pratique" est-elle de développer sans tenir compte des optimisations, à trouver après, ou finalement le code "optimisé" et "non-optimisé" sera t-il trop différent (et nécessite une réécriture complète) ?
- j'essaie d'éviter les miettes. Y-a-t-il là aussi, une bonne manière de faire pour les détecter (ou c'est d'expérience) ?

Je continue à m'entraîner. Voici la boucle pour chercher si un nombre est dans une liste ou non. S'il l'est, on ne fait rien. Sinon on l'ajoute. Au bout d'au moins 17 opérations d'ajout, si la taille de la liste dépasse une valeur, la liste est redécoupée (semblable à un FIFO).
Voici deux autres questions :
- je ne trouve pas de documentation sur le fonctionnement interne de certaines macro ou fonctions, leur intérêts / limites. Par exemple subseq est-elle une bonne idée ? J'utilise time pour tester les combinaisons, mais ça reste très sommaire (et long). Connais-tu une ressource à me conseiller sur ce sujet ?
- la fonction que je te présente serait placée dans une macro. Tu indiques dans ta réponse à un moment que tu "compiles ta liste" (en fait si j'ai bien compris, tu lis la compilation d'une fonction à une variable en particulier). Comment se déroule le processus en interne ? Ne faut-il pas avoir une étape avec typecase pour vérifier que cette liaison liste / fonction lors de la compilation, utilise à un moment donné une variable du bon type ?

L'étendue actuelle de la fonction, sur mon poste je tourne à 1,3 secondes avec la fonction génératrice aléatoire et 0.04 secondes sans (quel écart !!!) :

Code lisp :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/sbcl --script 
 
(defparameter test1 '()) 
 
(defparameter *taille-tampon* 100) 
 
(defvar etatRand (make-random-state t)) 
 
(time (dotimes 
	(n 1000000) ; incrémentation 
	(let 
		( 
			(y (random 1000 etatRand)) ; y est alératoire (à trouver) 
		) 
		(if 
			(not (find ; si pas trouvé... 
				y 
				test1 
			)) 
			(progn 
				(push y test1) ; ... j'ajoute à la liste 
				(if ; ... si la liste est trop importante et qu'il y a eu au moins 17 opérations depuis 
					(and 
						(= (mod n 17) 0) 
						(> (length test1) *taille-tampon*) 
					) 
					(setq test1 (subseq test1 0 *taille-tampon*)) ; je découpe la liste à la bonne taille 
				)
			) 
		) ; si y a été trouvé, on ne fait rien 
	)
)) 
 
; (print test1)

Enfin (pardon pour la longueur), il semble que la compilation de LISP produise un code machine différent du C et que l'intégration avec ctypes de Python (ou un appel quelconque par des outils habituels) n'est pas directement possible. Qu'en est-il ?

(Sinon c'est chouette LISP !)

Bonne journée,

Julien.

**Nothus** · 17/02/2019, 11h45

Un post pour la fonction que j'ai indiqué plus haut, en version macro (incrémentation par 1 d'une variable pour compter le nombre d'items trouvés au fil de l'exécution). Je gagne "seulement" 0,2 secondes vis-à-vis de la version non-compilée:

Code lisp :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/sbcl --script 
 
(defparameter test1 '()) 
 
(defparameter *taille-tampon* 100) 
(defparameter *ecart-tampon* 17) ; nbre premier 
 
(defvar etatRand (make-random-state t)) 
 
(defmacro 
	chercher (item liste num-op) 
	`(if 
		(not (find 
			,item  
			,liste  
		)) 
		(progn 
			(push ,item ,liste) 
			(if 
				(and 
					(= (mod ,num-op *ecart-tampon*) 0) 
					(> (length ,liste) *taille-tampon*) 
				) 
				(setq ,liste (subseq ,liste 0 *taille-tampon*)) 
			) 
			nil 
		) 
		t 
	) 
) 
 
(defparameter r 0)
 
(time (dotimes 
	(n 1000000) 
	(let 
		( 
			(y (random 1000 etatRand)) 
		) 
		(if 
			(chercher y test1 n)
			(incf r); (format t "~%trouvé y = ~s" y) 
		) 
	)
)) 
 
(format t "~%trouvé nbre = ~s~%" r) 
; (print test1)

Un constat très contre-intuitif : plus je diminue la taille de la liste "tampon" (où l'on cherche une valeur), plus la durée d'exécution est courte (on perd près d'une seconde d'exécution) alors que pourtant, cela déclenche justement les opérations d'ajout à la liste et d'une taille éventuelle si la liste est trop longue... ?

**byjav** · 17/02/2019, 16h45

la bonne "pratique" est-elle de développer sans tenir compte des optimisations, à trouver après

Bien sûr, comme toujours, il vaut mieux n’optimiser que les parties critiques.

ou finalement le code "optimisé" et "non-optimisé" sera t-il trop différent (et nécessite une réécriture complète) ?

Je suppose que ça dépend du style. Par exemple, si tu manipules ton container à travers de l’interface « make-my-container, add-to-my-container, my-container-contents », tu peux l’implémenter comme tu veux. (Si my-container-contents renvoie une liste et tu en es soupçonneux, tu peux ajouter la boucle « do-my-container » à l’interface.) En plus, de cette façon Lisp évolutionne vers la tâche. En fait, les listes et vecteurs, c’est le bas niveau du point de vue de ton porgramme.

Les caractéristiques plus avancées de Lisp peuvent rendre le code plus robuste. Par exemple, si l’on emploie le style piloté par les données, on ne doit pas nécessairement interpréter les données pendent l’exécution, mais on peut transformer les données en code pendant la compilation à l’aide des macros.

- j'essaie d'éviter les miettes. Y-a-t-il là aussi, une bonne manière de faire pour les détecter (ou c'est d'expérience) ?

Ben, on peut les détecter à l’aide de TIME. Bien sûr, on peut anticiper des miettes quand on fait des copies ou alloue de la mémoire. Je pense, c’est Graham qui écrit que de nos jours, les ramasse-miettes sont si efficaces que parfois il vaut mieux allouer.

Par exemple, si une variable est « de courte durée », la mémoire est probablement allouée sur la pile.

- je ne trouve pas de documentation sur le fonctionnement interne de certaines macro ou fonctions, leur intérêts / limites. Par exemple subseq est-elle une bonne idée ? J'utilise time pour tester les combinaisons, mais ça reste très sommaire (et long). Connais-tu une ressource à me conseiller sur ce sujet ?

Parce que c’est interne.

Moi, je me contente de lire Hyperspec. Par exemple,
http://www.lispworks.com/documentati...y/f_subseq.htm

subseq always allocates a new sequence for a result; it never shares storage with an old sequence.

Donc, subseq signifie toujours l’allocation. Dans ton cas, tu peux l’éviter en rejetant le cdr comme je l’écris plus bas.

Ou bien c’est évident que la fonction length doit parcourir la liste entière pour en calculer la longeur. Donc, c’est O(n), et pour cette raison elle est consideré « chère ». Mais dans ton cas ce n’est pas important, parce que la longeur est limitée a priori.

Tu indiques dans ta réponse à un moment que tu "compiles ta liste" (en fait si j'ai bien compris, tu lis la compilation d'une fonction à une variable en particulier). Comment se déroule le processus en interne ? Ne faut-il pas avoir une étape avec typecase pour vérifier que cette liaison liste / fonction lors de la compilation, utilise à un moment donné une variable du bon type ?

Quand je dis que je « compile la liste », je veux dire que je transforme la liste dans le code d’une fonction et la liste n’est plus nécessaire. (J’affecte cette fonction à une variable, mais ce n’est pas important). Je ne sais pas qu’est-ce que SBCL fait dans ce cas. Le standard différencie entre les fonctions interpretées et compilées et garantit qu’une fonction compilée renvoie des fonctions compilées. Mais en tout cas, SBCL compile tout par défaut.

Quant’aux types, c’est comme toujours. Si l’on s’en soucie, on peut, par exemple, ajouter la validation de la liste à la « fonction compilatrice » et un checktype à la lambda qu’elle renvoie.

L'étendue actuelle de la fonction, sur mon poste je tourne à 1,3 secondes avec la fonction génératrice aléatoire et 0.04 secondes sans (quel écart !!!) :

Il parait que dans le premier cas, tu as testé la fonction random.

D’habitude je prépare d’abord les données pour un test et ensuite utilise time dans le REPL.

Je dois dire que ton code est peu lisible à cause du formatage. Voici un bon guide :
http://dept-info.labri.fr/~idurand/e...dentation.html
Donc, ça serait plutôt

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(time
  (dotimes (n 1000000) ; incrémentation 
    ; y est alératoire (à trouver) 
    (let ((y (random 1000 etatRand))) 
      (if (not (find y test1)) 
          (progn 
            (push y test1) ; ... j'ajoute à la liste 
            ; ... si la liste est trop importante et qu'il y a eu au moins 17 opérations depuis  
            ; si y a été trouvé, on ne fait rien 
            (if (and (= (mod n 17) 0) 
                     (> (length test1) *taille-tampon*))
                ; je découpe la liste à la bonne taille  
                (setq test1 (subseq test1 0 *taille-tampon*))))))))

ou bien d’une façon plus idiomatique,

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(time
  (dotimes (n 1000000) ; incrémentation 
    ; y est alératoire (à trouver) 
    (let ((y (random 1000 etatRand))) 
      (unless (member y test1) 
        (push y test1) ; ... j'ajoute à la liste 
        ; ... si la liste est trop importante et qu'il y a eu au moins 17 opérations depuis  
        (when (and (zerop (mod n 17)) 
                   (> (length test1) *taille-tampon*))
          ; je découpe la liste à la bonne taille  
          (setf (rest (nthcdr (1- *taille-tampon*)) nil)))))))

Quand il s’agit d’un style impérative, c’est souvent pratique d’employer when et unless lorsqu’il n’y a qu’une branche

Dans ton cas, la longeur de la liste peut dépasser *taille-tampon*. Si tu imposerais une limite de longeur, tu pouvais créer un container à base d’un vecteur comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
vecteur[taille] vecteur;
int longeur = 0;
int tête = taille - 1;
function ajouter(x) {
    vecteur[tête] = x;
    tête = if tête > 0 then tête - 1 else taille - 1;
    longeur = min(longeur + 1, taille);
}
function nème(n) {
    assert(0 <= n < longeur);
    return vecteur((tête + 1 + n) mod taille);
}

Sans aucune gestion de mémoire.

**Pyramidev** · 17/02/2019, 18h45

Bonjour,

Pour tester l'existence d'un élément dans une collection volumineuse, au niveau des performances, la liste chaînée est la pire des collections, car la recherche a une complexité linéaire. Il vaut mieux utiliser une table de hachage, dont chaque recherche a une complexité constante.

Nothus, tu peux lire le chapitre Collections du livre Practical Common Lisp (dont le contenu est accessible en ligne). Ce chapitre te présentera, entre autres, les vecteurs et les tables de hachage en Common Lisp.

Cela dit, l'idéal est de programmer de telle sorte que l'on puisse facilement changer les détails d'implémentation (par exemple remplacer une liste chaînée par une table de hachage) en ne mettant à jour qu'une toute petite partie du code, sans devoir réécrire le reste du code. C'est pour cela que byjav a évoqué la possibilité de créer des fonctions intermédiaires comme make-my-container et add-to-my-container (rq : il en faut d'autres aussi) : le jour où le type de la collection changera, il faudra mettre à jour le code de ces fonctions intermédiaires, mais le code qui ne manipule la collection qu'à travers ces fonctions intermédiaires n'aura pas besoin d'être changé. C'est un exemple d'encapsulation.

**byjav** · 17/02/2019, 19h13

Dans ton cas, tu peux l’éviter en rejetant le cdr comme je l’écris plus bas.

Bien sûr, dans ce cas il faut bien vieiller que la liste ne partage pas la structure avec d’autres listes.

Enfin (pardon pour la longueur), il semble que la compilation de LISP produise un code machine différent du C et que l'intégration avec ctypes de Python (ou un appel quelconque par des outils habituels) n'est pas directement possible. Qu'en est-il ?

On a CFFI http://quickdocs.org/cffi/. Moi, je ne l’ai jamais employé.

**Nothus** · 17/02/2019, 20h46

Bonsoir Pyramidev,

Merci de ton retour.

Envoyé par Pyramidev

Cela dit, l'idéal est de programmer de telle sorte que l'on puisse facilement changer les détails d'implémentation

Tout à fait d'accord avec toi.

Envoyé par Pyramidev

Pour tester l'existence d'un élément dans une collection volumineuse, au niveau des performances, la liste chaînée est la pire des collections, car la recherche a une complexité linéaire. Il vaut mieux utiliser une table de hachage, dont chaque recherche a une complexité constante.

J'ai lu les différents liens que j'ai trouvé, dont celui que tu m'as indiqué. J'entends que la table de hashage est performante pour la recherche. Cependant j'ai mis en tampon la liste des dernières utilisateurs trouvés (considérés comme actifs et susceptibles d'autres activités, cf. mon post initial). La table hashée impose aussi de retrouver le ou les plus vieux, puis de les extraire (cela prendre la ressource), afin que la liste ne dépasse pas un seuil fixé (c-à-d l'équivalent d'une queue FIFO de taille fixe). Comment faire avec un vecteur ? (réponse en relisant : sort et subseq j'imagine...)

... En fait pas de question !

Merci Byjav pour CFFI. Entre temps, j'ai trouvé ECL, qui semble faire quelque chose de similaire (qualité ?) :
https://common-lisp.net/project/ecl/main.html

Bonne soirée,

Julien.

**byjav** · 21/02/2019, 15h18

Comment faire avec un vecteur ? (réponse en relisant : sort et subseq j'imagine...)

Pourquoi ? Je crois qu’un vecteur (conceptuellement) circulaire suffit, comme je l’ai ébauché au-dessus. On va en rond sans allouer de mémoire.

ECL est bon si on a besoin d’une étroite cooperation avec C.

**Nothus** · 28/02/2019, 16h38

Oui effectivement, j'ai mal raisonné et pas assez approfondi le type de la variable. Pour l'instant, j'ai résumé le fonctionnement de la liste à quelque chose de simple, qui fonctionne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(defparameter *clients* (make-array 0 :fill-pointer 0)) 
 
(time (dotimes (n 1000000)
	(let () 
		(when (> (length *clients*) 10) 
			(delete (elt *clients* 0) *clients*) ; FIFO 
		) 
		(vector-push-extend n *clients*) 
	))) 
 
(print *clients*)

Les résultats sont corrects vu que delete est destructif :

Code :

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

1
2
3
4
5
6
Evaluation took:
  0.220 seconds of real time
  0.219971 seconds of total run time (0.219971 user, 0.000000 system)
  100.00% CPU
  485,690,118 processor cycles
  0 bytes consed

Entre temps les discussions font remonter que c'est peut-être pas une si bonne idée d'avoir une liste d'utilisateurs en mémoire (surtout importante) alors qu'ils ont déjà été authentifiés. Si la majorité n'ont qu'une connexion (le plus souvent des utilisateurs humaines), c'est de la ressource gaspillée pour rien et c'est négligeable en terme de délais pour un fichier source sur un SDD si l'on reparcourt la liste (on regroupe les demandes à un instant donné) : l'argument est recevable. Argument moins vrais pour moi si l'on considère que l'outil gère aussi des utilisateurs non-humains, qui peuvent démultiplier les instances et où le critère du délai ne se compte pas de la même manière. Joie du projet

J'avoue que ECL permettrait d'avoir des modules appelables simplement en Python via le C -> du coup oui, ce point me semble important dans le choix.

Merci.

**byjav** · 03/03/2019, 15h33

Chez moi, ça donne

Code :

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

1
2
3
4
5
6
Evaluation took:
  0.286 seconds of real time
  0.284000 seconds of total run time (0.284000 user, 0.000000 system)
  99.30% CPU
  831,046,892 processor cycles
  0 bytes consed

Mais à vrai dire, la spécification permet qu’après un appel à DELETE, le contenu de l’argument soit des données inutiles.

Voilà une réalisation d’une pile limitée à base d’un vecteur « circulaire ». Ce n’est pas exactement la même chose, parce que seul l’élément le plus vieux est supprimé à chaque fois. Mais il n’y a aucune gestion de mémoire ni d’opérations complexes avec des vecteurs, donc le code est plus efficace.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
(defstruct (limited-stack (:constructor make-limited-stack (size &aux (length 0) (head (1- size)) (storage (make-array size)))))
  size
  length
  head
  storage)
 
(defun limited-stack-add (item stack)
  (setf (aref (limited-stack-storage stack) (limited-stack-head stack)) item)
  (when (< (limited-stack-length stack) (limited-stack-size stack))
    (incf (limited-stack-length stack)))
  (if (plusp (limited-stack-head stack))
      (decf (limited-stack-head stack))
      (setf (limited-stack-head stack) (1- (limited-stack-size stack))))
  item)
 
(defmacro do-limited-stack ((var stack &optional result) &body body)
  (let ((i-var (gensym "I-"))
        (stack-var (gensym "CACHE-"))
        (start-var (gensym "START-"))
        (end-var (gensym "END-"))
        (arr-var (gensym "ARRAY-"))
        (size-var (gensym "SIZE-")))
    `(let* ((,stack-var ,stack)
            (,start-var (1+ (limited-stack-head ,stack-var)))
            (,end-var (+ (limited-stack-head ,stack-var) (limited-stack-length ,stack-var)))
            (,arr-var (limited-stack-storage ,stack-var))
            (,size-var (limited-stack-size ,stack-var)))
       (loop with ,var
             for ,i-var from ,start-var to ,end-var
             do (progn
                  (setf ,var (aref ,arr-var (mod ,i-var ,size-var)))
                  ,@body)
             finally (return ,result)))))
 
(defun limited-stack-items (stack)
  (let ((items '()))
    (do-limited-stack (x stack (nreverse items))
      (push x items))))

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
* (defparameter *c* (make-limited-stack 10))
 
* (time (dotimes (n 1000000)
	  (limited-stack-add n *c*)))
 
Evaluation took:
  0.015 seconds of real time
  0.016000 seconds of total run time (0.016000 user, 0.000000 system)
  106.67% CPU
  43,161,011 processor cycles
  0 bytes consed
 
NIL
 
* (limited-stack-items *c*)
(999999 999998 999997 999996 999995 999994 999993 999992 999991 999990)

**Nothus** · 03/03/2019, 18h40

Ah ouai, il y a une belle différence de résultats !

Entre 0.286 et 0.015 s., c'est un coefficient par près de 20 !

J'ai potassé ton code (d'ailleurs merci, une fois encore). En somme un vecteur circulaire - la substantifique moelle -, c'est revenir à un point de départ passé un point, et écraser une valeur déjà existante. J'ai un peu honte de ne pas y avoir pensé avant... d'autant que tu me l'avais déjà soufflé il y a quelques messages dans du pseudo-code.

Là où je suis moins convaincu avec ton exemple, c'est la "complexité" pour y arriver (j'y reviendrai).

Après nos échanges précédents sur les listes, je n'avais pas gardé la définition de structures personnalisées en imaginant que les objets déjà existants (Array, Vector, etc.) étaient optimisés et qu'il n'était pas utile / performant / intelligent de "descendre" trop bas dans ce que propose le langage.

Du coup j'ai repris ton idée en me limitant à une structure en "triplet" : taille, pointeur, items. Une fonction permet d'ajouter un élément, en écrasant le plus ancien en jouant sur le pointeur d'accès.

Code lisp :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/usr/bin/sbcl --script 
 
(defstruct (file-attente 
    (:constructor creer-file-attente 
      (taille 
        &aux 
        (items (make-array taille))
      ) 
    )
  )
  taille
  (pointeur 0) 
  items) 
 
(defun ajouter-file-attente (file item) 
  (let ((pointeur (1+ (file-attente-pointeur file)))) 
    (when (> (1+ pointeur) (file-attente-taille file)) 
      (setf pointeur 0)
    ) 
    (setf (aref (file-attente-items file) pointeur) item) 
    (setf (file-attente-pointeur file) pointeur))) 
 
(defparameter *c* (creer-file-attente 10))
 
(time (dotimes (n 1000000)
  (ajouter-file-attente *c* n))) 
 
(print *c*)

Sur ma machine, je diminue encore le temps de calcul et je suis en dessous en moyenne de ton code.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Evaluation took:
  0.011 seconds of real time
  0.010770 seconds of total run time (0.010770 user, 0.000000 system)
  100.00% CPU
  23,777,704 processor cycles
  0 bytes consed
 
#S(FILE-ATTENTE
   :TAILLE 10
   :POINTEUR 0
   :ITEMS #(999999 999990 999991 999992 999993 999994 999995 999996 999997
            999998))

Il y a une différence - pas très subtile... - entre tes résultats et les miens : certes ma liste est "en bordel". Je ne m'occupe pas de la cohérence de "items", et il faut à partir du pointeur, recalculer l'ordre si l'on désire. Cependant ce n'est pas très compliqué vu qu'on a la taille et le pointeur.

Pour ce qui me concerne, cette donnée de "l'historique" véritable de la liste, en dehors de virer les éléments les plus anciens, ne m'intéresse finalement pas (je ne fais que la parcourir à la recherche d'un profil déjà enregistré dedans pour en extraire les résultats, sa position exacte dans la liste n'est pas informative en soi). J'ai juste à adapter l'exemple pour le cas où l'utilisateur trouvé dans la liste, est en bout de course (il faut le faire revenir en début de course).

Autre point d'intérêt : c'est maintenable "à mon niveau" (je sais que l'argument n'est guère recevable, cependant je préfère un code que je maîtrise parfaitement).

J'ai tout bon cette fois ?!

Avis sur l'intérêt de LISP sur projet

Lisp

Discussions similaires

Partager

Partager