Parece que siempre ha habido un malentendido en el círculo frontal: el front-end no puede usar el conocimiento del algoritmo. Durante mucho tiempo, todos pueden haber sido influenciados por esta declaración. Hasta que encontré una demanda de productos hace un tiempo, miré hacia atrás y descubrí que este no era el caso.
Clasificación frontal
Escenario de clasificación frontal
El front-end pasa la condición de clasificación al back-end como un parámetro de solicitud, y el back-end devuelve el resultado de clasificación como una respuesta de solicitud al front-end, que es un diseño común. Pero no es tan adecuado para algunos productos.
Imagine un escenario: cuando usa una aplicación de alimentos, a menudo cambia el método de clasificación, lo ordene por precio y luego ordene calificar.
En la producción real, debido a factores como el costo del servidor, cuando una sola consulta de datos se convierte en un cuello de botella de rendimiento general, también se considera que optimiza el rendimiento clasificándolo en el front-end.
Algoritmo de clasificación
Siento que no hay necesidad de introducir esto. Como algoritmo básico en informática, la descripción se copiará directamente de Wikipedia .
Este párrafo existe aquí puramente con el propósito de heredar el primero (hombre) y el segundo (shu).
Clasificación de JavaScript
Como hablamos de la clasificación front-end, naturalmente pensaremos en la interfaz nativa Array.prototype.sort JavaScript.
Esta interfaz ha existido desde ECMAScript 1st Edition . Veamos cómo se ve la descripción en la última especificación.
Array.prototype.sort Especificación
Array.prototype.sort(compareFn)
La copia del código es la siguiente:
Los elementos de esta matriz están ordenados. El tipo no es estable necesario (es decir, elementos que comparan igual no necesariamente permanecen en su orden original). Si se compara no está indefinido, debe ser una función que acepte dos argumentos x e y y devuelva un valor negativo si x <y, cero si x = y o un valor positivo si x> y.
Obviamente, la especificación no limita cuál es el algoritmo sort implementado internamente. Incluso la implementación de la interfaz no necesita ser ordenada estable . Esto es muy importante y estará involucrado muchas veces a continuación.
En este contexto, la clasificación frontal en realidad depende de la implementación específica de cada navegador. Entonces, ¿cómo implementan la clasificación de los navegadores convencionales? A continuación, comparamos brevemente Chrome , Firefox y Microsoft Edge , respectivamente.
Implementación en Chrome
El motor JavaScript de Chrome es V8. Como es de código abierto, puede mirar el código fuente directamente.
Todo el array.js se implementa en el idioma JavaScript. La parte del método de clasificación es obviamente mucho más complicada que el tipo rápido que he visto, pero obviamente el algoritmo central sigue siendo una clasificación rápida. La razón del algoritmo complejo es que V8 ha realizado muchas optimizaciones para las consideraciones de rendimiento. (Hablaré de eso a continuación)
Implementación en Firefox
No es posible determinar cuál será el algoritmo de clasificación de matriz que el motor JavaScript de Firefox estará a punto de usar. [3]
Según la información existente, Spidermoney implementa la clasificación de fusión internamente.
Implementación en Microsoft Edge
La parte central del código para el chakra de motor JavaScript de Microsoft Edge se abrió en GitHub a principios de 2016.
Al mirar el código fuente, podemos encontrar que el algoritmo de clasificación de matriz de Chakra también implementa una clasificación rápida. Y en comparación con V8, solo implementa una clasificación puramente rápida, sin rastro de optimizaciones de rendimiento en V8.
Problemas con la clasificación de la matriz de JavaScript
Como todos sabemos, la clasificación rápida es un algoritmo de clasificación inestable, mientras que la clasificación de fusión es un algoritmo de clasificación estable. Debido a las diferencias en la selección de algoritmo de diferentes motores, el front-end se basa en el código JavaScript implementado por la interfaz Array.Prototype.Sort, y el efecto de clasificación real realizado en el navegador es inconsistente.
Las diferencias en la estabilidad de clasificación deben activarse por escenarios específicos antes de que haya un problema; En muchos casos, la clasificación inestable no tendrá ningún impacto.
Si no hay necesidad de estabilidad en la clasificación de matrices en el desarrollo real del proyecto, entonces puede ver esto, y las diferencias de implementación entre los navegadores no son tan importantes.
Pero si el proyecto requiere que el tipo sea estable, entonces la existencia de estas diferencias no satisfará la demanda. Necesitamos hacer un trabajo extra para esto.
Por ejemplo:
Las reglas ganadoras finales para el sistema de subasta de licencia de vehículos motorizados en una determinada ciudad son:
1. Ordenar por precio en reversa;
2. El mismo precio se ordenará positivamente de acuerdo con la orden de licitación (es decir, el tiempo de envío de precios).
Si la clasificación se realiza en la parte delantera, es probable que el ganador que se muestra en el navegador utilizando un clasificación rápida sea inconsistente con las expectativas.
Explorar las diferencias
Antes de encontrar una solución, es necesario explorar las razones del problema.
Por qué Chrome usa una clasificación rápida
De hecho, esta situación existió desde el principio.
Chrome Beta se lanzó el 2 de septiembre de 2008. Sin embargo, poco después de su lanzamiento, algunos desarrolladores presentaron comentarios de errores #90 al grupo de desarrollo de Chromium. La implementación de clasificación de matriz de V8 no es estable.
Esta discusión de problemas de errores abarca mucho. Hasta el 10 de noviembre de 2015, los desarrolladores aún comentaron sobre la implementación de la clasificación de matriz en V8.
Al mismo tiempo, también notamos que el problema ha sido cerrado. Sin embargo, fue reabierto por los miembros del equipo de desarrollo en junio de 2013 como referencia para la discusión de la próxima especificación de ECMAScript.
Y la conclusión final de ES-Discuss es
La copia del código es la siguiente:
No cambia. Estable es un subconjunto de inestable. Y viceversa, cada algoritmo inestable devuelve un resultado estable para algunas entradas. El punto de Mark es que requerir "siempre inestable" no tiene significado, sin importar el idioma que elija.
/Andreas
Como se describe en la especificación Ecmascript 2015 final citada anteriormente en este artículo.
Características de los tiempos
En mi humilde opinión, este problema se informó al comienzo del lanzamiento de Chrome, que puede tener sus propias características especiales de los tiempos.
Como se mencionó anteriormente, la primera versión de Chrome se lanzó en septiembre de 2008. Según las estadísticas de Statcounter, los dos navegadores con la mayor participación de mercado durante ese período fueron IE (solo IE6 e IE7 en ese momento) y Firefox, con una cuota de mercado alcanzando el 67.16% y 25.77% respectivamente. En otras palabras, la cuota de mercado combinada de los dos navegadores supera el 90%.
Según otras estadísticas de algoritmo de clasificación del navegador, estos dos navegadores con más del 90% de participación de mercado adoptan una clasificación de matriz estable. Por lo tanto, es razonable ser cuestionado por los desarrolladores al comienzo del lanzamiento de Chrome.
Cumplir con las especificaciones
Desde la discusión de problemas de errores, podemos comprender aproximadamente algunas consideraciones de los miembros del equipo de desarrollo al usar una clasificación rápida de implementación del motor.
Una de ellas es que creen que el motor debe cumplir con la especificación de ECMAScript. Dado que la especificación no requiere una descripción de la clasificación estable, creen que la implementación de V8 está completamente en línea con la especificación.
Consideraciones de rendimiento
Además, creen que una consideración importante en el diseño V8 es el rendimiento del motor.
La clasificación rápida tiene un mejor rendimiento general que la clasificación de fusiones:
Mayor eficiencia informática. La clasificación rápida es más rápida en un entorno de ejecución de computadora real que otros algoritmos de clasificación con la misma complejidad del tiempo (en caso de no alcanzar la peor combinación)
Costos de espacio más bajos. El primero solo tiene la complejidad del espacio o (n), en comparación con la última complejidad del espacio o (n), el consumo de memoria es menor durante el tiempo de ejecución.
Optimización de rendimiento de V8 en el algoritmo de clasificación de matriz
Dado que V8 está muy interesado en el rendimiento del motor, ¿qué hace en la clasificación de matriz?
Al leer el código fuente, todavía aprendí algunos conocimientos básicos.
Sorteo de inserción mixta
La clasificación rápida es la idea de dividir y conquistar, descomponer grandes matrices y recurrirlas por capa por capa. Sin embargo, si la profundidad de la recursión es demasiado grande, el consumo de recursos de memoria de la pila de llamadas recursivas también será muy grande. La mala optimización puede incluso causar desbordamiento de pila.
La implementación actual de V8 es establecer un umbral y usar la clasificación de inserción para pequeñas matrices de 10 o menos longitudes en la capa más baja.
De acuerdo con los comentarios del código y las descripciones en Wikipedia, aunque la complejidad promedio de tiempo de inserción es O (n²) es peor que la de la clasificación rápida o (nn). Sin embargo, en el entorno de ejecución, la eficiencia de usar la clasificación de inserción de matrices pequeñas es más eficiente que la clasificación rápida, por lo que no se ampliará aquí.
Ejemplo de código V8
var Quicksort = function Quicksort (a, desde, a) {...... while (true) {// El sort de inserción es más rápido para matrices cortas. if (a - from <= 10) {inservationsort (a, de, a); devolver; } ......} ......};Tres números están en
Como se sabe, el talón de clasificación rápida de Aquiles es que el algoritmo degenera en la peor combinación de matriz.
El núcleo del algoritmo de clasificación rápida es seleccionar un pivote y descomponer la matriz que se ha comparado e intercambiado en dos áreas numéricas de acuerdo con la referencia para la recursión posterior. Imagine si, para una matriz ya ordenada, el primer o último elemento siempre se selecciona cada vez que se seleccione el elemento de referencia, entonces habrá un área numérica que está vacía cada vez, y el número recursivo de capas alcanzará n, lo que eventualmente conducirá a la degradación de la complejidad del tiempo del algoritmo a O (n²). Por lo tanto, la elección del pivote es muy importante.
V8 utiliza la optimización de median-of-three : además de los dos elementos al principio y al final, se selecciona otro elemento para participar en la competencia del elemento de referencia.
La estrategia de selección para el tercer elemento es más o menos:
Cuando la longitud de la matriz sea menor o igual a 1000, seleccione el elemento en la media posición como el elemento de destino.
Cuando la longitud de la matriz exceda de 1000, seleccione un elemento a una distancia de 200-215 (no fijo, cambiando con la longitud de la matriz) para determinar primero un lote de elementos candidatos. Luego ordene los elementos candidatos en este lote y use el valor medio resultante como el elemento objetivo.
Finalmente, tome el valor medio de los tres elementos como pivote.
Ejemplo de código V8
var getThirDIndex = function (a, desde, a) {var t_array = new GonalArray (); // Use tanto 'de' como 'a' para determinar los candidatos pivote. var increment = 200 + ((a - desde) y 15); var j = 0; de += 1; a -= 1; for (var i = from; i <to; i += increment) {t_array [j] = [i, a [i]]; j ++; } t_array.sort (function (a, b) {return compareFn (a [1], b [1]);}); var tercero_index = t_array [t_array.length >> 1] [0]; return Third_Index;}; var QuickSort = function Quicksort (a, de, a) {...... while (true) {...... if (a - from> 1000) {tercero_index = getThirdIndex (a, from, to); } else {tercero_index = desde + ((a - desde) >> 1); }} ......};Ordenar en su lugar
Al revisar el algoritmo de clasificación rápida, vi muchos ejemplos de implementación utilizando JavaScript en Internet.
Pero descubrí que una gran parte de la implementación del código es la siguiente
var Quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var izquierda = []; var right = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return Quicksort (izquierda) .concat ([Pivot], Quicksort (derecha));};El principal problema con el código anterior es: usar las dos áreas numéricas a la izquierda y a la derecha para almacenar subarrañas recursivas, por lo que requiere un espacio de almacenamiento adicional de O (N). Esta es una gran diferencia en comparación con la complejidad espacial promedio teórica O (N).
La sobrecarga del espacio adicional también afectará la velocidad total del tiempo de ejecución real. Esta es también una de las razones por las cuales la clasificación rápida puede funcionar en tiempos de ejecución reales más allá del mismo nivel de complejidad del tiempo. Por lo tanto, en términos generales, la clasificación rápida con un mejor rendimiento adoptará la clasificación en el lugar.
La implementación en el código fuente V8 es intercambiar elementos en la matriz original.
Por qué Firefox utiliza la clasificación de fusión
También hay una historia detrás de esto.
De hecho, cuando Firefox se lanzó al principio, no utilizó un algoritmo de clasificación estable para implementar la clasificación de matrices, que está bien documentado.
El algoritmo de clasificación de matriz implementado por la versión original de Firefox (Firebird) fue la clasificación de almacenamiento, que también es un algoritmo de clasificación inestable. Por lo tanto, alguien luego presentó un error.
El equipo de desarrollo de Mozilla ha realizado una serie de discusiones sobre este tema.
Desde el proceso de discusión, podemos dibujar algunos puntos
1. El competidor de Mozilla durante el mismo período fue IE6. De las estadísticas anteriores, podemos ver que IE6 es estable en la clasificación.
2.Brendan Eich, el padre de JavaScript, cree que la estabilidad es buena
3. Firefox usa una clasificación rápida antes de la clasificación de los montantes
Según la premisa principal de que los miembros del grupo de desarrollo tienden a implementar algoritmos de clasificación estable, Firefox3 toma la clasificación de fusiones como una nueva implementación de la clasificación de matriz.
Resolver las diferencias en la estabilidad de clasificación
He dicho mucho por lo que principalmente para decir las diferencias en la implementación de la clasificación de cada navegador y explicar algunas de las razones más superficiales por las que existen estas diferencias.
Pero después de leer esto, los lectores aún pueden tener preguntas: ¿qué debo hacer si mi proyecto solo necesita confiar en la clasificación estable?
Solución
De hecho, la idea de resolver este problema es relativamente simple.
El navegador elige diferentes algoritmos de clasificación para diferentes consideraciones. Algunos pueden tender a buscar un rendimiento extremo, mientras que otros tienden a proporcionar una buena experiencia de desarrollo, pero hay reglas a seguir.
A juzgar por la situación actual conocida, todos los navegadores convencionales (incluidos IE6, 7, 8) pueden enumerar básicamente la implementación de algoritmos de clasificación de matriz:
1. Fusionar clasificación/Timsort
2. Sorteo rápido
Entonces, ¿podemos transformar la clasificación rápida en una clasificación estable?
En términos generales, el uso de clasificación inestable para matrices de objetos afectará los resultados. Mientras que otros tipos de matrices en sí usan resultados de clasificación estable o inestable son iguales. Por lo tanto, el plan es más o menos como sigue:
Preprocese la matriz para que se clasifique y agregue los atributos de orden natural a cada objeto que se clasifiquen, para no entrar en conflicto con otros atributos del objeto.
El método de comparación de clasificación personalizada CompareFn siempre utiliza el orden natural como la segunda dimensión de juicio cuando el prejuicio es igual.
Cuando se enfrentan a implementaciones como la clasificación de fusiones, dado que el algoritmo en sí es estable, la comparación de pedidos naturales adicionales no cambiará el resultado de la clasificación, por lo que la compatibilidad del esquema es mejor.
Sin embargo, implica modificar la matriz a clasificar, y se necesita espacio adicional para almacenar propiedades de orden natural. Es concebible que los motores como V8 no usen métodos similares. Sin embargo, es factible como un plan de clasificación personalizado por los desarrolladores.
Ejemplo de código de esquema
'Use Strict'; const index = Symbol ('índice'); function getComparer (compare) {function de return (izquierda, derecho) {let result = compare (izquierda, derecha); Resultado de retorno === 0? izquierda [índice] - derecho [índice]: resultado; };} function sort (array, compare) {array = array.map ((item, index) => {if (typeof item === 'object') {item [index] = index;} return item;}); return array.sort (getComparer (comparar));}Lo anterior es solo un ejemplo de modificación de algoritmo simple que satisface la clasificación estable.
La razón por la que es simple es que las estructuras de datos como entradas de matriz en el entorno de producción real son complejas, y es necesario juzgar si se requieren más tipos de pedidos anticipados en función de la situación real.
Etiqueta
1. El front-end es ahora un concepto relativamente amplio. El front-end en este artículo se refiere principalmente al entorno utilizando el navegador como portador y JavaScript como lenguaje de programación.
2. Este artículo no tiene la intención de involucrar al algoritmo en su conjunto. Me gustaría usar algoritmos de clasificación comunes como punto de entrada.
3. Al confirmar el algoritmo implementado por la clasificación de la matriz de Firefox, se encontró un error relacionado con la clasificación en Spidermoney. En términos generales, durante la discusión, alguien sugirió usar el algoritmo Timsort con un mejor rendimiento en casos extremos para reemplazar la clasificación de fusión, pero los ingenieros de Mozilla dijeron que debido al problema de autorización de licencias del algoritmo de Timsort, no hay forma de usar directamente el algoritmo en el software de Mozilla y esperar la respuesta posterior de la otra parte.
Resumir
Lo anterior es un resumen y una solución a los problemas encontrados en la clasificación frontal. En los últimos años, cada vez más proyectos están cambiando hacia aplicaciones de clientes ricos, y la proporción de front-end en proyectos ha aumentado. Con la mejora adicional de la potencia informática del navegador en el futuro, permite algunos cálculos más complejos. Con el cambio de responsabilidades, el formulario frontal también puede sufrir algunos cambios importantes. Al caminar en el mundo, siempre debes tener una habilidad.