2009-08-26 30 views
5

Tengo problemas para encontrar la forma más eficaz de eliminar duplicados de una lista de cadenas (List).Eliminando cadenas duplicadas de List (.NET 2.0!)

Mi implementación actual es un bucle foreach dual que verifica el recuento de instancias de cada objeto siendo solo 1, de lo contrario, se elimina el segundo.

Sé que hay MUCHAS otras preguntas por ahí, pero todas las mejores soluciones requieren .net 2.0 anterior, que es el entorno de construcción actual en el que estoy trabajando. (GM y Chrysler son muy resistentes a los cambios ... :))

Esto limita los posibles resultados al no permitir ningún LINQ o HashSets.

El código que estoy usando es Visual C++, pero una solución C# también funcionará bien.

Gracias!

Respuesta

15

Esto probablemente no es lo que está buscando, pero si usted tiene control sobre esto, la forma más eficaz sería la de no añadirlos en primer lugar ...

¿Tiene control sobre ¿esta? Si es así, todo lo que tendría que hacer es llamar al myList.Contains(currentItem) antes de agregar el artículo y está configurado en

+0

Hah, nunca pensé en eso, ¡sí tengo control sobre la generación inicial de listas! – greggorob64

+0

LOL. ¡eso es GANAR! – Alan

+1

Tenga en cuenta que este enfoque no se escala muy bien a medida que aumenta el tamaño de la lista ... – Lee

9

. Podría hacer lo siguiente.

List<string> list = GetTheList(); 
Dictionary<string,object> map = new Dictionary<string,object>(); 
int i = 0; 
while (i < list.Count) { 
    string current = list[i]; 
    if (map.ContainsKey(current)) { 
    list.RemoveAt(i); 
    } else { 
    i++; 
    map.Add(current,null); 
    } 
} 

Esto tiene la sobrecarga de la construcción de un objeto Dictionary<TKey,TValue> que duplicar la lista de valores únicos en la lista. Pero es bastante eficiente en cuanto a la velocidad.

+0

+1 Lo primero que se me ocurrió fue comparar cada valor entre sí y eliminar los duplicados a medida que se encuentran, pero la complejidad es N^2. La solución de Jared es mucho más agradable ya que al usar una estructura de datos Dicitonary hará uso de hash y, por lo tanto, búsquedas muy rápidas. Complejidad = N (log N)? –

+0

Si la velocidad es importante, sería mejor crear una nueva lista de valores únicos en lugar de eliminar los duplicados de la lista original, ya que RemoveAt es O (n) pero Add es O (1) cuando conoce la longitud máxima por adelantado . – stevemegson

1

No soy doctorado en ciencia ficción, pero me imagino que usaría un diccionario, con los elementos en su lista ya que las teclas serían rápidas.

Dado que un diccionario no permite claves duplicadas, solo tendrías cadenas únicas al final de la iteración.

1

Solo recuerde cuando se proporciona una clase personalizada para anular el método Equals() para que Contains() funcione como se requiere.

Ejemplo

List<CustomClass> clz = new List<CustomClass>() 

public class CustomClass{ 

    public bool Equals(Object param){ 
     //Put equal code here... 
    } 
} 
1

Si usted va la ruta de "simplemente no añadir duplicados", a continuación, comprobar "List.Contains" antes de añadir un elemento funciona, pero su O (n^2) donde n es el número de cadenas que desea agregar. No es diferente de su solución actual utilizando dos bucles anidados.

Tendrá mejor suerte usando un hashset para almacenar artículos que ya haya añadido, pero desde que está utilizando .NET 2.0, un diccionario puede sustituir a un conjunto de hash:

static List<T> RemoveDuplicates<T>(List<T> input) 
{ 
    List<T> result = new List<T>(input.Count); 
    Dictionary<T, object> hashSet = new Dictionary<T, object>(); 
    foreach (T s in input) 
    { 
     if (!hashSet.ContainsKey(s)) 
     { 
      result.Add(s); 
      hashSet.Add(s, null); 
     } 
    } 
    return result; 
} 

Esto funciona en O (n) y usa O (2n) espacio, generalmente funcionará muy bien para hasta 100K elementos. El rendimiento real depende de la longitud promedio de las cadenas: si realmente necesita un rendimiento máximo, puede explotar algunas estructuras de datos más poderosas, como los intentos de hacer inserciones incluso más rápido.

+0

Los HashSet son .net 3.5+, que está fuera del alcance de esta pregunta. – greggorob64

+2

Mis códigos no usan HashSet, usa un diccionario que lo sustituye como HashSet. – Juliet

+0

Debería haber leído su código más a fondo, solo vi la palabra HashSet y salté sobre ella. – greggorob64