Big O de matrizes de JavaScript

Os arrays em JavaScript são muito fáceis de modificar, adicionando e removendo itens. De certa forma, mascara o fato de que a maioria dos arrays de linguagens tem tamanho fixo e requer operações complexas para redimensionar. Parece que o JavaScript facilita a escrita de código de array de baixo desempenho. Isso leva à pergunta:

Que desempenho (em termos de grande complexidade de tempo) posso esperar das implementações de JavaScript em relação ao desempenho do array?

Presumo que todas as implementações de JavaScript razoáveis ​​têm no máximo os seguintes grandes O's.

• Acesso - O (1)
• Anexando - O (n)
• Anexando - O (n)
• Inserção - O (n)
• Exclusão - O (n)
• Troca - O (1)

O JavaScript permite que você preencha previamente um array até um certo tamanho, usando a new Array(length)sintaxe. (Pergunta bônus: está criando um array desta maneira O (1) ou O (n)) Isto é mais parecido com um array convencional e, se usado como um array pré-dimensionado, pode permitir o acréscimo de O (1). Se a lógica de buffer circular for adicionada, você pode obter O (1) antes. Se uma matriz de expansão dinâmica for usada, O (log n) será o caso médio para ambos.

Posso esperar um desempenho melhor para algumas coisas do que minhas suposições aqui? Não espero que nada seja descrito em nenhuma especificação, mas, na prática, pode ser que todas as principais implementações usem arrays otimizados nos bastidores. Existem matrizes de expansão dinâmica ou algum outro algoritmo de aumento de desempenho em funcionamento?

PS

O motivo de estar me perguntando isso é que estou pesquisando alguns algoritmos de classificação, a maioria dos quais parece assumir que anexar e excluir são operações O (1) ao descrever seu grande O geral.

_{NOTA: Embora essa resposta esteja correta em 2012, os mecanismos usam representações internas muito diferentes para objetos e matrizes hoje. Esta resposta pode ou não ser verdadeira.}

Em contraste com a maioria das linguagens, que implementam arrays com, bem, arrays, em Javascript os arrays são objetos e os valores são armazenados em uma tabela de hash, assim como os valores regulares dos objetos. Assim sendo:

• Acesso - O (1)
• Anexar - Amortizado O (1) (às vezes é necessário redimensionar a tabela de hash; normalmente, apenas a inserção é necessária)
• Prepending - O (n) via unshift, uma vez que requer a reatribuição de todos os índices
• Inserção - Amortizado O (1) se o valor não existir. O (n) se você deseja deslocar os valores existentes (por exemplo, usando splice).
• Exclusão - Amortizado O (1) para remover um valor, O (n) se você deseja reatribuir índices via splice.
• Troca - O (1)

Em geral, a configuração ou desconfiguração de qualquer chave em um dicionário é amortizada O (1), e o mesmo se aplica a matrizes, independentemente de qual seja o índice. Qualquer operação que requeira a renumeração dos valores existentes é O (n) simplesmente porque você deve atualizar todos os valores afetados.

garantia

Não há garantia de complexidade de tempo especificada para nenhuma operação de array. O desempenho dos arrays depende da estrutura de dados subjacente que o mecanismo escolhe. Os motores também podem ter representações diferentes e alternar entre eles dependendo de certas heurísticas. O tamanho inicial da matriz pode ou não ser uma heurística.

realidade

Por exemplo, o V8 usa (a partir de hoje) hashtables e listas de arrays para representar arrays. Ele também tem várias representações diferentes para objetos, portanto, matrizes e objetos não podem ser comparados. Portanto, o acesso à matriz é sempre melhor que O (n) e pode até ser tão rápido quanto um acesso à matriz C ++. Anexar é O (1), a menos que você alcance o tamanho da estrutura de dados e tenha que ser escalado (que é O (n)). Prepending é pior. A exclusão pode ser ainda pior se você fizer algo como delete array[index](não!), Pois isso pode forçar o mecanismo a alterar sua representação.

adendo

Use matrizes para estruturas de dados numéricos. É para isso que eles foram feitos. É para isso que os motores os otimizam. Evite matrizes esparsas (ou, se necessário, espere um desempenho pior). Evite arrays com tipos de dados mistos (pois isso torna as representações internas mais complexas ).

Se você realmente deseja otimizar para um determinado mecanismo (e versão), verifique seu código - fonte para a resposta absoluta.