Une idée de la manière dont je peux voir la mise en œuvre de méthodes javascript natives spécifiquement le tri méthode. La raison pour laquelle je cherche cela, je me demandais simplement ce que l'algorithme utilisé est et quelle est la complexité de la même chose.
Je trie un énorme objet JSON en JavaScript et je me demandais si je devais écrire ma propre Mety Hod pour la même chose.
La mise en œuvre diffère également du navigateur au navigateur?
3 Réponses :
Jetez un coup d'œil à la mise en œuvre de WebKit: https://gist.github.com/964673 . Apparemment, il utilise un tri de tri / sélection min. De: http://svn.webkit.org/repository /webkit/trunk/source/javascriptcore/Runtime/arrayPrototype.cpp
Spidermonkey semble utiliser effectivement Mergesort. Voir: http://hg.mozilla.org/mozilla -Central / Fichier / 28BE8DF0DEB7 / JS / SRC / JSARRAY.CPP .
La mise en œuvre diffère également du navigateur au navigateur?
Oui, la norme ECMAScript ne spécifie pas quel algorithme doit être utilisé. Afaik Mozillas Spidermonkey utilise Mergesort et WebKit utilise la sélection de sélection. Qu'est-ce que IE utilise, vous devez probablement demander à quelqu'un chez Microsoft, car c'est une source fermée.
Et je suis prêt à parier quelques dollars que vous ne pouvez pas trouver un algorithme meilleur / plus rapide que celui implémenté dans le moteur JavaScript des navigateurs.
c'est vrai .. mais je peux l'écrire d'une manière qui convient à mon problème .. Je ne suis pas inquiet pour la performance sur chrome ou FFX. C'est surtout ie7
Malheureusement, il ne semble pas être une méthode standardisée.
Jusqu'à ce moment-là, vous pouvez écrire votre propre fonction d'alphabétisation simple: P>
sortObject = function (){
var arr = [], i;
for(i in this){
arr.push({index:i,content:this[i]});
delete this[i];
}
arr.sort();
for(i in arr){
var item = arr[i];
this[item.index] = item.content;
}
return this; // make chainable
}
var obj = {
acronym: "OOP",
definition: "Object-Oriented Programming",
article: "http://wikipedia.org/OOP"
};
sortObject.apply(obj); // indices are "acronym", "article", "definition"
Quoi que vous fassiez, je peux vous garantir que vous ne sera pas Code optimisé à la main C ou C ++ code dans JS pour le cas général. Utilisez simplement l'option existante, cela fonctionnera assez bien. Et si ce n'est pas le cas, le goulot d'étranglement est probablement pas
trier mais certains de vos algorithmes.Non, il n'y a pas d'autre goulot d'étranglement ..Les performances sont suffisamment bonnes mais comme l'absence d'entités augmente le nombre de comparaisons augmente. Se demandait ce qui se passe à l'intérieur de cette méthode.
Bien sûr, le nombre de comparaisons augmenter, même les algorithmes de tri des meilleurs (complexité-sage) sont
O (n * journal n) ;)