Ordenación de mapas de proximidad

ProxmapSort , o Proxmap sort , es un algoritmo de ordenación que funciona dividiendo una matriz de elementos de datos, o claves, en una serie de "submatrices" (denominadas "cubos" en ordenaciones similares). El nombre es la abreviatura de calcular un "mapa de proximidad", que indica para cada clave K el comienzo de una submatriz donde K residirá en el orden ordenado final. Las claves se colocan en cada submatriz mediante ordenación por inserción . Si las claves están "bien distribuidas" entre las submatrices, la ordenación se produce en tiempo lineal. Las estimaciones de complejidad computacional involucran la cantidad de submatrices y la función de mapeo de proximidad, la "clave de mapa", utilizada. Es una forma de ordenación por cubo y por radix .

Una vez que se completa un ProxmapSort, se puede utilizar ProxmapSearch para encontrar claves en la matriz ordenada a tiempo si las claves se distribuyeron bien durante la ordenación. ${\estilo de visualización O(1)}$

Ambos algoritmos fueron inventados a finales de la década de 1980 por el profesor Thomas A. Standish en la Universidad de California, Irvine .

En general: Dada una matriz A con n claves:

• Asignar una clave a una submatriz de la matriz de destino A2 , aplicando la función de asignación de clave a cada elemento de la matriz
• determinar cuántas claves se asignarán a la misma submatriz, utilizando una matriz de "conteos de aciertos", H
• determinar dónde comenzará cada submatriz en la matriz de destino para que cada contenedor tenga exactamente el tamaño adecuado para contener todas las claves que se asignarán a él, utilizando una matriz de "proxmaps", P
• Para cada clave, calcula la submatriz a la que se asignará, utilizando una matriz de "ubicaciones", L
• Para cada clave, busque su ubicación, colóquela en esa celda de A2 ; si choca con una clave que ya está en esa posición, ordene por inserción la clave en su lugar, moviendo las claves mayores que esta clave hacia la derecha en una unidad para hacer un espacio para esta clave. Dado que el subconjunto es lo suficientemente grande como para contener todas las claves asignadas a él, dicho movimiento nunca hará que las claves se desborden en el subconjunto siguiente.

Versión simplificada: dada una matriz A con n claves

1. Inicializar : crea e inicializa 2 matrices de tamaño n : hitCount , proxMap y 2 matrices de longitud A : location y A2 .
2. Partición : utilizando una función mapKey cuidadosamente elegida , divida el A2 en submatrices utilizando las claves en A
3. Dispersar : Leer sobre A , colocando cada clave en su contenedor en A2 ; ordenación por inserción según sea necesario.
4. Recopilar : visite las submatrices en orden y vuelva a colocar todos los elementos en la matriz original, o simplemente use A2 .

Nota: las "claves" también pueden contener otros datos, por ejemplo, una matriz de objetos de Estudiante que contienen la clave más un ID y un nombre de estudiante. Esto hace que ProxMapSort sea adecuado para organizar grupos de objetos, no solo las claves en sí.

Considere una matriz completa: A [ 0 a n-1 ] con n claves. Sea i un índice de A. Ordene las claves de A en la matriz A2 de igual tamaño.

La función clave del mapa se define como mapKey(key) = floor(K).

// Calcular el número de aciertos 
para i = 0 a 11 // donde 11 es n { H [ i ] = 0 ; } para i = 0 a 12 // donde 12 es A.length { pos = MapKey ( A [ i ] ); H [ pos ] = H [ pos ] + 1 ; }      

      

      

      
        


runningTotal = 0 ; // calcular mapa de proximidad – ubicación del inicio de cada subarreglo para i = 0 a 11 si H [ i ] = 0 P [ i ] = - 9 ; de lo contrario P [ i ] = runningTotal ; runningTotal = runningTotal + H [ i ] ;   
     
       
          
    
          
            

para i = 0 a 12 // calcular la ubicación – submatriz – en A2 en la que se colocará cada elemento en A L [ i ] = P [ MapKey ( A [ i ] ) ] ;      
      

para I = 0 a 12 ; // ordenar elementos A2 [ I ] = < vacío > ; para i = 0 a 12 // insertar cada elemento en el subarreglo comenzando en inicio, conservando el orden { inicio = L [ i ] ; // el subarreglo para este elemento comienza en esta ubicación inserción realizada = falso ; para j = inicio hasta ( < se encuentra el final de A2 y no se realiza la inserción > ) { si A2 [ j ] == < vacío > // si el subarreglo está vacío, solo se coloca el elemento en la primera posición del subarreglo A2 [ j ] = A [ i ] ; inserción realizada = verdadero ; de lo contrario si A [ i ] < A2 [ j ] // la clave pertenece a A2[j] int fin = j + 1 ; // encontrar el final de la parte usada del subarreglo – donde el primer <vacío> es while ( A2 [ fin ] != < vacío > ) fin ++ ; para k = fin - 1 a j // mover claves más grandes a la derecha 1 celda A2 [ k + 1 ] = A2 [ k ] ; A2 [ j ] = A [ i ] ; inserción realizada = verdadera ; // agregar nueva clave } }      
      
      

       
       
                  
    
            
              
               
             
                  
               
                
                   
                  
                  
                
    

Aquí A es la matriz que se va a ordenar y las funciones mapKey determinan la cantidad de submatrices que se van a utilizar. Por ejemplo, floor(K) simplemente asignará tantas submatrices como enteros haya de los datos en A. Dividir la clave por una constante reduce la cantidad de submatrices; se pueden utilizar diferentes funciones para traducir el rango de elementos en A a submatrices, como convertir las letras A–Z en 0–25 o devolver el primer carácter (0–255) para ordenar cadenas. Las submatrices se ordenan a medida que llegan los datos, no después de que todos los datos se hayan colocado en la submatriz, como es típico en la ordenación por cubos .

ProxmapSearch utiliza la matriz proxMap generada por un ProxmapSort realizado previamente para encontrar claves en la matriz ordenada A2 en tiempo constante.

• Ordene las claves utilizando ProxmapSort, manteniendo la función MapKey y las matrices P y A2
• Para buscar una clave, vaya a P[MapKey(k)], el inicio de la submatriz que contiene la clave, si esa clave está en el conjunto de datos
• Buscar secuencialmente la submatriz; si se encuentra la clave, devolverla (y la información asociada); si se encuentra un valor mayor que la clave, la clave no está en el conjunto de datos
• Calcular P[MapKey(k)] lleva tiempo. Si se utilizó una clave de mapa que proporciona una buena distribución de claves durante la ordenación, cada submatriz está limitada por encima por una constante c , por lo que se necesitan, como máximo, c comparaciones para encontrar la clave o saber que no está presente; por lo tanto, ProxmapSearch es . Si se utilizó la peor clave de mapa, todas las claves están en la misma submatriz, por lo que ProxmapSearch, en este peor caso, requerirá comparaciones.${\estilo de visualización O(1)}$${\estilo de visualización O(1)}$${\displaystyle O(n)}$

La función mapKey(key) devuelve
     floor(key
 )

    proxMap ← matriz proxmap generada previamente de tamaño n
    A2 ← matriz previamente ordenada de tamaño n
La función proxmap-search(key) es 
    para i = proxMap[mapKey(key)] hasta length(array) − 1 si sortedArray[i].key == key entonces devuelve
         sortedArray[i]

            

El cálculo de H, P y L lleva tiempo. Cada uno de ellos se calcula con una pasada a través de una matriz, con un tiempo constante empleado en cada ubicación de la matriz. ${\displaystyle O(n)}$

• Peor de los casos: MapKey coloca todos los elementos en una submatriz, lo que genera una ordenación por inserción estándar y un tiempo de .${\displaystyle O(n^{2})}$
• Mejor caso: MapKey entrega la misma pequeña cantidad de elementos a cada submatriz en un orden en el que se produce el mejor caso de ordenación por inserción. Cada ordenación por inserción es , c el tamaño de las submatrices; hay p submatrices, por lo tanto p * c = n , por lo que la fase de inserción toma O(n); por lo tanto, ProxmapSort es .${\displaystyle O(c)}$${\displaystyle O(n)}$
• Caso promedio: cada submatriz tiene un tamaño máximo de c , una constante; la ordenación por inserción para cada submatriz es entonces O(c^2) en el peor de los casos, una constante. (El tiempo real puede ser mucho mejor, ya que los c elementos no se ordenan hasta que se coloca el último elemento en el contenedor). El tiempo total es la cantidad de contenedores, (n/c) , multiplicado por = .$Estilo de visualización O(c^{2})}$${\displaystyle O(n)}$

Es imprescindible contar con una buena función MapKey para evitar el peor de los casos. Debemos saber algo sobre la distribución de los datos para obtener una buena clave.

1. Ahorre tiempo: guarde los valores de MapKey(i) para que no sea necesario volver a calcularlos (como en el código anterior)
2. Ahorrar espacio: Los proxMaps se pueden almacenar en la matriz hitCount, ya que los conteos de aciertos no son necesarios una vez que se calcula el proxmap; los datos se pueden volver a ordenar en A, en lugar de usar A2, si uno tiene cuidado de anotar qué valores A se han ordenado hasta ahora y cuáles no.

Implementación del código JavaScript:

Matriz . prototipo . ProxmapSort = function () { //-- Fecha de edición: 2019/11/13 Taiwán --// var inicio = 0 ; var fin = esta . longitud ; var A2 = nueva matriz ( fin ); var MapKey = nueva matriz ( fin ); var hitCount = nueva matriz ( fin ); para ( var i = inicio ; i < fin ; i ++ ) { hitCount [ i ] = 0 ; } var min = esta [ inicio ]; var max = esta [ inicio ]; para ( var i = inicio + 1 ; i < fin ; i ++ ) { si ( esta [ i ] < min ) { min = esta [ i ]; } de lo contrario { si ( esta [ i ] > max ) { max = esta [ i ]; }} } //Optimización 1. Guarde MapKey[i]. para ( var i = inicio ; i < fin ; i ++ ) { MapKey [ i ] = Math.floor ((( este [ i ] - min ) / ( máximo - min )) * ( fin - 1 ) ); hitCount [ MapKey [ i ] ] ++ ; }  

     
     
      
      
      
  
               
     
     
           
            
             
  
  
           
                  
    
  
  //Optimización 2. ProxMaps almacena en hitCount. 
hitCount [ end - 1 ] = end - hitCount [ end - 1 ]; for ( var i = end - 1 ; i > start ; i -- ){ hitCount [ i - 1 ] = hitCount [ i ] - hitCount [ i - 1 ]; } //insertar A[i]=this[i] en la posición correcta de A2 var insertIndex = 0 ; var insertStart = 0 ; for ( var i = start ; i < end ; i ++ ) { insertIndex = hitCount [ MapKey [ i ]]; insertStart = insertIndex ; while ( A2 [ insertIndex ] != null ) { insertIndex ++ ; } while ( insertarÍndice > insertarInicio && this [ i ] < A2 [ insertarÍndice - 1 ]) { A2 [ insertarÍndice ] = A2 [ insertarÍndice - 1 ]; insertarÍndice -- ; } A2 [ insertarÍndice ] = this [ i ]; } for ( var i = inicio ; i < fin ; i ++ ) { this [ i ] = A2 [ i ]; } };      
          
        
  
  
     
     
           
      
      
          
            
        
      
    
      
  
               

Dado que ProxmapSort no es una ordenación por comparación , el límite inferior Ω( n log n ) no es aplicable. ^{[ cita requerida ]} Su velocidad se puede atribuir a que no se basa en comparaciones y utiliza matrices en lugar de objetos asignados dinámicamente y punteros que deben seguirse, como se hace cuando se usa un árbol de búsqueda binaria .

ProxmapSort permite el uso de ProxmapSearch. A pesar del tiempo de compilación O(n), ProxMapSearch lo compensa con su tiempo de acceso promedio, lo que lo hace muy atractivo para bases de datos grandes. Si no es necesario actualizar los datos con frecuencia, el tiempo de acceso puede hacer que esta función sea más favorable que otras ordenaciones que no se basan en comparaciones . ${\estilo de visualización O(1)}$

Al igual que ProxmapSort, la ordenación por cubos generalmente opera sobre una lista de n entradas numéricas entre cero y alguna clave o valor máximo M y divide el rango de valores en n cubos, cada uno de tamaño M / n . Si cada cubo se ordena utilizando la ordenación por inserción , se puede demostrar que ProxmapSort y la ordenación por cubos se ejecutan en un tiempo lineal previsto. ^{[1] [ ¿ investigación original? ]} Sin embargo, el rendimiento de esta ordenación se degrada con la agrupación (o muy pocos cubos con demasiadas claves); si muchos valores ocurren juntos, todos caerán en un solo cubo y el rendimiento se verá gravemente disminuido. Este comportamiento también es válido para ProxmapSort: si los cubos son demasiado grandes, su rendimiento se degradará gravemente.

• Thomas A. Standish. Estructuras de datos en Java. Addison Wesley Longman, 1998. ISBN 0-201-30564-X . Sección 10.6, págs. 394–405. 
• Standish, TA; Jacobson, N. (2005). "Uso de O ( n ) Proxmap Sort y O (1) Proxmap Search para motivar a los estudiantes de CS2 (Parte I)". Boletín ACM SIGCSE . 37 (4). doi :10.1145/1113847.1113874.
• Standish, TA; Jacobson, N. (2006). "Uso de O ( n ) Proxmap Sort y O (1) Proxmap Search para motivar a los estudiantes de CS2, Parte II". Boletín ACM SIGCSE . 38 (2). doi :10.1145/1138403.1138427.
• Norman Jacobson "Una sinopsis de ProxmapSort y ProxmapSearch" del Departamento de Ciencias de la Computación, Escuela de Información y Ciencias de la Computación Donald Bren , UC Irvine .

• http://www.cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html
• https://web.archive.org/web/20120712094020/http://www.valdosta.edu/~sfares/cs330/cs3410.a.sorting.1998.fa.html
• https://web.archive.org/web/20120314220616/http://www.cs.uml.edu/~giam/91.102/Demos/ProxMapSort/ProxMapSort.c