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

Télécharger le projet
Commenter

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.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_Klephte)