Sinon il y a Vector, c'est peut-être plus performant. Après même dans les langages "performants", les modifications ponctuelles et aléatoires dans un tableau sont à éviter.
https://hackage.haskell.org/package/vector
Cela dépend de ce que l’on fait. Pour un FFT, on ne va pas modifier le tableau élément par élément, on crée à chaque itération un tableau complet en O(n) et on reste globalement en O(n.log(n)).
Pour une résolution de n équations à n inconnues, à chaque étape, on modifie n-1 lignes. (De l’ordre de n*n modifications). Du coup, en utilisant une modification de n*(n-1) valeur, on a une copie de n*n valeurs suivie de n*(n-1) opérations. On peut aussi demander un tableau initialisé avec une formule différente pour la ligne non modifiée (pivot) er pour les autres.
Bref, il peut y avoir beaucoup d’algorithmes qui s'exécuteraient dans des temps comparables avec des tableaux immuables.
Mais on a pas une journée devant nous, le plus souvent! On est dans la vraie vie, si on ne livre pas le client en mai, le PDG de chez le client saute. Donc la journée de maintenance préventive(c'est le terme qu'on utilise pour faire ce que tu dis), c'est quand il n'y a pas le feu. Ce qui est fort rare. La plupart du temps, on garde le gros tas tel qu'il est tant qu'on a pas explicitement à le changer. On sait qu'il faudrait le faire, mais si on met ça en priorité, on perd le client, et on ferme boutique. C'est triste. Mais c'est le monde réel.
Si dans 5 mois on est morts, à quoi ça sert de préparer l'avenir à 5 ans? Bosser dans une structure intuable(la fonction publique) te fait louper quelques évidences fondamentales. La survie à long terme n'a de sens que si on survit à court terme, déjà.
Ben oui. des gens très compétents. Le glandu de base, il fera un truc pas si lent en impératif. Dans les autres paradigmes.... 80% des boites n'ont que des Glandus médiocres à leur disposition. Est-ce surprenant qu'elles préfèrent éviter les "bonnes pratiques" qui rendent les stars si efficaces?
Les 4 règles d'airain du développement informatique sont, d'après Michael C. Kasten :
1)on ne peut pas établir un chiffrage tant qu'on a pas finalisé la conception
2)on ne peut pas finaliser la conception tant qu'on a pas complètement compris toutes les exigences
3)le temps de comprendre toutes les exigences, le projet est terminé
4)le temps de terminer le projet, les exigences ont changé
Et le serment de non-allégiance :
Je promets de n’exclure aucune idée sur la base de sa source mais de donner toute la considération nécessaire aux idées de toutes les écoles ou lignes de pensées afin de trouver celle qui est la mieux adaptée à une situation donnée.
Dans le cas que je t'ai donné, ça prends quelques minutes à regarder rapidement les warnings des outils de vérifications que tu utilises et te fait gagner très rapidement du temps (e.g. le cas du chemin absolu).
Dès que tu reçois du code, tu vas bien au minimum le compiler, faire un rapide Hello World avant de commencer à l'utiliser, non ?
Si tu commences déjà à l'utiliser, à écrire une grosse fonction, pour t'apercevoir qu'il y a un truc qui ne marche pas, ça va déjà te prendre beaucoup plus de temps à corriger que si tu avais commencé progressivement avec un Hello World.
De même ça te coûte rien de passer 2-3 minutes à parcourir les warnings quand tu sais que derrière certains d'entre eux pourront te faire gagner très rapidement plusieurs heures.
EDIT: Surtout que ça évite les mauvaises surprises 5 minutes avant la livraison chez le client, là où tu as encore moins de temps.
Mais c'est tout aussi bien de vivre à la fois à long et à court terme.
Vivre que de fuites en avant te permettra peut-être de t'en sortir à court terme, mais cela va devenir de plus en plus difficile avec un impact négatif sur les salariés.
Si tu n'es pas capable de sortir la tête du guidon, tu peux passer des mois à faire des choses inutiles et à devoir tout jeter ensuite. Et ce n'est pas parce que je suis dans la fonction publique que je ne connais pas ça, on a des deadlines avec les conférences, et faut maximiser nos nombres de publis pour obtenir un poste.
Sachant qu'un code de moins bonne qualité, c'est aussi plus de bugs, un client pas forcément content quand ça plante, et de la maintenance à faire.
EDIT: Dans la recherche, c'est pas joyeux non plus, avec des deadlines impossibles à tenir, heureusement souvent repoussées de 1-2 semaines, et les confs s'enchaînent assez rapidement.
Derrière si y'a pas la qualité, le papier est rejeté et on a perdu du temps. Sachant qu'il faut être toujours dans les meilleurs.
Et même en impératif, on peut se retrouver avec des horreurs... surtout avec les I/O.
Les fonctions sont décrites ici : http://hackage.haskell.org/package/v...ta-Vector.html il est clairement précisé que les modifications sont en O(n+m) où n est la taille du tableau et m le nombre de modifications.
Si vraiment on souhaite multiplier les écritures ponctuelles dans une structure fonctionnelle (immuable), il vaut mieux des arbres (temps en log(n) et non en O(n)).
Pour revenir à l’article sur les performances autorisées par Haskell, il convient de noter que le gain de performance est entre un langage interprété maison et un langage compilé. Le résultat n’est pas trop étonnant.
La difficulté est effectivement d'arriver à glisser un peu de long terme dans tout ce court-termisme. Je suis toujours content quand j'y arrive. Mais ce n'est pas toujours possible. Je me souviens, prestataire chez un client précis, que je pouvais planquer une ou deux heures par semaine, maximum. C'est le temps que j'avais pour penser au long terme. Tout le reste, c'était urgences et urgences.
Dans ce genre de contextes, on se satisfait parfois de solutions, euh, sub-optimales en termes de dette technique, pour rester poli. Et on est content quand on arrive à glisser une fiabilisation en loucedé. Mes chefs sur place m'ont explicitement refusé un dev de 5 jours - qui aurait fait gagner 3 jours de maintenance par mois. Motif? "ce n'est pas du projet, ce n'est pas justifiable".
Tu prèches un convaincu. Qui a parfois été coupable, d'ailleurs..... Mais l'objet est particulièrement piégeux à ce niveau. Imagine un getter qui va chercher en I/O la même donnée à chaque fois, sans bufferisation..... le truc typique dont le débutant sera fier. En impératif pur, l'équivalent, c'est de se retaper le code d'accès I/O à chaque fois. C'est moins motivant pour le débutant perdu. Le résultat est le même, mais l'erreur sera plus tentante dans un cas comme dans l'autre. Après, oui, je l'ai déjà vu, le coup de la même requête SQL(50 lignes, ramenant un paquet de données, pour n'en utiliser qu'une) recopiée plusieurs fois de suite. Mais ça me semble moins fréquent en impératif.
Les 4 règles d'airain du développement informatique sont, d'après Michael C. Kasten :
1)on ne peut pas établir un chiffrage tant qu'on a pas finalisé la conception
2)on ne peut pas finaliser la conception tant qu'on a pas complètement compris toutes les exigences
3)le temps de comprendre toutes les exigences, le projet est terminé
4)le temps de terminer le projet, les exigences ont changé
Et le serment de non-allégiance :
Je promets de n’exclure aucune idée sur la base de sa source mais de donner toute la considération nécessaire aux idées de toutes les écoles ou lignes de pensées afin de trouver celle qui est la mieux adaptée à une situation donnée.
Le problème c'est que dans une telle situation, les employés risquent de ne pas tenir le rythme avec des conséquences plus ou moins dramatiques.
D'autant plus que dans un tel cas, rien n'est fait pour résoudre ce problème, quitte, e.g. à engager des fonctions supports.
Après, oui, si tu as des contraintes de tes chefs, tu ne peux pas y faire grand chose.
Mais bon, ce n'est pas parce que ton chef t'interdit e.g. d'aller sur Internet que cela ne serait pas une bonne chose et ne serait pas rentable très rapidement si tu le faisais.
EDIT: si ton estimation est correcte, imagine, 5 jours de devs un peu intensif que tu rentabilises en 2 mois. Après, tu as 3 jours par mois "libre" où tu pourras sortir la tête de l'eau… et faire d'autres trucs du genre.
Si tu as 2-3 trucs du genre, ça te fais 9 jours par mois de gagnés (sur 21 jours de travail), c'est énorme. Déjà rien que 3 jours, ça te fais 14% de temps "libre" sur ton mois.
Si tu trouves 7 trucs du genre, t'as même plus besoin de travailler dans le mois ! Et si t'en trouves encore plus, tu devras travailler un nombre de jour négatif !
Il y a un langage fonctionnel qui gagne a être connu des utilisateurs d’Excel, c’est le langage M derrière PowerQuery. Le langage est purement fonctionnel : aucune variable référencée (comme le ref 42 d’Ocaml), ni de monade comme dans Haskell.
Contrairement au langage de macro d’Excel (Visual Basic), les traitement se font par tableaux entiers (une fonction Table.AddColumn ajoute à un tableau une colonne définie par une fonction choisie par exemple ligne => ligne[colonne A] + ligne[colonne B] cela se réécrit en _ => _[colonne A] + _[colonne B] soit en supprimant des _ _ => [colonne A] + [colonne B] ou encore each [colonne A] + [colonne B]. On a donc plusieurs «*sucres syntaxiques*» qui rend le langage adapté à certains usages. La fonction qui ajoute cette colonne s’occupera de la boucle, alors qu’en VB, il y a des boucles FOR / NEXT à gérer. Des fonctions assurent des jointures, ce qui rend l’ensemble efficace pour pal mal d’opérations.
Le langage est très orienté tableau. Soit t un tableau, on peut prendre une colonne en écrivant t[colonne A] ou une ligne t{42}.
Je me suis amusé à l’implémenter en Java (sans la multitude de fonctions). Et le traitement des tableaux m’a donné du fil à retordre. D’autant plus que le langage permet de retourner une liste de 1000000000 éléments en un rien de temps : {1..1000000000} et on peut manipuler ce tableau (concatenation, etc) avec plusieurs opérations en O(1).
Dans le cas que tu cites, est-ce que l'exécution ne se fait pas "à partir de la fin" ?
C'est à dire qu'il construit une sorte d'arbre d'exécution (quitte à l'optimiser un peu au passage), et quand tu dois afficher la valeur d'une cellule, il remonte l'arbre puis le redescent en faisant les calculs nécessaires, en gardant sur les nœuds les valeurs déjà calculées ? Quitte à utiliser du BLAS pour certaines opérations ?
Je n’ai pas saisi le sens "à partir de la fin". Il se trouve que M est un langage paresseux ainsi, un let a=un_très_gros_calcul () in 42 n’évaluera pas a et retournera directement 42.
Pour mon implémentation des tableaux (je ne sais pas si M fait pareil, mais cela ne m’étonnerait pas), je les code sous forme d’objet tableau qui peut être implémenté différemment selon la fonction qui le retourne. Un tableau {1..1000000} ressemblera à un range(1,1000001) de Python, mais j’ai codé aussi un tableau qui est un arbre de sous tableaux pour permettre des concaténations ou écrire {1..10, 4,42, 100..200}. Chaque tableau connaît sa longueur (un List.Length retourne immédiatement la longueur). Le polymorphisme de Java permet de coder différents types de tableau facilement et retourner un objet qui a les bonnes propriétés. Un type d’objet Liste est le résultat d’une sélection de colonne dans un tableau( table[colonne]... c’est juste un objet qui pointe le tableau et le numéro de la colonne. Lorsque l’on indexe cette liste, on indexe le tableau, ce qui donne une ligne (record), et il suffit de l’indexer avec le numéro de la colonne).
Oui désolé, une évaluation paresseuse, j'avais oublié le nom
Pour des très gros tableaux, il pourrait même être possible qu'il passe par GPU (?).
Après, ce n'est pas parce que le code est fonctionnel, que l'interpéteur est écrit en fonctionnel.
Derrière tu peux peut-être avoir des tableaux mutables modifiés si le tableau d'origine ne sera plus utilisé par la suite.
Le GPU, je ne pense pas. Le List.Transform n’évalue rien mais retourne quelque chose dont les accès initient une évaluation. Il n’est pas possible d’anticiper ce qui sera évalué et donc je pense que ce serait une usine à gaz de définir une structure qui alimente un GPU. Modifier le tableau nécessite d’avoir l’assurance que la version originale ne sera pas utilisée (et va modifier un {1..100000} codé comme une paire (start,end))
Pour des optimisations SIMD (SSE...) il faut plutôt se tourner vers Julia. Mais là, le parallélisme est évident : certaines fonctions sont vectorielles. Il suffit de préfixer par un point (.*, .+, ...) À ce sujet, définir un langage performant à typage dynamique me sidère un peu. Pour moi, c’était antinomique jusqu’à ce que j’essaye ce langage.
S'il n'y a aucun effets de bords, il n'est pas impossible que l'interpréteur n’exécute pas toutes les opérations lignes par lignes, mais au contraire construise un arbre d'exécution dans une phase de lecture, puis fasse l'exécution dans une seconde phase. Personnellement, c'est l'approche que je prendrais si je devais faire cela.
Sur ce type de code, ça doit pas prendre énormément de temps de construire un tel arbre, mais derrière tu peux faire d'énormes optimisations, surtout quand derrière c'est pour un tableur avec potentiellement de très nombreuses lignes.
Jusqu'à pousser le vice de ne calculer les valeurs que lors de l'affichage des cellules à l'écran.
Un article interessant sur les tableaux performants en fonctionnel : https://www.tweag.io/posts/2017-08-0...n-haskell.html
Je ne suis pas du tout d'accord avec cette interprétation. L'application initiale était en C++ mais il fallait un système de règles expressives et modifiables à chaud, ce qu'ils ont implémenté avec leur langage maison. C'est une solution assez classique quand le C++ n'est plus assez expressif ni flexible (dans le même genre, il y a pléthore de libs C++ avec surcouche Python). Donc on peut tourner le problème dans tous les sens mais le fait est qu'ils ont remplacé un morceau de leur solution en C++ maison par un morceau en haskell, qui, pour le même cahier des charges, est plus performant.
Oui, effectivement, lorsque mon interpréteur lit le programme, il construit un arbre d’exécution, et les évaluation retardées car paresseuses ne sont que des pointeurs sur cet arbre. Certaines constantes sont calculées avec cet arbre (ainsi, une variable - un nom - est remplacé par la position de la variable dans le contexte d’exécution : profondeur, index).
Justement, avec ça, tu sais que si un nœud (variable) n'a qu'un seul fils (i.e. une seule arrête, ou plusieurs arrêtes pointant vers le même fils) alors tu sais qu'elle ne sera plus utilisée par la suite, donc que tu peux faire des opérations "in-place".
Merci pour l’article. Je note «*In contrast, vector favours whole-vector processing collective operations — also referred to as wholemeal programming*». Il convient donc de privilégier des traitements de tableaux globaux pour minimiser les copies de tableau à chaque petit changement. Avec des structures non fonctionnelle (tableaux C ou Ocaml), on peut moins se poser de questions.
J’ai compris qu’il ont remplacé le FXL maison par du Haskell. Forcément, remplacer de l’interprété par du compilé ne peut qu’améliorer les choses (même si les règles sont analysées par FXL au chargement et codées en AST en mémoire). Mais le choix est intelligent, Haskell peut faire un bon langage de règle.Je ne suis pas du tout d'accord avec cette interprétation. L'application initiale était en C++ mais il fallait un système de règles expressives et modifiables à chaud, ce qu'ils ont implémenté avec leur langage maison. C'est une solution assez classique quand le C++ n'est plus assez expressif ni flexible (dans le même genre, il y a pléthore de libs C++ avec surcouche Python). Donc on peut tourner le problème dans tous les sens mais le fait est qu'ils ont remplacé un morceau de leur solution en C++ maison par un morceau en haskell, qui, pour le même cahier des charges, est plus performant.
Les pointeurs ne sont que dans un sens... du noeuds qui utilise la variable vers la variable. Pas l’inverse. Si chaque variable pointait sur une liste chaînée d’expression l’utilisant, il y aurait beaucoup de travail pour mettre ces listes à jour. Pas sûr qu’on y gagnerait au final.
Le langage M ne donne pas de fonction qui retourne un tableau avec une seule (ou quelques) valeurs modifiées. Ainsi, il n’y a pas d’intérêt à «*optimiser*» ce type de traitement. Autant réalouer un nouveau tableau si besoin (ex : List.Transform), il n’y a pas d’intérêt à modifier sur place un tableau existant. Il n’y a qu’Haskell avec son opérateur de modification : let t2 = t1 // [ liste_de_modif ] in ... qui pourrait être utile à optimiser... et cela n’a pas été fait. Signe peut-être que le remède serait pire que le mal.
Si tu fais du doublement chaîné, ça se fait très rapidement :
Ok. Et je présumes que comme tu utilises un GC, l'allocation te coûte presque rien.
Code : Sélectionner tout - Visualiser dans une fenêtre à part c->next->previous = c; // pseudo code
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager