Maneira eficiente de inserir um número em uma matriz classificada de números?

142

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.
Elliot Kroo
fonte
o uso de emenda na segunda implementação é um pouco inútil. Por que não usar push?
Breton
Bom ponto, eu apenas copiei do primeiro.
287 Elliot Kroo
4
Qualquer coisa que contenha 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.
Jrandom_hacker
6
Além disso, para referência futura para pessoas que usam esse código, o código possui um erro ao tentar inserir no início da matriz. Olhe mais abaixo para o código corrigido.
Pinocchio
3
Não use parseIntuse em seu Math.floorlugar. Math.flooré muito mais rápido que parseInt: jsperf.com/test-parseint-and-math-floor
Hubert Schölnast

Respostas:

58

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:

First Method:
~54 milliseconds
Second Method:
~57 seconds

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:

First Method:
1 milliseconds
Second Method:
34 milliseconds
Sam Phillips
fonte
1
Arrays.sort sons muito terrível
njzk2
2
Parece que o array.splice deve estar fazendo algo realmente inteligente, para inserir um único elemento em 54 microssegundos.
precisa saber é o seguinte
@ gnasher729 - Não acho que matrizes Javascript sejam realmente iguais a matrizes fisicamente contínuas como as que temos em C. Acho que os mecanismos JS podem implementá-las como um mapa / dicionário de hash, permitindo a inserção rápida.
Ian Ian
1
ao usar uma função comparadora Array.prototype.sort, você perde os benefícios do C ++ porque a função JS é chamada de mais.
aleclarson
Como o Primeiro Método se compara agora que o Chrome usa o TimSort ? Da Wikipedia TimSort : "Na melhor das hipóteses, que ocorre quando a entrada já está classificada, [TimSort] é executado em tempo linear".
poshest
47

Simples ( Demo ):

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}
Web designer
fonte
4
Bom toque. Eu nunca ouvi falar em usar operadores bit a bit para encontrar o valor médio de dois números. Normalmente eu multiplicaria por 0,5. Existe um aumento significativo no desempenho dessa maneira?
Jackson
2
@Jackson x >>> 1é deslocamento à direita binário 1 posição, que é efetivamente apenas uma divisão por 2. por exemplo, para 11: 1011-> 101resultados a 5.
Qwerty
3
@Qwerty @Web_Designer Já estando nessa faixa, você poderia explicar a diferença entre >>> 1e ( vista aqui e ali ) >> 1?
yckart 26/02
4
>>>é 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 para 0b1000o 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).
asherkin
2
@ asherkin - Isso não está certo: "se você mudar para a 0b1000direita 1 lugar, >>receberá 0b1100". Não, você entendeu 0b0100. 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).
precisa saber é o seguinte
29

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 locationOffunção para o meu propósito devido a ter objetos complexos e, portanto, a necessidade de uma função de comparação, como em Array.sort():

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};
kwrl
fonte
7
Parece digno de nota, para o registro, que esta versão funciona corretamente ao tentar inserir no início da matriz. (Vale a pena mencioná-lo porque a versão na pergunta original tem um bug e não funciona correctamente para esse caso.)
garyrob
3
Não tenho certeza se minha implementação foi diferente, mas precisava alterar o ternário para 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.
Niel
3
@ James: Os parâmetros start e end são usados ​​apenas na chamada recursiva e não serão utilizados na chamada inicial. Como esses são valores de índice para a matriz, eles devem ser do tipo inteiro e, na chamada recursiva, isso é implicitamente indicado.
kwrl
1
@TheRedPea: não, eu quis dizer >> 1deve ser mais rápido (ou não mais lento) que/ 2
kwrl
1
Eu posso ver um problema em potencial com o resultado da comparerfunção. Neste algoritmo, ele é comparado, +-1mas pode ser um valor arbitrário <0/ >0. Veja a função comparar . A parte problemática não é apenas a switchafirmação, mas também a linha: if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;onde cé comparada -1também.
Exavier
19

Há um erro no seu código. Deve ler-se:

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

Sem essa correção, o código nunca poderá inserir um elemento no início da matriz.

SyntheticZero
fonte
por que você está fazendo um int com 0? ou seja, o que começa || 0 faz?
Pinóquio
3
@Pinocchio: start || 0 é um equivalente curto de: if (! Start) start = 0; - No entanto, a versão "mais longa" é mais eficaz, porque não atribui uma variável a si mesma.
SuperNova
11

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:

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

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:

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

Link JS Bin atualizado

domoarigato
fonte
Em JavaScript, a classificação de inserção que você propõe será mais lenta que o método de pesquisa e emenda binária, porque a emenda tem uma implementação rápida.
trincot
a menos que o javascript possa de alguma forma violar as leis da complexidade do tempo, eu sou cético. Você tem um exemplo executável de como o método de busca e emenda binário é mais rápido?
domoarigato 7/19
Retiro meu segundo comentário ;-) De fato, haverá um tamanho de matriz além do qual uma solução de árvore B superará a solução de emenda.
trincot
9

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.

sth
fonte
Vale a pena notar que a inserção de um elemento em uma matriz tem uma complexidade de O (n), portanto o resultado final deve ser o mesmo.
NemPlayer 15/03
5

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 whileloop 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 o Array.sort()comparador padrão por padrão, mas aceita uma função comparadora personalizada, se desejado.

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

Se você está aberto ao uso de outras bibliotecas, lodash fornece sortedIndex e sortedLastIndex funções, que podem ser usados no lugar do whileloop. 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).

Sean, o Feijão
fonte
a chamada para arr.splice()é certamente O (n) complexidade do tempo.
Domoarigato 18/05/19
4

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.

agorenst
fonte
1
+1 porque qualquer coisa que contenha 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.
j_random_hacker
Acredito que o tipo de inserção também seja O (n) melhor caso e O (n ^ 2) pior caso (embora o caso de uso do OP seja provavelmente o melhor caso).
Domoarigato 18/05/19
Menos um por falar com o OP. O primeiro parágrafo senti como uma admoestação unnessessary por não saber como funciona a emenda sob o capô
Matt Zera
2

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.

gabtub
fonte
Por que não testar estruturas de dados projetadas para implementar inserção e pesquisa rápidas? ex. pular listas e BSTs. stackoverflow.com/a/59870937/3163618
qwr 23/01
Como o Native compara agora que o Chrome usa o TimSort ? Da Wikipedia TimSort : "Na melhor das hipóteses, o que ocorre quando a entrada já está classificada, é executada em tempo linear".
poshest
2

Aqui está uma versão que usa lodash.

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

Nota: SortIndex faz uma pesquisa binária.

I. Cantrell
fonte
1

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?

qwr
fonte
Como isso respondeIs there a good reason to choose [splice into location found] over [push & sort]?
greybeard 23/01
1
@greybeard Responde ao título. cinicamente, nenhuma das opções é eficiente.
qwr 23/01
Nenhuma das opções poderia ser eficiente se envolverem a cópia de vários elementos de uma matriz.
qwr 23/01
1

Aqui está a minha função, usa a pesquisa binária para encontrar o item e insere apropriadamente:

function binaryInsert(val, arr){
    let mid, 
    len=arr.length,
    start=0,
    end=len-1;
    while(start <= end){
        mid = Math.floor((end + start)/2);
        if(val <= arr[mid]){
            if(val >= arr[mid-1]){
                arr.splice(mid,0,val);
                break;
            }
            end = mid-1;
        }else{
            if(val <= arr[mid+1]){
                arr.splice(mid+1,0,val);
                break;
            }
            start = mid+1;
        }
    }
    return arr;
}

console.log(binaryInsert(16, [
    5,   6,  14,  19, 23, 44,
   35,  51,  86,  68, 63, 71,
   87, 117
 ]));

Oguz Yilmaz
fonte
0

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.

Rama Hoetzlein
fonte
sim, mas não, depende do seu algoritmo de classificação. Usando um bubble sort na ordem inversa, o seu tipo, se o último elemento não é classificado é sempre o (n)
njzk2
-1
function insertOrdered(array, elem) {
    let _array = array;
    let i = 0;
    while ( i < array.length && array[i] < elem ) {i ++};
    _array.splice(i, 0, elem);
    return _array;
}
Marina
fonte