Algoritmo de clasificación más eficiente para muchas teclas idénticas?

votos
8

¿Cuál es el algoritmo más eficiente para agrupar elementos idénticos en una matriz, teniendo en cuenta lo siguiente?

  1. Casi todos los artículos están duplicados varias veces.
  2. Los elementos no son necesariamente enteros o cualquier otra cosa que sea similarmente simple. El rango de las teclas ni siquiera está bien definido, y mucho menos pequeño. De hecho, las claves pueden ser estructuras arbitrarias. Esto descarta las formas más simples de clasificación de conteo.
  3. Nos preocupan las propiedades tanto asintóticas como no asintóticas, y n puede ser pequeña en ocasiones. Sin embargo, cuando n es pequeño, el rendimiento sigue siendo importante porque esta función se puede llamar varios millones de veces en un bucle en millones de pequeños conjuntos de datos. Esto descarta cualquier función costosa de hash o el uso de una estructura de datos compleja que necesita realizar muchas asignaciones de memoria.
  4. Los datos pueden ordenarse en orden arbitrario siempre que todos los elementos idénticos estén agrupados.

Si esto es confuso, aquí hay un ejemplo, suponiendo que una función de este tipo se llame groupIdentical:

uint[] foo = [1,2,3,2,1,5,4,5];
uint[] bar = groupIdentical(foo);
// One possibile correct value for bar:
// bar == [2,2,1,1,3,4,5,5].
// Another possible correct answer:
// bar == [1,1,2,2,5,5,4,3].

Sin embargo, como recordatorio, no podemos asumir que los datos están compuestos como enteros.

Editar: Gracias por las respuestas. Mi principal problema con el hash es que las tablas hash realizan asignaciones de memoria con frecuencia. Lo que terminé haciendo fue escribir mi propia tabla hash que usa un asignador de región que tuve para solucionar este problema. Funciona bien.

Publicado el 09/12/2008 a las 22:00
fuente por usuario
En otros idiomas...                            


9 respuestas

votos
10

Creo que podrías hacer hash con los objetos, ya que el orden real no importa, solo agrupamiento. Objetos idénticos terminarán agrupados en el mismo cubo. Esto supone que cada tipo que le interese tiene su propia función hash, o puede definir uno propio y sobrecargarlo (tomando cada tipo como un parámetro para una definición de función hashCode diferente).

Para evitar colisiones entre los tipos de datos (para que las cadenas no terminen en el mismo cubo que los dobles, por ejemplo), necesitarás codificar el tipo de datos en el hash. Entonces, por ejemplo, si tiene un hash de 32 bits, tal vez los primeros 5 bits podrían codificar el tipo de datos, por lo que puede tener 32 tipos diferentes en el mismo mapa hash.

EDITAR: Permítanme agregar que la razón por la que sugiero un mapa hash personalizado es porque no conozco uno que exponga lo suficiente de su implementación interna para que pueda obtener los valores de cada segmento. Puede haber tal implementación que yo no sepa. Hay muchas cosas que no sé :)

Respondida el 09/12/2008 a las 22:04
fuente por usuario

votos
4

La palabra mágica que estás buscando aquí es multiset (o bolsa ). No es realmente un tipo en absoluto, ya que no le importa el orden, siempre y cuando tenga todos los elementos con las mismas teclas agrupadas. Hay varias implementaciones enlatadas disponibles, dependiendo del idioma que esté usando, pero en general la versión anterior es asintóticamente óptima, creo: insert()es un tiempo constante, ya que puede calcular un hash en O (1) y anexar insertos que colisionan una lista en O (1) tiempo; puedes recuperar un elemento de los contenedores en O (1) vez, solo agarras el primero en el contenedor; y, por lo tanto, puede recopilarlos todos en el tiempo O (n) , ya que recupera nelementos con O (1) para cada elemento.

Respondida el 09/12/2008 a las 23:17
fuente por usuario

votos
3

Un mergesort galopante, como el ordenamiento incorporado de python (cf timsort ), tiene un buen rendimiento esperado cuando hay grandes series de datos ya ordenados (como, en su ejemplo, objetos idénticos) - omitirá O (log ( N)) trabajo por fusión. También puede distribuir un mergesort entre múltiples CPU y discos, si su conjunto de datos es extremadamente grande (esto se llama clasificación "externa"). Sin embargo, será el peor caso O (Nlog (N)).

Los únicos géneros que son más rápidos que Nlog (N) son géneros de conteo, que explotan algunas propiedades comunes de las claves. Para usar una ordenación de tiempo lineal (tabla hash o clasificación raíz / cubo), deberá hacer un hash de las estructuras para generar algún tipo de clave numérica.

Radix sort hará múltiples pasadas a través de las claves, por lo que su tiempo esperado será más largo que un enfoque hashtable; y, dado que no le importa el orden lexicográfico, la solución de tabla hash suena mejor para usted, si puede permitirse el hash de las claves.

Respondida el 09/12/2008 a las 22:10
fuente por usuario

votos
1

Creo que el hashing en cubos sería la mejor solución, suponiendo que haya un hash que preserve el operador = mapeo (0.0 podría no hash a lo mismo -0.0, pero podrían ser "iguales"). Suponiendo que solo tiene un operador igual y menor que, podría implementar un algoritmo de ordenación rápida rudimentario para elegir el primer elemento como pivote y colocar el grupo que está por debajo de un grupo, y mayor que en otro grupo, y luego repetir el proceso en cada grupo.

Respondida el 09/12/2008 a las 22:16
fuente por usuario

votos
1

3-way QuickSort funciona muy bien cuando hay una gran cantidad de duplicados.

Respondida el 09/12/2008 a las 22:14
fuente por usuario

votos
0

Algoritmo simple con orden de ejecución de O (n (n-1) / 2) es el siguiente:

  1. Supongamos que la matriz de entrada nombrada como Entrada tiene un tamaño como n.
  2. Asigne una memoria para la matriz de devolución con el mismo tamaño nombrado como Resultado
  3. Asigne una memoria para la matriz booleana con el mismo tamaño llamado Visited y establezca todo Visted como falso
  4. Supongamos que hay una función Igual llamada Igual que devuelve verdadera si ambos elementos son iguales o son falsos.
  5. Supongamos que el índice de matriz comienza de 1 a n
  6. Por favor vea el código Pseudo C a continuación:
function groupIdentical(Input) 
{
    k=1;
    for i=1 to n 
    {
        Visited[i]=false ;
    }

    for i=1 to n
    {
        if( !Visited(i) )
        {   
            Result[k++]=Input[i];
            for j= (i+1) to n
            {
                if( Equals(i,j) )
                {
                    Result[k++]=Input[j];
                    Visited[j]=true;
                }   
            }
        }
    }
    return Result;
}
Respondida el 10/12/2008 a las 08:16
fuente por usuario

votos
0

¿Tal vez un árbol R + B o AVL? Por otra parte, todavía sería en última instancia O (NlogN). También podría usar heapsort, no será peor y no habrá uso de memoria adicional ...

Respondida el 09/12/2008 a las 22:36
fuente por usuario

votos
0

Creo que debido a que tiene objetos arbitrarios que no desea copiar demasiado, puede usar referencias o punteros para el ordenamiento y, si es necesario, copiar los objetos en orden posteriormente.

Respondida el 09/12/2008 a las 22:19
fuente por usuario

votos
0

Si conoce el rango de los valores posibles, y es pequeño, podría hacer: (código pseudo-ish)

uint[] bucket = new int[10];
foreach(uint val in foo) {
    ++bucket[val];
}

uint bar_i = 0;
uint[] bar = new int[foo.length];
foreach(int val = 0; val < 10; val++) {
    uint occurrences = bucket[val];
    for(int i=0; i < occurrences; i++) {
        bar[bar_i++] = val;
    }
}
Respondida el 09/12/2008 a las 22:16
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more