. tris XML en Javascript: Comparaison des performances .

Depuis sa version 1.5, firefox supporte la spécification e4x (ECMAScript for XML) specification qui facilite la manipulation d'arbres XML.
Avant: 

var a = document.createElement('personne');
a.setAttribute('prenom', 'paul');
a.setAttribute('nom', 'dupond');
a.setAttribute('age', '32');

alert(a.getAttribute('age'));

Après: 

var tree = <personne prenom="paul" nom="dupond" age="32" />;

// affiche l'age de paul
alert(tree.@age);

Cependant, la spécification ne définit pas de méthode de tri d'un arbre XML. Cet article présente 5 méthodes différentes de tri d'un arbre, en terminant par une comparaison de leurs performances respectives.

Tri par tas (en javascript) 

function swap(array, x, y)
{
    if(x == y)
    { return; }
		
    let elt1 = array.node[x];
    let elt2 = array.node[y];

    array.node[y] = <{elt1.name()}/>;
    array.node[x] = elt2;
    array.node[y] = elt1;
}

function heapify(array, count)
{
    start = count / 2 - 1;
     
    while(start >=  0)
    {
    	siftDown(array, start, count-1);
	start = start - 1;
    }
}
 
function siftDown(array, start, end)
{
    root = start;

    while(root * 2 + 1 <=  end)
    {
    	child = root * 2 + 1;
	if(child < end && array.node[child].@key < array.node[child + 1].@key)
	{ child = child + 1; }
        
        if(array.node[root].@key < array.node[child].@key)
        {
            swap(array, root, child);
            root = child;
        } else {
            return;
        }
    }
}

function heapsort(array) 
{
    heapify(array, array.node.length());
 
    end = array.node.length() - 1;
    while(end > 0)
    {         
        swap(array, end, 0);
        end = end - 1;
        siftDown(array, 0, end);
    }
} 

// Génération des données de test et tri de ces données
var xml =  <xml></xml>;
for(let i = 0; i < 500; i++)
{ xml.node[i] = <node key={Math.floor(Math.random() * 2000)}/>; }

s = Date.now();
heapsort(xml);
alert('heapsorted (' + (Date.now() - s) + ')');

» Référence | Télécharger l'exemple

Tri rapide (en javascript)

function swap(array, x, y)
{
    if(x == y)
    { return; }
		
    let elt1 = array.node[x];
    let elt2 = array.node[y];

    array.node[y] = <{elt1.name()}/>;
    array.node[x] = elt2;
    array.node[y] = elt1;
}

function partition(array, left, right, pivotIndex)
{
    let pivotValue = array.node[pivotIndex].@key;
    swap(array, pivotIndex, right);
    let storeIndex = left;
    for(let i = left; i < right; i++)
    {
    	if(array.node[i].@key <= pivotValue)
        {
            swap(array, storeIndex, i);
            storeIndex += 1;
        }
    }
     
    swap(array, right, storeIndex);
    return storeIndex;
}

function quicksort(array, left, right)
{
    if(right > left)
    {
        let pivotIndex = left;
        pivotNewIndex  = partition(array, left, right, pivotIndex);
        quicksort(array, left, pivotNewIndex-1);
        quicksort(array, pivotNewIndex+1, right);
    }
}


// Génération des données de test et tri de ces données
var xml =  <xml></xml>;
for(let i = 0; i < 500; i++)
{ xml.node[i] = <node key={Math.floor(Math.random() * 2000)}/>; }

s = Date.now();
quicksort(xml, 0, xml.node.length()-1);
alert('quicksorted (' + (Date.now() - s) + ')');

» Référence | Télécharger l'exemple

Tri de tableau, en utilisant une fonction de comparaison javascript

// Génération des données
var xml =  <xml></xml>;
for(let i = 0; i < 500; i++)
{
    xml.node[i] = <node key={Math.floor(Math.random() * 2000)}/>;
}

// Remplissage du tableau avec ces données
s = Date.now();
ar = new Array();
for each(let node in xml.node)
{ ar.push(node); }

// Tri du tableau
ar.sort(function(a, b)
  {
  	if(a.@key < b.@key)
  	{ return - 1; }
  	else if(a.@key > b.@key)
  	{ return 1; }
  	
  	return 0; 
  });
alert('arraysorted (' + (Date.now() - s) + ')');

» Télécharger l'exemple

Tri de tableau, en utilisant la fonction native de comparaison

// Génération des données
var xml =  <xml></xml>;faire chuter
for(let i = 0; i < 500; i++)
{
    xml.node[i] = <node key={Math.floor(Math.random() * 2000)}/>;
}

// Remplissage du tableau avec ces données
s = Date.now();
ar = new Array();
for each(let node in xml.node)
{ ar.push(node.@key); }

// Tri du tableau
ar.sort();
alert('arraysorted (' + (Date.now() - s) + ')');

» Télécharger l'exemple

Tri XSLT

// Génération des données
var xml =  <xml></xml>;	
for(let i = 0; i < 500; i++)
{
  xml.node[i] = <node key={Math.floor(Math.random() * 2000)}/>;
}

// Tri XSLT
s = Date.now();
// xslt stylesheet
var xslt = '<?xml version="1.0" encoding="UTF-8"?>' + 
    '<xsl:stylesheet version="1.0"' + 
    ' 				xmlns="http://www.w3.org/1999/xhtml" xmlns:html="http://www.w3.org/1999/xhtml"'+
    '         xmlns:xsl="http://www.w3.org/1999/XSL/Transform">' + 
    '<xsl:output method="xml" indent="yes" />' + 	
    '<xsl:template match="/">' + 
    '	<xsl:apply-templates select="//node">' + 
    '		<xsl:sort select="@key" />' +
    '	</xsl:apply-templates>' +
    '</xsl:template>' +		
    '<xsl:template  match="node">' +
    '	<xsl:copy-of select="."/>' +
    '</xsl:template>' +
    '</xsl:stylesheet>';

var xsltproc = new XSLTProcessor();
xsltproc.importStylesheet(new DOMParser().parseFromString(xslt, "text/xml"));

var sorted = new XML(new XMLSerializer().serializeToString(
		xsltproc.transformToDocument(new DOMParser().parseFromString(xml, "text/xml")))
	);
alert('xsltsorted (' + (Date.now() - s) + ')');

» Référence | Télécharger l'exemple

Conclusion

Les résultats obtenus sont présentés dans le tableau suivant (NOTE: les vitesses ne sont pas intéressantes en tant que telles, c'est leur variation d'une méthode à une autre qui l'est) :

Méthode/Vitesse Tri par tas Tri rapide Tri de tableau (indirect) Tri de tableau (direct) tri via XSLT
5500 ms 4200 ms 220 ms 13 ms 35 ms

Les tri par tas et tri rapide étant écrit entièrement en javascript, ce sont naturellement les deux méthodes les plus lentes, Mais on peut faire deux remarques:

En conclusion, s'il est naturel d'utiliser un tableau pour trier des données basiques (entiers, chaînes de caractères), il sera préférable d'utiliser le tri XSLT pour trier un objet XML. Les performances sont très proches d'un "tri tableau", tout en étant plus souple à utiliser (tris multi-critères notamment).

$2007/06/22$

Blog