Tableau généré et trié par le client
5/5 (7 avis)
Vue 7 586 fois - Téléchargée 625 fois
Description
Le but ici est d'illustrer plusieurs techniques de développement javascript.
La première concerne une structure de stockage dont l'initialisation par un script ASP ou PHP est extrêmement simple.
La seconde est l'implémentation de deux méthodes de tri, le bubblesort et le quicksort, avec ci-dessous un tableau des performances obtenues avec ces deux algorithmes et la comparaison avec le Sort natif du javascript.
#lignes BubbleSort QuickSort
100 40ms 8ms
500 1500ms 40ms
1000 5800ms 60ms
5000 ... 500ms
Le tout est une interface efficace affichant un tableau généré sur la base de la structure de données permettant le tri de son contenu, ainsi avec le tri natif, un tableau de 10 000 lignes est trié en moins d'une demi seconde !
Une demo en ligne est visible à l'adresse http://www.grandville.net/download/list.html
Avec une telle interface, il est possible de retourner aux clients des tableaux de grande taille et ainsi réduire la sollicitation des serveurs web et d'économiser de la bande passante toute en ayant une interface utilisateur très véloce.
La première concerne une structure de stockage dont l'initialisation par un script ASP ou PHP est extrêmement simple.
La seconde est l'implémentation de deux méthodes de tri, le bubblesort et le quicksort, avec ci-dessous un tableau des performances obtenues avec ces deux algorithmes et la comparaison avec le Sort natif du javascript.
#lignes BubbleSort QuickSort
100 40ms 8ms
500 1500ms 40ms
1000 5800ms 60ms
5000 ... 500ms
Le tout est une interface efficace affichant un tableau généré sur la base de la structure de données permettant le tri de son contenu, ainsi avec le tri natif, un tableau de 10 000 lignes est trié en moins d'une demi seconde !
Une demo en ligne est visible à l'adresse http://www.grandville.net/download/list.html
Source / Exemple :
<!--
list.html
Exemple de génération d'un tableau par un javascript
et trois fonctions de tri BubbleSort, QuickSort et tri natif
V2.0 20/07/2009 ajout du tri natif et correction du générateur rndString
V1.0 18/07/2009 version initiale
-->
<html>
<head>
</head>
<body>
<style type="text/css">
#DN td {font-weight:normal; color:#fff; font-size:15px;}
#DN td.sel {font-weight:bold; color:#fff;font-size:15px;}
#DN td.crt {font-weight:normal;font-size:12px;background:#888;}
#DN td.typ {font-weight:normal;font-size:12px;background:#ccc;}
#DN td.exp1 {background:red;color:#000;}
#DN td.exp2 {background:#FFCC33;color:#000;}
#DN tr { font-size:11px;font-family:verdana;font-weight:bold;color:#fff; background:#0033CC; padding:2px 0; text-indent:2px; margin-top:2px; border:1px solid #09d;}
</style>
<input type="text" value="" id="NB"><input type="button" value="Randomize" onclick="javascript:RandomizeCertList(document.getElementById('NB').value);Redraw();"> <br>
<select id='algo'><option>BubbleSort</option><option>QuickSort</option><option>Native</option></select>
<br>
<div id=message style="font-family:verdana;;font-size:20px"><br></div><br>
<div id=DN></div>
<script language="javascript">
// définition de la structure de stockage des éléments du tableau
function cert(s1, s2, s3, s4, s5){
this.issuer=s1
this.subject=s2
this.expire=s3
this.auth=s4
this.pvk=s5
return this
}
// fonction retournant au format HTML une ligne de tableau
// contenant l'élément donné en paramètre
function TR(a,cert){
// en fonction du type de certificat
// l'image change [CA+[pvk|!pvk]|CRT+[pvk|!pvk]]
if(cert.auth)
if(cert.pvk)
strIcone = "<IMG src=\"images/rootpvk.png\">"
else
strIcone = "<IMG src=\"images/root.png\">"
else
if(cert.pvk)
strIcone = "<IMG src=\"images/certpvk.png\">"
else
strIcone = "<IMG src=\"images/cert.png\">"
// en fonction de proximité de l'expiration
// la couleur change
if(cert.expire<1){
return '<TR><TD class=\"typ\">'+strIcone+'</TD><TD class=\"crt\">'+cert.issuer+'</TD><TD class=\"crt\">'+cert.subject+'</TD><TD class=\"crt exp1\">'+cert.expire+'</TD></TR>';
}else if(cert.expire<2){
return '<TR><TD class=\"typ\">'+strIcone+'</TD><TD class=\"crt\">'+cert.issuer+'</TD><TD class=\"crt\">'+cert.subject+'</TD><TD class=\"crt exp2\">'+cert.expire+'</TD></TR>';
}else{
return '<TR><TD class=\"typ\">'+strIcone+'</TD><TD class=\"crt\">'+cert.issuer+'</TD><TD class=\"crt\">'+cert.subject+'</TD><TD class=\"crt\">'+cert.expire+'</TD></TR>';
}
}
// génération aléatoire des différents champs de la structure
function rndExpire(){
return Math.floor(Math.random() * 5);
}
function rndIssuer(){
var myArray = new Array("VeriSign Class 3 Secure Server CA","GTE CyberTrust Global Root","VeriSign Class 3 Extended Validation SSL SGC CA","thawte Primary Root CA");
return myArray[Math.floor(Math.random() * 4)];
}
function rndTrue(){
return Math.floor(Math.random()*2);
}
function rndString(){
str="ABCDEFGHIJKLMNOPRSTUVWXYZ";
var sRnd = '';
for (var i=0; i < str.length; i++){
if(i==1){str+=' ';}
var randomPoz = Math.floor(Math.random() * str.length);
sRnd += str.substring(randomPoz,randomPoz+1);
}
return sRnd;
}
// ces fonctions permettent de retourner les valeurs
// à indexer aux routines de tri
function CompIssuer(a,b){var x = a.issuer.toUpperCase();var y = b.issuer.toUpperCase();return ComparaisonFunction(x,y);}
function GetIssuer(a){return a.issuer.toUpperCase();}
function CompSubject(a,b){var x = a.subject.toUpperCase();var y = b.subject.toUpperCase();return ComparaisonFunction(x,y);}
function GetSubject(a){return a.subject.toUpperCase();}
function CompExpiration(a,b){var x = a.expire;var y = b.expire;return ComparaisonFunction(x,y);}
function GetExpiration(a){return a.expire;}
function CompType(a,b){var x = '*'+a.auth+a.pvk;var y = '*'+b.auth+b.pvk;return ComparaisonFunction(x,y);} // l'étoile garantie que ce sera une chaine de caractères !
function GetType(a){return '*'+a.auth+a.pvk;} // l'étoile garantie que ce sera une chaine de caractères !
function GetComparaisonFunction(bSortOrder){
if(bSortOrder){
return function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
}else{
return function (e1,e2){ return e1 > e2 ? -1 : e1 == e2 ? 0 : 1; };
}
}
function SortCol1(){
// fonction déclenchée par le clic sur la colonne 1
if(CurrentCol==1){
// clic sur la même colonne -> inversion de l'ordre
bSortOrder=!bSortOrder;
}else{
// premier clic sur la même colonne -> on fixe un ordre par défaut
CurrentCol=1;bSortOrder=1;
};
switch(document.getElementById('algo').selectedIndex){
case 0:
Compute('BubbleSort(GetIssuer)');break;
case 1:
Compute('quickSort(GetIssuer,0,nbcount-1)');break;
case 2:
Compute('mycert.sort(CompIssuer)');break;
}
}
// pour les autres colonnes ... même principe ...
function SortCol2(){if(CurrentCol==2){bSortOrder=!bSortOrder}else{CurrentCol=2;bSortOrder=1};switch(document.getElementById('algo').selectedIndex){case 0:Compute('BubbleSort(GetSubject)');break;case 1:Compute('quickSort(GetSubject,0,nbcount-1)');break;case 2:Compute('mycert.sort(CompSubject)');break;};}
function SortCol3(){if(CurrentCol==3){bSortOrder=!bSortOrder}else{CurrentCol=3;bSortOrder=1};switch(document.getElementById('algo').selectedIndex){case 0:Compute('BubbleSort(GetExpiration)');break;case 1:Compute('quickSort(GetExpiration,0,nbcount-1)');break;case 2:Compute('mycert.sort(CompExpiration)');break;};}
function SortType(){if(CurrentCol==4){bSortOrder=!bSortOrder}else{CurrentCol=4;bSortOrder=1};switch(document.getElementById('algo').selectedIndex){case 0:Compute('BubbleSort(GetType)');break;case 1:Compute('quickSort(GetType,0,nbcount-1)');break;case 2:Compute('mycert.sort(CompType)');break;};}
function Compute(a) {
// mesure des temps d'exécutions
ComparaisonFunction = GetComparaisonFunction(bSortOrder);
document.body.style.cursor='wait';
Debut = new Date();
eval(a);
Sort = new Date();
Redraw();
Fin = new Date();
// affichage
document.getElementById('message').innerHTML=a+' Sort:'+(Sort-Debut)+'ms, Draw:'+(Fin-Sort)+'ms';
}
function Redraw(){
// affichage du tableau repeuplé
document.body.style.cursor='wait';
obj=document.getElementById('DN');
html="<table id=DN><tr><td onclick=\"SortType();\"></td><td "+((CurrentCol==1)?"class=\"sel\"":"")+" onclick=\"SortCol1();\">Issuer</td><td "+((CurrentCol==2)?"class=\"sel\"":"")+" onclick=\"SortCol2();\">Subject</td><td "+((CurrentCol==3)?"class=\"sel\"":"")+" onclick=\"SortCol3();\">Expire</td></tr>";
for(a=0;mycert[a];a++){
html+=TR(a,mycert[a]);
}
obj.innerHTML='</table>'+html;
document.body.style.cursor='default';
}
// tri quickSort
// le principe pour un tri croissant est de séparer les données en deux
// moitiés puis de s'assurer que tous les éléments
// de la moitié gauche sont plus petits que le pivot qui est lui
// même plus petit que tous les éléments de droite.
// puis récursivement pour chaque moitié on recommence jusqu'a ce que les moitiés
// soient réduites à un seul élement, à la fin les éléments sont tous triés
// du plus petit au plus grand.
// Cette méthode de tri est très semblable à un arbre binaire et peut être
// extraordinairement plus performante sil elle est multithreadée avec
// des langages comme le java ou le C.
//
function quickSort(a, left, right) {
index = partition(a,left, right);
if (left < index - 1)
quickSort(a,left, index - 1);
if (index < right)
quickSort(a,index, right);
}
function partition(arr, left, right){
i = left;
j = right;
pivot = arr(mycert[Math.floor((left + right) / 2)]);
while (i <= j) {
while(ComparaisonFunction(arr(mycert[i]),pivot)>0)
i++;
while(ComparaisonFunction(arr(mycert[j]),pivot)<0)
j--;
if (i <= j) {
var dummy = mycert[i];
mycert[i] = mycert[j];
mycert[j] = dummy;
i++;
j--;
}
};
return i;
}
// tri BubbleSort
// le plus trivial, on prend chaque élément qu'on compare
// à chaque élément suivant et on permutte en fonction de l'ordre choisi
function BubbleSort(a) {
for (var i=0; mycert[i]; i++){
for (var j=i+1; mycert[j]; j++){
if ((a(mycert[j]) < a(mycert[i]) && bSortOrder) || (a(mycert[j]) > a(mycert[i]) && !bSortOrder)) {
var dummy = mycert[i];
mycert[i] = mycert[j];
mycert[j] = dummy;
}
}
}
}
// un générateur de basard
function RandomizeCertList(iNB){
delete mycert;
mycert=new Array();
nbcount=0;
for(a=0;a<iNB;a++){
mycert[nbcount++]= new cert(rndIssuer(),rndString(),rndExpire(),rndTrue(),rndTrue());
}
}
nbcount=0;
mycert=new Array();
// si cette page était générée par un script, voici à quoi ressemblerait
// l'initialisation des données à afficher
//mycert[nbcount++]=new cert('AG Consulting Personal identification Authority','Arnaud Grandville',1,0,0);
//mycert[nbcount++]=new cert('AG Consulting WebServer Authority','www.grandville.net',5,0,0);
CurrentCol = 1;
bSortOrder = 1;
RandomizeCertList(10);
document.getElementById('NB').value=10;
Redraw();
</script>
</body>
</html>
Conclusion :
Avec une telle interface, il est possible de retourner aux clients des tableaux de grande taille et ainsi réduire la sollicitation des serveurs web et d'économiser de la bande passante toute en ayant une interface utilisateur très véloce.
Codes Sources
A voir également
- Quicksort js
- Quicksort javascript - Meilleures réponses
- Javascript trie - Meilleures réponses
- Trier tableau généré en js ✓ - Forum - Javascript / DHTML
- Récupération de données d'un fichier, mise dans dans tableau de structure, tri de ce tableau - Codes sources - C / C++ / C++.NET (Divers)
- C / C++ / C++.NET : Classe pile&tableau generique - CodeS SourceS - Guide
- Création tableau 2 dimensions + tri ✓ - Forum - Java
- Enregistrement automatique avec la date et l'heure de mes tableaux generé sous ✓ - Forum - Visual Basic 6
20 juil. 2009 à 14:28
20 juil. 2009 à 14:18
Pour répondre à THE_WWT, je dirais qu'en règle générale, il n'est pas résonnable de faire trier un résultat par le client mais que dans mon cas particulier, le coût de collecte des données (dans le produit final) justifie que le client fasse ce travail lui même. De plus, comme tu t'en doutes, il ne s'agit que d'une partie d'un ensemble plus complexe permettant l'édition et la modification hors ligne de ces données (sans solliciter le serveur), seul le post final provoquant l'enregistrement.
Cela dit, j'ai regardé plus en détail le code que tu as posté et je te félicite pour la beauté du style, j'ai surtout aimé la fonction cf (comparaison fonction ??) qui éviterait dans mon cas les conditions d'ordres sur les tris. Je vais donc intégrer cette astuce et proposer une nouvelle version en ajoutant le sort natif pour avoir un comparatif entre un tri pourri (bubblesort), un bien (quicksort) et un excellent (sort natif) qui permet de trier dans un temp inférieur à la seconde un tableau de plusieurs milliers de lignes ...
- Messages postés
-
177
- Date d'inscription
- jeudi 5 octobre 2006
- Statut
- Membre
- Dernière intervention
- 16 janvier 2009
120 juil. 2009 à 12:03
je parle en effet de la fonction Array#sort(comparator) qui trie une collection et peut prendre une fonction de comparaison en paramètre.
@LeFauve42: Tout simplement parce que durant le tri le navigateur est bloqué. Je suis d'accord avec toi si ta collection comporte moins de 25 éléments le navigateur est bloqué moins d'une milliseconde. Cependant, si tu utilises la pagination du jeu de résultat le tri coté client n'est plus envisageable (tout simplement car il ne dispose pas de l'ensemble de la collection).
Cdlt,
Pierrick
20 juil. 2009 à 10:12
Si on n'a pas des miliers de lignes, et qu'on veut permettre a l'utilisateur de changer le tri (en cliquant sur le titre des colonnes) ca me parait un solution bien meilleure que de redemander au serveur une nouvelle liste, non ?
Je suis aussi curieux de savoir ce que tu entends par "la fonction de tri du navigateur". Est-ce que tu parles de la methode sort() de la classe Array ?
Eric
20 juil. 2009 à 09:20
sinon THE_WWT qu'entends tu par "La conclusion est que la fonction tri du navigateur (mis à part IE6) est toujours la meilleure..." c'est quoi la fonction de tri du navigateur??
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.