Téléchargez AlgoLab à partir d'un lecteur Google ( fichiers AlgoLab (Excel 2007-2013) .xlsm et AlgoLab (Excel 97-2003) .xls ).Ce dont les bolcheviks parlent depuis si longtemps et ce que je poursuis depuis plusieurs années à un rythme différent est finalement arrivé. Il y a quelques années, il a écrit une petite macro pour créer une animation gif algorithmique pour la habrastaty. Au fil du temps, mon humble instrument a atteint une taille impressionnante, ce qui n'est plus une honte à révéler au monde.
Alors rencontrez.
AlgoLab est une application Excel (c'est-à-dire un fichier Excel avec des macros) dans laquelle vous pouvez vous familiariser étape par étape avec les algorithmes de tri. Et il y a aussi la possibilité de préparer une animation gif.
Exemples d'animation généréeTri des arbres binaires
Tri des spaghettis
Tri de sommeil
Seulement 4 feuilles - 2 principales et 2 donc, informatives. Les voici:
Cliquer sur une image ouvrira une image en taille réelle- Feuille de tri. Sur cette feuille, vous pouvez rapidement former un tableau et sélectionner un algorithme de tri.
- Processus de feuille. Ici, nous observons étape par étape comment fonctionne tel ou tel algorithme.
- Feuille de tri. Voici un résumé des algorithmes.
- Graphique de feuille. Il existe également un calendrier de publication prévu pour les articles sur le tri.
Découvrons ces fiches plus en détail.
Feuille de tri
La partie supérieure de la feuille est consacrée à la génération d'un tableau non trié (afin qu'il y ait de quoi alimenter l'algorithme), ainsi qu'à l'enregistrement de la visualisation sous forme d'images sur votre ordinateur:
Sur la toute première ligne se trouve le tableau lui-même. Si nécessaire, vous pouvez modifier manuellement les valeurs de chaque élément:
En haut à gauche, vous devez spécifier les principales caractéristiques du tableau généré:
La taille, si les valeurs du tableau doivent être non répétitives (0 - non, 1 - oui), qui correspondent aux éléments minimum et maximum du tableau. Les macros VBA incluent une résistance au vandalisme aux données d'entrée, vous pouvez donc entrer des valeurs incorrectes. Dans ce cas, l'application déterminera à quoi doit correspondre telle ou telle caractéristique.
Et aussi une option pour déterminer s'il est nécessaire d'exécuter l'algorithme étape par étape (= 1) ou s'il est possible d'appliquer un tri à la structure et d'afficher uniquement le résultat final (= 0). Bien sûr, l'application Excel elle-même a été créée pour observer l'ensemble du processus en mode étape par étape, de sorte que la valeur ici est généralement égale à un. Mais parfois, lors des tests, j'annule cette option pour simplement vérifier si le nouvel algorithme que j'ajoute à AlgoLab.xlsm fonctionne (c'est-à-dire que je dois d'abord voir si le tableau trié est le résultat final, sans perdre de temps à visualiser la visualisation )
Un peu à droite se trouve la zone dans laquelle vous pouvez spécifier la manière dont les éléments du tableau non trié généré ne sont pas triés.
Générer un tableau mélangé au hasard? Ou peut-être organiser les éléments par ordre décroissant? Ou rendre le tableau presque trié (et spécifier également le coefficient de tri presque)?
Pour sélectionner l'une de ces méthodes, il vous suffit de cliquer sur la cellule contenant l'élément. En conséquence, le tableau est régénéré dans la première ligne. La cellule sélectionnée devient bleue.
À gauche se trouve le territoire qui sera nécessaire si vous avez besoin non seulement d'admirer la visualisation, mais également d'enregistrer l'ensemble du processus image par image sous forme d'images.
Tout d'abord, vous devez spécifier si vous souhaitez exporter les étapes de tri en général vers les images (= 0, sinon, = 1 si oui, et cette option est «ponctuelle», c'est-à-dire qu'elle est réinitialisée à zéro une fois le tri terminé). Deuxièmement, vous devez spécifier le format d'image (seulement 4 options sont possibles: GIF, JPG, PNG et BMP. La dernière option donne le résultat de la plus haute qualité, donc je le recommande). Troisièmement, vous devez spécifier le chemin d'accès au dossier où enregistrer les images (cliquez sur cette cellule et une boîte de dialogue s'ouvrira pour sélectionner un répertoire). Vient ensuite la cellule que la macro elle-même remplit - l'identifiant de session (nécessaire pour le nom unique du sous-dossier pour enregistrer les trames de cette application de tri particulière). Et il faut aussi spécifier correctement la zone de capture (coordonnées des cellules en haut à gauche et en bas à droite, ce seront les cadres qui se limiteront à elles - ne pas copier toute la feuille?)
Eh bien, dans la partie la plus à droite, vous trouverez la cellule "Trier" (qui agit comme un bouton pour démarrer le processus, lorsque vous choisissez le tri et la génération d'un tableau, cliquez simplement dessus).
Même à côté de ce bouton vivent divers caractères spéciaux qui peuvent être utilisés dans la visualisation. Ces cellules n'ont pas besoin d'être touchées.
En bas, la chose la plus importante est le choix de l'algorithme. Il vous suffit de cliquer sur le nom du tri, après quoi la cellule avec elle deviendra bleue.
Sur plus de 80 algorithmes, environ la moitié d'entre eux sont disponibles aujourd'hui. Jusqu'à présent, ceux non réalisés ont une apparence pâle par rapport à ceux déjà mis en œuvre. Je n'ai toujours pas réussi à en faire (et je n'ai même pas commencé l'implémentation). Certains sont en cours de développement. Certains d'entre eux sont écrits et testés et seront disponibles très bientôt (en particulier, presque tous les tri par encarts sont prêts pour moi, cependant, je les ajouterai à l'application dès que des habrastats seront publiés pour ces tri dans les semaines à venir et partagerai le AlgoLab.xlsm mis à jour - et que faire, je ne veux pas gâcher de nouveaux épisodes de ma série).
Je prévois de modifier certains des tri déjà mis en œuvre. La visualisation ne me satisfait pas partout.
Mais dans ce domaine, lors du choix d'un algorithme, des informations récapitulatives le concernant sont chargées. Les informations sont extraites de la feuille "Tri", elles sont automatiquement rétractées avec une macro. Soit dit en passant, si vous modifiez le texte dans cette zone, alors sur la feuille d'origine, il changera également.
Triez, comme vous pouvez le voir. Afin de ne pas se confondre dans toute cette splendeur, ils sont divisés en classes, selon la méthode fondamentale d'organisation des données utilisée. Quelles sont ces classes?
- Tri aléatoire. Les éléments du tableau sont mélangés au hasard et cela continue jusqu'à ce que la structure soit soudainement ordonnée.
- Trie les échanges. Une comparaison (et un échange) total par paire des éléments du tableau est organisée.
- Trier les insertions. Les éléments sont sélectionnés et chacun est inséré à sa place.
- Trier par choix. Dans le sous-tableau, l'élément maximum est sélectionné, qui est inséré à la fin du sous-tableau. Ensuite, pour la partie non triée restante, la même procédure est répétée.
- Fusionner les tris. Sous-réseaux ordonnés recherchés qui se connectent les uns aux autres.
- Trier par distribution. Les éléments sont divisés en classes jusqu'à ce que cela conduise au résultat souhaité.
- Tri hybride. Les méthodes d'échange, d'insertion, de sélection, de fusion et de distribution sont combinées.
- Tri parallèle. Algorithmes dans lesquels un traitement parallèle de différentes parties du réseau est fourni.
- Réseaux de tri. Le tableau est transmis via le réseau de tri; en sortie, il est ordonné.
- Autres tri. Pseudo-algorithmes, tri comiques et simplement extravagants.
Dans les harastings à venir, des nuances détaillées pour chaque classe seront mises en évidence. Eh bien, nous passons à la feuille suivante.
Fiche de processus
En fait, lors de la génération d'un tableau, en choisissant un algorithme et en cliquant sur le bouton "Trier", la macro renvoie à cette feuille. C'est ici que se déroule le mystère de l'organisation des données.
Pendant tout le processus ci-dessus, vous serez accompagné de cette merveilleuse fenêtre:
Étant donné que le mode d'affichage est pas à pas, pour passer à l'étape suivante, il est nécessaire d'y
appuyer sur le bouton «Nouvelle étape» . Ce n'est pas très pratique de le faire avec la souris, donc le focus de la fenêtre est toujours sur ce bouton. Autrement dit, pour passer aux étapes suivantes, il vous suffit de ne pas être paresseux pour appuyer sur Entrée clavier (aucun autre geste ne sera nécessaire).
Le bouton «Terminer» affiche le processus à partir d'une vue étape par étape. L'algorithme terminera son travail en silence et n'affichera que le résultat final. Vous ne verrez pas la dernière étape de l'opération de tri.
Le bouton "Abandonner" arrête complètement le travail des macros à cette étape.
Le bouton «Instantané» vous permet d'enregistrer une capture d'écran de cette étape particulière. Vous trouverez ensuite l'image dans le dossier spécifié dans les paramètres de la feuille de tri.
Feuille de tri
Un immense tableau contenant toutes sortes de connaissances sur les tris est stocké ici. Comme vous vous en souvenez, les informations sont extraites d'ici lors du choix du tri sur la feuille de tri. Je me repens, bien que la qualité du remplissage soit médiocre, il n'y avait pas assez de persévérance pour introduire minutieusement le maximum de données correctes. J'espère rattraper son retard dans un avenir très proche.
Graphique de feuille
Sur cette feuille, vous pouvez vous familiariser avec mes fantasmes sur les dates des sorties habrastatiques les plus proches sur les sortes.
Je vais parler des algorithmes dans cet ordre.
Échanges → Insertions → Sélection → Fusionner → Distribution →
→ Hybrides → Parallèle → Réseau → Aléatoire
Les classes générales sont répertoriées, mais en général, plusieurs opus obéissant à un tel schéma général seront consacrés à chaque classe.
- Description de la classe de tri. Introduction, nuances de base inhérentes à tous les types de classe, types de classe de base. En règle générale, ces articles d'introduction contiennent des informations assez connues. Mais quand même, j'essaierai de ne pas m'ennuyer.
- Quelques sortes de classes peu connues. Ici, je vous ravirai avec du nouveau matériel, sur lequel il n'y a pratiquement aucune information en russe. Et vous ne trouverez rien, même en anglais. Les articles séparés ne porteront pas uniquement sur le tri des échanges, car il n'y a pas longtemps de temps pour une exclusivité intéressante.
- Comparaison pratique des classes entre elles. Pour chaque groupe d'algorithmes, un article final sera consacré au test des tri sur différents ensembles de données. Ici, je vous promets beaucoup de découvertes incroyables!
Comparaison de tri pratique
Il était prévu de comparer uniquement l'implémentation d'algorithmes en python. Cependant, après avoir vu les premiers résultats sur l'exemple du tri des gnomes, je suis arrivé à la conclusion qu'ils donneraient une idée fausse de la vitesse relative.
Python a son propre système d'accès à la mémoire des variables (surtout si ces variables sont affectées les unes aux autres), c'est pourquoi les algorithmes optimisés peuvent fonctionner plus lentement.
Une situation similaire avec Shaker / Bubble. Contrairement aux attentes, le tri par bulles fonctionne plus rapidement que le tri par shaker (bien que le tri par shaker soit un tri par bulles amélioré).
Pour le contrôle, j'ai également testé les triages en PHP (je travaille principalement dans ce langage, donc un test alternatif était plus rapide et plus facile à créer dessus). Là, la situation est déjà «normale» - le «gnome» optimisé sur tous les ensembles de données fonctionne clairement plus rapidement que la normale.
Cependant, PHP a également la réputation d'être "imparfait" et un outil lent, j'ai donc décidé qu'il n'était pas non plus adapté aux conclusions globales. Pour minimiser les reproches possibles [en choisissant le mauvais langage pour tester la vitesse réelle], j'ai décidé de minimiser les principaux tests également en Java. Cependant, j'ai rencontré une pénurie de connaissances pour cette langue. Hélas, il n'a pas grandi ensemble.
Ainsi, les tests seront immédiatement en
trois langues:
- Python Tout d'abord, ce langage est le plus approprié pour décrire l'algorithme. Puisqu'il existe des fonctions correctes, nous mesurerons leur temps. Mais les résultats seront quelque peu douteux.
- PHP Au départ, je n'allais en aucun cas utiliser ce langage dans une série d'articles. Mais puisque j'ai écrit un environnement dessus pour tester les tris et les implémentations elles-mêmes sur ce PL sont disponibles, alors pourquoi pas. Les résultats pratiques par lesquels on peut juger de l'efficacité relative des algorithmes sont plus adéquats par rapport à Python.
Java C'est à partir des résultats en Java que nous tirerons les principales conclusions.
Bien sûr, toutes les options dans toutes les langues seront partagées.
FAQ
Je prévois déjà quelques questions du public, j'y répondrai tout de suite.
Pourquoi le programme de visualisation des algorithmes est-il implémenté dans Excel?
Donc, à un moment donné, c'était plus rapide et plus facile (pour moi). L'espace en treillis des feuilles de calcul s'est avéré être une solution clé en main très, très pratique pour visualiser le travail avec les tableaux.
Ok, jetons un œil à toutes ces sortes. Et ensuite?
Basé sur AlgoLab, je ferai des visualisations pour les arbres, les graphiques. La nappe d'Ulam, la fourmi de Langton, c'est tout. Il y a encore des blancs pour 2048 (l'IA joue en utilisant la méthode minimax et Monte Carlo - vous devez la terminer). Les travaux sont beaucoup de terres.
Les références
Téléchargez AlgoLab à partir d'un lecteur Google ( fichiers AlgoLab (Excel 2007-2013) .xlsm et AlgoLab (Excel 97-2003) .xls ).Articles de la série