Matriz que pode ser redimensionada rápido

Question

Eu estou procurando uma espécie de matriz tipo de dados que facilmente pode ter itens adicionados, sem um acerto de desempenho.

• Sistema array -. Redim Preserve copia todo RAM do velho para o novo, tão lento como quantidade de elementos existentes
• System.Collections ArrayList -. Bom o suficiente
?
• System.Collections IList -. Bom o suficiente
?

Answer 1

Apenas para resumir algumas estruturas de dados:

System.Collections.ArrayList : estruturas de dados sem tipo são obsoletos. Use List (de t) em seu lugar.

System.Collections.Generic.List (de t) : isto representa uma matriz redimensionável. Esta estrutura de dados utiliza uma matriz interna por trás dos bastidores. Adicionando itens a lista é O (1), enquanto a matriz subjacente não foi preenchido, caso contrário, o seu S (n + 1) para redimensionar a matriz interna e copiar os elementos por cima.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

Adicionando itens só é eficiente quando se adiciona a parte de trás da lista. Inserindo nas forças médias a matriz para deslocar todos os itens para a frente, o que é uma operação O (n). Excluindo itens também é O (n), uma vez que as necessidades matriz para itens de deslocamento para trás.

System.Collections.Generic.LinkedList (de t) : se você não precisa de acesso aleatório ou indexada a itens em sua lista, por exemplo, você só pretende adicionar itens e iterate de primeira a última, em seguida, um LinkedList é seu amigo. Inserções e remoções são O (1), de pesquisa é O (n).

Answer 2

Você deve usar o genérico lista <> ( System.Collections.Generic. lista) para isso. Atua em amortizados tempo .

Ele também partilha as seguintes características com Arrays.

• Acesso rápido aleatório (você pode acessar qualquer elemento na lista em O (1))
• É rápido de varrer
• Lento para inserir e remover objetos no início ou no meio (uma vez que tem de fazer uma cópia de toda a listbelieve)

Se precisar de inserções rápidas e exclusões no início ou no final, use um vinculado-lista ou filas

Answer 3

O relator LinkedList trabalho estrutura para você? Não é (em alguns casos) tão intuitivo como uma matriz em linha reta, mas é muito rápido.

• addlast para anexar ao fim
• AddBefore / AddAfter para inserir na lista
• AddFirst para anexar ao início

Não é tão rápido para acesso aleatório no entanto, como você tem que interagir sobre a estrutura para acessar seus itens ... no entanto, ele tem .ToList () e .ToArray () para pegar uma cópia da estrutura na lista forma / matriz para para acesso de leitura, você poderia fazer isso em uma pitada. O aumento das inserções desempenho podem superar a diminuição da necessidade de acesso aleatório desempenho ou talvez não. Vai depender inteiramente de sua situação.

Há também esta referência que irá ajudá-lo a decidir qual é o caminho certo a seguir:

Quando usar uma lista ligada mais uma lista de matriz / array?

Answer 4

O que é "suficientemente bom" para você? O que exatamente você quer fazer com que a estrutura de dados?

n estrutura de matriz (isto é, S (n) de acesso) permite a inserção no meio sem um O (n) de tempo de execução; inserção no final é O (n) pior caso uma junta (1) amortizado para matrizes auto-redimensionamento como ArrayList.

Talvez hashtables (amortizado O (1) acesso e em qualquer lugar de inserção, mas O (n) pior caso para inserção) ou árvores (O (log (n)) para o acesso e em qualquer lugar de inserção, garantida) são mais adequadas.

Answer 5

Se a velocidade é o seu problema, eu não vejo como a resposta selecionada é melhor do que usar uma matriz de cru, embora se redimensiona, ele usa exatamente o mesmo mecanismo que você usaria para redimensionar um array (e deve levar apenas um toque mais longo) a menos que você está sempre adicionando ao fim, caso em que ele deve fazer as coisas um pouco mais esperto, porque ele aloca um pedaço de cada vez, em vez de apenas um elemento.

Se você costuma adicionar perto do início / meio da sua coleção e não indexe para o meio / fim, muitas vezes, você provavelmente vai querer uma lista ligada. Que terá o tempo de inserção mais rápido e terá grande momento iteração, ele só suga a indexação (como olhar para o 3º elemento do final, ou o elemento 72).