Alternativas más rápidas a .Distinct()

Question

Estoy haciendo un videojuego donde el rendimiento es crítico.

Estoy usando el método de extensión .Distinct() para obtener un valor único de una lista. ¿Hay una forma más rápida de hacerlo? (incluso si eso significa tener muchas más líneas de código)

Answer 1

.Distinct es una llamada O(n).
No puede obtener nada más rápido que eso.

Sin embargo, debe asegurarse de que su GetHashCode (y, en menor medida, Equals) sea lo más rápido posible.

Dependiendo de su situación, puede reemplazar el List<T> con un HashSet<T>, lo que evitará que se inserten duplicados en primer lugar. (aún tiene una inserción de O(1))

Sin embargo, Siempre haga un perfil de su código antes de llegar a conclusiones sobre lo que necesita ser más rápido.

Answer 2

¿Tiene que ser una lista?

¿Sería posible cambiar de Lista a HashSet? HashSet evita que los objetos se inserten en la lista más de una vez en primer lugar, por lo que el Distintivo ya está hecho.

Answer 3

Si puede hacer la diferencia en su lugar, se puede hacer muy rápidamente y con cero asignaciones usando primero Array.Sort y luego:

TSource oldV = source[0]; 
int pos = 1; 
for (int i = 1; i < source.Count; i++) 
{ 
    var newV = source[i]; 
    source[pos] = newV; 
    if (!eqComparer.Equals(newV, oldV)) 
    { 
     pos++; 
    }     
    oldV = newV; 
} 
//pos now == the new size of the array 

A continuación, tendrá que hacer un seguimiento del tamaño más pequeño ahora de el arreglo, o use Array.resize (Pero eso asignará un nuevo arreglo)

Alternativamente, si hace este mismo acercamiento con un List<T> puede llamar al RemoveRange al final para redimensionarlo sin asignarlo. Esto termina siendo significativamente más rápido.

Otros carteles son probablemente correctos, aunque puede lograr este objetivo de otra manera, como usar un hashset en primer lugar, o mantener colecciones paralelas donde una contiene solo los elementos distintivos todo el tiempo. Compensación de los pequeños costos en insertar/eliminar para que no se requiera ningún tiempo para obtener el conjunto distinto.