Descargue AlgoLab desde una unidad de Google ( archivos AlgoLab (Excel 2007-2013) .xlsm y AlgoLab (Excel 97-2003) .xls ).Lo que los bolcheviques han estado hablando durante tanto tiempo y lo que he estado persiguiendo durante varios años a un ritmo diferente finalmente ha sucedido. Hace unos años, escribió una pequeña macro para crear animaciones gif algorítmicas para habrastaty. Con el tiempo, mi humilde instrumento ha crecido a un tamaño impresionante, lo que ahora no es una pena revelar al mundo.
Entonces conocete.
AlgoLab es una aplicación de Excel (es decir, un archivo de Excel con macros) en el que puede familiarizarse paso a paso con los algoritmos de clasificación. Y también existe la oportunidad de preparar gif-animación.
Ejemplos de animación generada.Clasificación de árboles binarios
Clasificación de espagueti
Tipo de dormir
Solo 4 hojas: 2 principales y 2 informativas. Aquí están:
Al hacer clic en una imagen, se abrirá una imagen a tamaño completo- Ordenar hoja. En esta hoja, puede formar rápidamente una matriz y seleccionar un algoritmo de clasificación.
- Proceso de hoja. Aquí observamos paso a paso cómo funciona este o aquel algoritmo.
- Ordenar hoja. Aquí hay un resumen de los algoritmos.
- Gráfico de hoja. También hay un cronograma de lanzamiento planificado para artículos sobre clasificación.
Conozcamos estas hojas con más detalle.
Hoja de clasificación
La parte superior de la hoja está dedicada a la generación de una matriz sin clasificar (de modo que haya algo para alimentar el algoritmo), así como a guardar la visualización en forma de imágenes en su computadora:
En la primera línea está la matriz misma. Si es necesario, puede cambiar manualmente los valores de elementos individuales en él:
En la esquina superior izquierda, debe especificar las características principales de la matriz generada:
El tamaño, si los valores en la matriz no deben repetirse (0 - no, 1 - sí), que son iguales a los elementos mínimo y máximo en la matriz. Las macros de VBA incluyen resistencia al vandalismo a los datos de entrada, por lo que puede ingresar algunos valores incorrectos. En este caso, la aplicación determinará a qué debe ser igual esta o aquella característica.
Y también una opción para determinar si es necesario ejecutar el algoritmo paso a paso (= 1) o si es posible aplicar la clasificación a la estructura y mostrar solo el resultado final (= 0). Por supuesto, la aplicación Excel en sí misma fue creada para observar todo el proceso en modo paso a paso, por lo que el valor aquí suele ser igual a uno. Pero a veces, cuando pruebo, anulo esta opción para verificar si el nuevo algoritmo que agrego a AlgoLab.xlsm funciona (es decir, primero necesito ver si la matriz ordenada es el resultado final, sin perder tiempo viendo la visualización) )
Un poco a la derecha está el área en la que puede especificar cómo no se ordenan exactamente los elementos en la matriz sin clasificar generada.
Generar matriz mixta al azar? ¿O tal vez organizar los elementos en orden descendente? ¿O hacer que la matriz esté casi ordenada (y también especificar el coeficiente de casi clasificación)?
Para seleccionar cualquiera de estos métodos, solo necesita hacer clic en la celda con el elemento. Como resultado, la matriz se regenera en la primera línea. La celda seleccionada se volverá azul.
A la izquierda está el territorio que será necesario si necesita no solo admirar la visualización, sino también guardar todo el proceso cuadro por cuadro como imágenes.
Primero, debe especificar si exportar los pasos de clasificación en general a las imágenes (= 0, si no, = 1 en caso afirmativo, y esta opción es "única", es decir, se restablece a cero después de completar la clasificación). En segundo lugar, debe especificar el formato de la imagen (solo son posibles 4 opciones: GIF, JPG, PNG y BMP. La última opción ofrece el resultado de mayor calidad, por lo que lo recomiendo). En tercer lugar, debe especificar la ruta a la carpeta donde guardar las imágenes (haga clic en esta celda y se abrirá un cuadro de diálogo para seleccionar un directorio). Luego viene la celda que la macro completa: el identificador de sesión (necesario para el nombre único de la subcarpeta para guardar fotogramas de esta aplicación de clasificación en particular). Y también es necesario especificar el área de captura correctamente (las coordenadas de las celdas superior izquierda e inferior derecha, serán los marcos los que se limitarán a ellas, ¿no copiar toda la hoja?)
Bueno, en la parte derecha encontrará la celda "Ordenar" (que actúa como un botón para iniciar el proceso, al elegir ordenar y generar una matriz, simplemente haga clic en ella).
Incluso al lado de este botón viven varios personajes especiales que se pueden usar en la visualización. Estas células no necesitan ser tocadas.
En la parte inferior, lo más importante es la elección del algoritmo. Solo necesita hacer clic en el nombre del tipo, después de lo cual la celda con él se volverá azul.
De los más de 80 algoritmos, aproximadamente la mitad de ellos están disponibles hoy. Hasta ahora, los no realizados tienen una apariencia pálida en comparación con los ya implementados. Todavía no he logrado hacer algo (y ni siquiera he comenzado la implementación). Algunos están en desarrollo. Algunos de ellos están escritos y probados y estarán disponibles muy pronto (en particular, casi todas las clasificaciones por insertos están listos para mí, sin embargo, los agregaré a la aplicación tan pronto como se publiquen los habrastats para estas clasificaciones en las próximas semanas y compartiré el AlgoLab.xlsm actualizado - y qué hacer, no quiero estropear nuevos episodios de mi serie).
Planeo modificar algunas de las clasificaciones ya implementadas. La visualización no me satisface en todas partes.
Pero en esta área, al elegir un algoritmo, se carga información de resumen sobre él. La información se toma de la hoja "Ordenar", se retrae automáticamente con una macro. Por cierto, si cambia el texto en esta área, también cambiará en la hoja original.
Ordenar, como puedes ver mucho. Para no confundirse en todo este esplendor, se dividen en clases, según el método fundamental de organización de datos que se utilice. ¿Qué son estas clases?
- Clasificación aleatoria Los elementos de la matriz se mezclan aleatoriamente y esto continúa hasta que la estructura se ordena de repente.
- Ordena intercambios. Se organiza una comparación total por pares (e intercambio) de elementos de matriz.
- Ordenar inserciones. Los elementos se seleccionan y cada uno se inserta en su lugar.
- Ordenar por elección. En la submatriz, se selecciona el elemento máximo, que se inserta al final de la submatriz. Luego, a la parte restante sin clasificar, se repite el mismo procedimiento.
- Combinar clasificaciones. Subarreglas ordenadas buscadas que se conectan entre sí.
- Ordenar por distribución. Los elementos se dividen en clases hasta que esto conduce al resultado deseado.
- Clasificación híbrida. Se combinan los métodos de intercambio, inserción, selección, fusión y distribución de algoritmos.
- Clasificación paralela. Algoritmos donde se proporciona el procesamiento paralelo de diferentes partes de la matriz.
- Clasificación de redes. La matriz se pasa a través de la red de clasificación; en la salida, se ordena.
- Otras clasificaciones. Pseudo algoritmos, clasificaciones cómicas y simplemente extravagantes.
En los próximos harastings, se resaltarán matices detallados para cada clase. Bueno, pasamos a la siguiente hoja.
Hoja de proceso
En realidad, al generar una matriz, elegir un algoritmo y hacer clic en el botón "Ordenar", la macro se lanza a esta hoja. Es aquí donde tiene lugar el misterio de la organización de datos.
Durante todo el proceso anterior, te acompañará esta maravillosa ventana:
Dado que el modo de visualización es paso a paso, para continuar con el siguiente paso, es necesario
presionar el botón "Nuevo paso" . No es muy conveniente hacer esto con el mouse, por lo que el foco de entrada de la ventana siempre está en este botón. Es decir, para continuar con los siguientes pasos, simplemente no necesita ser flojo para presionar el teclado Intro (no se requerirán otros gestos).
El botón "Finalizar" muestra el proceso desde una vista paso a paso. El algoritmo completará silenciosamente su trabajo y mostrará solo el resultado final. La etapa final de la clasificación no se verá.
El botón "Abortar" detiene completamente el trabajo de las macros en este paso.
El botón "Instantánea" le permite guardar una captura de pantalla de este paso en particular. Luego encontrará la imagen en la carpeta que se especifica en la configuración de la hoja de clasificación.
Ordenar hoja
Aquí se almacena una gran tabla con todo tipo de conocimiento sobre los tipos. Como recordará, la información se extrae de aquí al elegir la clasificación en la hoja de clasificación. Me arrepiento, aunque la calidad del llenado es regular, no hubo suficiente perseverancia para introducir minuciosamente la cantidad máxima de datos correctos. Espero ponerme al día en un futuro muy cercano.
Gráfico de hoja
En esta hoja puedes conocer mis fantasías sobre las fechas de los lanzamientos habrásticos más cercanos sobre los tipos.
Hablaré sobre algoritmos en este orden.
Intercambios → Inserciones → Selección → Fusionar → Distribución →
→ Híbridos → Paralelo → Red → Aleatorio
Las clases generales se enumeran, pero en general, se dedicarán a cada clase varias opciones que obedecen a un esquema tan general.
- Descripción de la clase de clasificación. Introducción, matices básicos inherentes a todas las clases, clases básicas. Típicamente, estos artículos introductorios contendrán información bastante conocida. Pero aún así, intentaré no aburrirme.
- Algunas clases de clase poco conocidas. Aquí te deleitaré con material nuevo, sobre el cual prácticamente no hay información en ruso. Y no encontrarás nada incluso en inglés. Los artículos separados no serán solo sobre la clasificación de intercambios, porque hace tiempo que no hay tiempo para una exclusiva interesante.
- Comparación práctica de clases entre ellos. Para cada grupo de algoritmos habrá un artículo final dedicado a probar clasificaciones en diferentes conjuntos de datos. ¡Aquí prometo muchos descubrimientos increíbles!
Comparación práctica de clasificación
Se planeó comparar solo la implementación python de algoritmos. Sin embargo, después de ver los primeros resultados en el ejemplo de clasificación de gnomos, llegué a la conclusión de que darán una idea errónea sobre la velocidad relativa.
Python tiene su propio sistema de acceso a la memoria de variables (especialmente si estas variables se asignan entre sí), razón por la cual los algoritmos optimizados pueden funcionar más lentamente.
Una situación similar con Shaker / Bubble. Contrariamente a lo esperado, la clasificación de burbujas funciona más rápido que la clasificación de agitadores (aunque Shaker Sort es una clasificación de burbujas mejorada).
Para el control, también probé las clasificaciones en PHP (principalmente trabajo en este lenguaje, por lo que una prueba alternativa fue más rápida y fácil de crear en él). Allí la situación ya es "normal": el "gnomo" optimizado en todos los conjuntos de datos funciona claramente más rápido de lo normal.
Sin embargo, PHP también tiene una reputación de ser "imperfecto" y una herramienta lenta, por lo que decidí que tampoco era adecuado para conclusiones globales. Para minimizar los posibles reproches [al elegir el lenguaje incorrecto para probar la velocidad real], decidí minimizar las pruebas principales también en Java. Sin embargo, me encontré con una escasez de mi conocimiento de este idioma. Por desgracia, no creció juntos.
Por lo tanto, las pruebas se realizarán de inmediato en
tres idiomas:
- Pitón En primer lugar, este lenguaje es más adecuado para describir el algoritmo. Como hay funciones correctas que funcionan, mediremos el tiempo para ellas. Pero los resultados serán algo dudosos.
- PHP Inicialmente, no iba a usar este lenguaje de ninguna manera en una serie de artículos. Pero dado que escribí un entorno para probar las clasificaciones y las implementaciones en este PL están disponibles, entonces ¿por qué no? Los resultados prácticos por los cuales se puede juzgar la efectividad relativa de los algoritmos son más adecuados en comparación con Python.
Java Se basa en los resultados en Java que sacaremos las principales conclusiones.
Por supuesto, se compartirán todas las opciones en todos los idiomas.
FAQ
Ya preveo algunas preguntas de la audiencia, responderé de inmediato.
¿Por qué se implementa el programa para visualizar algoritmos en Excel?
Entonces, en un momento fue más rápido y fácil (para mí). El espacio reticular de las hojas de cálculo resultó ser una solución llave en mano muy, muy conveniente para visualizar el trabajo con matrices.
Ok, echemos un vistazo a todos estos tipos. Que sigue
Basado en AlgoLab, haré visualizaciones para árboles, gráficos. El mantel de Ulam, la hormiga de Langton, eso es todo. Todavía hay espacios en blanco para 2048 (AI juega con el método minimax y Monte Carlo, debe terminarlo). Las obras son mucha tierra.
Referencias
Descargue AlgoLab desde una unidad de Google ( archivos AlgoLab (Excel 2007-2013) .xlsm y AlgoLab (Excel 97-2003) .xls ).Artículos de la serie