IndexOf muito lento na lista. solução mais rápida?

StackOverflow https://stackoverflow.com/questions/1075734

  •  21-08-2019
  •  | 
  •  

Pergunta

Eu tenho lista genérica que deve ser um fim preservado para que eu possa recuperar o índice de um objeto na lista. O problema é IndexOf é muito lento. Se eu comentar o IndexOf para fora, o código é executado rápido quanto pode ser. Existe uma maneira melhor, como um preservada lista de hash encomendados para c #?

Obrigado, Nate

  • Editar - A ordem em que são adicionados os itens / inserido é a ordem que ele precisa ser. Sem classificação sobre eles é necessário. Também esta lista tem o potencial para ser atualizado frequentemente, adicionar, remover inserção. Basicamente eu preciso para traduzir o objeto para um índice devido a serem representados em um controle de grade para que eu possa executar operações no controle de grade com base no índice.
Foi útil?

Solução

Se ele não está classificado, mas a ordem precisa ser preservado , então você pode ter um Dictionary<YourClass, int> separado que deve conter o índice para cada elemento.

Se você quiser uma lista ordenada, em seguida, verificar as mensagens anteriores -. Você pode usar SortedList<Tkey, TValue> em .Net 3.5, ou classificá-lo e usar BinarySearch em versões mais antigas .Net

[Editar] Você pode encontrar exemplos semelhantes na web, por exemplo: orderedlist. Este usa internamente um ArrayList e um HashTable, mas você pode facilmente torná-lo genérico.

[Edit2] Opa .. o exemplo que dei você não implementa IndexOf da maneira que eu descrevi no início ... Mas você começa o ponto - uma lista deve ser ordenada, o outro usado para pesquisa rápida <. / p>

Outras dicas

Ordenar-lo usando List<T>.Sort , em seguida, usar o List<T>.BinarySearch método: "Pesquisas todo o List(T) ordenada para um elemento [... ] Este método é uma operação de o (N log N), onde N é o número de elementos no intervalo ".

Veja o fundo do este artigo aqui .

Parece que escrever o seu próprio método para recuperar o índice é muito mais rápido do que usando o método IndexOf, devido ao fato de que ele põe em um método virtual, dependendo do tipo.

Algo como isso pode, portanto, melhorar o seu desempenho. Eu escrevi um pequeno teste de unidade para verificar se isso melhora o desempenho da pesquisa, e ele fez, em cerca de 15x em uma lista com 10.000 itens. 

static int GetIndex(IList<Item> list, Item value)
{
    for (int index = 0; index < list.Count; index++)
    {
        if (list[index] == value)
        {
             return index;
        } 
    }
    return -1;
}

Talvez você está procurando SortedList<TKey, TValue> ?

Eu sugiro usar o SortedList<TKey, TValue> ou SortedDictionary<TKey, TValue> classe se você precisar os itens ordenados. As diferenças são as seguintes.

  • usos SortedList<TKey, TValue> menos memória do que SortedDictionary<TKey, TValue>.

  • SortedDictionary<TKey, TValue> tem operações de inserção e remoção mais rápida para dados não ordenados:. O (N log N), em oposição a O (n) para SortedList<TKey, TValue>

  • Se a lista é preenchida de uma só vez a partir de dados classificados, SortedList<TKey, TValue> é mais rápido do que SortedDictionary<TKey, TValue>.

Se você quiser apenas para preservar a ordem, você pode apenas usar um Dictionary<TKey, TValue> e armazenar o item como chave eo índice de valor. A desvantagem é que a reorganização da itens, inserções ou exclusão são muito caros para fazer.

Se a ordem dos objetos na lista tem a ser preservado, então a única maneira que eu posso pensar de onde você está indo para obter o mais rápido possível o acesso é para dizer ao objeto o seu índice posição é quando a sua adicionado, etc, para a lista. Dessa forma, você pode consultar o objeto de obter seu índice na lista. A desvantagem, e é uma grande desvantagem na minha opinião, é que os objetos inseridos agora têm uma dependência na lista.

Bem, não há razão que você nunca deve ter que pedir uma lista de hash ... isso é uma espécie de ponto. No entanto, uma lista de hash deve fazer o truque muito facilmente.

Se você estiver usando a classe List, em seguida, você poderia usar o método de classificação para classificar-lo depois é inicialmente povoada, em seguida, usar o método BinarySearch para encontrar o elemento apropriado.

Eu não tenho certeza sobre detalhes em C #, mas você pode ser capaz de classificá-lo (QuickSort?) E, em seguida, usar uma pesquisa binária sobre ele (desempenho BinarySearch é O (log2 (N)), contra sequencial, tais como indexOf, que é O (n)). (IMPORTANTE: Para um binário Search, sua estrutura deve ser resolvido)

Quando você inserir itens para sua estrutura de dados, você pode tentar uma pesquisa binária modificado para encontrar o ponto de inserção, bem como, ou se você está adicionando um grande grupo, você adicioná-los e, em seguida, tipo-los.

O único problema é que a inserção será mais lenta.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top