Il semble qu'il y ait toujours eu un malentendu dans le cercle frontal: le frontal ne peut pas utiliser la connaissance des algorithmes. Pendant longtemps, tout le monde a peut-être été influencé par cette déclaration. Jusqu'à ce que je rencontre une demande de produit il y a quelque temps, j'ai regardé en arrière et j'ai constaté que ce n'était pas le cas.
Tri avant
Scénario de tri avant
Le frontal passe la condition de tri à l'arrière-end en tant que paramètre de demande, et le back-end renvoie le résultat de tri en tant que réponse de demande au frontal, ce qui est une conception courante. Mais ce n'est pas si adapté à certains produits.
Imaginez un scénario: lorsque vous utilisez une application alimentaire, changez-vous souvent la méthode de tri, triez-la par prix, puis triez par note.
Dans la production réelle, en raison de facteurs tels que le coût du serveur, lorsqu'une seule requête de données devient un goulot d'étranglement global de performances, il est également considéré comme optimiser les performances en le triant en frontal.
Algorithme de tri
Je pense qu'il n'est pas nécessaire de le présenter. En tant qu'algorithme de base en informatique, la description sera copiée directement à partir de Wikipedia .
Ce paragraphe existe ici uniquement dans le but de hériter du premier (homme) et du second (Shu).
Tri javascript
Puisque nous parlons du tri frontal, nous penserons naturellement à l'interface native de JavaScript Array.prototype.sort .
Cette interface existe depuis ECMAScript 1st Edition . Voyons à quoi ressemble sa description dans la dernière spécification.
Array.prototype.sort Spécification
Array.prototype.sort(compareFn)
La copie de code est la suivante:
Les éléments de ce tableau sont triés. Le tri n'est pas nécessaire (c'est-à-dire que les éléments qui comparent l'égalité ne restent pas nécessairement dans leur ordre d'origine). Si comparé n'est pas non défini, il devrait être une fonction qui accepte deux arguments x et y et renvoie une valeur négative si x <y, zéro si x = y, ou une valeur positive si x> y.
De toute évidence, la spécification ne limite pas ce que l'algorithme sort implémenté est en interne. Même l'implémentation de l'interface n'a pas besoin d'être triée stable . Ceci est très important et sera impliqué à plusieurs reprises ensuite.
Dans ce contexte, le tri frontal dépend en fait de l'implémentation spécifique de chaque navigateur. Alors, comment les navigateurs grand public implémentent-ils le tri? Ensuite, nous comparons brièvement Chrome , Firefox et Microsoft Edge respectivement.
Implémentation dans Chrome
Le moteur JavaScript de Chrome est le V8. Puisqu'il est open source, vous pouvez consulter directement le code source.
L'ensemble Array.js est implémenté dans la langue javascript. La partie de la méthode de tri est évidemment beaucoup plus compliquée que le tri rapide que j'ai vu, mais évidemment, l'algorithme de base est toujours un tri rapide. La raison de l'algorithme complexe est que V8 a fait de nombreuses optimisations pour les considérations de performance. (Je vais en parler ensuite)
Implémentation dans Firefox
Il n'est pas possible de déterminer l'algorithme de tri du tableau que le moteur JavaScript de Firefox sera sur le point d'utiliser. [3]
Selon les informations existantes, SpiderMoney implémente le tri de fusion en interne.
Implémentation dans Microsoft Edge
La partie principale du code du chakra du moteur JavaScript de Microsoft Edge a été ouverte sur Github début 2016.
En regardant le code source, nous pouvons constater que l'algorithme de tri de tableau de Chakra implémente également le tri rapide. Et par rapport au V8, il implémente uniquement le tri purement rapide, sans aucune trace d'optimisations de performances en V8.
Problèmes avec le tri du tableau JavaScript
Comme nous le savons tous, le tri rapide est un algorithme de tri instable, tandis que le tri de fusion est un algorithme de tri stable. En raison des différences de sélection d'algorithmes de différents moteurs, le frontal s'appuie sur le code JavaScript implémenté par l'interface array.prototype.sort, et l'effet de tri réel effectué dans le navigateur est incohérent.
Les différences de stabilité de tri doivent être déclenchées par des scénarios spécifiques avant qu'il n'y ait un problème; Dans de nombreux cas, le tri instable n'aura aucun impact.
S'il n'y a pas besoin de stabilité dans le tri des tableaux dans le développement réel du projet, vous pouvez réellement le voir, et les différences de mise en œuvre entre les navigateurs ne sont pas si importantes.
Mais si le projet exige que le type soit stable, l'existence de ces différences ne répondra pas à la demande. Nous devons faire un travail supplémentaire pour cela.
Par exemple:
Les règles de victoire finales pour le système d'enchères de licence de véhicules à moteur dans une certaine ville sont:
1. Trier par prix en sens inverse;
2. Le même prix sera trié positivement en fonction de l'ordonnance d'appel d'offres (c'est-à-dire le temps de soumission des prix).
Si le tri est effectué à l'avant, le gagnant affiché dans le navigateur à l'aide d'un tri rapide est susceptible d'être incompatible avec les attentes.
Explorez les différences
Avant de trouver une solution, il est nécessaire d'explorer les raisons du problème.
Pourquoi Chrome utilise un tri rapide
En fait, cette situation existait depuis le début.
Chrome Beta a été publié le 2 septembre 2008. Cependant, peu de temps après sa sortie, certains développeurs ont soumis un commentaire de bogue n ° 90 au Chromium Development Group. L'implémentation de tri du tableau de V8 n'est pas stable.
Cette discussion sur le problème des bogues s'étend beaucoup. Jusqu'au 10 novembre 2015, les développeurs ont toujours commenté la mise en œuvre du tri des tableaux en V8.
Dans le même temps, nous avons également remarqué que le problème avait été fermé. Cependant, il a été rouvert par les membres de l'équipe de développement en juin 2013 en tant que référence pour la discussion de la prochaine spécification ECMAScript.
Et la conclusion finale de l'ES-Discuss est
La copie de code est la suivante:
Cela ne change pas. Stable est un sous-ensemble de instable. Et vice versa, chaque algorithme instable renvoie un résultat stable pour certaines entrées. Le point de Mark est que nécessiter «toujours instable» n'a aucun sens, quelle que soit la langue que vous choisissez.
/ Andreas
Comme décrit dans la spécification finalisée ECMAScript 2015 citée plus tôt dans cet article.
Caractéristiques de l'époque
IMHO, ce problème a été signalé au début de la libération de Chrome, qui peut avoir ses propres caractéristiques spéciales de l'époque.
Comme mentionné ci-dessus, la première version de Chrome a été publiée en septembre 2008. Selon les statistiques de StatCounter, les deux navigateurs avec la part de marché la plus élevée au cours de cette période étaient IE (seuls IE6 et IE7 à l'époque) et Firefox, avec des parts de marché atteignant 67,16% et 25,77% respectivement. En d'autres termes, la part de marché combinée des deux navigateurs dépasse 90%.
Selon une autre statistique des algorithmes de tri de navigateur, ces deux navigateurs avec plus de 90% de parts de marché adoptent un tri stable. Par conséquent, il est raisonnable d'être remis en question par les développeurs au début de la sortie de Chrome.
Respecter les spécifications
À partir de la discussion sur le problème des bogues, nous pouvons à peu près comprendre certaines considérations des membres de l'équipe de développement dans l'utilisation du tri rapide de la mise en œuvre du moteur.
L'un d'eux est qu'ils croient que le moteur doit se conformer à la spécification ECMAScript. Étant donné que la spécification ne nécessite pas de description du tri stable, ils croient que l'implémentation de V8 est entièrement conforme à la spécification.
Considérations de performance
En outre, ils croient qu'une considération importante dans la conception V8 est les performances du moteur.
Le tri rapide fonctionne de meilleures performances globales que la fusion du tri:
Efficacité informatique plus élevée. Le tri rapide est plus rapide dans un environnement d'exécution d'ordinateur réel que les autres algorithmes de tri avec la même complexité du temps (en cas de ne pas frapper la pire combinaison)
Réduire les coûts d'espace. Le premier n'a qu'une complexité spatiale O (n), par rapport à la complexité spatiale O (n), la consommation de mémoire est moindre pendant l'exécution.
Optimisation des performances du V8 dans l'algorithme de tri des tableaux
Étant donné que V8 est très intéressé par les performances du moteur, que fait-il dans le tri des tableaux?
En lisant le code source, j'ai quand même appris quelques connaissances de base.
Tri mixte
Le tri rapide est l'idée de diviser et de conquérir, de décomposer de grands tableaux et de les récurer vers le bas par couche. Cependant, si la profondeur de la récursivité est trop grande, la consommation de ressources de mémoire de la pile d'appels récursive sera également très importante. Une mauvaise optimisation peut même provoquer un débordement de pile.
L'implémentation actuelle de V8 consiste à définir un seuil et à utiliser le tri des insert pour de petits tableaux de 10 longueurs ou moins dans la couche la plus basse.
Selon les commentaires et descriptions du code dans Wikipedia, bien que la complexité de temps moyenne du tri d'insertion soit O (n²) est pire que celle du tri rapide O (nn). Cependant, dans l'environnement de course, l'efficacité de l'utilisation du tri insert de petits tableaux est plus efficace que le tri rapide, il ne sera donc pas élargi ici.
Exemple de code V8
var Quicksort = fonction Quicksort (a, from, to) {...... while (true) {// Le tri d'insertion est plus rapide pour les tableaux courts. if (to - from <= 10) {insertionsort (a, from, to); retour; } ......} ......};Trois nombres sont dans
Comme on le sait, le talon d'Achille à tri rapide est que l'algorithme dégénère dans la pire combinaison de tableau.
Le cœur de l'algorithme de tri rapide consiste à sélectionner un pivot, et à décomposer le tableau qui a été comparé et échangé en deux zones de nombre en fonction de la référence pour la récursivité ultérieure. Imaginez si, pour un tableau déjà commandé, le premier ou le dernier élément est toujours sélectionné chaque fois que l'élément de référence est sélectionné, il y aura une zone numérique vide à chaque fois, et le nombre récursif de couches atteindra n, ce qui mènera finalement à la dégradation de la complexité temporelle de l'algorithme à O (n²). Par conséquent, le choix du pivot est très important.
V8 utilise l'optimisation de median-of-three : en plus des deux éléments au début et à la fin, un autre élément est sélectionné pour participer à la compétition de l'élément de référence.
La stratégie de sélection pour le troisième élément est à peu près:
Lorsque la longueur du tableau est inférieure ou égale à 1000, sélectionnez l'élément à la demi-position comme élément cible.
Lorsque la longueur du réseau dépasse 1000, sélectionnez un élément à une distance de 200-215 (non fixé, changeant avec la longueur du réseau) pour déterminer d'abord un lot d'éléments candidats. Triez ensuite les éléments candidats de ce lot et utilisez la valeur médiane résultante comme élément cible.
Enfin, prenez la valeur médiane des trois éléments comme pivot.
Exemple de code V8
var getThirdIdEx = fonction (a, from, to) {var t_array = new interalArray (); // Utilisez à la fois «de» et «pour» pour déterminer les candidats au pivot. var incrément = 200 + ((à - de) & 15); var j = 0; de + = 1; à - = 1; pour (var i = de; i <à; i + = incrément) {t_array [j] = [i, a [i]]; j ++; } t_array.sort (fonction (a, b) {return comparefn (a [1], b [1]);}); var tiers_index = t_array [t_array.length >> 1] [0]; return tiers_index;}; var Quicksort = function Quicksort (a, from, to) {...... while (true) {...... if (to - from> 1000) {tiers_index = getTHirdIndex (a, from, to); } else {tiers_index = de + ((à - de) >> 1); }} ......};Trier en place
Lors de l'examen de l'algorithme de tri rapide, j'ai vu de nombreux exemples d'implémentation à l'aide de JavaScript sur Internet.
Mais j'ai trouvé qu'une grande partie de l'implémentation du code est la suivante
var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var gauche = []; var droit = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {Left.push (arr [i]); } else {droite.push (arr [i]); }} return Quicksort (gauche) .concat ([pivot], Quicksort (à droite));};Le principal problème avec le code ci-dessus est: l'utilisation des deux zones numériques à gauche et à droite pour stocker les sous-réseaux récursifs, il nécessite donc un espace de stockage supplémentaire de O (n). Il s'agit d'une grande différence par rapport à la complexité spatiale moyenne théorique O (n).
Les frais généraux d'espace supplémentaires affecteront également la vitesse globale de l'exécution réelle. C'est également l'une des raisons pour lesquelles le tri rapide peut fonctionner à des temps d'exécution réels au-delà du même niveau de complexité de temps. Par conséquent, de manière générale, le tri rapide avec de meilleures performances adoptera le tri sur place.
L'implémentation dans le code source V8 consiste à échanger des éléments sur le tableau d'origine.
Pourquoi Firefox utilise le tri de fusion
Il y a aussi une histoire derrière.
En fait, lorsque Firefox a été publié au début, il n'a pas utilisé d'algorithme de tri stable pour implémenter le tri des tableaux, qui est bien documenté.
L'algorithme de tri du tableau implémenté par la version originale de Firefox (Firebird) était un tri de tas, qui est également un algorithme de tri instable. Par conséquent, quelqu'un a ensuite soumis un bogue.
L'équipe de développement de Mozilla a mené une série de discussions sur cette question.
Du processus de discussion, nous pouvons tirer certains points
1. Le concurrent de Mozilla pendant la même période a été IE6. D'après les statistiques ci-dessus, nous pouvons voir que IE6 est stable dans le tri.
2.Brendan Eich, le père de Javascript, pense que la stabilité est bonne
3. Firefox utilise le tri rapide avant le tri des tas
Sur la base de la prémisse principale que les membres du groupe de développement ont tendance à mettre en œuvre des algorithmes de tri stables, FireFox3 prend le tri de fusion en tant que nouvelle implémentation du tri des tableaux.
Résoudre les différences dans le tri stabilité
J'ai dit tant de choses au-dessus principalement pour raconter les différences dans la mise en œuvre de tri de chaque navigateur et pour expliquer certaines des raisons les plus superficielles pour lesquelles ces différences existent.
Mais après avoir lu ceci, les lecteurs peuvent toujours avoir des questions: que dois-je faire si mon projet a juste besoin de compter sur un tri stable?
Solution
En fait, l'idée de résoudre ce problème est relativement simple.
Le navigateur choisit différents algorithmes de tri pour différentes considérations. Certains peuvent avoir tendance à poursuivre des performances extrêmes, tandis que d'autres ont tendance à offrir une bonne expérience de développement, mais il y a des règles à suivre.
À en juger par la situation connue actuelle, tous les navigateurs traditionnels (y compris IE6, 7, 8) peuvent essentiellement énumérer la mise en œuvre d'algorithmes de tri des tableaux:
1. Fusionner le tri / Timsort
2. Sort rapide
Donc, nous pouvons simplement transformer le tri rapide en un tri stable?
D'une manière générale, l'utilisation de tri instable pour les réseaux d'objets affectera les résultats. Tandis que d'autres types de tableaux eux-mêmes utilisent des résultats de tri stables ou instables sont égaux. Par conséquent, le plan est à peu près le suivant:
Prétraitez le tableau à tri et ajoutez des attributs d'ordre naturel à chaque objet à tri, afin de ne pas entrer en conflit avec d'autres attributs de l'objet.
Méthode de comparaison de tri personnalisée Comparefn utilise toujours l'ordre naturel comme deuxième dimension de jugement lorsque le pré-jugement est égal.
Lorsqu'ils sont confrontés à des implémentations telles que le tri de fusion, puisque l'algorithme lui-même est stable, la comparaison supplémentaire des commandes naturelles ne modifiera pas le résultat de tri, donc la compatibilité du schéma est meilleure.
Cependant, il s'agit de modifier le tableau à tri, et un espace supplémentaire est nécessaire pour stocker les propriétés de commande naturelle. Il est concevable que les moteurs comme V8 ne soient pas utilisés par des méthodes similaires. Cependant, il est possible comme un plan de tri personnalisé par les développeurs.
Exemple de code du schéma
'use strict'; const index = symbol ('index'); function getComparer (comparer) {return function (gauche, droit) {let result = compare (gauche, droite); Retour Résultat === 0? gauche [index] - droit [index]: résultat; };} fonction tri (array, compare) {array = array.map ((item, index) => {if (typeof item === 'objet') {item [index] = index;} return item;}); return array.sort (getComparer (comparer));}Ce qui précède n'est qu'un exemple de modification d'algorithme simple qui satisfait le tri stable.
La raison pour laquelle il est simple est que les structures de données en tant qu'entrées de tableau dans l'environnement de production réel sont complexes, et il est nécessaire de juger si davantage de types de précommandation sont requis en fonction de la situation réelle.
Étiqueter
1. Le front-end est désormais un concept relativement large. Le front-end dans cet article fait principalement référence à l'environnement utilisant le navigateur comme opérateur et javascript comme langage de programmation.
2. Cet article n'a pas l'intention d'impliquer l'algorithme dans son ensemble. Je voudrais utiliser des algorithmes de tri communs comme point d'entrée.
3. Lors de la confirmation de l'algorithme implémenté par le tri du tableau Firefox, un bogue lié à la tri a été trouvé dans Spidermoney. D'une manière générale, lors de la discussion, quelqu'un a suggéré d'utiliser l'algorithme Timsort avec de meilleures performances dans des cas extrêmes pour remplacer le tri de la fusion, mais Mozilla Engineers a déclaré qu'en raison du problème d'autorisation de licence de l'algorithme Timsort, il n'y a aucun moyen d'utiliser directement l'algorithme dans le logiciel de Mozilla et d'attendre la réponse subséquente de l'autre partie.
Résumer
Ce qui précède est un résumé et une solution aux problèmes rencontrés dans le tri frontal. Ces dernières années, de plus en plus de projets changent vers de riches applications clients, et la proportion de front-end dans les projets a augmenté. Avec une amélioration supplémentaire de la puissance de calcul du navigateur à l'avenir, il permet des calculs plus complexes. Avec le changement de responsabilités, la forme frontale peut également subir des changements majeurs. Lorsque vous marchez dans le monde, vous devez toujours avoir une compétence.