Qual coleção do .NET fornece a pesquisa mais rápida

Tenho 60 mil itens que precisam ser verificados em uma lista de 20 mil. Existe um objeto de coleção (como List, HashTable) que fornece um Contains()método excepcionalmente rápido ? Ou vou ter que escrever o meu? Em outras palavras, é o Contains()método padrão apenas digitalizar cada item ou usar um algoritmo de pesquisa melhor.

foreach (Record item in LargeCollection)
{
    if (LookupCollection.Contains(item.Key))
    {
       // Do something
    }
}

Nota . A lista de pesquisa já está classificada.

No caso mais geral, considere System.Collections.Generic.HashSetcomo sua estrutura de dados padrão "Contém" a força de trabalho, pois leva tempo constante para avaliar Contains.

A resposta real para "Qual é a coleta pesquisável mais rápida" depende do tamanho específico dos dados, do pedido, do custo de hash e da frequência de pesquisa.

Se você não precisar fazer pedidos, tente HashSet<Record>(novo no .Net 3.5)

Se fizer isso, use ae List<Record>ligue BinarySearch.

Você já considerou List.BinarySearch(item)?

Você disse que sua grande coleção já está classificada, portanto esta parece ser a oportunidade perfeita? Um hash seria definitivamente o mais rápido, mas isso traz seus próprios problemas e requer muito mais sobrecarga para armazenamento.

Você deve ler este blog que testou a velocidade de vários tipos diferentes de coleções e métodos para cada um, usando técnicas simples e multithread.

De acordo com os resultados, a BinarySearch em uma List e a SortedList foram os melhores desempenhos constantemente em execução ao procurar algo como um "valor".

Ao usar uma coleção que permite "chaves", o Dictionary, ConcurrentDictionary, Hashset e HashTables tiveram o melhor desempenho geral.

Mantenha as duas listas xey na ordem de classificação.

Se x = y, faça sua ação, se x <y, avance x, se y <x, avance y até que uma lista esteja vazia.

O tempo de execução dessa interseção é proporcional a min (tamanho (x), tamanho (y))

Não execute um loop .Contains (), isso é proporcional a x * y, o que é muito pior.

Se for possível classificar seus itens, existe uma maneira muito mais rápida de fazer isso, fazendo pesquisas importantes em uma hashtable ou em uma árvore-b. Embora se seus itens não são classificáveis, você não pode realmente colocá-los em uma árvore B de qualquer maneira.

De qualquer forma, se você classificar as duas listas, é apenas uma questão de andar na lista de pesquisa em ordem.

Walk lookup list
   While items in check list <= lookup list item
     if check list item = lookup list item do something
   Move to next lookup list item

Se você estiver usando o .Net 3.5, poderá criar um código mais limpo usando:

foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
  //dostuff
}

Eu não tenho. Net 3.5 aqui e, portanto, isso não foi testado. Ele se baseia em um método de extensão. Não que LookupCollection.Intersect(LargeCollection)provavelmente não é o mesmo que LargeCollection.Intersect(LookupCollection)... o último é provavelmente muito mais lento.

Isso pressupõe que LookupCollection é um HashSet

Se você não está preocupado com o ruído de cada último desempenho, a sugestão de usar uma pesquisa binária ou HashSet é sólida. Seus conjuntos de dados não são grandes o suficiente para que isso seja um problema em 99% das vezes.

Mas se essa é apenas uma das milhares de vezes que você faz isso e o desempenho é crítico (e provado ser inaceitável usando a pesquisa binária HashSet /), você certamente poderia escrever seu próprio algoritmo que percorreu as listas classificadas fazendo comparações à medida que avançava. Cada lista seria percorrida no máximo uma vez e, nos casos patológicos, não seria ruim (uma vez que você seguisse esse caminho, provavelmente descobriria que a comparação, assumindo que seja uma sequência ou outro valor não integral, seria a despesa real e otimização seria o próximo passo).