Find () vs. enumeração em listas

Question

Eu estou trabalhando com uma base de código onde as listas precisam ser freqüentemente procurado por um único elemento.

É mais rápido usar um predicado e find () do que fazer manualmente uma enumeração na lista?

Por exemplo:

string needle = "example";
FooObj result = _list.Find(delegate(FooObj foo) {
    return foo.Name == needle;
});

vs.

string needle = "example";
foreach (FooObj foo in _list)
{
    if (foo.Name == needle)
        return foo;
}

Enquanto eles são equivalentes em termos de funcionalidade, eles são equivalentes em desempenho bem?

Answer 1

Eles não são equivalentes no desempenho. O método Find () requer um método (neste caso delegado) invocação para cada item na lista. Invocação de método não é livre e é relativamente caros em comparação com uma comparação em linha. A versão foreach requer nenhuma invocação de método extra por objeto.

Dito isto, eu não iria escolher um ou outro com base no desempenho até que eu realmente perfilado meu código e descobriu que este é um problema. Eu ainda não encontrou a sobrecarga deste cenário a cada ser um problema "caminho quente" para o código que eu escrevi e eu usar esse padrão muito com Pesquisa e outros métodos semelhantes.

Answer 2

Se pesquisar sua lista é muito lento como está, provavelmente você pode fazer melhor do que uma busca linear. Se você pode manter a lista ordenada, você pode usar uma pesquisa binária para encontrar o elemento em tempo O (lg n).

Se você está procurando um toda muito, pensar em substituir essa lista com um dicionário para indexar seus objetos pelo nome.

Answer 3

Tecnicamente, o desempenho de tempo de execução da versão delegado será ligeiramente pior do que a outra versão -. Mas na maioria dos casos, você seria duramente pressionado para perceber qualquer diferença

De mais importância (IHMO) é o desempenho em tempo de código de ser capaz de escrever o que quiser, ao invés de como você quer. Isso faz uma grande diferença na capacidade de manutenção.

Este código original:

string needle = "example";
foreach (FooObj foo in _list)
{
    if (foo.Name == needle)        
        return foo;
}

requer qualquer manutenção para ler o código e entender que você está procurando um item específico.

Este código

string needle = "example";
return _list.Find(
    delegate(FooObj foo) 
    {
        return foo.Name == needle;
    });

deixa claro que você está procurando um item específico -. Rápida de se entender

Finalmente, este código, usando recursos do C # 3.0:

string needle = "example";
return _list.Find( foo => foo.Name == needle);

faz exatamente a mesma coisa, mas em uma linha que é ainda mais rápido para ler e compreender (bem, depois de entender lambda expressões , de qualquer maneira).

Em resumo, dado que o desempenho das alternativas é quase igual, escolher o que torna o código mais fácil de ler e manter.

Answer 4

"Eu estou trabalhando com uma base de código em que listas necessidade de ser freqüentemente pesquisados ?? para um único elemento"

É melhor mudar sua estrutura de dados para ser Dicionário em vez de lista para obter um melhor desempenho

Answer 5

pergunta homóloga foi solicitado List.ForEach vs foreach iteração ( foreach vs someList.Foreach () {} ).

Nesse caso List.ForEach foi um pouco mais rápido.

Answer 6

Como Jared apontou, há diferenças.

Mas, como sempre, não se preocupe se você não sabe que é um gargalo. E se é um gargalo, que é provavelmente porque as listas são grandes, caso em que você deve considerar o uso de um achado mais rápido - uma tabela hash ou árvore binária, ou mesmo apenas ordenar a lista e fazer busca binária vai lhe dar log (n) desempenho que terá muito mais impacto do que ajustar o seu caso linear.