Eu tenho uma matriz JavaScript classificada e quero inserir mais um item na matriz, para que a matriz resultante permaneça classificada. Eu certamente poderia implementar uma função simples de inserção no estilo quicksort:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.splice(locationOf(element, array) + 1, 0, element);
return array;
}
function locationOf(element, array, start, end) {
start = start || 0;
end = end || array.length;
var pivot = parseInt(start + (end - start) / 2, 10);
if (end-start <= 1 || array[pivot] === element) return pivot;
if (array[pivot] < element) {
return locationOf(element, array, pivot, end);
} else {
return locationOf(element, array, start, pivot);
}
}
console.log(insert(element, array));
[AVISO] este código tem um erro ao tentar inserir no início da matriz, por exemplo insert(2, [3, 7 ,9]
) produz incorreto [3, 2, 7, 9].
No entanto, notei que as implementações da função Array.sort podem fazer isso por mim e nativamente:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.push(element);
array.sort(function(a, b) {
return a - b;
});
return array;
}
console.log(insert(element, array));
Existe um bom motivo para escolher a primeira implementação sobre a segunda?
Editar : observe que, no caso geral, uma inserção de O (log (n)) (conforme implementada no primeiro exemplo) será mais rápida que um algoritmo de classificação genérico; no entanto, esse não é necessariamente o caso do JavaScript em particular. Observe que:
- O melhor caso para vários algoritmos de inserção é O (n), que ainda é significativamente diferente de O (log (n)), mas não tão ruim quanto O (n log (n)), conforme mencionado abaixo. Seria o algoritmo de classificação específico usado (consulte Implementação Javascript Array.sort? )
- O método de classificação no JavaScript é uma função nativa; portanto, é possível obter enormes benefícios - O (log (n)) com um coeficiente enorme ainda pode ser muito pior que O (n) para conjuntos de dados de tamanho razoável.
fonte
splice()
(por exemplo, seu 1º exemplo) já é O (n). Mesmo que não crie internamente uma nova cópia de toda a matriz, ele potencialmente precisará desviar todos os n itens para trás 1 posição para que o elemento seja inserido na posição 0. Talvez seja rápido porque é uma função nativa e a constante é baixo, mas é O (n) no entanto.parseInt
use em seuMath.floor
lugar.Math.floor
é muito mais rápido queparseInt
: jsperf.com/test-parseint-and-math-floorRespostas:
Assim como um único ponto de dados, para testar, testei isso inserindo 1000 elementos aleatórios em uma matriz de 100.000 números pré-classificados usando os dois métodos usando o Chrome no Windows 7:
Portanto, pelo menos nessa configuração, o método nativo não compensa isso. Isso é verdade mesmo para conjuntos de dados pequenos, inserindo 100 elementos em uma matriz de 1000:
fonte
Array.prototype.sort
, você perde os benefícios do C ++ porque a função JS é chamada de mais.Simples ( Demo ):
fonte
x >>> 1
é deslocamento à direita binário 1 posição, que é efetivamente apenas uma divisão por 2. por exemplo, para 11:1011
->101
resultados a 5.>>> 1
e ( vista aqui e ali )>> 1
?>>>
é um deslocamento à direita sem sinal, enquanto que>>
estende o sinal - tudo se resume à representação na memória de números negativos, onde o bit alto é definido se negativo. Então, se você mudar para0b1000
o lugar certo com o>>
que obterá0b1100
, se você usar,>>>
receberá0b0100
. Embora no caso indicado na resposta isso realmente não importe (o número que está sendo deslocado não seja maior que o valor máximo de um inteiro positivo de 32 bits assinado nem negativo), é importante usar o correto nesses dois casos (você precisa escolher qual caso você precisa lidar).0b1000
direita 1 lugar,>>
receberá0b1100
". Não, você entendeu0b0100
. O resultado dos diferentes operadores de deslocamento à direita será o mesmo para todos os valores, exceto números negativos e números maiores que 2 ^ 31 (ou seja, números com 1 no primeiro bit).Pergunta muito boa e notável, com uma discussão muito interessante! Eu também estava usando a
Array.sort()
função depois de empurrar um único elemento em uma matriz com alguns milhares de objetos.Eu tive que estender sua
locationOf
função para o meu propósito devido a ter objetos complexos e, portanto, a necessidade de uma função de comparação, como emArray.sort()
:fonte
return c == -1 ? pivot : pivot + 1;
para retornar o índice correto. Caso contrário, para uma matriz com comprimento 1, a função retornaria -1 ou 0.>> 1
deve ser mais rápido (ou não mais lento) que/ 2
comparer
função. Neste algoritmo, ele é comparado,+-1
mas pode ser um valor arbitrário<0
/>0
. Veja a função comparar . A parte problemática não é apenas aswitch
afirmação, mas também a linha:if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;
ondec
é comparada-1
também.Há um erro no seu código. Deve ler-se:
Sem essa correção, o código nunca poderá inserir um elemento no início da matriz.
fonte
Sei que essa é uma pergunta antiga que já tem uma resposta e há várias outras respostas decentes. Vejo algumas respostas que propõem que você pode resolver esse problema consultando o índice de inserção correto em O (log n) - você pode, mas não pode inserir nesse período, porque a matriz precisa ser parcialmente copiada para criar espaço.
Conclusão: se você realmente precisa de inserções e exclusões O (log n) em uma matriz classificada, precisa de uma estrutura de dados diferente - não de uma matriz. Você deve usar um B-Tree . Os ganhos de desempenho que você obterá ao usar uma B-Tree para um grande conjunto de dados, superarão qualquer uma das melhorias oferecidas aqui.
Se você deve usar uma matriz. Eu ofereço o código a seguir, com base na classificação por inserção, que funciona, se e somente se a matriz já estiver classificada. Isso é útil para o caso em que você precisa recorrer após cada inserção:
Ele deve operar em O (n), que eu acho que é o melhor que você pode fazer. Seria melhor se js suportasse atribuição múltipla. Aqui está um exemplo para brincar:
Atualizar:
isso pode ser mais rápido:
Link JS Bin atualizado
fonte
Sua função de inserção pressupõe que a matriz especificada é classificada; ela pesquisa diretamente o local em que o novo elemento pode ser inserido, geralmente apenas observando alguns dos elementos da matriz.
A função de classificação geral de uma matriz não pode aceitar esses atalhos. Obviamente, pelo menos, é necessário inspecionar todos os elementos da matriz para verificar se eles já estão ordenados corretamente. Somente esse fato torna a classificação geral mais lenta que a função de inserção.
Um algoritmo de classificação genérico geralmente é em média O (n ⋅ log (n)) e, dependendo da implementação, pode ser o pior caso se a matriz já estiver classificada, levando a complexidades de O (n 2 ) . A pesquisa direta da posição de inserção possui apenas uma complexidade de O (log (n)) , portanto será sempre muito mais rápido.
fonte
Para um pequeno número de itens, a diferença é bastante trivial. No entanto, se você estiver inserindo muitos itens ou trabalhando com uma matriz muito grande, chamar .sort () após cada inserção causará uma quantidade enorme de sobrecarga.
Acabei escrevendo uma função de pesquisa / inserção binária bastante precisa para esse propósito exato, então pensei em compartilhá-la. Como ele usa um
while
loop em vez de recursão, não há ouvidos para chamadas de função extras, então acho que o desempenho será ainda melhor do que qualquer um dos métodos originalmente postados. E emula oArray.sort()
comparador padrão por padrão, mas aceita uma função comparadora personalizada, se desejado.Se você está aberto ao uso de outras bibliotecas, lodash fornece sortedIndex e sortedLastIndex funções, que podem ser usados no lugar do
while
loop. As duas possíveis desvantagens são: 1) o desempenho não é tão bom quanto o meu método (pensei que não tenho certeza do quanto é pior) e 2) não aceita uma função comparadora personalizada, apenas um método para obter o valor para comparar (usando o comparador padrão, presumo).fonte
arr.splice()
é certamente O (n) complexidade do tempo.Aqui estão alguns pensamentos: Primeiro, se você está realmente preocupado com o tempo de execução do seu código, não deixe de saber o que acontece quando você chama as funções internas! Eu não sei de cima em javascript, mas um rápido google da função de emenda retornou isso , o que parece indicar que você está criando uma nova matriz a cada chamada! Não sei se isso realmente importa, mas certamente está relacionado à eficiência. Vejo que Breton, nos comentários, já apontou isso, mas certamente vale para qualquer função de manipulação de array que você escolher.
De qualquer forma, para realmente resolver o problema.
Quando li que você queria classificar, meu primeiro pensamento é usar a classificação por inserção! . É útil porque é executado em tempo linear em listas classificadas ou quase ordenadas . Como suas matrizes terão apenas 1 elemento fora de ordem, isso conta como quase classificado (exceto, bem, matrizes de tamanho 2 ou 3 ou o que for, mas nesse momento, vamos lá). Agora, implementar a classificação não é tão ruim assim, mas é um incômodo com o qual você pode não querer lidar e, novamente, eu não sei nada sobre javascript e se será fácil ou difícil ou qualquer outra coisa. Isso elimina a necessidade da sua função de pesquisa e você apenas pressiona (como sugerido Breton).
Em segundo lugar, sua função de pesquisa "quicksort-esque" parece ser um algoritmo de pesquisa binário ! É um algoritmo muito bom, intuitivo e rápido, mas com um problema: é notoriamente difícil de implementar corretamente. Não ousarei dizer se o seu está correto ou não (espero que esteja, é claro! :)), mas tenha cuidado se quiser usá-lo.
De qualquer forma, resumo: o uso de "push" com classificação de inserção funcionará em tempo linear (supondo que o restante da matriz seja classificada) e evitará quaisquer requisitos complicados de algoritmo de pesquisa binária. Não sei se essa é a melhor maneira (implementação subjacente de matrizes, talvez uma função interna maluca faça melhor, quem sabe), mas me parece razoável. :) - Agor.
fonte
splice()
já é O (n). Mesmo se ele não cria internamente uma nova cópia de toda a matriz, que potencialmente tem para desviar todos os itens n back 1 posição se o elemento deve ser inserido na posição 0.Aqui está uma comparação de quatro algoritmos diferentes para realizar isso: https://jsperf.com/sorted-array-insert-comparison/1
Algoritmos
Ingênuo é sempre horrível. Parece que para tamanhos de matriz pequenos, os outros três não diferem muito, mas para matrizes maiores, os dois últimos superam a abordagem linear simples.
fonte
Aqui está uma versão que usa lodash.
Nota: SortIndex faz uma pesquisa binária.
fonte
A melhor estrutura de dados que consigo pensar é uma lista de pulos indexados que mantém as propriedades de inserção de listas vinculadas com uma estrutura hierárquica que permite operações de tempo de log. Em média, pesquisas, inserção e pesquisas de acesso aleatório podem ser feitas em O (log n).
Uma árvore estatística de pedidos permite a indexação do tempo do log com uma função de classificação.
Se você não precisar de acesso aleatório, mas precisar de inserção de O (log n) e procurar chaves, poderá abandonar a estrutura da matriz e usar qualquer tipo de árvore de pesquisa binária .
Nenhuma das respostas usadas
array.splice()
é eficiente, uma vez que esse tempo médio é de O (n). Qual é a complexidade temporal de array.splice () no Google Chrome?fonte
Is there a good reason to choose [splice into location found] over [push & sort]?
Aqui está a minha função, usa a pesquisa binária para encontrar o item e insere apropriadamente:
fonte
Não re-classifique após cada item, pois é um exagero.
Se houver apenas um item para inserir, você poderá encontrar o local para inserir usando a pesquisa binária. Em seguida, use memcpy ou similar para copiar em massa os itens restantes para liberar espaço para o item inserido. A pesquisa binária é O (log n) e a cópia é O (n), fornecendo O (n + log n) total. Usando os métodos acima, você está reorganizando após cada inserção, que é O (n log n).
Isso importa? Digamos que você esteja inserindo k elementos aleatoriamente, onde k = 1000. A lista classificada é de 5000 itens.
Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
Re-sort on each = k*(n log n) = ~60 million ops
Se os k itens a serem inseridos chegarem sempre, será necessário pesquisar + mover. No entanto, se você receber uma lista de k itens para inserir em uma matriz classificada - antecipadamente -, poderá fazer ainda melhor. Classifique os itens k separadamente da matriz n já classificada. Em seguida, faça uma classificação de varredura, na qual você move as duas matrizes ordenadas simultaneamente, mesclando uma na outra. - Classificação de mesclagem em uma etapa = k log k + n = 9965 + 5000 = ~ 15.000 ops
Atualização: em relação à sua pergunta.
First method = binary search+move = O(n + log n)
.Second method = re-sort = O(n log n)
Explica exatamente os horários que você está recebendo.fonte
fonte