net - ¿Qué es mejor para crear estructuras de datos distintas: HashSet o Linq''s Distinct()?

iset c#

Question

Me pregunto si puedo obtener un consenso sobre qué método es el mejor método para crear un conjunto distinto de elementos: un conjunto de C# HashSet o el uso IEnumerable''s .Distinct() , ¿cuál es una función de Linq?

Digamos que estoy haciendo un bucle a través de los resultados de la consulta desde la base de datos con DataReader, y mis opciones son agregar los objetos que construyo a una List<SomeObject> o a un HashSet<SomeObject> Con la opción List , acabaría teniendo que hacer algo como:

myList = myList.Distinct().ToList<SomeObject>();

Con el HashSet , mi entendimiento es que agregar elementos al mismo se encarga de la no duplicación, asumiendo que haya anulado los métodos GetHashCode() y Equals() en SomeObject. Me preocupan principalmente los aspectos de riesgo y rendimiento de las opciones.

Gracias.

Answer 1

"Mejor" es una palabra difícil de usar, ya que puede significar muchas cosas diferentes para diferentes personas.

Para facilitar la lectura, optaría por Distinct() ya que personalmente me parece más comprensible.

Para el rendimiento, sospecho que una implementación HashSet hecha a mano podría tener un rendimiento ligeramente más rápido, pero dudo que sea muy diferente, ya que la implementación interna de Distinct sin duda usará algún tipo de hash.

Para lo que considero que es la "mejor" implementación ... Creo que debería usar Distinct pero de alguna manera empujar esto hacia la capa de la base de datos, es decir, cambiar la base de datos SELECT antes de llenar el DataReader.

Answer 2

Anthony Pegram lo ha dicho lo mejor. Utilice la herramienta adecuada para el trabajo. Digo esto porque un Distinct o HashSet no es tan diferente cuando se trata de rendimiento. Use un HashSet cuando la colección siempre debe contener solo elementos distintos. También le dice al programador que no puedes agregarle duplicados. Use una List<T> normal List<T> y .Distinct() ella cuando tendrá que agregar duplicados y eliminar los duplicados más adelante. La intención importa.

En general,

a) un HashSet puede no servir de nada si está agregando nuevos objetos desde db y no ha especificado sus propios Equals personalizados. Cada objeto de db puede ser una nueva instancia para su hashset (si es que está recién iniciando) y eso llevará a duplicados en la colección. En ese caso use la List<T> normal List<T> .

b) Si tiene un comparador de igualdad definido para hashset, y su colección siempre debe contener solo objetos distintos, use hashset.

c) Si tiene un comparador de igualdad definido para el hashset y desea solo objetos distintos de db, pero la colección no siempre tiene solo objetos distintos (es decir, los duplicados deben agregarse más adelante), un enfoque más rápido es obtener los elementos de db a un hashset y luego devolver una lista regular de ese hashset.

d) Lo mejor que debes hacer es asignar la tarea de eliminar duplicados a la base de datos, esa es la herramienta correcta ¡ Y eso es de primera clase!

En cuanto a las diferencias de rendimiento, en mis pruebas siempre encontré que HashSet era más rápido, pero eso es solo marginal. Eso es obvio considerando que con el enfoque de lista primero debe agregar y luego hacer una diferencia en él.

Método de prueba: Comenzando con dos funciones generales,

public static void Benchmark(Action method, int iterations = 10000)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < iterations; i++)
        method();

    sw.Stop();
    MsgBox.ShowDialog(sw.Elapsed.TotalMilliseconds.ToString());
}

public static List<T> Repeat<T>(this ICollection<T> lst, int count)
{
    if (count < 0)
        throw new ArgumentOutOfRangeException("count");

    var ret = Enumerable.Empty<T>();

    for (var i = 0; i < count; i++)
        ret = ret.Concat(lst);

    return ret.ToList();
}

Implementación:

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
HashSet<int> hash = new HashSet<int>();

Benchmark(() =>
{
    hash.Clear();
    foreach (var item in d)
    {
        hash.Add(item);
    }
});

~ 3300 ms

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
List<int> list = new List<int>();

Benchmark(() =>
{
    list.Clear();
    foreach (var item in d)
    {
        list.Add(item);
    }

    list = list.Distinct().ToList();
});

~ 5800 ms

Una diferencia de 2,5 segundos no es mala para una lista de 10000 objetos cuando se iteran otras 10000 veces. Para casos normales la diferencia será apenas perceptible.

El mejor enfoque posible para usted con su diseño actual:

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
HashSet<int> hash = new HashSet<int>();
List<int> list = new List<int>();

Benchmark(() =>
{
    hash.Clear();
    foreach (var item in d)
    {
        hash.Add(item);
    }

    list = hash.ToList();
});

~ 3300 ms

No hay ninguna diferencia significativa, ver ..

En parte no relacionado: después de publicar esta respuesta, tenía curiosidad por saber cuál es el mejor enfoque para eliminar duplicados de una lista normal.

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
HashSet<int> hash = new HashSet<int>();
List<int> list = new List<int>();

Benchmark(() =>
{
    hash = new HashSet<int>(d);
});

~ 3900 ms

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
List<int> list = new List<int>();

Benchmark(() =>
{
    list = d.Distinct().ToList();
});

~ 3200 ms

Aquí, la herramienta correcta Distinct es más rápida que HashSet HashSet ! Tal vez es la sobrecarga de crear un conjunto hash.

He probado con varias otras combinaciones como tipos de referencia, sin duplicados en la lista original, etc. Los resultados son consistentes.

Answer 3

La implementación de Distinct puede usar HashSet. Eche un vistazo a la implementación de Edulinq de Jon Skeet .

Answer 4

Si yor recorre los resultados de un DbReader agregando sus resultados a un Hashset sería mejor que agregarlo a una Lista y hacer un Distinct en eso. Usted ahorraría una iteración. (Distinto utiliza internamente un HashSet)

Answer 5

Lo que es mejor es lo que más expresa expresando tu intención. Los detalles de la implementación interna serán más o menos iguales, la diferencia es "¿quién está escribiendo el código?"

Si su intención es crear desde cero una colección distinta de elementos de una fuente que no sea una colección de dichos elementos, argumentaría en favor de HashSet<T> . Tienes que crear el elemento, tienes que crear la colección, también podrías crear el correcto desde el principio.

De lo contrario, si ya tiene una colección de elementos y desea eliminar los duplicados, abogaría por invocar a Distinct() . Ya tienes una colección, solo quieres una forma expresiva de obtener los distintos elementos de ella.

Answer 6

Para colecciones grandes, es probable que HashSet sea más rápido. Se basa en el código hash de los objetos para determinar rápidamente si un elemento ya existe en el conjunto.

En la práctica, (lo más probable) no importará (pero debe medir si le importa).

Instintivamente supuse al principio que HashSet sería más rápido, debido a la rápida comprobación de hash que utiliza. Sin embargo, busqué la implementación actual (4.0) de Distinct en las fuentes de referencia, y utiliza una clase Set similar (que también se basa en el hashing) debajo de las portadas. Conclusión; No hay diferencia de rendimiento práctico.

Para su caso, me gustaría ir con .Distinct para la legibilidad - claramente transmite la intención del código. Sin embargo, estoy de acuerdo con una de las otras respuestas, de que probablemente debería realizar esta operación en la base de datos si es posible.