Java

Pb d'utilisation des classes enveloppes + algo de tri

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Pb d'utilisation des classes enveloppes + algo de tri

Roco

Salut :hello:

Voilà mon pb. J'ai tenté de "convertir" un algo de tri rapide (version à pile) de C++ vers Java.

Ma contrainte m'imposait d'utiliser une pile standard de Java (java.util.Stack). Mais voilà, il faut bien évidemment remplir cette pile avec des objets, j'ai du me servir (mal) de la classe enveloppe Integer car cette algo sensé être plus rapide que le tri rapide (version récursive) me donne un temps pourtant nettement moins bon.

Bon je n'utilise pas du tout la même base d'algo dans les deux. Donc il faudra que pour bien pouvoir les comparer que je les harmonise. Mais en attendant je soupsonne quand même ma conversion de code et mes conversions de type.

Voilà la source en C++ :

Code :

void tritab :: tri_rapide() {
std::stack<int> stack1;
int p;
int d = 0;
int f = taille - 1;
while(true) {
while(f-d>0) {
p = repartition(d, f);
if( (p - d) < (f - p) ) {
stack1.push(p+1);
stack1.push(f);
f = p - 1;
}
else {
stack1.push(d);
stack1.push(p-1);
d = p + 1;
}
}
if(stack1.empty()) {
break;
}
f = stack1.top();
stack1.pop();
d = stack1.top();
stack1.pop();
}
}

Et ma conversion en Java

Code :

public void triRapide2() {
Stack maPile = new Stack() ;
Object objet;
int p;
int d = 0;
int f = dimension - 1;
while(true) {
while(f - d > 0) {
p = repartition(d, f);
if( (p - d) < (f - p) ) {
maPile.push( new Integer(p+1));
maPile.push(new Integer(f));
f = p - 1;
}
else {
maPile.push(new Integer(d));
maPile.push(new Integer(p-1));
d = p + 1;
}
}
if( maPile.empty() ) {
break;
}
objet = maPile.pop();
f = ((Integer)objet).intValue();
objet = maPile.pop();
d = ((Integer)objet).intValue();
}
}

Bon donc ça marche bien (encore heureux) mais nivo perfs c à chier.

EDIT : put1 fais chier mon indentation a merdé. Tant pis flemme de remettre ça au propre :sweat:

Message édité par Roco le 29-11-2002 à 23:09:50

---------------
[:roco] Un chtit café et hop ça repart !

Publicité

kadreg

profil: Utilisateur

Roco a écrit a écrit :

Salut :hello:

Bon donc ça marche bien (encore heureux) mais nivo perfs c à chier.

Tout java défini en une phrase

---------------
brisez les rêves des gens, il en restera toujours quelque chose... -- laissez moi troller sur discu !

Roco

kadreg a écrit a écrit :

Tout java défini en une phrase

Tu peux sortir [:xmamatx]

Nan sérieux. Algorithmiquement ce code devrait être le plus rapide de mes tris (tous codé en Java :fou: ) or ce n'est pas le cas. Donc soit mon algo est faux (je vérifie cela ce WE), soit mes conversions sont vraiment mal faites (et je pense que c'est le cas).

++

---------------
[:roco] Un chtit café et hop ça repart !

charlene

Verba volant, scripta manent

Roco a écrit a écrit :

Tu peux sortir [:xmamatx]

Nan sérieux. Algorithmiquement ce code devrait être le plus rapide de mes tris (tous codé en Java :fou:

) or ce n'est pas le cas. Donc soit mon algo est faux (je vérifie cela ce WE), soit mes conversions sont vraiment mal faites (et je pense que c'est le cas).

++

on peut avoir des exemples de performance qu'on puisse juger

---------------
Défiance (ou méfiance) est mère de sûreté

leirn

A.D.I.D.A.S.

algorithmikement c pas comme ca kon ecrit un tri

recherche dicotomik power: N log (N), normalement le plus rapide

tri a bulles (celebre N²)

la complexité du tien c koi? (pas envi de la calculer)

---------------
"Je brandirai une épée d'orichalque, je m'assouvirai sur des Templiers." | "Avec dans son sillage l'Ombre du Diable, Leirn appelait les morts pour une danse macabre et déchainaît les horreurs de la nuit..."

leirn

A.D.I.D.A.S.

charlene a écrit a écrit :

on peut avoir des exemples de performance qu'on puisse juger

une perf ca se fais pas au juger comme ca... suivant ce ke fais la machine ailleurs, ce kya en ram, etc... ya des variations... normalement fo relancer la machine entre chak bench sur un algo...

mais une complexité ca se mesure normalement, saf ke la, je suis en week end

Roco

charlene a écrit a écrit :

on peut avoir des exemples de performance qu'on puisse juger

Volontiers voilà mes sources mais bon jvois pas trop l'intérêt par rapport à ma question...

http://algorithmique.free.fr/sources/

---------------
[:roco] Un chtit café et hop ça repart !

charlene

Verba volant, scripta manent

Leirn a écrit a écrit :

une perf ca se fais pas au juger comme ca... suivant ce ke fais la machine ailleurs, ce kya en ram, etc... ya des variations... normalement fo relancer la machine entre chak bench sur un algo...

mais une complexité ca se mesure normalement, saf ke la, je suis en week end

oui merci je suis au courant !
Mais le monsieur dit qu'il est pas content des performances, sans aucun chiffre pour appuyer son propos. alors bon, c'est dur de se faire une idée

Message édité par charlene le 29-11-2002 à 23:48:22

---------------
Défiance (ou méfiance) est mère de sûreté

leirn

A.D.I.D.A.S.

charlene a écrit a écrit :

oui merci je suis au courant !
Mais le monsieur dit qu'il est pas content des performances, sans aucun chiffre pour appuyer son propos. alors bon, c'est dur de se faire une idée

vi, d'ailleurs ta vu, je lui ai reclamé dess chiffres

leirn

A.D.I.D.A.S.

Roco a écrit a écrit :

Volontiers voilà mes sources mais bon jvois pas trop l'intérêt par rapport à ma question...

http://algorithmique.free.fr/sources/

tu veux pas plutot nous donenr la complexité directement au lieu des sources?

fais une recherche sur des algo de tri par dichotomie sinon, je pens epas kil y ait mieux ke O(N*log(N)) (remark, si kkun a je suis tres interressé)

Publicité

Roco

Leirn a écrit a écrit :

tu veux pas plutot nous donenr la complexité directement au lieu des sources?

fais une recherche sur des algo de tri par dichotomie sinon, je pens epas kil y ait mieux ke O(N*log(N)) (remark, si kkun a je suis tres interressé)

Jpeux vous donner la complexité bien sûr mais c po mon problème!

Mon problème c que sur papier, mon algo tri rapide à pile devrait être plus rapide que mon algo tri rapide récursif et que là c po le cas. D'ailleurs si vous voulez rentrer à fond dans les détails, mon algo de tri par tas devrait être le meilleur de tous, or il se fait battre par mon algo de tri rapide. Sinon l'insertion dichotomique c le meilleur tri pour un faible nombre d'éléments (<100000) .Après c les tri rapides et par tas (voire ptet fusion) qui remportent.

---------------
[:roco] Un chtit café et hop ça repart !

leirn

A.D.I.D.A.S.

Roco a écrit a écrit :

Jpeux vous donner la complexité bien sûr mais c po mon problème!

Mon problème c que sur papier, mon algo tri rapide à pile devrait être plus rapide que mon algo tri rapide récursif et que là c po le cas. D'ailleurs si vous voulez rentrer à fond dans les détails, mon algo de tri par tas devrait être le meilleur de tous, or il se fait battre par mon algo de tri rapide. Sinon l'insertion dichotomique c le meilleur tri pour un faible nombre d'éléments (<100000) .Après c les tri rapides et par tas (voire ptet fusion) qui remportent.

dichotomik perd en desosu de 4 aussi je kroi
sur papier avec les memes actions? pit etre ya des choses kil fait plus lentement ke d'autres? (je cherche hein)

souk

Tourist

juste pour dire qu'effectivement le tri en tas est le meilleur en moyenne, mais le tri rapide est meilleur sur les cas usuels d'utilisation...
et puis il y a des tris en complexite O(n), mais y a des contraintes sur les elements a trier bien sur (genre trier un tableau de n entiers distincts deux a deux strictement positifs inferieurs a p (avec p>n cela va de soi)

ok je sors :bounce:

benou

à mon avis, le problème vient du fait que tu utilises des Integer : tu n'arrêtes pas d'instancier des Integer tout au long de ton algo. Quand on veut gagner en perfs en java, on essaye de limiter le nomber de création d'objet

benou

et puis moi si je cherchais des perfs, j'utiliserai pas une Stack : ca hérite de Vector, et donc, c'est un objet synchronizé => pas performant !

je sais que tu as dit que c'était une de tes contraintes mais bon ...

Roco

benou a écrit a écrit :

à mon avis, le problème vient du fait que tu utilises des Integer : tu n'arrêtes pas d'instancier des Integer tout au long de ton algo. Quand on veut gagner en perfs en java, on essaye de limiter le nomber de création d'objet

C'est à mon avis aussi le gros problème...

---------------
[:roco] Un chtit café et hop ça repart !

Roco

benou a écrit a écrit :

et puis moi si je cherchais des perfs, j'utiliserai pas une Stack : ca hérite de Vector, et donc, c'est un objet synchronizé => pas performant !

je sais que tu as dit que c'était une de tes contraintes mais bon ...

Je fais quoi alors. Bon je peux éventuellement implémenter moi-même une pile d'entiers (si j'explique bien mes raisons, ça devrait passer). A ton avis c la meilleur solution?

---------------
[:roco] Un chtit café et hop ça repart !

benou

si tu cherche les perfs, sert toi d'un bête tableau et d'un entier pour connaitre l'index du sommet de la pile : en plus tu connais la taille du tableau à instancier => c'est ce qu'il y a de plus efficace. Et puis c'est pas bien compliqué en plus ...

Roco

benou a écrit a écrit :

si tu cherche les perfs, sert toi d'un bête tableau et d'un entier pour connaitre l'index du sommet de la pile : en plus tu connais la taille du tableau à instancier => c'est ce qu'il y a de plus efficace. Et puis c'est pas bien compliqué en plus ...

Tu pourrais m'expliquer (si tu avais deux ou trois liens en plus ça serait pas mal aussi) pkoi ces implémentations sont si peu performantes

---------------
[:roco] Un chtit café et hop ça repart !

LeGreg

Roco a écrit a écrit :

Tu pourrais m'expliquer (si tu avais deux ou trois liens en plus ça serait pas mal aussi) pkoi ces implémentations sont si peu performantes

ben c'est pas dur a deviner, a chaque ligne de ta fonction, il y a un "new quelquechose"

je rappelle que new c'est equivalent a l'appel d'un malloc suivi d'un appel de fonction constructeur..

Bref dans une fonction de tri, my guess c'est que c'est tres mauvais (pour le moins)..

LeGreg

---------------
voxel terrain render engine | animation mentor

phenixl

T'as code comment ta pile ?

Edit :

Si c'est une stack java oublie les perfs... De meme reutilise tes objets au lieu de les instancier non stop.

Edit bis :

Oublie les perfs si tu utilises java.util.* (tout court)

Message édité par phenixl le 30-11-2002 à 15:18:04

darklord

You're welcome

kadreg a écrit a écrit :

Tout java défini en une phrase

troll de movaise kalyté

---------------
Just because you feel good does not make you right

HappyHarry

DarkLord a écrit a écrit :

troll de movaise kalyté

bah c kadreg hein, on peut pas lui demander d'avoir la quantité ET la qualité [:spamafote]

darklord

You're welcome

HappyHarry a écrit a écrit :

bah c kadreg hein, on peut pas lui demander d'avoir la quantité ET la qualité [:spamafote]

bin vi [:spamafote]

---------------
Just because you feel good does not make you right

kadreg

profil: Utilisateur

Je me disais bien que mon nez me grattait ... :hello:

---------------
brisez les rêves des gens, il en restera toujours quelque chose... -- laissez moi troller sur discu !

darklord

You're welcome

kadreg a écrit a écrit :

Je me disais bien que mon nez me grattait ... :hello:

:lol: :lol: :lol: :lol:

:hello:

---------------
Just because you feel good does not make you right

HappyHarry

kadreg a écrit a écrit :

Je me disais bien que mon nez me grattait ... :hello:

tu parles avec tes multis t'as les moyens de surveiller tous les topics

BifaceMcLeOD

The HighGlandeur

Pourtant pas sorcier... :sarcastic:

Code :

import java.util.EmptyStackException;
public class IntegerArrayStack {
/**
* Creates an empty <tt>IntegerArrayStack</tt>.
*/
public IntegerArrayStack() {
this(10);
}
/**
* Creates an empty <tt>IntegerArrayStack</tt> with a default size.
*/
public IntegerArrayStack(int initialSize) {
this.size = 0;
this.elementData = new int[initialSize];
}
/**
* Pushes an item onto the top of this stack.
*
* @param item the item to be pushed onto this stack.
* @return the <tt>item</tt> argument.
*/
public int push(int item) {
if (this.size >= this.elementData.length) {
this.ensureCapacity(this.size);
}
this.elementData[this.size] = item;
this.size++;
return item;
}
/**
* Removes the item at the top of this stack and returns that
* item as the value of this function.
*
* @return The item at the top of this stack.
* @throws EmptyStackException if this stack is empty.
*/
public int pop() {
if (this.size == 0) {
throw new EmptyStackException();
}
this.size--;
return this.elementData[this.size];
}
/**
* Looks at the item at the top of this stack without removing
* it from the stack.
*
* @return the item at the top of this stack.
* @throws EmptyStackException if this stack is empty.
*/
public int peek() {
if (this.size == 0) {
throw new EmptyStackException();
}
return this.elementData[this.size - 1];
}
/**
* Tests if this stack is empty.
*
* @return <tt>true</tt> if and only if this stack contains
* no items; <tt>false</tt> otherwise.
*/
public boolean empty() {
return (this.size == 0);
}
/**
* Increases the capacity of this <tt>IntegerArrayStack</tt>
* instance, if necessary, to ensure that it can hold at
* least the number of elements specified by the minimum
* capacity argument.
*
* @param minCapacity the desired minimum capacity.
*/
public void ensureCapacity(int minCapacity) {
int oldCapacity = this.elementData.length;
if (minCapacity > oldCapacity) {
int[] oldData = this.elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
this.elementData = new int[newCapacity];
System.arraycopy(oldData, 0,
this.elementData, 0, this.size);
}
}
private int[] elementData;
private int size;
}

Bon, à vue de nez, ça compile, mais je n'ai pas testé.

Message édité par BifaceMcLeOD le 02-12-2002 à 12:04:32

Publicité

FORUM HardWare.fr

Programmation

Java

Pb d'utilisation des classes enveloppes + algo de tri

Sujets relatifs
[Algo] Zetes daccord avec moi ? (truc hyper facile) :D	Algo dont work ?!
Recherche infos sur algo d'encodage MPEG, et autres ...	Tomcat 4 - Paramétrage pour une utilisation en production
Utilisation de javax.comm (accès au port série, //, ...) + DEPRECATE	utilisation d un formulaire avec interaction d une base odb
[algo/C/C++/java/php/...]fct recursive de permutation ?	utilisation de sscanf: :/
classes et threads	Utilisation de valgrind : comprendre les messages
Plus de sujets relatifs à : Pb d'utilisation des classes enveloppes + algo de tri

Page générée en 0.127 secondes