Discussion :

[seb-astien]

Bonjour,
Je souhaite permuter tous les éléments d'un tableau. Le problème est que pour un grand nombre d'objets à permuter, la fonction réalisée prend trop de temps. Auriez vous une solution plus rapide ?

Le tableau phi est le tableau qui permet de definir une permutation et de la conserver (il faut absolument que je conserve les positions de départ et d 'arrivée).
exemple pour un tableau de 3 objets à permuter avec phi = {1,2,0} et un tableau {4,5,6} à permuter, ca va donner en sortie le tableau suivant :
{6,4,5}

Voila ce qui a été fait :


Code:
protected Ball[] permuteList(Ball[] tabBall) {

int size = tabBall.length;
Ball[] result = new Ball[size];

int pos;
for (int i = 0; i < size; i++) {
pos = phi[i];
result[pos] = tabBall[i];
}
return result;
}


Merci pour votre aide

[nicolas581]

J'ai vu ta question dans le forum java, mais je te reponds ici pour un point
purement sur la complexité.
Je ne vois pas comment tu pourrais accélerer tes affectations,
en effet tu est obligé de parcourir ton tableau phi. Ce qui te donne
un complexité linéaire.
Tu as donc deux choix possibles pour accélérer ta fonction :
1 - Choix algorithmique : meme si tu permutes tous les objets. Existe-t-il une sorte de structure dans la permutation ?
2 - Choix Java trouver une autre façon pour affecter les valeurs mais je ne vois pas ce que tu peux faire étant donné que c'est assez simple.

Bref, avec ton code tu es linéaire donc si tu veux gagner du temps essaye de te pencher sur 1 -

[seb-astien]

Existe-t-il une sorte de structure dans la permutation ?

Je sais pas si je vais bien repondre à ta question...on va essayer. Voila comment ca se passe. Au depart on a un tableau à permuter. On génère de manière aléatoire une permutation que je stocke dans phi. Je permute le tableau de depart en fonction de phi pour obtenir le tableau permuté.
Donc a priori pas de structure dans la premut !

[nicolas581]

Si le tirage est bien aléatoire il ne doit pas y avoir de structure .

La seule solution est de repenser dans quel contexte tu souhaites avoir
ce tableau "desordonné". Explique mieux ton problème en général. Quels sont les tailles de tableau que tu veux traiter ? Uniquement pour des entier ?
etc. Quand tu dis que ça te prends du temps, en min, h, jours ?

Mais je ne pense que ce soit un problème que l'on peut mettre avec une complexité inférieure.

[Nemerle]

Tu ne peux pas énormément réduire ton temps de calcul, car il faut bien que tu le remplisse ton tableau!!

Néanmoins, il y a peut-être une façon de gagner du temps:
Tu pars d'un tableau T à permuter;
Plutôt que de construire un tableau RES t'obligeant à écrire chaque élément de RES à partir de T, tu MODIFIES T.

Ce que tu gagne? Et bien tu utilises des permutations élémentaires pour permuter ton tableau! Une permutation élémentaire échange 2 éléments et laisse fixe les autres. L'avantage? Il y aura un certain nombres d'éléments de T qui ne bougerons pas, et tu n'auras pas de traitement à faire sur eux...

Tu tires donc le % d'éléments fixe,
Tu tires des perm. élémentaires (i.e. 2 positions dans T) et tu échanges les élements de T assiciés; tu en tires ce qu'il te faut pour laisser ton % d'éléments fixe....

Tu peux éventuellement gagner du temps par cette méthode, en fixant le nombre d'éléments fixe à 30% en moyenne par exemple....


Enfin, je ne sais si cela t'aide...

[seb-astien]

Merci pour votre aide !
J'arriverai pas à faire mieux visiblement.