Pb d'utilisation des classes enveloppes + algo de tri

Marsh Posté le 29-11-2002 à 23:07:54

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 !

Reply

Marsh Posté le 29-11-2002 à 23:07:54

Reply

Marsh Posté le 29-11-2002 à 23:10:14

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 !

Reply

Marsh Posté le 29-11-2002 à 23:13:22

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 !

Reply

Marsh Posté le 29-11-2002 à 23:32:32

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é

Reply

Marsh Posté le 29-11-2002 à 23:42:52

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..."

Reply

Marsh Posté le 29-11-2002 à 23:43:54

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

---------------
"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..."

Reply

Marsh Posté le 29-11-2002 à 23:46:22

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 !

Reply

Marsh Posté le 29-11-2002 à 23:47:42

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é

Reply

Marsh Posté le 29-11-2002 à 23:49:04

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

---------------
"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..."

Reply

Marsh Posté le 29-11-2002 à 23:50:11

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é)

---------------
"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..."

Reply

Marsh Posté le 29-11-2002 à 23:50:11

Reply

Marsh Posté le 29-11-2002 à 23:53:25

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 !

Reply

Marsh Posté le 29-11-2002 à 23:56:04

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)

---------------
"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..."

Reply

Marsh Posté le 30-11-2002 à 09:02:07

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:

Reply

Marsh Posté le 30-11-2002 à 10:59:55

à 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

Reply

Marsh Posté le 30-11-2002 à 11:02:50

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 ...

Reply

Marsh Posté le 30-11-2002 à 12:02:53

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 !

Reply

Marsh Posté le 30-11-2002 à 12:04:17

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 !

Reply

Marsh Posté le 30-11-2002 à 12:08:11

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 ...

Reply

Marsh Posté le 30-11-2002 à 12:20:58

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 !

Reply

Marsh Posté le 30-11-2002 à 12:30:46

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

Reply

Marsh Posté le 30-11-2002 à 15:15:04

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

Reply

Marsh Posté le 30-11-2002 à 21:59:42

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

Reply

Marsh Posté le 30-11-2002 à 22:35:57

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]

Reply

Marsh Posté le 30-11-2002 à 22:37:05

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

Reply

Marsh Posté le 30-11-2002 à 22:39:01

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 !

Reply

Marsh Posté le 30-11-2002 à 22:39:20

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

Reply

Marsh Posté le 30-11-2002 à 22:42:06

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

Reply

Marsh Posté le 02-12-2002 à 12:01:22

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

Reply

Marsh Posté le

Reply

Pb d'utilisation des classes enveloppes + algo de tri

Sujets relatifs:

Leave a Replay