[quote=“Hoshin”]
Ceci dit fran, je ne sais pas ce que tu en penses mais perso j’ai découvert PERL en stage et je le trouve fort sympatique aussi =). L’article wikipedia dessus le désigne comme la “tronçonneuse suisse des langages de programmation” et en un sens je suis assez d’accord, rien que pour la gestion “gratuite” des listes et des hashtables 
Ceci dit il me semble qu’il en va de même pour Ocaml, c’est plus dans la façon de concevoir le programme que l’on change d’approche au final.[/quote]
Il n’y a pas une programmation en PERL mais des programmations en Perl, en fait Perl est très varié et chacun pourra le programmer à sa façon en Perl. Par contre, Perl est trop tolérant pour être apte à de gros projets: Un programme Perl peut tourner sans faire ce qu’on croit qu’il devrait faire, c’est ennuyeux car ça rend le débuguage très dur.
[quote=“MisterFreez”]Même code que ma version C++, mais en Java. L’API File de java est vraiment agréable à utiliser.
[/quote]
Arf j’avais l’intention de mettre la version Java, tant pis j’ai été trop lent 
+1 pour File !
[quote=“fran.b”][quote=“Hoshin”]
Ceci dit fran, je ne sais pas ce que tu en penses mais perso j’ai découvert PERL en stage et je le trouve fort sympatique aussi =). L’article wikipedia dessus le désigne comme la “tronçonneuse suisse des langages de programmation” et en un sens je suis assez d’accord, rien que pour la gestion “gratuite” des listes et des hashtables Ceci dit il me semble qu’il en va de même pour Ocaml, c’est plus dans la façon de concevoir le programme que l’on change d’approche au final.[/quote]
Il n’y a pas une programmation en PERL mais des programmations en Perl, en fait Perl est très varié et chacun pourra le programmer à sa façon en Perl. Par contre, Perl est trop tolérant pour être apte à de gros projets: Un programme Perl peut tourner sans faire ce qu’on croit qu’il devrait faire, c’est ennuyeux car ça rend le débuguage très dur.[/quote]
Je suis d’accord et mais malgrès que j’apprécie beaucoup perl, j’ai du mal avec leur concept objet (initial pas Moose) qui est très limité.
Allez, un exercice pour compléter l’idée d’Ashgenesis (je l’ai donné à mes élèves): On a un damier N x N, chaque case, identifié par le couple (i,j) (i=numéro de ligne, j= numéro de colonne) a une altitude donnée par le contenu de M(i,j) (M est un tableau de réels aléatoires compris entre 0 et 1).
Un case a quatre cases voisines immédiates (on ne compte pas les cases diagonale, les voisins de i,j sont (i-1),j (i+1),j i,(j+1) et i,(j-1)), 3 si on est au bord et 2 si on est à un coin. Une marche d’escalier est constituée de 2 cases voisines, l’une étant strictement plus basse que l’autre. Il s’agit de trouver la longueur du plus grand escalier que l’on puisse faire.
Le programme est sommaire:
[code]mardi 17 novembre 2009, 16:25:17 (UTC+0100)
francois@bling:~/Caml$ date ; ./escalier 3500 ;date
mardi 17 novembre 2009, 16:25:28 (UTC+0100)
16
mardi 17 novembre 2009, 16:27:14 (UTC+0100
francois@bling:~/Caml$ time ./escalier 3500
16
real 1m46.457s
user 0m57.408s
sys 0m0.273s
francois@bling:~/Caml$ time ./escalier 1000
14
real 0m8.523s
user 0m4.210s
sys 0m0.024s
francois@bling:~/Caml$ time ./escalier 500
13
real 0m2.125s
user 0m1.046s
sys 0m0.004s
francois@bling:~/Caml$ time ./escalier 100
10
real 0m0.104s
user 0m0.099s
sys 0m0.003s
francois@bling:~/Caml$
[/code]J’ai mis les temps d’éxécution pour donner une indication (le programme est en N²). À titre d’indicatif et juste histoire de mettre la pression :
francois@bling:~/Caml$ grep -c "" escalier.ml
32
francois@bling:~/Caml$ grep -c "^$" escalier.ml
2
francois@bling:~/Caml$
Donc le programme a 32 lignes dont 2 lignes vides.
Voilà, ça va occuper…
Réponse à M3t4linux:
Oui c’est verbeux car l’analyse en objets avant programmation est plus longue mais la maintenance du code c’est du gâteau, en non objet la programmation est souvent séquentielle.
Passer du séquentiel en objet c’est un peu passer de la 2D à la 3D.
Mon code n’est pas parfait, j’ai fait ça rapidement.
J’ai créé deux classes, une pour dire le contenu d’un dossier (Adir) et l’autre (Readdir) pour manipuler ces objets.
J’ai programmé en objective C sous linux avant qu’Apple ne le récupère pour son OS X (XCode). j’ai osé espéré un
noyau en objective C après l’échec en C++. 
Objective C c’est vraiment du plaisir contrairement au C que je trouve lourd pour de gros projets et C++ bordélique
avec son héritage multiple entre autre…
Pour plus d’infos: http://www.gnustep.org/resources/documentation/ObjectivCBook.pdf
(pourrait on avoir des rennes avec le père Noël?)
[quote=“fran.b”]Allez, un exercice pour compléter l’idée d’Ashgenesis (je l’ai donné à mes élèves): On a un damier N x N, chaque case, identifié par le couple (i,j) (i=numéro de ligne, j= numéro de colonne) a une altitude donnée par le contenu de M(i,j) (M est un tableau de réels aléatoires compris entre 0 et 1).
Un case a quatre cases voisines immédiates (on ne compte pas les cases diagonale, les voisins de i,j sont (i-1),j (i+1),j i,(j+1) et i,(j-1)), 3 si on est au bord et 2 si on est à un coin. Une marche d’escalier est constituée de 2 cases voisines, l’une étant strictement plus basse que l’autre. Il s’agit de trouver la longueur du plus grand escalier que l’on puisse faire.
[/quote]
Je n’ai pas vraiment compris l’intitulé de ton problème…
Lorsque je le lis, plusieurs questions apparaisent:
- Où est l’interet de ton tableau de réels aléatoires?
- Ton escalier peut dériver comme ça:
_
|_
|_
_|
_|
|______
|ou pas ?
Est-il unidirectionnel ou peut-il revenir en arrière?
[quote=“L0u!$”][quote=“fran.b”]Allez, un exercice pour compléter l’idée d’Ashgenesis (je l’ai donné à mes élèves): On a un damier N x N, chaque case, identifié par le couple (i,j) (i=numéro de ligne, j= numéro de colonne) a une altitude donnée par le contenu de M(i,j) (M est un tableau de réels aléatoires compris entre 0 et 1).
Un case a quatre cases voisines immédiates (on ne compte pas les cases diagonale, les voisins de i,j sont (i-1),j (i+1),j i,(j+1) et i,(j-1)), 3 si on est au bord et 2 si on est à un coin. Une marche d’escalier est constituée de 2 cases voisines, l’une étant strictement plus basse que l’autre. Il s’agit de trouver la longueur du plus grand escalier que l’on puisse faire.
[/quote]
Je n’ai pas vraiment compris l’intitulé de ton problème…
Lorsque je le lis, plusieurs questions apparaisent:
- Où est l’interet de ton tableau de réels aléatoires?[/quote]
C’est lui qui indique l’altitude des cases au début. «a une altitude donnée par le contenu de M(i,j) …».
[quote]
- Ton escalier peut dériver comme ça:
_
|_
|_
_|
_|
|______
|ou pas ?
Est-il unidirectionnel ou peut-il revenir en arrière?[/quote]
Il peut aller dans tous les sens, seule contrainte, les marches doivent descendre.
Exemple:M=
[|[|0.884322984327; 0.0520026295247; 0.795264828825|];
[|0.811461626626; 0.862344519674; 0.31882802132|];
[|0.898239660449; 0.248499153757; 0.286820504692|]|]
La longueur maximal est 3 (3 sauts de marches soit 4 cases), par exemple
(lire 4->"->2->1)
_ _ _
_ 4 3
_ 1 2Tu ne peux pas revenir en arrière puisque ça t’obligerait à remonter.
Autre exemple avec n = 4:
[|[|0.887778006775; 0.436275326685; 0.381016838942; 0.53834099456|];
[|0.288193368793; 0.707981481566; 0.239922144359; 0.837537678392|];
[|0.850175907176; 0.200143617831; 0.32454786688; 0.40751065869|];
[|0.104135604194; 0.780965171522; 0.279165471898; 0.028625619634|]|]
tu trouves 5 avec
_ _ _ _
_ _ _ 5
_ _ 3 4
_ _ 2 1[quote=“fran.b”]Allez, un exercice pour compléter l’idée d’Ashgenesis (je l’ai donné à mes élèves): On a un damier N x N, chaque case, identifié par le couple (i,j) (i=numéro de ligne, j= numéro de colonne) a une altitude donnée par le contenu de M(i,j) (M est un tableau de réels aléatoires compris entre 0 et 1).
Un case a quatre cases voisines immédiates (on ne compte pas les cases diagonale, les voisins de i,j sont (i-1),j (i+1),j i,(j+1) et i,(j-1)), 3 si on est au bord et 2 si on est à un coin. Une marche d’escalier est constituée de 2 cases voisines, l’une étant strictement plus basse que l’autre. Il s’agit de trouver la longueur du plus grand escalier que l’on puisse faire.
[…]
Donc le programme a 32 lignes dont 2 lignes vides.
Voilà, ça va occuper…[/quote]
Je débute en Python, j’en suis à 54 lignes, dont 6 lignes vides.
[code]#!/usr/bin/python
-- coding:utf8 --
from random import random
N = 3500
Génération matrice avec nombres aléatoires
M = N*[0]
for i in range(N): M[i] = N*[0]
for i in range(N):
for j in range(N): M[i][j] = random()
Parcours de la matrice depuis le point de départ fournit
def parcours(i, j):
global COUNT, MAX
BLOCK = False
# Vers la droite (j+1)
if j+1<N and M[i][j] > M[i][j+1]:
COUNT+=1
parcours(i, j+1)
COUNT-=1
else: BLOCK = True
# Vers le bas (i+1)
if i+1<N and M[i][j] > M[i+1][j]:
BLOCK = False
COUNT+=1
parcours(i+1, j)
COUNT-=1
else: BLOCK = True
# Vers la gauche (j-1)
if (i-1)>=0 and M[i][j] > M[i][j-1]:
BLOCK = False
COUNT+=1
parcours(i, j-1)
COUNT-=1
else: BLOCK = True
# Vers la haut (i-1)
if (i-1)>=0 and M[i][j] > M[i-1][j]:
BLOCK = False
COUNT+=1
parcours(i-1, j)
COUNT-=1
else: BLOCK = True
# Mémorisation du maximum dès qu'on est dans une impasse
if BLOCK and MAX < COUNT: MAX = COUNT
Lancement de la moulinette
MAX = 0
COUNT=0
for i in range(N):
for j in range(N): parcours(i,j)
print “\nSCORE MAXIMUM = %s” % MAX[/code]
Ça doit pas être super optimisé aussi Mais avec une grille de 3500x3500 j’obtiens :
[code]time ./exo-escalier.py
SCORE MAXIMUM = 14
./exo-escalier.py 121.21s user 0.35s system 99% cpu 2:01.66 total[/code]
Salutations,
J’ai testé ton script sommairement, Keldath, qui semble correct.
J’aurais une chose à ajouter cependant :
# Vers la haut (i-1)
if (i-1)>=0 and M[i][j] > M[i-1][j]:
BLOCK = False
COUNT+=1
parcours(i-1, j)
COUNT-=1
else: BLOCK = TrueEt une chose à corriger :
# Vers la gauche (j-1)
if (j-1)=0 and M[i][j] > M[i][j-1]:Bien à vous tous.
Hello,
EDIT : Je n’ai rien dit, tu as raison vapula !
[quote]Et une chose à corriger :
[code]
Vers la gauche (j-1)
if (j-1)=0 and M[i][j] > M[i][j-1]:
[/code][/quote]
Ah oui, merci, j’avais laissé un i en trop 
Mais je te corrige à mon tour, c’est ‘>=’ et non ‘=’. Faute de frappe ?
Ton programme est de complexité largement supérieur à N², pour te donner une idée, si je prends Ocaml (nettement plus efficace que Camllight à la compilation), j’obtiens la réponse pour n=1000 en 7.091922s (contre 20 pour camllight), pour n=1500 en 15.899582s, n= 2000 en 28.2897s, n= 3000 en 63.920283s, n= 4000 en 113.5567s et n=5000 en 178.013s (en gros tu quadruples le temps d’exécution lorsque tu doubles n).
Pour tester ton programme prend n=5000, la réponse doit venir dans les 3 minutes.
Rq: Compte tenu que les escaliers ont une longueur de l’ordre de 16-17 au maximum, ça limite l’importance de ce que je viens de dire (c’est une complexité au pire cas) mais tu peux rendre facilement ton programme 50 fois plus rapide au moins.
Dommage que je sois une buse en algo Mais ce cas pratique me donne une raison de m’y replonger pour progresser.
Je l’ai relancé sur ma machine de stage (un AMD Sempron, celle utilisée plus haut était un C2D, mais ça doit pas changer grand chose non plus), j’obtiens donc pour N=5000 :
[code]time ./exo-escalier.py
SCORE MAXIMUM = 14
real 16m24.937s
user 15m12.769s
sys 0m1.204s[/code]
Donc le passage de 3500 à 5000 s’est traduit par un temps passant de 121s à 16m24.937s = 985s, tu as
(985/121)=(5000/3500)^(5,8), ton programme est en gros en N^5,8 (estimation très grossière, je le sens plutôt exponentiel).
si ton programme était en N², tu devrais avoir un temps de
121*(5000/3500)²=246s soit 4’ 6" (4m6s).
Tu refais plein de calcul déjà fait, essaye de le revoir.
[quote=“fran.b”]Tu refais plein de calcul déjà fait, essaye de le revoir.[/quote]La génération de la matrice déjà, je pense la parcourir trop de fois. Je regarde ça en détail dès que j’ai du temps !
Fais gaffe à ce que tu calcul Keldath. J’ai déjà ma version qui marche en C++ et qui a des perf’ plutôt bonnes sur mon wind (Atom 270). Par contre j’ai du mal si la matrice grandi trop c’est mort, j’ai fais un test avec 35 000 et le programme plante. Il faut ajouter des mémoires tampon si je veux que ça marche. Je laisse Keldath chercher un peu, je pofine mon code pour qu’il respecte un peu mieux le paradigme objet (et peut être améliorer les perf’ avec de la parallélisation) puis vous file mon code (demain je pense).
En tout cas merci fran.b, l’exo m’a pas mal plu.
Je vais lancer 20000 mais ça devrait prendre 40 minutes environ (90 pour 30000) mais il y a le souci de la mémoire…
[code]francois@bling:~/Caml$ time ./Oesc 10000
15
real 10m1.455s
user 5m18.313s
sys 0m2.153s
[/code]
Edit: Ça swappe énormément, pas assez de RAM apparemment du coup la machine rame, j’arrête…
Pareil mon miens j’ai fais le calcul à N=35000, mon programme tente d’allouer plus de 12Go, le bad_alloc arrive vite.
[quote=“MisterFreez”]Fais gaffe à ce que tu calcul Keldath.[/quote]J’ai compris (du moins je crois :p). Le problème est que je pars dans une direction, et une fois bloqué, je relance le truc avec comme point de départ une des directions déjà parcourues… je vérifie le même chemin plusieurs fois pour rien.
Reste à corriger, peut-être ce soir sinon ça ne sera pas avant demain (je ne vois pas encore trop comment faire, à part une seconde matrice pour mémo via un booléen les points déjà visités ?).
(si j’ai vu juste sur mon soucis, hésite pas à poster ta solution C++ MisterFreez)
Donc voila pour les benchmarck :% time ./escalier 10000
16
./escalier 10000 120,82s user 8,32s system 56% cpu 3:47,15 total
% time ./escalier 20000
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
zsh: abort ./escalier 20000
./escalier 20000 0,00s user 0,00s system 2% cpu 0,161 total
[134]% time ./escalier 15000
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
zsh: abort ./escalier 15000
./escalier 15000 0,00s user 0,00s system 49% cpu 0,008 total
[134]% time ./escalier 12000
15
./escalier 12000 183,70s user 20,84s system 45% cpu 7:32,40 total
Et voici mon code :
[code]#include
#include
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
namespace{
typedef std::vector<std::pair<double,short> > tableau;
class Plateau{
public:
Plateau(const int taille){
this->taille = taille;
tab = new tableau(taille*taille);
//srandom(time(NULL));
srandom(1);
for(tableau::iterator i = tab->begin(); i < tab->end(); ++i){
i->first = (double)random() / (double)RAND_MAX;
i->second = -1;
}
} // genTab()
short plusLongEsc(void){
short result = 0, tmp;
for(tableau::iterator I = tab->begin(); I < tab->end(); ++I){
tmp = tailleChem(I);
if(result < tmp){
result = tmp;
}
}
return result;
}
private:
short tailleChem(const tableau::iterator I){
using namespace std;
short size = 0, tmp;
if(I->second != -1) return I->second;
if(I > tab->begin() && (I-1)->first < I->first){
size = tailleChem(I-1) + 1;
}
if(I+1 < tab->end() && (I+1)->first < I->first){
tmp = tailleChem(I+1) + 1;
if(tmp > size) size = tmp;
}
if((I-taille) > tab->begin() && (I-taille)->first < I->first){
tmp = tailleChem(I-taille) + 1;
if(tmp > size) size = tmp;
}
if(I+taille < tab->end() && (I+taille)->first < I->first){
tmp = tailleChem(I+taille) + 1;
if(tmp > size) size = tmp;
}
I->second = size;
return size;
} // tailleChem()
int taille;
tableau *tab;
};
} // namespace
int main (int argc, char ** argv){
using namespace std;
int taille = 5;
if(2 == argc){
taille = atoi(argv[1]);
}
Plateau p = Plateau(taille);
cout << p.plusLongEsc() << endl;
return 0;
} // end of main()[/code]
Ma matrice contiens pour chaque case deux valeurs la hauteur et la taille du plus long chemin possible à partir de celle-ci. Tu ne re-calcul pas deux fois le même chemin et tu te retrouve à ne faire qu’un seul calcul par case, d’où la complexité en N².
Si tu veut faire des recherches sur ce genre de technique ça s’appelle la programmation dynamique (j’ai étudié ça l’an dernier).
Une méthode pour paralléliser ça c’est de créer un pool de thread (autant que d’unité de calcul de la machine) et lors de la boucle principale, appelé un thread sur la première case et un sur la dernière et ainsi de suite. Et poser des vérous sur chaque case.
C’est une solution envisageable, Keldath. C’est de cette manière que pour N=5000, je passe de 10’ à 6’ (environ).
Par contre, fran.b, tu parles de temps de réponse et de complexité.
(Arrete moi si je me trompe quelquepart.)
Pour un nombre d’éléments à analyser N1, on obtient une durée T1,
Pour un nombre d’éléments à analyser N2, on obtient une durée T2.
(Cette formulation me semble suspecte.)
Tu obtiens une estimation grossière (selon tes termes) en appliquant la formule :
i = (N2/N1)^x[/i]
A partir de x, tu détermines la complexité (N^x).
Quel est l’objectif, en terme de complexité, d’un point du vue général?
Faut-il avoir x le plus proche de 1 (à 1, la durée est proportionnelle au nombre d’éléments)?
(Dans le cas présent, on devrait avoir x proche de 2, car on traite un tableau à 2 dimensions.)