El rendimiento cuando la comprobación de duplicados

Question

He estado trabajando en un proyecto donde necesito para iterar a través de una colección de datos y eliminar las entradas donde la "clave principal" se duplica.He intentado usar un

List<int>

y

Dictionary<int, bool>

Con el diccionario encontré un rendimiento ligeramente mejor, aunque nunca se necesita el Booleano etiquetados con cada entrada.Mi expectativa es que esto es debido a que una Lista permite el acceso indizado y un Diccionario no.Lo que me pregunto es, ¿hay una mejor solución a este problema.No necesito para acceder a las entradas de nuevo, sólo necesito la pista de lo principal "claves" que he visto y asegurarse de que sólo se realice, además de trabajar en las entradas que tienen una nueva clave principal.Estoy usando C# y .NET 2.0.Y no tengo control sobre la fijación de los datos de entrada para eliminar los duplicados de la fuente (por desgracia!).Y así que usted puede tener una idea de la escala, en general estoy de comprobación de duplicados de aproximadamente 1.000.000 de veces en la aplicación, pero en los subgrupos de no más de unos 64.000 que tiene que ser único.

Answer 1

Se ha añadido la clase HashSet en .NET 3.5.Pero supongo que será a la par con el Diccionario.Si usted tiene menos de decir un 100 elementos de una Lista realizará probablemente mejor.

Answer 2

Editar:No importa mi comentario.Pensé que usted está hablando acerca de C++.No tengo idea de si mi post es relevante en el C# mundo..

Un hash de la tabla podría ser un poco más rápido.Árboles binarios (que es lo que se utiliza en el diccionario) tienden a ser relativamente lento debido a la forma en que la memoria se accede.Esto es especialmente cierto si el árbol es muy grande.

Sin embargo, antes de cambiar su estructura de datos, ¿has probado a usar un custom piscina asignador de su diccionario?Apuesto a que el tiempo no pasó recorriendo el árbol en sí, sino en los millones de asignaciones y deallocations el diccionario va a hacer por usted.

Usted puede ver a un factor de 10 a la velocidad del impulso sólo conectar una simple piscina asignador en el diccionario de la plantilla.Afaik boost tiene un componente que puede ser utilizado directamente.

Otra opción:Si usted sabe que sólo 64.000 entradas en su enteros existe usted puede escribir en un archivo y crear una perfecta función de hash para ello.De esa manera usted puede utilizar la función de hash para asignar los números enteros en el 0 64.000 rango de índice y un poco de matriz.

Probablemente la manera más rápida, pero menos flexible.Usted tiene que rehacer su perfecta función hash (se puede hacer de forma automática cada vez que el conjunto de números enteros cambios.

Answer 3

Yo realmente no se lo que están pidiendo.

En primer lugar, es justo lo contrario de lo que dices.El diccionario tiene acceso indizado (es una tabla hash), mientras que de la Lista no.

Si usted ya dispone de los datos en un diccionario, a continuación, todas las claves son únicas, no puede haber duplicados.

Yo susspect tiene los datos almacenados en otro tipo de datos y se almacena en el diccionario.Si ese es el caso de la inserción de los datos se trabajo con dos dictionarys.

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

Answer 4

Si están buscando la singularidad de los números enteros, y el rango de números enteros es limitado es suficiente, entonces usted podría utilizar una matriz.

Para un mejor embalaje puede implementar un mapa de bits de la estructura de los datos (básicamente una matriz, pero cada uno de int en la matriz representa el 32 puntos en el espacio de claves mediante el uso de 1 bit por clave).De este modo, si el número máximo es de 1.000.000 de sólo necesita ~30.5 KB de memoria para la estructura de datos.

Realiza un mapa de bits sería O(1) (por cheque) que es difícil de superar.

Answer 5

No era una pregunta hace un tiempo en eliminación de duplicados de un array.Para el propósito de la cuestión de rendimiento no era mucho de un examen, pero es posible que desee echar un vistazo a las respuestas que podría dar algunas ideas.También, podría estar fuera de base aquí, pero si usted está tratando de eliminar los duplicados de la matriz, a continuación, un comando como LINQ Enumerable.Distintas podría dar mejor rendimiento que algo que usted mismo escribe.Como resulta que hay una manera de conseguir LINQ trabajando .NET 2.0 así que esto podría ser una ruta que vale la pena investigar.

Answer 6

Si usted va a utilizar una Lista, utilice el BinarySearch:

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
} 

También puede utilizar esto para cualquier tipo para el que puede definir un IComparer mediante el uso de una sobrecarga:BinarySearch( T elemento, IComparer< T > );