[Tableaux] un sort qui trie mal

Bonjour à tous!
Bon, avant que le grand match commence, j'ai un petit problème à vous soumettre :
Je récupère un tableau Array ( [136] => 1 [152] => 0 [157] => 0 [163] => 0 [65] => 0 [84] => 0 [196] => 0 [154] => 0 [153] => 0 [155] => 0 [165] => 0 )
Les clés de ce tableau correspondent à des index d'une table MySQL, qui sont déjà triés.
Maintenant, ce que j'aimerais faire, c'est trier suivant les valeurs, mais quand celles-ci sont égales, que je garde l'ordre pré-établit.
Suis pas sur que ça soit bien clair, donc, dans l'exemple que je viens de donner, je voudrais avoir : Array ( [152] => 0 [157] => 0 [163] => 0 [65] => 0 [84] => 0 [196] => 0 [154] => 0 [153] => 0 [155] => 0 [165] => 0 [136] => 1 )
J'ai donc pensé à la fonction asort... Ben non, perdu! La fonction asort me donne ceci : Array ( [154] => 0 [153] => 0 [155] => 0 [165] => 0 [196] => 0 [84] => 0 [152] => 0 [157] => 0 [163] => 0 [65] => 0 [136] => 1 ). Les clés ne sont plus dans l'ordre que je désire, à valeurs égales...
J'ai essayé de comprendre la fonction array_multisort... mais j'ai abandonné, parce que je ne comprends rien à ce qu'il y a d'écrit, et malgré de nombreuses tentatives, le résultat donné n'est pas celui recherché...
Quelqu'un aurait une suggestion?
P.S.: pourquoi mon code ressort-il aussi mal? Fais-je quelque chose qu'il ne faut pas?

Bonjour,

je te conseille d'utiliser la fonction usort qui te permet d'utiliser une fonction que tu auras défini toi même pour pouvoir ordonner ton tableau comme tu l'entends, sinon, il me semble qu'il n'y a pas de fonctions native php te permettant de faire ce que tu veux, quant à array_multisort il suffit de s'habituer à sa syntaxe, une fois maitrisée c'est une fonction très puissante pour faire des tris selon plusieurs critères.

PS : Sort() ne trie pas mal ! elle ne fait que ce qu'on lui demande ;)

Bon courage,


Fred

Ben, ce que j'aurais voulu que sort face, c'est garder le même ordre initial en cas d'égalité. Donc, sort trie mal :mouarf:
J'ai essayé usort également. Sauf que je n'ai pas bien compris comment fonctionnait cette fonction non plus.
Je n'arrive pas à récupérer les clés, mais uniquement les valeurs! Alors, mon tableau est peut être trié suivant les valeurs, mais je ne connais plus du tout les clés, et je ne peux pas les retrouver :(

Bon, alors, voila comment j'ai réussi à résoudre mon problème.
Mais franchement, je trouve ça minable, parce que php est incapable de trier un tableau correctement, c est fou! 8O
Bon, donc au départ, je pensais avoir un tableau comme ca : Array ( [136] => 1 [152] => 0 [157] => 0 [163] => 0 [65] => 0 [84] => 0 [196] => 0 [154] => 0 [153] => 0 [155] => 0 [165] => 0 ); mais en définitive, pour faire ce que je voulais, il a fallu que je fasse 2 tableaux
lk = Array ( [0] => 136 [1] => 152 [2] => 157 [3] => 163 [4] => 65 [5] => 84 [6] => 196 [7] => 154 [8] => 153 [9] => 155 [10] => 165 )
et lv = Array ( [0] => 1 [1] => 0 [2] => 0 [3] => 0 [4] => 0 [5] => 0 [6] => 0 [7] => 0 [8] => 0 [9] => 0 [10] => 0 )
A chaque fois que je récupère une nouvelle valeur dans les tableaux, je fais ça :

Code:

---

1 2 3 4

$lk[] = $ligne['id']; $lv[] = $lev; $lk = tri($lk,$lv); sort($lv);

---

ou

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

function tri($leskey,$tableau){ $i = count($tableau) - 1; while(($i > 0) && ($tableau[$i] < $tableau[$i - 1])){ $val = $leskey[$i]; $leskey[$i] = $leskey[$i - 1]; $leskey[$i - 1] = $val; $val = $tableau[$i]; $tableau[$i] = $tableau[$i - 1]; $tableau[$i - 1] = $val; $i--; } return $leskey; }

---

Je sais, c'est totalement bidon, mais c'est la seule solution que j'ai pu trouver qui fasse ce que je demandais à la base.
Alors si quelqu'un a une solution plus propre, je suis toute ouie!
Ciao

en PHP tu as les fonctions *sort* qui peuvent trier sur les clé ou les valeurs, et converser l'ordre associatif.

en gros je verrais bien un tri sur tes valeurs d'abord, et apres sur tes clés ...

Sauf que le tri sur les clés ne doit pas se faire!
Si tu veux, les clés que je récupère correspondent à des index d'une table, et à des titres de livre.
Je récupère donc le tableau trié... donc il faudrait pas que ça me trie les clés par ordre croissant ou décroissant, ça servirait à rien.

Citation:

---

. Les clés ne sont plus dans l'ordre que je désire, à valeurs égales...

---

Citation:

---

Sauf que le tri sur les clés ne doit pas se faire!

---

soit tu te contredis, soit j'ai rien compris.

;)

Euh... :oops:
Alors, reprenons.
J'ai fait un formulaire de recherche. Ce formulaire doit permettre de retrouver des titres de livre.
Pour pouvoir retrouver des titres approchant, j'ai fait une fonction qui permet de trouver des titres, en utilisant la fonction levenshtein.
Le tableau a donc pour clés les index de la table (qui sont triés par ordre alphabétique), et en valeur la valeur du levenshtein correspondant.
Voulant afficher les titres par pertinence ET par ordre alphabetique, il faut donc que je mette les levenshtein les plus petits au début, tout en gardant l'ordre initial des clés.
Je ne peux donc pas retrier les clés après, car je n'aurai plus le classement alphabétique.
Est ce plus clair?

un autre exemple plus court que celui du premier post serait le bienvenue ;)

Ben...
Alors, admettons que j'ai le tableau suivant : Array([136] => 1, [152] => 0, [57] => 0, [17] => 1);
Ils sont actuellement classes par ordre alphabétique. Je veux maintenant garder cet ordre alphabétique sur les clés, mais trier les valeurs par ordre croissant.
Donc obtenir le tableau suivant : Array([152] => 0, [57] => 0, [136] => 1, [17] => 1).

je comprend mieux.

et je pense qu'effectivement, je suis pas sur que ca soit plus simple de passer par des fonctions PHP pour faire cela.

tu veux quelque chose de spécifique, donc on est toujours mieux servi par soit même ... ;)

:( C'est bien ce que je craignais :(
Mais bon, maintenant, c'est que je sais pas si ce que j'ai fait est optimal ou pas. J'ai récupéré mes vieux cours d'algo, mais je sais même pas si c'est transposable en php de manière satisfaisante ou pas... :oops:
En tout cas, merci pour ton aide Maxoo!

Salut,

J'ai balayé toutes les fonctions de tri de php (très instructif :) ). La plus proche des besoins étant "uasort". J'ai essayé de créer la fonction ad hoc mais le pb se pose donc lorsque 2 valeurs sont identiques.
La solution idéale aurait été de dire que, dans ce cas, cela revient à un "inférieur" et la première clé reste devant.

Code:

---

1 2 3 4 5 6 7 8 9 10

$tab = array('136' => 1, '152' => 2, '157' => 0, '163' => 1, '65' => 2, '84' => 1, '196' => 0, '154' => 0, '153' => 0, '155' => 0, '165' => 0 ); print_r($tab); echo '<br/><br/>'; uasort($tab, 'compare'); print_r($tab); echo '<br/><br/>';   function compare ($a, $b) { if ($a == $b) return -1; return ($a > $b) ? 1 : -1; }

---

Le problème est que, d'une part, on a accès uniquement aux valeurs et non aux clés associées et que, d'autre part, les valeurs (et clefs associées) envoyées à la fonction ne correspondent pas forcement à l'ordre original du tableau. C'est à dire que sur le tableau ci-dessus (prenons le cas de 2 clés à 0) il ne va pas forcement envoyer 157 et 196 (ordre original) mais peut-être 165 et 155 (faut bien qu'il sache comment trier ces 2 clés l'une par rapport à l'autre). Ainsi, quelque soit le retour sur une égalité (return 0 ou 1 ou -1), le résultat de correspondra, à mon avis, jamais à l'ordre original.

Tout ça pour en arriver à une autre possibilité : plutôt que de trier le tableau final, ne te serait-il pas possible de trier dès la création.
En supposant que la valeur (0,1,2...) soit un ordre de pertinence (d'où l'intéret de trier par valeur décroissante), vois si tu ne peux pas séparer tes résultats dans des tableaux séparés. Pour obtenir, toujours selon le tableau ci dessus:

Citation:

---

array([0] => array(157, 196, 154, 153, 155, 165),
[1] => array(136, 163, 84),
[2] => array(152, 65));

et s'il aucune clé de correspond à 1 :
//$arr = array('136' => 3, '152' => 2, '157' => 0, '163' => 3, '65' => 0, '84' => 0 ); deviendrait

array([0] => array(157, 65, 84),
[3] => array(136, 163),
[2] => array(152));

---

J'ai été suffisament clair ?

Citation:

---

Envoyé par Ricou13

J'ai été suffisament clair ?

---

Non :aie:
Pour la fonction uasort, j'en étais arrivé à la même conclusion que toi, même si je ne comprends toujours pas pourquoi il ne pourrait pas me garder mon ordre original, mais bon... :?
Par contre, par rapport à ce que je fais maintenant, je trie bien le tableau à sa création : j'insère la nouvelle valeur dans le tableau $lk, et je le place ensuite à l'endroit correspondant. Je fais un petit tri par insertion.
Le problème, si je me rappelle bien, c'est que la complexité d'une telle fonction est en o(n²), non?
Il faudrait que j'essaye de voir si les autres algos de tri que je retrouve peuvent être transposés en php (normalement, oui? 8O ), et de faire des tests sur la rapidité des résultats (c'est quoi déjà la fonction pour calculer un temps en millisecondes?... non, c est bon, je vais chercher :roll: )
P.S.: au fur et à mesure que je tape ce message, je crois que j'ai compris ce que tu voulais que je fasse Ricou... Est-ce plus rapide?... oui, je sais, je vais tester :aie:

Tout mon raisonnement se base sur l'axiome disant que la valeur d'une clé représente son degré de pertinence.

Il te faut un tableau général array(pertinence de degré 0, pertinence de degré 1, pertinence de degré 2...) où chaque élément de pertinence est lui même un tableau contenant simplement la liste des clés ayant cette pertinence. Ce tableau sera donc très simple à trier et l'ordre d'insertion sera respecté puisque jamais manipulé.

Code:

---

1 2 3 4 5 6 7 8 9 10

while (boucle de traitement) { //Traitement / analyse retournant une clé et sa valeur (pertinence) ... $cle = ... $valeur = ... ... // Insertion dans le tableau $TabGeneral[$valeur][] = $cle; }

---

Ce qui te donne un tableau à deux dimensions où les clé sont classées par valeur.
Ensuite, pour les afficher, il te suffit de trier par dimension 1 (la valeur) et d'afficher la 2eme dimension telle quelle (les clés correpondantes)

il se peut cependant qu'il y ait un bug à traiter, dans "$TabGeneral[$valeur][] = $cle;" au cas où le sous-tableau [$valeur] n'existe pas encore mais je crois que php se contentera de le créer.

je pense effectivement, même s'il ya longtemps que je ne connais plus les formules d'estimation de temps (auxquelles je ne comprenais rien d'ailleurs :) ), que c'est beaucoup plus rapide dans le sens où :
- l'insertion dans le tableau se fait en une seule instruction
- le tri est basique (un simple sort suffit) sur la première dimension uniquement, les clés n'étant jamais triées.

Tiens! Un pote à moi qui ne comprends rien à la complexité d'un algo!! Ca fait plaisir!! :mouarf:
Je suis en train de tester tout ça, je te tiens au courant (ainsi que ceux qui seraient intéressés, bien évidemment!)

Faut dire que c'était mal barré quand mon prof m'expliquait "qu'il fallait mieux utiliser un tri alphanumérique suivi d'un recherche dicotomique plutôt qu'un balayage séquentiel du tableau parce que la première méthode aurait un temps moyen de "logn² * n" alors que la seconde serait de "log2 * n²" (ndr : les formules que j'indique c'est n'importe quoi, soyez en conscient :) ) et donc qu'on obtiendrait un gain de 25 ns sur le temps d'occupation du processeur"

Ce à quoi je répondais "Qu'est-ce qu'on en a à bat..., pour des logiciels de bureautique sur des processeurs à 3GHz et des utilisateurs qui vont à 2 à l'heure en vitesse de pointe ?"

Et c'était le même dialogue concernant l'optimisation de la structure des bases de données afin de réduire au maximum l'espace disque occupé. Bref passer 3 jours d'analyse et de test pour gagner 30 Mo sur une base de 500 Mo alors que les disques de maintenant en font plusieurs centaines de Go. 8O

J'avais l'impression que les cours n'avaient pas évolué depuis les années 50 où l'espace mémoire et bande (les disques n'existaientpas encore :P ) se comptait en Ko et qu'il fallait y faire attention.

Ah, l'époque de mon premier ordinateur (un Sinclair ZX Spectrum) avec son extension mémoire de 16Ko et la révolution quand j'ai acheté un Atari ST avec 512 Ko. A l'époque, je me demandais même ce que je pourrais faire d'autant de mémoire. :mouarf2:

:lol: :lol:
Je suis pas vraiment d'accord avec toi sur l'histoire de l'optimisation des bdd, mais bon, chacun son truc ;)
Surtout que tu vas être content d'apprendre qu'après mes tests, ta méthode s'avère plus performante que celle que j'ai trouvée.
Quand on a beaucoup de données (307 clés dans le tableau 8O ), ta méthode donne un résultat dans une moyenne de 0.044289491176605s (pour 100 essais consécutifs), alors que mon petit tri par insertion donne un résultat en 0.20086414575577s en moyenne (et je peux te dire qu'on la sent la différence malgré tout!).
Donc voila! Pour le moment, je garde ton bout de code Ricou, mais je n'ai pas dit mon dernier mot!! :mrgreen:

Je suis d'accord qu'il est idiot de mettre un "long" sur un champ dont les valeurs ne dépasseront jamais la taille d'un "byte"
Mais mettre un varchr(50) au cas où, alors qu'un varchar(40) semble suffire, ca va pas changer grand chose surtout si on est pas absolument certain de la taille maximale des données.
c'est dans ce sens que je parle d'optimisation inutile.

Combien de fois j'ai vu des champ "Nom" ou "adresse" limités à 20 caractères parce qu'on croit que cela suffit et qu'on se retrouve comme un c... parce que la personne à un nom composé qui fait 21 caractères.

Quand je crée un bdd, je pense à une structure cohérente et logique même si elle n'est pas totalement optimale.

;)

N'empêche : 4,5 fois plus rapide ! Yo ! Je vais changer mon pseudo en "Ricou 4,5x" :mrgreen:

Ah mais c'est de ça que tu parlais en disant optimisation de bdd.... Alors oui, je suis d'accord avec toi à 100%!! :mouarf:
Bref... pour en revenir à nos moutons, je sais pas pourquoi je m'enchose à chercher une nouvelle méthode. 8O
Celle que tu as proposé Ricou me semble la meilleure, et de loin! Franchement, je suis bête de me compliquer la tâche.
Donc je te remercie Ricou pour ton idée de génie (je sais, j'ai eu la même, mais je l'ai exploité comme un sagouin...:arf: ), et je mets "Résolu"!
Ciao tout le monde.