Buscar () vs. enumeración en listas

Question

Estoy trabajando con una base de códigos donde las listas deben buscarse con frecuencia para un solo elemento.

¿Es más rápido usar un Predicado y Buscar () que hacer una enumeración manualmente en la Lista?

por ejemplo:

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;
}

Si bien son equivalentes en funcionalidad, ¿también son equivalentes en rendimiento?

Answer 1

No son equivalentes en rendimiento. El método Find () requiere una invocación del método (en este caso delegado) para cada elemento de la lista. La invocación del método no es gratuita y es relativamente costosa en comparación con una comparación en línea. La versión foreach no requiere una invocación de método adicional por objeto.

Dicho esto, no elegiría uno u otro en función del rendimiento hasta que realmente perfilara mi código y encontré que esto era un problema. Todavía no he encontrado la sobrecarga de este escenario para cada una de las "rutas de acceso" " " problema para el código que he escrito y uso mucho este patrón con Buscar y otros métodos similares.

Answer 2

Si la búsqueda en su lista es demasiado lenta, es probable que pueda hacerlo mejor que una búsqueda lineal. Si puede mantener la lista ordenada, puede utilizar una búsqueda binaria para encontrar el elemento en tiempo O (lg n).

Si está buscando un lote entero , considere reemplazar esa lista con un Diccionario para indexar sus objetos por nombre.

Answer 3

Técnicamente, el rendimiento en tiempo de ejecución de la versión del delegado será ligeramente peor que la de la otra versión, pero en la mayoría de los casos, será difícil percibir cualquier diferencia.

Más importante (IHMO) es el rendimiento del tiempo de código de poder escribir lo que quiere, en lugar de cómo lo quiere. Esto hace una gran diferencia en la mantenibilidad.

Este código original:

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

requiere que cualquier mantenedor lea el código y comprenda que estás buscando un artículo en particular.

Este código

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

deja claro que estás buscando un artículo en particular, más rápido de entender.

Finalmente, este código, utilizando las características de C # 3.0:

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

hace exactamente lo mismo, pero en una línea es incluso más rápido de leer y entender (bueno, una vez que entiendas expresiones lambda , de todos modos).

En resumen, dado que el rendimiento de las alternativas es casi igual, elija la que facilite la lectura y el mantenimiento del código.

Answer 4

" Estoy trabajando con una base de código donde las listas deben buscarse con frecuencia para un elemento único "

Es mejor cambiar la estructura de datos para que sea Diccionario en lugar de Lista para obtener un mejor rendimiento

Answer 5

Se hizo una pregunta similar para List.ForEach vs. foreach-iteration ( foreach vs someList.Foreach () {} ).

En ese caso, List.ForEach fue un poco más rápido.

Answer 6

Como señaló Jared, hay diferencias.

Pero, como siempre, no se preocupe a menos que sepa que es un cuello de botella. Y si se trata de un cuello de botella, probablemente se deba a que las listas son grandes, en cuyo caso debería considerar usar una búsqueda más rápida: una tabla hash o un árbol binario, o incluso simplemente ordenar la lista y hacer una búsqueda binaria le dará un registro (n) rendimiento que tendrá mucho más impacto que ajustar su caso lineal.