Parece que sempre houve um mal-entendido no círculo de front-end: o front-end não pode usar o conhecimento do algoritmo. Por um longo tempo, todos podem ter sido influenciados por esta afirmação. Até que encontrei uma demanda de produtos há um tempo, olhei para trás e descobri que esse não era o caso.
Classificação front-end
Cenário de classificação front-end
O front-end passa a condição de classificação para o parâmetro de back-end como uma solicitação, e o back-end retorna o resultado de classificação como uma resposta de solicitação ao front-end, que é um design comum. Mas não é tão adequado para alguns produtos.
Imagine um cenário: quando você usa um aplicativo de alimentos, geralmente muda o método de classificação, classifica -o por preço e, em seguida, classifica a classificação.
Na produção real, devido a fatores como o custo do servidor, quando uma única consulta de dados se torna um gargalo geral de desempenho, também é considerado para otimizar o desempenho, classificando-o no front-end.
Algoritmo de classificação
Sinto que não há necessidade de apresentar isso. Como algoritmo básico na ciência da computação, a descrição será copiada diretamente da Wikipedia .
Este parágrafo existe aqui puramente para o propósito de herdar o primeiro (homem) e o segundo (shu).
JavaScript Classificação
Como conversamos sobre a classificação do front-end, naturalmente pensaremos na nativa da interface do JavaScript Array.prototype.sort .
Esta interface existe desde ECMAScript 1st Edition . Vamos ver como é a descrição na especificação mais recente.
Especificação de array.prototype.sort
Array.prototype.sort(compareFn)
A cópia do código é a seguinte:
Os elementos dessa matriz são classificados. O tipo não é necessário estável (ou seja, elementos que comparam igual não permanecem necessariamente em sua ordem original). Se comparado não é indefinido, deve ser uma função que aceite dois argumentos x e y e retorna um valor negativo se x <y, zero se x = y, ou um valor positivo se x> y.
Obviamente, a especificação não limita o que é o algoritmo de sort implementado internamente. Mesmo a implementação da interface não precisa ser classificada estável . Isso é muito importante e estará envolvido muitas vezes a seguir.
Nesse contexto, a classificação front-end depende da implementação específica de cada navegador. Então, como os navegadores principais implementam a classificação? Em seguida, comparamos brevemente o Chrome , o Firefox e o Microsoft Edge , respectivamente.
Implementação no Chrome
O mecanismo JavaScript do Chrome é V8. Como é de código aberto, você pode olhar diretamente para o código -fonte.
Toda a Array.js é implementada no idioma JavaScript. A parte do método de classificação é obviamente muito mais complicada do que a classificação rápida que eu vi, mas obviamente o algoritmo principal ainda é classificação rápida. A razão para o algoritmo complexo é que o V8 fez muitas otimizações para considerações de desempenho. (Vou falar sobre isso a seguir)
Implementação no Firefox
Não é possível determinar qual o algoritmo de classificação da matriz que o mecanismo JavaScript do Firefox estará prestes a usar. [3]
De acordo com as informações existentes, o SpiderMoney implementa a classificação internamente.
Implementação no Microsoft Edge
A parte central do código para o chakra do mecanismo JavaScript do Microsoft Edge foi inaugurada proveniente do GitHub no início de 2016.
Observando o código -fonte, podemos descobrir que o algoritmo de classificação da matriz do Chakra também implementa a classificação rápida. E comparado ao V8, ele implementa apenas a classificação puramente rápida, sem traços de otimizações de desempenho no V8.
Problemas com a classificação de JavaScript
Como todos sabemos, a classificação rápida é um algoritmo de classificação instável, enquanto a classificação de mesclagem é um algoritmo de classificação estável. Devido às diferenças na seleção de algoritmos de diferentes motores, o front-end depende do código JavaScript implementado pela interface Array.prototype.Sort, e o efeito de classificação real executado no navegador é inconsistente.
As diferenças na estabilidade da classificação precisam ser desencadeadas por cenários específicos antes que haja um problema; Em muitos casos, a classificação instável não terá nenhum impacto.
Se não houver necessidade de estabilidade na classificação de matrizes no desenvolvimento real do projeto, você poderá ver isso, e as diferenças de implementação entre os navegadores não são tão importantes.
Mas se o projeto exigir que o tipo seja estável, a existência dessas diferenças não atende à demanda. Precisamos fazer algum trabalho extra para isso.
Por exemplo:
As regras finais vencedoras para o sistema de leilão de licença de veículo a motor em uma determinada cidade são:
1. Classificar por preço ao contrário;
2. O mesmo preço será classificado positivamente de acordo com a ordem de licitação (ou seja, o horário de envio do preço).
Se a classificação for feita no front -end, o vencedor exibido no navegador usando a classificação rápida provavelmente será inconsistente com as expectativas.
Explore as diferenças
Antes de encontrar uma solução, é necessário explorar os motivos do problema.
Por que o Chrome usa classificação rápida
De fato, essa situação existia desde o início.
O Chrome Beta foi lançado em 2 de setembro de 2008. No entanto, logo após seu lançamento, alguns desenvolvedores enviaram feedback de bugs nº 90 ao grupo de desenvolvimento do cromo. A implementação de classificação da matriz do V8 não é estável.
Essa discussão em questão de bug se estende muito. Até 10 de novembro de 2015, os desenvolvedores ainda comentaram a implementação da classificação do Array no V8.
Ao mesmo tempo, também percebemos que o problema foi fechado. No entanto, foi reaberto pelos membros da equipe de desenvolvimento em junho de 2013 como uma referência para discussão do ECMAScript Próximo especificação.
E a conclusão final de Es-Discuss é
A cópia do código é a seguinte:
Não muda. Estável é um subconjunto de instável. E vice -versa, todo algoritmo instável retorna um resultado estável para algumas entradas. O ponto de Mark é que exigir "sempre instável" não tem significado, independentemente da linguagem que você escolher.
/Andreas
Conforme descrito na especificação ECMAScript 2015 finalizada citada anteriormente neste artigo.
Características dos tempos
IMHO, esse problema foi relatado no início do lançamento do Chrome, que pode ter suas próprias características especiais do Times.
Como mencionado acima, a primeira versão do Chrome foi lançada em setembro de 2008. Segundo as estatísticas do StatCounter, os dois navegadores com a maior participação de mercado durante esse período foram IE (apenas IE6 e IE7 naquela época) e Firefox, com a participação de mercado atingindo 67,16% e 25,77%, respectivamente. Em outras palavras, a participação de mercado combinada dos dois navegadores excede 90%.
De acordo com outra estatística do algoritmo de classificação do navegador, esses dois navegadores com mais de 90% de participação de mercado adotam a classificação estável. Portanto, é razoável ser questionado pelos desenvolvedores no início do lançamento do Chrome.
Cumprir as especificações
A partir da discussão em questão de bugs, podemos entender aproximadamente algumas considerações dos membros da equipe de desenvolvimento ao usar a classificação rápida da implementação do motor.
Uma delas é que eles acreditam que o mecanismo deve cumprir a especificação do ECMAScript. Como a especificação não requer uma descrição da classificação estável, eles acreditam que a implementação do V8 está totalmente alinhada com a especificação.
Considerações de desempenho
Além disso, eles acreditam que uma consideração importante no design V8 é o desempenho do mecanismo.
A classificação rápida tem melhor desempenho geral do que a classificação de mesclagem:
Maior eficiência da computação. A classificação rápida é mais rápida em um ambiente de execução de computador real do que outros algoritmos de classificação com a mesma complexidade de tempo (no caso de não atingir a pior combinação)
Custos de espaço mais baixos. O primeiro tem apenas a complexidade do espaço O (n), em comparação com a complexidade do espaço O (n) O (n), o consumo de memória é menor durante o tempo de execução.
Otimização de desempenho do V8 no algoritmo de classificação de matrizes
Como o V8 está muito interessado no desempenho do motor, o que ele faz na classificação da matriz?
Ao ler o código -fonte, ainda aprendi algum conhecimento básico.
Classificação de inserção mista
Classificação rápida é a idéia de dividir e conquistar, decompor grandes matrizes e recolocando -os na camada por camada. No entanto, se a profundidade da recursão for muito grande, o consumo de recursos da memória da pilha de chamadas recursivo também será muito grande. A baixa otimização pode até causar transbordamento de pilha.
A implementação atual do V8 é definir um limite e usar a classificação Inserir para pequenas matrizes de 10 ou menos comprimentos na camada mais baixa.
De acordo com os comentários e descrições do código na Wikipedia, embora a complexidade média do tempo da classificação de inserção seja O (N²) seja pior do que a de classificação rápida O (NN). No entanto, no ambiente de corrida, a eficiência de usar a classificação de inserção de pequenas matrizes é mais eficiente do que a classificação rápida, para que não seja expandida aqui.
Exemplo de código V8
var chapicSort = função QuickSort (a, de, para) {...... while (true) {// O tipo de inserção é mais rápido para matrizes curtas. if (para - de <= 10) {insertionsort (a, de, para); retornar; } ......} ......};Três números estão em
Como se sabe, o calcanhar de Aquiles de classificação rápido é que o algoritmo degenera na pior combinação de matriz.
O núcleo do algoritmo de classificação rápido é selecionar um pivô e decompor a matriz que foi comparada e trocada em duas áreas numéricas de acordo com a referência para a recursão subsequente. Imagine se, para uma matriz já ordenada, o primeiro ou o último elemento for sempre selecionado toda vez que o elemento de referência for selecionado, haverá uma área numérica que estiver vazia toda vez, e o número recursivo de camadas atingirá n, que acabará por levar à degradação da complexidade do tempo do algoritmo para O (N²). Portanto, a escolha do pivô é muito importante.
O V8 usa a otimização da median-of-three : além dos dois elementos no início e no final, outro elemento é selecionado para participar da competição do elemento de referência.
A estratégia de seleção para o terceiro elemento é aproximadamente:
Quando o comprimento da matriz for menor ou igual a 1000, selecione o elemento na metade da posição como o elemento de destino.
Quando o comprimento da matriz exceder 1000, selecione um elemento a uma distância de 200-215 (não fixado, mudando com o comprimento da matriz) para determinar um lote de elementos candidatos primeiro. Em seguida, classifique os elementos candidatos neste lote e use o valor médio resultante como o elemento de destino.
Finalmente, pegue o valor mediano dos três elementos como pivô.
Exemplo de código V8
var getthirdIndex = function (a, de, para) {var t_array = new internalArray (); // Use 'de' e 'para' para determinar os candidatos ao pivô. var increment = 200 + ((para - de) e 15); var j = 0; de += 1; para -= 1; for (var i = de; i <para; i += incremento) {t_array [j] = [i, a [i]]; j ++; } t_array.sort (function (a, b) {return comparefn (a [1], b [1]);}); var terceiro_index = t_array [t_array.length >> 1] [0]; retornar terceiro_index;}; var chapicSort = função QuickSort (a, de, para) {...... while (true) {...... se (para - de> 1000) {terceiro_index = getThirdIndex (a, de, para); } else {terceiro_index = de + ((para - de) >> 1); }} ......};Classificar no lugar
Ao revisar o algoritmo de classificação rápida, vi muitos exemplos de implementação usando JavaScript na Internet.
Mas descobri que grande parte da implementação do código é a seguinte
var wicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (ar.Length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var esquerdo = []; var à direita = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} Retorne QuickSort (esquerda) .Concat ([Pivot], QuickSort (direita));};O principal problema com o código acima é: usando as duas áreas de números à esquerda e direita para armazenar subarrays recursivos, portanto, requer espaço de armazenamento adicional de O (n). Essa é uma grande diferença em comparação com a complexidade espacial média teórica O (n).
A sobrecarga de espaço adicional também afetará a velocidade geral do tempo de execução real. Essa também é uma das razões pelas quais a classificação rápida pode ser executada em tempos de execução reais além do mesmo nível de complexidade do tempo. Portanto, de um modo geral, a classificação rápida com melhor desempenho adotará a classificação no local.
A implementação no código -fonte V8 é trocar elementos na matriz original.
Por que o Firefox usa classificação de mesclagem
Há também uma história por trás disso.
De fato, quando o Firefox foi lançado no início, ele não usou um algoritmo de classificação estável para implementar a classificação de matrizes, que está bem documentada.
O algoritmo de classificação da matriz implementado pela versão original do Firefox (Firebird) foi a classificação de heap, que também é um algoritmo de classificação instável. Portanto, alguém mais tarde enviou um bug.
A equipe de desenvolvimento da Mozilla conduziu uma série de discussões sobre esse assunto.
Do processo de discussão, podemos desenhar alguns pontos
1. O concorrente de Mozilla durante o mesmo período foi IE6. A partir das estatísticas acima, podemos ver que o IE6 é estável na classificação.
2.Brendan Eich, o pai de JavaScript, acha que a estabilidade é boa
3. O Firefox usa classificação rápida antes da classificação de heap
Com base na premissa principal de que os membros do grupo de desenvolvimento tendem a implementar algoritmos de classificação estáveis, o Firefox3 exige a classificação da mesclagem como uma nova implementação da classificação de matrizes.
Resolva as diferenças na classificação da estabilidade
Eu disse muito acima principalmente para contar as diferenças na implementação de classificação de cada navegador e explicar algumas das razões mais superficiais pelas quais essas diferenças existem.
Mas depois de ler isso, os leitores ainda podem ter perguntas: o que devo fazer se meu projeto precisar apenas confiar na classificação estável?
Solução
De fato, a idéia de resolver esse problema é relativamente simples.
O navegador escolhe diferentes algoritmos de classificação para diferentes considerações. Alguns podem tender a buscar um desempenho extremo, enquanto outros tendem a proporcionar uma boa experiência de desenvolvimento, mas há regras a seguir.
A julgar pela situação atual conhecida, todos os navegadores principais (incluindo IE6, 7, 8) podem basicamente enumerar a implementação de algoritmos de classificação de matrizes:
1. Merge classificação/TimSort
2. Classificação rápida
Então, podemos simplesmente transformar a classificação rápida em uma classificação estável?
De um modo geral, o uso de classificação instável para matrizes de objetos afetará os resultados. Enquanto outros tipos de matrizes usam resultados de classificação estáveis ou instáveis são iguais. Portanto, o plano é aproximadamente o seguinte:
Pré -processo a matriz a ser classificada e adicione atributos de ordem natural a cada objeto a ser classificado, para não conflitar com outros atributos do objeto.
O método de comparação de classificação personalizado CompareFN sempre usa a ordem natural como a dimensão do segundo julgamento quando o pré-julgamento é igual.
Ao enfrentar implementações como a classificação de mesclagem, como o algoritmo em si é estável, a comparação adicional de pedidos naturais não alterará o resultado de classificação, portanto a compatibilidade do esquema é melhor.
No entanto, envolve a modificação da matriz a ser classificada e é necessário um espaço adicional para armazenar propriedades de pedidos naturais. É concebível que motores como V8 não usem métodos semelhantes. No entanto, é viável como um plano de classificação personalizado pelos desenvolvedores.
Exemplo de código do esquema
'Use Strict'; const index = símbolo ('index'); função getComparer (compare) {return function (esquerda, direita) {let resultado = compare (esquerda, direita); resultado de retorno === 0? Esquerda [índice] - direita [índice]: resultado; };} Função de função (Array, compare) {Array = Array.map ((item, index) => {if (typeof item === 'object') {item [index] = index;} retornar item;}); Return Array.sort (getComparer (compare));}O exposto acima é apenas um exemplo simples de modificação do algoritmo que satisfaz a classificação estável.
A razão pela qual é simples é que as estruturas de dados como entradas de matriz no ambiente de produção real são complexas e é necessário julgar se mais tipos de pré-encomenda são necessários com base na situação real.
Marcação
1. O front-end agora é um conceito relativamente amplo. O front-end neste artigo refere-se principalmente ao ambiente usando o navegador como transportadora e JavaScript como linguagem de programação.
2. Este artigo não pretende envolver o algoritmo como um todo. Eu gostaria de usar algoritmos de classificação comuns como ponto de entrada.
3. Ao confirmar o algoritmo implementado pela classificação do Firefox, um bug relacionado ao tipo foi encontrado em SpiderMoney. De um modo geral, durante a discussão, alguém sugeriu o uso do algoritmo TimSort com melhor desempenho em casos extremos para substituir a classificação de mesclagem, mas a Mozilla Engineers disse que, devido ao problema de autorização de licença do algoritmo TimSort, não há como usar diretamente o algoritmo no software Mozilla e a resposta da outra parte da parte subsequente.
Resumir
O exposto acima é um resumo e solução para os problemas encontrados na classificação front-end. Nos últimos anos, mais e mais projetos estão mudando para aplicativos ricos em clientes, e a proporção do front-end em projetos aumentou. Com a melhoria adicional do poder de computação do navegador no futuro, ele permite alguns cálculos mais complexos. Com a mudança de responsabilidades, o formulário front-end também pode sofrer algumas mudanças importantes. Ao caminhar no mundo, você deve sempre ter uma habilidade.