# Coder dans plusieurs langages **URL:** \ **Category:** Programmation\ **Created:** [Février 20, 2016, 9:00 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239 "2016-02-20T21:00:57Z")\ **Posts on this page:** 20\ **Page:** 3
**Author:** ![Keldath](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/k/f17d59/32.png) [@Keldath](https://www.debian-fr.org/u/Keldath)\ **Post date:** [Février 20, 2016, 9:03 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/41 "2016-02-20T21:03:37Z")
[quote=“vapula”]C’est une solution envisageable, Keldath. C’est de cette manière que pour N=5000, je passe de 10’ à 6’ (environ).[/quote]Hum, en fait on ne règle que la moitié du problème en stockant un booléen (dans une seconde matrice ou dans un doublet dans la 1ère matrice comme le fait MisterFreez), et on fausse le résultat final. Faut forcément stocker le résultat maxi qu’on puisse atteindre depuis une case déjà parcourue. @MisterFreez : À ce propos, sur cette valeur que tu initialises à -1, conceptuellement il ne serait pas mieux d’utiliser boost::optional ? (ça reste du détail) ---
**Author:** ![MisterFreez](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/m/bb73d2/32.png) [@MisterFreez](https://www.debian-fr.org/u/MisterFreez)\ **Post date:** [Février 20, 2016, 9:03 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/42 "2016-02-20T21:03:39Z")
Si j’utilise boost, j’aurais utilisé autre chose que des vectors aussi. 😉 Je n’utilise pas boost pour des codes que j’envoie comme ça sur internet, pour simplifier les tests si quelqu’un veut vérifier l’exécution du programme. ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:03 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/43 "2016-02-20T21:03:46Z")
Ici, on ne peut faire mieux que N² puisque le nombre de case est en N². Sinon, oui il s’agit bien de la programmation dynamique (cas où une solution optimale se déduit d’une solution optimale d’un pbm plus petit). Une complexité en N² ici signifie donc qu’on ne fait qu’un nombre fini précis d’opérations sur chaque case. Voilà le pbm en camllight: [code]let domatrice n = let m = make\_matrix n n 0.0 in ( for i = 0 to n-1 do for j = 0 to n-1 do m.(i).(j) \<- random\_\_float 1.0; done;done; m);; let calcul matrice = let n = vect\_length matrice in let hauteur = make\_matrix n n (-1) in let voisin\_bas (i,j) = let ok (ip,jp) = if ((ip \>= 0) && (jp \>= 0) && (ip \< n) && (jp \< n) && (matrice.( ip).(jp) \< matrice.(i).(j))) then [ip,jp] else [] in flat\_map ok [(i-1,j);(i+1,j);(i,j-1);(i,j+1)] in let maxl l = list\_it max l 0 in let rec h i j = if (hauteur.(i).(j) \>= 0) then hauteur.(i).(j) else let c = maxl (0::(map (function (ip,jp) -\> (h ip jp) +1) (voisin\_bas (i,j)))) in (hauteur.(i).(j) \<- c;c) in let maxi = ref 0 in for i = 0 to (n-1) do for j = 0 to (n-1) do if (h i j) \> !maxi then maxi := hauteur.(i).(j); done;done; !maxi;; print\_string (calcul (domatrice sys\_\_command\_line.(1));;print\_newline ();; [/code] voisin (i,j) donne la liste des voisons de la se (,j) plus bas que cette case, maxl est le maximum d’une liste, h i j donne la longueur du plus grand escalier d’origine en (i,j), calcul M donne le résultat pour la matrice M. ---
**Author:** ![BBT1](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/b/ecc23a/32.png) [@BBT1](https://www.debian-fr.org/u/BBT1)\ **Post date:** [Février 20, 2016, 9:04 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/44 "2016-02-20T21:04:03Z")
Aller, pour le fun, l’exercice de l’escalier en scala avec 2 threads (mais bon, 3 min pour compiler, 3 min pour executer avec N=1000… c’est pas encore ça 😆 ) [code]import scala.concurrent.SyncVar import scala.concurrent.ops.\_ object Escalier { ``` class Marche(h: Float) { var dist = new SyncVar[Int] var distAvailable : Boolean = false val hauteur : Float = h override def toString: String = "{" + dist.get + ", " + hauteur + "}" } val N = 1000 val escalier = { val e = new Array[Array[Marche]](N) val r = new java.util.Random() List.range(0, N) foreach (i => { e(i) = new Array[Marche](N) List.range(0, N) foreach (j => { e(i)(j) = new Marche(r.nextFloat()) }) }) e } def trouveEscalier(i: Int, j: Int): Int = { val m = escalier(i)(j) if (m.distAvailable) { m.dist.get } else { var h = m.hauteur var d = -1 List((i-1, j), (i+1, j), (i, j-1), (i, j+1)) foreach (c => c match { case (newi, newj) => if (0 <= newi && newi < N && 0 <= newj && newj < N && escalier(newi)(newj).hauteur > h) d = max(d, trouveEscalier(newi, newj)) }) m.dist.set(d + 1) m.distAvailable = true return d + 1 } } def main(args: Array[String]) { println("Escalier: start") def trouveRegion(debut: Int, fin: Int)(): Int = { var localDist = 0 List.range(0, N) foreach (i => { List.range(debut, fin) foreach (j => { val d = trouveEscalier(i, j) if (d > localDist) localDist = d }) }) localDist } var maxDist = par[Int, Int](trouveRegion(0, N/2-1), trouveRegion(N/2, N)) match { case (d1, d2) => max(d1, d2) } //print(this) println("maxDist = " + maxDist) println("Escalier: end") } def max(a: Int, b: Int): Int = if (a > b) a else b override def toString: String = { var s = ""; List.range(0, N) foreach (i => { List.range(0, N) foreach (j => { s += "(" + i + "," + j + ") = " + escalier(i)(j) + "\n" }) }) s } ``` }[/code] ---
**Author:** ![MisterFreez](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/m/bb73d2/32.png) [@MisterFreez](https://www.debian-fr.org/u/MisterFreez)\ **Post date:** [Février 20, 2016, 9:04 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/45 "2016-02-20T21:04:04Z")
Comment est gérée l’accès concurrent aux variables ? ---
**Author:** ![BBT1](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/b/ecc23a/32.png) [@BBT1](https://www.debian-fr.org/u/BBT1)\ **Post date:** [Février 20, 2016, 9:04 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/46 "2016-02-20T21:04:22Z")
Pour l’accès concurrent aux variables, j’ai juste protégé Marche.dist pour éviter des incohérences si il y a écritures / lectures simultanées sur le champs. Il est donc possible qu’un dist soit calculé plusieurs fois, mais je me suis dit que c’était moins grave que de provoquer de la contention en mettant des locks partout. Sur le code, c’est fait avec "var dist = new SyncVar[Int]" dist est donc de type SyncVar et est un conteneur d’Int. SyncVar propose les méthode get et set qui sont protégées de manière classique. D’ailleurs j’en profite pour dire qu’en fait scala c’est rapide, il faut juste utiliser une jvm récente de chez sun et pas du gcj… et c’est bien intégré avec eclipse (même si j’aime beacoup emacs). Je monte jusqu’à 3000\*3000 cases en 34 sec, au delà j’explose la mémoire… ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/47 "2016-02-20T21:05:00Z")
Allez, un autre pbm si la complexité vous amuse, il y a [là](http://boisson.homeip.net/sac.txt) une liste de 100 réels compris entre 0 et 50. Elle commence par [quote]76.6006173876 53.2095327249 62.8074649884 6.11430589708 57.5346438343 6.85180377081 92.6405477265 37.3201741611 79.5546082158 84.2004758651 …[/quote] Vous disposez d’un temps fini mettons cinq minutes pour trouver la somme la plus grande possible que vous pouvez former avec ces réels (chaque élément ne peut être pris qu’une fois au plus bien sûr) et qui soit inférieur à 500. Par exemple on a ` 498.387973897=3.02292807563+13.3202226366+5.85383028871+2.89972820541 +2.73708440896+99.7235716825+52.0153159277+85.1318409761+78.872384595 +34.8696397735+38.7548745113+81.1865528156` mais on peut faire mieux. C’est le problème du sac à dos, il est NP-complet, c’est à dire qu’à l’heure actuelle, on ne connait pas pour la solution exacte de méthode meilleure (fondamentalement) que l’essai systématique de toutes les additions soit ici 2^100 additions soit en gros 10^30 de combinaisons possibles (essayez pour voir 🙂). Donc là le pbm est: vous avez droit à au plus 5 minutes de temps de calcul (ou 10 ou 15 mais une borne fixe raisonnable et petite, 5 me parait bien). Il faut trouver une somme inférieure à 500 la plus proche possible de 500. Voilà, enjoy… ---
**Author:** ![MisterFreez](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/m/bb73d2/32.png) [@MisterFreez](https://www.debian-fr.org/u/MisterFreez)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/48 "2016-02-20T21:05:10Z")
5 minutes c’est pour le code ou pour le l’exécution ? Celui qui arrive à trouver une méthode pour trouver le résultats qui ne soit pas une énumération de toutes les possibilités gagne 1 000 000$ si je ne m’abuse. ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/49 "2016-02-20T21:05:13Z")
L’éxécution… Je n’ai pas dit de trouver la solution mais de trouver une somme la plus proche possible de 500 en un temps limité (5mn). (On peut faire nettement mieux que 498.387973897…) Il n’est pas possible d’énumérer toutes les possibilités ici… ---
**Author:** ![Ashgenesis](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/a/57b2e6/32.png) [@Ashgenesis](https://www.debian-fr.org/u/Ashgenesis)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/50 "2016-02-20T21:05:14Z")
@gege2061 : Merci pour votre coopération lol, plus sérieusement merci c’est sympa et intéressant. @fran.b : Super c’est sympa d’avoir ajouter un petit exos et tu m’as donnée une idée. Sinon dis voir ta liste ne serait pas comprise plutôt entre 0 et 100 et non 50 ? Ah oui j’en rajoute un petit qui pourrais être sympa car je l’ai fait en C je vous mettrais le code après vos réponses, Créer un algorithme permettant de générer une liste de mots à partir d’une suite de caractères prédéfini. L’objectif étant là, la performance le maximum de mot de 1 à 6 caractères en un temps minimum. Si vous pouvez pousser jusqu’à 8 ou plus amusez-vous. voici la liste des caractères > [@](#): > > a,z,e,r,t,y,u,i,o,p,q,s,d,f,g,h,j,k,l,m,w,x,c,v,b,n,A,Z,E,R,T,Y,U,I,O,P,Q,S,D,F,G,H,J,K,L,M,W,X,C,V,B,N,0,1,2,3,4,5,6,7,8,9 ---
**Author:** ![MisterFreez](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/m/bb73d2/32.png) [@MisterFreez](https://www.debian-fr.org/u/MisterFreez)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/51 "2016-02-20T21:05:15Z")
[quote=“fran.b”]L’éxécution… Je n’ai pas dit de trouver la solution mais de trouver une somme la plus proche possible de 500 en un temps limité (5mn). (On peut faire nettement mieux que 498.387973897…) Il n’est pas possible d’énumérer toutes les possibilités ici…[/quote] C’est une énumération des parties si je ne m’abuse, je coderais ça 😃 Pour voir les perfs que ça donne avec et sans optimisation. @Ashgenesis \> Générer des mots du dictionnaires ou autre ? ---
**Author:** ![Ashgenesis](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/a/57b2e6/32.png) [@Ashgenesis](https://www.debian-fr.org/u/Ashgenesis)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/52 "2016-02-20T21:05:15Z")
Pas forcément du dictionnaire, ça doit pouvoir être n’importe quel assemblage mais l’idée est là. L’algo n’est pas complexe là où ça devient plus complexe c’est pour l’optimisation. ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/53 "2016-02-20T21:05:19Z")
[code]let liste= [“a”;“z”;“e”;“r”;“t”;“y”;“u”;“i”;“o”;“p”;“q”;“s”; “d”;“f”;“g”;“h”;“j”;“k”;“l”;“m”;“w”;“x”;“c”;“v”;“b”;“n”;“A”;“Z”; “E”;“R”;“T”;“Y”;“U”;“I”;“O”;“P”;“Q”;“S”;“D”;“F”;“G”;“H”;“J”;“K”; “L”;“M”;“W”;“X”;“C”;“V”;“B”;“N”;“0”;“1”;“2”;“3”;“4”;“5”;“6”;“7”;“8”;“9”];; let rajoute x l = let rec boucle res l1 = function | [] -\> (x::l1)::res | l2 -\> (boucle (((List.rev l2)@(x::l1))::res) ((List.hd l2)::l1) ([List.tl](http://List.tl) l2)) in boucle [] [] (List.rev l);; let fabrique = let rec boucle entete l = function | 0 -\> print\_string (String.concat “” entete);print\_newline (); | \_ when l = [] -\> () | k -\> (boucle entete ([List.tl](http://List.tl) l) k); (List.map (function x -\> (boucle x ([List.tl](http://List.tl) l)(k-1))) (rajoute (List.hd l) entete));(); in boucle [];; fabrique liste (int\_of\_string Sys.argv.(1));;[/code] Ça affiche [quote]$ ./Genere 8 98765432 89765432 87965432 87695432 87659432 87654932 87654392 87654329 97865432 79865432 78965432 78695432 78659432 78654932 78654392 78654329 97685432 79685432 76985432 76895432 76859432 76854932 76854392 … [/quote] et on a [quote]francois@bling:~/Caml$ time (/tmp/Genere 2 \> /dev/null) real 0m0.018s user 0m0.007s sys 0m0.001s francois@bling:~/Caml$ time (/tmp/Genere 3 \> /dev/null) real 0m0.869s user 0m0.406s sys 0m0.019s francois@bling:~/Caml$ time (/tmp/Genere 4 \> /dev/null) real 0m55.205s user 0m24.991s sys 0m1.582s [/quote]Explosif tout de même, la complexité est en (n!).binomial(l,n) où l = card(liste) et n le nombre de lettres voulues… soit en gros ici si l \>\> n, en l^n (62^n), le temps est multiplié par 62 à chaque rajout de 1 dans la longueur voulue. On a bien 0,869\*62=53,878 à comparer aux 55,205s réel. ---
**Author:** ![Hoshin](https://www.debian-fr.org/user_avatar/www.debian-fr.org/hoshin/32/3672_2.png) [@Hoshin](https://www.debian-fr.org/u/Hoshin)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/54 "2016-02-20T21:05:20Z")
Pour la somme de réels, en triant et en procédant de façon gloutonne on obtient 499.246198063525. En supposant qu’on fasse un tri-fusion on doit être en n\*log(n) niveau complexité (peu ou prou) sachant que la partie “somme gloutonne” se fait en une passe. Il y a sans doute moyen d’optimiser parceque je suppose que si tu parles de “minutes” de temps d’execution un programme comme : ```auto #!/usr/bin/perl -w use strict; use warnings; use Data::Dumper; my $fname = "sac.txt"; open(my $handle, "<" , $fname); my @numbers = <$handle>; my $max = 500; @numbers = sort {$b <=> $a} @numbers; my @sumlist; my $cursum = 0; for my $item (@numbers){ if($cursum + $item < $max){ push @sumlist, $item; $cursum+=$item; } } #print Dumper(@sumlist)."\n"; print $cursum; ``` doit pouvoir être modifié pour faire mieux ^^. On n’est pas exactement dans le cas “scolaire” du knapsack d’une certaine façon puisqu’on a un sac “sans fond” et que la limite se trouve à la valeur de ce dernier et non pas, comme c’est proposé en général, par le nombre d’unités “emportables”. On pourrait imaginer faire du backtracking et chercher des solutions “plus optimales” depuis celles-ci en reculant dans la liste des éléments utilisés je pense, mais flemme là tout de suite 😛 ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/55 "2016-02-20T21:05:21Z")
La manière gloutonne est une façon de faire mais ne donne pas la meilleure solution loin de là. Le coùut du tri est négligeable à coté des autres méthode. Entre autres, en 36s > [@](#): > > 499.446751165=23.1362279621+77.9955179748+94.7937294632+53.8651860445 > +14.8421974342+0.823815509831+81.1865528156+66.6315851583+86.1719388021 > > real 0m35.596s (mais ça n’est pas la meilleure solution). Pour donner une indication, en se limitant à 5 minutes de calcul, j’ai trouvé `499.928271032=57.5346438343+17.0334454898+75.7969259544+20.9026319593 +62.9199411652+7.40644982461+52.8213197774+53.8651860445+31.8177186297 +30.7653326084+5.85383028871+68.3686480214+14.8421974342 real 4m52.506s ` Sinon, en allant jusqu’à 1 heure, j’ai trouvé `499.964120742=6.85180377081+3.02292807563+11.3861047321+5.14089910613 +0.971225682395+2.89972820541+4.98373837349+34.7356876877+85.1318409761 +78.872384595+3.01480164877+81.1865528156+86.1719388021+95.5944862711 ` ---
**Author:** ![BBT1](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/b/ecc23a/32.png) [@BBT1](https://www.debian-fr.org/u/BBT1)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/56 "2016-02-20T21:05:23Z")
J’obtient 499.999969 en 30s. Je trie la liste par ordre décroissant, et j’utilise une méthode proche de la recherche exhaustive en procédant avec une structure recursive classique mais en prenant soin d’utiliser les nombres les plus gros d’abord. Si il y en a que ça intéresse, je veux bien tenter une version multithread / multimachine en MPI. Le code en C: [code]#include \ #include \ #include \ #define N (100) // Nombre de flottants a comparer #define V (500.0) // Valeur dont la somme doit se rapprocher #define COMPUTATION\_TIME (30) // tps de calcul en s /\*\* Declarations \*\*/ int main(void); void init\_tab(float tab[]); void sort\_tab(float tab[], int debut, int fin); inline void swap(float \*a, float \*b); void print\_tab(float tab[]); typedef unsigned char set\_t[N/8 + ((N % 8 != 0) ? 1 : 0)]; typedef struct { set\_t values; float sum; } sum\_data\_t; inline void set\_add(set\_t \*s, int v); inline void set\_remove(set\_t \*s, int v); inline void set\_empty(set\_t \*s); inline int set\_present(set\_t \*s, int v); void set\_print(set\_t \*s, float tab[]); sum\_data\_t find\_sum(float tab[], sum\_data\_t data, int n, time\_t tmax); /\*\* Definitions \*\*/ int main(void) { float tab[N]; // Tableau contenant les reels a comparer time\_t t0 = time(NULL); srand(t0); time\_t tmax = t0 + COMPUTATION\_TIME; init\_tab(tab); sort\_tab(tab, 0, N-1); print\_tab(tab); sum\_data\_t data = { .sum = 0 }; set\_empty(&data.values); data = find\_sum(tab, data, 0, tmax); printf(“somme”); set\_print(&data.values, tab); printf(" = %f\n", data.sum); return EXIT\_SUCCESS; } void init\_tab(float tab[]) { int i; for (i=0 ; i\= fin) return; /\* le pivot est choisi au milieu du tableau _/ int ip = (fin - debut) / 2 + debut; /_ indice pivot _/ float vp = tab[ip]; /_ valeur pivot \*/ /\* on echange le pivot avec la fin du tableau \*/ tab[ip] = tab[fin]; ip = fin; int i = debut; while (i \< ip) { if (tab[i] \>= vp) { i++; } else { tab[ip] = tab[i]; tab[i] = tab[ip - 1]; ip–; } } tab[ip] = vp; sort\_tab(tab, debut, ip); sort\_tab(tab, ip + 1, fin); } inline void swap(float \*a, float \*b) { float tmp = \*a; \*a = \*b; \*b = tmp; } void print\_tab(float tab[]) { int i; for (i=0 ; i\= N) || (data.sum \>= V)) return data; sum\_data\_t d1 = data; if (time(NULL) \< tmax) { d1.sum += tab[n]; set\_add(&d1.values, n); d1 = find\_sum(tab, d1, n+1, tmax); } sum\_data\_t d2 = find\_sum(tab, data, n+1, tmax); if (d1.sum \>= V) { return d2; } else { if (d1.sum \> d2.sum) return d1; else return d2; } }[/code] La trace : `time ./sad 48.874928 48.794579 48.766930 48.435478 48.288498 47.163425 46.923443 46.731804 46.233017 44.243988 43.889679 43.883499 43.871532 43.487438 43.335075 42.619370 42.190098 41.717640 40.901173 40.723492 40.360466 39.882793 39.285011 38.566193 38.459301 37.471668 37.239227 36.526993 36.275585 35.775795 34.299057 34.295807 34.038166 32.455868 31.889019 31.517603 30.793783 30.662928 30.346117 29.661764 29.352058 28.760130 28.170591 28.122038 28.070105 26.945034 26.606070 25.989651 25.926979 25.615543 24.136974 24.108459 23.388412 23.149200 23.126448 22.988241 22.182993 21.517275 19.631130 18.020473 16.989527 16.362711 15.745818 15.287122 15.065371 14.144320 14.046489 13.988007 13.662770 13.226750 12.838037 12.642454 11.782660 11.520141 11.147648 10.911448 10.879205 10.288710 9.706027 9.521898 8.517546 8.290475 7.903265 7.838439 7.057403 6.685324 6.605367 4.563943 4.522942 3.762777 3.495317 3.265114 2.970361 2.549328 2.526348 2.143126 1.871138 1.297340 0.684354 0.584297 somme{48.874928, 48.794579, 48.766930, 48.435478, 48.288498, 47.163425, 46.923443, 46.731804, 46.233017, 24.108459, 11.147648, 8.290475, 7.903265, 6.685324, 4.563943, 3.265114, 2.526348, 1.297340, } = 499.999969 ./sad 19,11s user 10,46s system 99% cpu 29,752 total` ---
**Author:** ![BBT1](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/b/ecc23a/32.png) [@BBT1](https://www.debian-fr.org/u/BBT1)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/57 "2016-02-20T21:05:23Z")
Bon, à mon tour de poser un problème : On a une carte de la galaxie avec les coordonnées dans l’espace (x, y, z) de systèmes planétaires. Le but est de trouver les 2 systèmes les plus proches l’un de l’autre le plus rapidement possible. Les coordonnées de la carte vont chacune de -1.10^6 à +1.10^6 sur chaque coordonnée et il y a 10^5 planètes placées aléatoirement sur la carte. Enjoy 😃 ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/58 "2016-02-20T21:05:25Z")
[quote=“BBT1”]J’obtient 499.999969 en 30s. Je trie la liste par ordre décroissant, et j’utilise une méthode proche de la recherche exhaustive en procédant avec une structure recursive classique mais en prenant soin d’utiliser les nombres les plus gros d’abord. Si il y en a que ça intéresse, je veux bien tenter une version multithread / multimachine en MPI…[/quote] Je vais regarder ça mais utilise mes données (j’ai donné le lien) car là je ne peux pas comparer avec mes temps… (de plus je me suis gourré, c’est des valeurs entre 0 et 100.0) mais à vue de nez c’est plus efficace que ma méthode (je suis un peu déçu d’ailleurs 🙂) Voilà le pgm que j’ai fait: [code]type somme = {v:float;s:string};; (\* fusion de deux listes triées \*) let fusion = let rec boucle resultat l1 l2 = match l1,l2 with | [],\_ -\> resultat@l2 | \_,[] -\> resultat@l1 | (a::ls1),(b::ls2) when (a.v \< b.v) -\> (boucle (resultat@[a]) ls1 l2) | \_,(b::ls2) -\> (boucle (resultat@[b]) l1 ls2) in boucle [];; (\* on enlève les elts \> seuil \*) let tronque liste seuil = let rec boucle resultat liste\_en\_cours = match liste\_en\_cours with | (a::suite) when (a.v \<= seuil) -\> (boucle (resultat@[a]) suite) | \_ -\> resultat in (boucle [] liste);; let add e x = {v=x.v+.e;s=x.s^"+"^(string\_of\_float e)};; let rajoute liste elt seuil = (tronque (fusion liste (List.map (function x-\> add elt x) liste)) seuil);; (\* on tronque la liste de telle manière que deux éléments consécutifs vérifient a’\>(1+eps).a \*) let selection epsilon lst = let rec boucle elt\_en\_cours liste\_renvoyee liste = match liste with | [] -\> liste\_renvoyee | a::suite when a.v\>(1.0 +. epsilon)\*.elt\_en\_cours -\> (boucle a.v (liste\_renvoyee@[a]) suite) | a::suite -\> (boucle elt\_en\_cours liste\_renvoyee suite) in match lst with | [] -\> [] | a::suite -\> (boucle a.v [a] suite);; (\* on ajoute les éléments les uns après les autres \*) let variante\_eps\_b epsilon lst somme = let rec boucle liste reste n = match reste with | [] -\> List.hd (List.rev liste) | a::suite -\> print\_int n;print\_newline (); (boucle (selection epsilon (rajoute liste a somme)) suite (n-1)) in (boucle [{v=0.0;s=“0”}] lst (List.length lst));; let resolution\_eps\_b epsilon lst = (variante\_eps\_b (epsilon /. (float\_of\_int (List.length lst))) lst);; (\* pour faire une liste aléatoire \*) let rec rand\_list borne = function | 0 -\> [] | n -\> (Random.float borne)::(rand\_list borne (n-1));; let grosse\_liste = [ 76.6006173876 ; 53.2095327249 ; 62.8074649884 ; 6.11430589708 ; …];; 76.3344025048 ; 99.8239434767 ];; let res= (resolution\_eps\_b (float\_of\_string Sys.argv.(1)) grosse\_liste (float\_of\_string Sys.argv.(2)))in print\_string ((string\_of\_float res.v)^"="^res.s);; print\_newline ();; [/code] Je ne conserve que les sommes suffisamment éloignés les unes des autres, ça garantit un algorithme en O(n²/eps) et en pratique en O(n/eps), ça garantit aussi la marge d’erreur faite mais avec ces données c’est moins efficace. Il serait peut être meilleur en prenant des données étalées et un seuil plus grand (Il faudrait faire un test…) mais je pense qu’il restera moins efficace que le tien: Je trouve avec tes données `499.890758=0+46.731804+43.487438+38.566193+37.471668+36.526993+34.295807 +28.76013+28.122038+26.945034+25.926979+24.136974+22.182993+16.989527 +16.362711+15.745818+14.046489+13.988007+9.521898+6.685324+3.762777 +3.495317+2.970361+1.871138+1.29734 ` en 7mn et des brouettes. Comme quoi une bonne heuristique est meilleure qu’une approximation même controlée en pratique (alors qu’en théorie non…) ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/59 "2016-02-20T21:05:41Z")
Précision: ton algorithme est nettement meilleur dans les faits, j’ai essayé aussi avec la liste par ordre croissant: Tout d’abord la victoire de Caml sur le C (en fait je pense qu’il doit y avoir un souci dans ton code, ça n’est pas normal cette différence de performance, il faudrait le vérifier mais je n’ai pas trop le temps): Avec tes données, en 2s [quote]500.=48.874928+48.794579+48.76693+48.435478+48.288498+47.163425 +46.923443+46.731804+46.233017+43.335075+14.046489+4.563943 +3.762777+3.495317+0.584297 real 0m2.016s Les sommes successives trouvées: francois@bling:~/Caml$ time ./Osacados2ibis 1.0 500.0 499.890404=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+44.243988+24.136974+1.29734 499.987628=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+44.243988+23.388412+2.143126 499.993659=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+44.243988+22.988241+2.549328 499.999823=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+44.243988+22.988241+1.871138+0.684354 499.999922=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+44.243988+10.879205+6.605367+4.563943+3.495317 499.99997=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+44.243988+9.706027+7.903265+3.265114+2.526348+2.143126 499.999971=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+43.889679+10.28871+8.290475+3.495317+2.526348+1.29734 499.999988=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+43.871532+11.147648+9.521898+3.265114+1.29734+0.684354 499.999996=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443 +46.731804+46.233017+43.487438+10.28871+6.685324+3.495317+3.265114+1.29734+0.684354 +0.584297 500.=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443+46.731804 +46.233017+43.335075+14.046489+4.563943+3.762777+3.495317+0.584297 [/quote] Le programme: [code]type somme = {v:float;s:string};; (\* tri d’une liste de réel _) let rec tri\_rapide l = let rec partage x l1 l2 = function | [] -\> (l1,l2) | y::ll -\> if x \< y (_ mettre \> pour le tri décroissant \*) then (partage x l1 (y::l2) ll) else (partage x (y::l1) l2 ll) in match l with | [] -\> [] | x::ll -\> let (l1,l2) = (partage x [] [] ll) in (tri\_rapide l1)@[x]@(tri\_rapide l2);; let maxi = ref {v=0.0;s=“0”};; let temps = (float\_of\_string Sys.argv.(1));; let traite s = if (s.v \> (!maxi).v) then ( maxi:=s;print\_float s.v;print\_string ("="^s.s);print\_newline ());; let add e x = {v=x.v+.e;s=x.s^"+"^(string\_of\_float e)};; let rec cherche sol reste butee = match reste with | [] -\> (traite sol);if (Sys.time () \>= temps) then failwith “fini” | a::suite when a \> butee -\> (cherche sol suite butee) | a::suite -\> ((cherche (add a sol) suite (butee -. a)); (cherche sol suite butee));; let grosse\_liste = [ 76.6006173876 ; 53.2095327249 ; 62.8074649884 ; … 5.87672187988 ; 76.3344025048 ; 99.8239434767 ];; cherche (!maxi) (tri\_rapide grosse\_liste) (float\_of\_string Sys.argv.(2));; [/code] En une seconde [quote]499.999672721=0.823815509831+0.971225682395+2.73708440896+2.89972820541 +3.01480164877+3.02292807563+4.98373837349+5.14089910613+5.85383028871 +5.87672187988+6.11430589708+6.85180377081+7.40644982461+11.3861047321 +12.0469895844+12.417446767+13.3202226366+13.6029593057+14.6877222571 +14.8421974342+15.7364627081+17.0334454898+20.9026319593+23.1362279621 +23.2963494749+26.313173451+30.5372024126+31.8177186297+33.9888211399 +36.5765033284+39.8388409985+52.8213197774 real 0m1.009s ou par ordre décroissant 499.999993256=99.8239434767+99.7235716825+99.3410284839+98.3687380235 +78.7359242322+13.3202226366+5.87672187988+3.01480164877 +0.971225682395+0.823815509831 real 0m0.662s [/quote] En 10s [quote]499.999969477=0.823815509831+0.971225682395+2.73708440896+2.89972820541 +3.01480164877+3.02292807563+4.98373837349+5.14089910613+5.85383028871 +5.87672187988+6.11430589708+6.85180377081+7.40644982461+11.3861047321 +12.0469895844+12.417446767+13.3202226366+13.6029593057+14.6877222571 +14.8421974342+15.7364627081+17.0334454898+20.9026319593+23.1362279621 +23.2963494749+30.7653326084+34.7356876877+34.8696397735+37.3201741611 +45.7887165638+68.4143256997 real 0m11.440s et par ordre décroissant 499.999999309=0+99.8239434767+99.7235716825+99.3410284839+98.3687380235 +45.7887165638+29.4346057232+12.417446767+6.11430589708 +5.14089910613+3.02292807563+0.823815509831 real 0m13.496s [/quote] Par ordre croissant, c’est moins bon ce qui se comprend facilement en fait en 1mn [quote]499.999994849=0.823815509831+0.971225682395+2.73708440896 +2.89972820541+3.01480164877+3.02292807563+4.98373837349+5.14089910613 +5.85383028871+5.87672187988+6.11430589708+6.85180377081+7.40644982461 +11.3861047321+12.0469895844+12.417446767+13.3202226366+13.6029593057 +14.6877222571+14.8421974342+15.7364627081+17.0334454898+20.9026319593 +23.1362279621+23.2963494749+52.0153159277+52.8213197774+62.8074649884 +84.2498011722 real 0m50.070s[/quote] en 3mn [quote]499.999997615=0+0.823815509831+0.971225682395+2.73708440896+2.89972820541 +3.01480164877+3.02292807563+4.98373837349+5.14089910613+5.85383028871 +5.87672187988+6.11430589708+6.85180377081+7.40644982461+11.3861047321 +12.0469895844+12.417446767+13.3202226366+13.6029593057+14.6877222571 +14.8421974342+15.7364627081+17.0334454898+20.9026319593+23.2963494749 +32.6907368819+33.9888211399+42.2539841857+78.872384595+87.2242057917 real 3m17.307s [/quote] et par ordre décroissant en 30s: [quote]499.999999309=0+99.8239434767+99.7235716825+99.3410284839+98.3687380235 +45.7887165638+29.4346057232+12.417446767+6.11430589708+5.14089910613 +3.02292807563+0.823815509831 [/quote] et en mojns de 2mn [quote]499.999999554=0+99.8239434767+99.7235716825+99.3410284839+98.3687380235 +17.0334454898+15.7364627081+14.8421974342+14.6877222571+13.3202226366 +12.417446767+6.11430589708+5.85383028871+2.73708440896 real 1m47.338s [/quote] Bon, le truc 3D maintenant… mais après mes copies. ---
**Author:** ![BBT1](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/b/ecc23a/32.png) [@BBT1](https://www.debian-fr.org/u/BBT1)\ **Post date:** [Février 20, 2016, 9:05 UTC](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239/60 "2016-02-20T21:05:44Z")
Est-ce que tu as une différence de temps d’exécution significative entre le cas où tu fournis statiquement les données et le cas ou le programme les acquiert dynamiquement ? Je me disais qu’en théorie, le compilo pourrait être assez malin pour précalculer un max de valeurs… Mais bon, le temps de compilation s’en resentirai forcément… J’avais testé 30 sec au hasard (le temps que j’étais prêt à attendre devant mon écran quoi) mais on peut sûrement faire mieux en compilant en -O3 et en limitant le nombre d’appel à time() (ce que je n’ai pas fait). Si je suis motivé je fais un petit bench ce soir 😉 [Page précédente](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239.md?page=2) [Page suivante](https://www.debian-fr.org/t/coder-dans-plusieurs-langages/23239.md?page=4)