11

Estou usando Entity Framework em um projeto ASP.NET MVC onde tenho uma simples lista de strings e preciso remover apenas o primeiro item.

Usei o seguinte comando:

minhaLista.RemoveAt(0);

Bem, mas usando uma ferramenta de performance do Visual Studio, pude perceber que em uma lista muito grande o processo consome bastante processamento.

Existe alguma alternativa que consuma menos?

2 Respostas 2

7

Uma instância de List<> utiliza, internamente, um array para manter as referências aos membros da coleção. Este precisa ser manipulado/redimensionado quando você insere ou remove um item.

Para operações de inserção/remoção, uma LinkedList<> é em torno de 100 vezes mais rápida do que uma List<>, pois sua mecânica interna apenas referencia itens com os membros mais próximos.

Quando um item é removido, as referências de apenas 2 membros (se o membro retirado estiver entre dois) são atualizadas.

Fonte da estimativa.

Documentação da classe LinkedList<> na MSDN.

6

Tem que analisar o que você pode perder. A busca ou acesso por índice na estrutura mostrada pelo Ono Sendai é péssima (não que a resposta dele seja ruim, pelo contrário), se isso não é importante, vá nela.

Se o acesso for importante tem que achar outra estrutura. Pode ser que tenha que repensar totalmente o que está usando, o erro pode estar em outro lugar. Sem contexto é difícil dizer.

Uma coisa que pode fazer se puder mudar a estrutura é usar um array. Aí pode usar o ArraySegment. Você pode "criar" um segmento onde o primeiro elemento não está presente, você não apaga o dado, mas fica com uma estrutura onde aquele elemento não é mais acessado e os índices são obviamente reposicionados. Então se você pega um segmento começando no elemento 1, este elemento passará ser o 0 na nova variável. O acesso continua fácil e rápido como é no Array ou List, não copia nada e consegue o que deseja.

Outras soluções podem ser possíveis se algumas condições puderem ser atendidas.

var novoArray = new ArraySegment<Cliente>(meuArray, 1, meuArray.Length - 1);

Coloquei no GitHub para referência futura.

Agora tem o Span que é quase certo que seja a melhor solução em todos os sentidos.

6
  • bigown muito obrigado pela sua resposta. Mas por que exatamente a resposta do lbotinelly seria péssima? Commented 11/02/2016 às 10:21
  • 2
    Eu não disse que a resposta dele seria péssima, ela é ótima, tanto que disse para usar, desde que possa conviver com acesso com velocidade péssima. A lista ligada tem complexidade de acesso O(N), quanto que uma lista ou array tem complexidade O(1). Ou seja, o acesso direto deste, mesmo no pior caso, é quase instantâneo, basta uma operação simples. A lista ligada no pior caso tem que percorrer toda a lista para achar alguma coisa. Isto vale para o acesso pelo índice ou pelo valor. Eu não sei o que é melhor para seu caso, até porque não conheço seu caso.É possível que não seja nem a minha
    – Maniero
    Commented 11/02/2016 às 10:29
  • Opa, agora ficou bem mais claro. Muito obrigado. Commented 11/02/2016 às 10:34
  • 2
    É uma informação conhecida. Uma lista comum se comporta exatamente como um array, então eles são iguais. Além disto costuma ter na documentação. Saber o Big O é fundamental para escolher a estrutura de dados ou algoritmo certo a usar. Uma tabela genérica simplificada (pode não valer para a implementação específica) bigocheatsheet.com Melhor resposta no site: pt.stackoverflow.com/a/56868/101 Note que existem truques que pode fazer os compromissos mudarem. Uma lista pode ter a inserção O(N) ou O(1) dependendo do truque e o estado que ela está.
    – Maniero
    Commented 11/02/2016 às 11:12
  • 1
    @JedaiasRodrigues O ponto do bigown é perfeito no que tange à performance. Se sua lista existe para expressar uma fila FIFO (First In, First Out) então um LinkedList é a melhor opção. Porém se você for iterar na lista de maneira não-serial o LinkedList não é a melhor opção.
    – OnoSendai
    Commented 18/02/2016 às 13:28

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .