¿Cómo diferenciar entre algoritmos de clasificación internos y externos en términos simples? ¿Cómo se lo explica a los principiantes?

Afortunadamente, este es un concepto bastante laico, suponiendo que conozca la diferencia entre la memoria principal (RAM) y la memoria externa (disco duro).

La memoria principal es muy rápida de leer y escribir, pero una máquina típica tiene mucho menos que la memoria externa (en estos días, aproximadamente 8 GB de RAM a 2 TB de disco es bastante típico).

En los casos en que necesitemos ordenar más datos de los que caben en la memoria principal, necesitamos un algoritmo de clasificación externo. En lugar de ordenar todo en la memoria, clasificamos fragmentos de datos en la memoria a la vez, volcamos los resultados en un archivo, y así sucesivamente hasta que tengamos un archivo completamente ordenado.

Divide y conquista algoritmos como la combinación de clasificación utilizada comúnmente para la clasificación externa, porque dividen el problema de clasificar todo en una serie de clasificaciones más pequeñas en trozos a la vez.

Gracias por A2A,

En la clasificación interna, tiene suficiente espacio para guardar sus datos y hacer el procesamiento y mantenerlos allí después.

En la ordenación externa no tiene suficiente espacio en la memoria principal para guardar todos los datos. Fue difícil mover los cubos, por lo que aquí el tiempo de acceso es alto si los datos están en el disco. Así que traes una parte, la ordenas y la colocas de nuevo y luego la combinas en una sola.

Los algoritmos de dividir y conquistar, como la ordenación por fusión, se usan comúnmente para la ordenación externa, porque dividen el problema de ordenar todo en una serie de ordenaciones más pequeñas en trozos a la vez.

Espero que esto ayude 🙂

Considere un escenario en el que tiene que pintar 100 cubos. Tienes una gran sala donde puedes acomodar todos estos 100 cubos. Aún tiene lugar para pararse, mantenga los elementos necesarios para pintar los cubos como un pincel, etc. Para finalizar la tarea, ingrese en la habitación y pinte todos los cubos uno por uno y manténgalos allí.

Ahora piense que tiene una habitación que solo puede acomodar 10 cubos a la vez. Los 100 cubos se mantienen en un lugar fijo al soporte, lo que dificulta retirar el cubo cada vez y moverlo para pintarlo por completo. Después de colocar estos 10 cubos, todavía tiene un lugar para que se pare, conserve las herramientas necesarias para pintar los cubos. Entonces, para pintarlos y terminar la tarea, tire de 10 cubos a la vez y muévalos libremente, gírelos o haga lo que sea necesario para pintar esos cubos por completo y colocarlos nuevamente en los soportes.

Ahora estos cubos son sus datos. Lugar para guardar los cubos, herramientas y pararse es la memoria. El lugar donde debe guardar las herramientas es la cantidad de memoria principal que puede usar para almacenar las variables adicionales requeridas para la clasificación.

En la ordenación interna, tiene suficiente espacio para almacenar sus datos y hacer el procesamiento y mantenerlos allí después.

En la ordenación externa no tiene suficiente espacio en la memoria principal para guardar todos los datos. Fue difícil mover los cubos, por lo que aquí el tiempo de acceso es alto si los datos están en el disco. Así que traes una parte, la ordenas y la colocas de nuevo y luego la combinas en una sola.

More Interesting

¿Por qué es importante almacenar y organizar datos de manera eficiente dentro de estructuras específicas al programar?

Sea X la solución del costo O (n ^ k) para un problema Q en NP-c. ¿Implicaría que existe una solución de costo O (n ^ k) para todos los problemas Q 'en NP-c?

¿Cuáles son los algoritmos populares de aprendizaje automático en línea y sus casos de uso típicos?

Siempre sueño con trabajar en grandes empresas tecnológicas como Google o Facebook, pero mi habilidad con los algoritmos es muy débil. Intento resolver problemas en Google Code Jam y CodeChef, pero solo puedo resolver los fáciles. ¿Qué tengo que hacer?

¿Cuáles son algunas buenas ideas sobre proyectos en algoritmos y / o estructuras de datos?

¿Cuál es el mejor libro para ayudar a entender la programación práctica orientada a objetos?

¿Cuál es la diferencia entre las funciones recursivas estáticas y las funciones recursivas no estáticas C / C ++?

¿El algoritmo codicioso siempre resuelve el problema de cobertura de subconjunto?

¿Cuál es el mejor algoritmo para encontrar una ruta más corta a través de todos los puntos de control dados?

Si los algoritmos avanzados y las estructuras de datos nunca se utilizan en la industria, ¿por qué aprenderlos?

¿Qué algoritmos de Machine Learning pueden usarse para el aprendizaje supervisado incremental?

¿Cómo entrenan algunas aplicaciones los algoritmos de aprendizaje automático en tiempo real en su teléfono?

¿Cuál es el algoritmo de coincidencia utilizado por las declaraciones de consulta SQL del servidor SQL como "Me gusta 'A%'", "Me gusta '% A'" o "Me gusta '% A%'"?

¿Qué es un algoritmo recursivo (pseudocódigo) que calcula la suma de los primeros enteros positivos impares?

¿Cómo puedo escribir un programa para encontrar el MCM de dos enteros positivos de su factorización prima?