Reflexiones sobre la clasificación diaria de matrices Swift
El autor recientemente encontró un problema de clasificación.
Después de hacer preguntas en el grupo
Un breve resumen
No dudéis de mi comida, a nadie le gusta.
?
Clasificación general, por ejemplo:
Ascendente/descendente según la edad de la persona. Generalmente utilizamos la clasificación integrada de Swift para resolver este problema.
Se producirán nuevos resultados después de ordenar sin afectar la secuencia original; sort() guarda los resultados en la matriz original.
?
No sé si alguna vez has pensado en este problema.
Precisamente
¿Cuál es el principio de clasificación?
?
?
El algoritmo de clasificación integrado de Swift, sort(), adopta TimSort después de Swift5, que es más estable que el Introsort anterior.
¿Qué es la estabilidad?
La capacidad de mantener el orden original de elementos iguales después de ordenarlos.
Por ejemplo
En datos reales, puede afectar la estabilidad de la secuencia ordenada.
La aplicación de música clasifica las mejores canciones según su popularidad.
Si no es lo suficientemente estable, las mismas canciones populares pueden tener resultados de clasificación diferentes cada vez.
?
TimSort también es un algoritmo híbrido, ordenación por inserción O (N^2) y ordenación por fusión O (nlogn). Debido a que tanto la inserción como la fusión son estables, TimSort también lo es.
El principio fundamental de TimSort es cortar y fusionar.
Consulte TimSort para conocer la implementación específica.
Entonces, desde esta perspectiva, la complejidad temporal del algoritmo de clasificación es O (nlogn).
?
Los requisitos del autor son:
Existe una lista de orígenes, pero la información está incompleta. Debe solicitar una lista detallada específica a través de la matriz de identificación de la lista de origen.
Anulación de la lista de origen
Sin embargo, la lista de detalles devueltos no está ordenada en el orden solicitado por los identificadores (ni ascendente ni descendente).
Requiere clasificación manual.
?
El título puede entenderse como:
?
?
Solución violenta: bucle de doble capa, complejidad temporal o (N2)
Función de orden superior: filtro flatMap, similar a la solución de fuerza bruta, complejidad temporal o (n^2) .
@sage** propuso:
Mapa plano:
Fusiona los resultados en una nueva matriz, elimina automáticamente el valor nulo y descomprime los valores opcionales.
Debido a la relación de anidamiento y la omisión de constantes, la complejidad temporal de esta solución también es O(N2).
?
Primero asigne la matriz del modelo a un diccionario y luego busque la asignación de identificadores en el diccionario. La complejidad del tiempo es O (n).
@Damonwo** propuso
En general, O(2n) =》; ¿entonces esta solución es O(n)
?
Empecé a querer usar sort, pero mi comprensión de sort era como aterrizar en la luna.
Quédate en la superficie, así que
Esta solución
@Winter *Proposal
El primer paso de esta solución se basa en subíndices asigne la matriz de identificadores al diccionario.
Obtener
[23:1, 77:2, 56:3, 9:0, 87:4]
Finalmente, según el orden ascendente del peso del indicador, clasificando las edades de las personas mediante el cierre de clasificación.
?
¿Finalmente conseguiste
[77:2, 9:0, 87:5, 56:4, 23:1]
?
Entonces el tiempo total es O(n) O(n) O(nlogn), los valores más grandes son O(nlogn).
?
Esta solución es similar a sort1 y la complejidad temporal es O (nlogn).
Autor @Tilami Bux * *, propuesto
Después de la optimización, el primer paso de índice también se coloca en el mapeo para reducir la complejidad del tiempo de búsqueda.
Es decir,
Esta idea es equivalente a sort1.
Entonces el tiempo total es O(n) O(nlogn), los valores más grandes son O(nlogn).
?
En el desarrollo real
La elección del algoritmo sigue siendo secundaria.
Independientemente de la complejidad del tiempo, las funciones de alto orden harán que Swift sea elegante; por el contrario, intente utilizar una complejidad de tiempo más baja.
Aunque este es un tipo condicional pequeño.
?
Cuantas más opciones tengas.
¿Se dividirá en ventajas y desventajas
?
Bienvenido a compartir tus propios métodos~