Tableau généré et trié par le client

Soyez le premier à donner votre avis sur cette source.

Vue 7 217 fois - Téléchargée 604 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

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

Ajouter un commentaire

Commentaires

Messages postés
253
Date d'inscription
vendredi 13 juin 2003
Statut
Membre
Dernière intervention
18 mai 2009

Quand on a toutes les données et qu'on veux trier avec les pc d'aujourd hui je ne voit pas pourquoi faire un appel serveur,c'est d'ailleur un peu la mode aujourd hui un retour vers des clients semi-lourd (silverlight, flash,javascript avancé..) ça économise de la bande passante et du CPU serveur...non?
Messages postés
21
Date d'inscription
mardi 20 mai 2003
Statut
Membre
Dernière intervention
7 octobre 2011

Bonjour et merci pour vos réactions sur ce script.
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
1
Bonjour à tous,

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
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009

THE_WWT: Que veux-tu dire par "le tri coté client n'est jamais une bonne solution" ?

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
Messages postés
253
Date d'inscription
vendredi 13 juin 2003
Statut
Membre
Dernière intervention
18 mai 2009

Très bonne source, interressante :)
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??
Afficher les 7 commentaires

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.