Le tri est un concept simple, mais puissant. À l'aide d'une liste non organisée d'éléments, vous pouvez utiliser un algorithme pour les trier dans un ordre particulier. Cette idée peut paraître simpliste, mais les opérations de tri sont très fréquentes en informatique sous diverses formes. L'une des applications les plus importantes est l'accélération de la recherche. Par exemple, votre ordinateur trie les fichiers par nom et par taille pour vous permettre de trouver rapidement celui dont vous avez besoin. L'UEFN vous permet de trier les objets dans l'organiseur par type pour regrouper les éléments et organiser votre projet. Dans Fortnite, les joueurs du tableau de scores sont classés selon de nombreuses statistiques, comme les éliminations et le temps au tour, pour que tout le monde sache qui est en tête.
Appliquer le tri au code Verse peut vous permettre d'améliorer votre jouabilité et certains aspects de votre développement. Par exemple, vous pourriez classer une matrice de joueurs en fonction de leur score dans un tournoi, en éliminant ceux ayant obtenu le moins de points à chaque manche. En triant cette matrice à la fin de chaque manche, vous pouvez rapidement trouver les joueurs ayant obtenu les scores les plus faibles et les définir comme spectateurs. D'autre part, vous pouvez tout aussi rapidement récupérer les joueurs ayant obtenu les meilleurs scores et leur attribuer un bonus pour la manche suivante. Vous pouvez même utiliser cette liste triée pour créer des classements locaux persistants, pour que les joueurs sachent quels adversaires surveiller pendant le jeu. Et si vous avez une liste de personnes que vous aimeriez mentionner sur votre île, vous pouvez trier leurs noms par ordre alphabétique pour les afficher facilement.
Dans chacun de ces exemples, le tri est utilisé de différentes manières, mais en réalité, ils utilisent tous un algorithme de tri pour atteindre leur objectif. Les algorithmes de tri implémentent la logique qui trie vos listes. Il existe de nombreux types différents à choisir en fonction de vos besoins. Le tri est certes un outil puissant, mais il est important de comprendre son fonctionnement si vous souhaitez l'intégrer à vos projets. Cette page couvre les principaux concepts relatifs au tri et décrit comment choisir l'algorithme qui fonctionne le mieux pour votre projet. Pour consulter les implémentations d'algorithmes de tri spécifiques, cliquez sur le lien disponible à la fin de cette page.
Merge Sort
Merge sort est un algorithme de tri de type diviser pour régner. Cela signifie qu'il divise le groupe d'éléments à trier en groupes plus petits avant de trier ces groupes plus petits. Il combine ensuite les petits groupes en tenant compte du fait qu'ils ont déjà fait l'objet d'un tri.
Implémenter Merge Sort
L'implémentation suivante s'appelle elle-même pour trier par fusion les matrices divisées. Il s'agit donc d'une fonction récursive. En présence d'une fonction récursive, vous devez spécifier un scénario de base pour éviter une récursivité infinie. Cet algorithme divisant les matrices en deux à chaque fois, le scénario de base consiste en une matrice d'un seul élément. La matrice est donc considérée comme triée pour commencer avec un élément et peut être fusionnée avec une autre matrice à élément unique et ainsi de suite, jusqu'à obtenir la matrice d'éléments complète.
L'implémentation suivante est générique en utilisant des types paramétriques pour ses paramètres. En d'autres termes, vous pouvez utiliser le type de votre choix pour les éléments et votre propre fonction de comparaison comme arguments. Vous pouvez donc disposer d'une matrice d'entiers que vous triez ou d'une matrice dont le type est plus complexe, comme une classe triable. La fonction Compare est un autre paramètre auquel vous pouvez transmettre vos propres fonctions personnalisées. Si vous voulez trier dans l'ordre croissant ou en fonction de certains champs d'une classe, vous pouvez le spécifier dans votre fonction personnalisée, sans modifier cette implémentation de fonction générique.
Pour implémenter le tri par fusion dans Verse, procédez comme suit :
-
Commencez par écrire le scénario de base : un seul élément dans la matrice. Si un élément maximum est présent, renvoyez l'argument Array transmis à la fonction.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Vérifiez que la matrice contient plusieurs éléments, sinon le scénario de base est atteint. else: # Renvoyez la matrice transmise, car nous avons atteint le scénario de base. Tableau -
Ensuite, divisez la matrice en deux.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Vérifiez que la matrice contient plusieurs éléments, sinon le scénario de base est atteint. Mid:int = Floor(Length / 2) # Obtenez l'index du milieu de la matrice. Left:[]t = Array.Slice[0, Mid] # Divisez la matrice en deux. Cela permet de conserver les éléments du début jusqu'à l'index Mid - 1. Right:[]t = Array.Slice[Mid] # Divisez la matrice en deux. Cela permet de conserver les éléments de l'index Mid jusqu'à la fin de la matrice. else: # Renvoyez la matrice transmise, car nous avons atteint le scénario de base. Tableau -
Appelez
MergeSortsur chaque moitié de la matrice initiale, puisMergepour fusionner les deux moitiés.MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Vérifiez que la matrice contient plusieurs éléments, sinon le scénario de base est atteint. Mid:int = Floor(Length / 2) # Obtenez l'index du milieu de la matrice. Left:[]t = Array.Slice[0, Mid] # Divisez la matrice en deux. Cela permet de conserver les éléments du début jusqu'à l'index Mid - 1. Right:[]t = Array.Slice[Mid] # Divisez la matrice en deux. Cela permet de conserver les éléments de l'index Mid jusqu'à la fin de la matrice. then: # Appelez MergeSort sur la partie gauche de la matrice. LeftSorted:[]t = MergeSort(Left, Compare) # Appelez MergeSort sur la partie droite de la matrice. RightSorted:[]t = MergeSort(Right, Compare) # Combinez les deux matrices et renvoyez le résultat. Merge(LeftSorted, RightSorted, Compare) else: # Renvoyez la matrice transmise, car nous avons atteint le scénario de base. Tableau -
Lors de la fusion des deux moitiés, comparez les éléments de chaque matrice et ajoutez-les à la matrice obtenue jusqu'à ce que tous les éléments des deux matrices aient été ajoutés. Pour ce faire, utilisez une variable d'index pour suivre les positions dans chaque matrice. Chaque fois que la fonction
Compareréussit, l'élément de la matrice de gauche doit être ajouté et sa variable d'index doit avancer vers la position suivante dans la matrice, sinon faites de même avec l'élément de la matrice de droite. Une fois que tous les éléments de l'une des matrices ont été ajoutés, ajoutez les éléments restants de l'autre matrice puisqu'elle a déjà été triée.# Une fonction d'aide pour MergeSort qui combine les matrices divisées dans un ordre basé sur la fonction Compare. Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= var LeftIndex:int = 0 var RightIndex:int = 0 var MergedArray:[]t = array{} # Parcourez en boucle tous les éléments des matrices pour les ajouter à la variable MergedArray. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Comparez l'élément contenu dans la matrice de gauche avec l'élément contenu dans la matrice de droite. # Utilisez la fonction Compare transmise en tant qu'argument if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # À ce stade, nous avons ajouté tous les éléments de l'une des matrices. # Vérifiez maintenant quelle matrice contient encore des éléments à fusionner et ajoutez tous les éléments restants. if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # Quittez la boucle, car nous avons fini d'ajouter tous les éléments. break # Renvoyez la matrice fusionnée. MergedArray
Script complet
# Un algorithme de tri qui divise une matrice en deux, trie chaque partie de la matrice divisée, puis les combine.
# Il s'agit d'une implémentation récursive, où la fonction s'appelle elle-même pour fusionner et trier les matrices divisées.
# Pour atteindre le scénario de base (la condition pour arrêter la récursivité), la matrice ne doit compter qu'un seul élément.
# Cette implémentation générique utilise des types paramétriques, vous pouvez donc fournir votre propre type et votre propre fonction de comparaison comme arguments.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
Length:int = Array.Length
if:
Length > 1 # Vérifiez que la matrice contient plusieurs éléments, sinon le scénario de base est atteint.
Mid:int = Floor(Length / 2) # Obtenez l'index du milieu de la matrice.
Left:[]t = Array.Slice[0, Mid] # Divisez la matrice en deux. Cela permet de conserver les éléments du début jusqu'à l'index Mid - 1.
Right:[]t = Array.Slice[Mid] # Divisez la matrice en deux. Cela permet de conserver les éléments de l'index Mid jusqu'à la fin de la matrice.
then:
# Appelez MergeSort sur la partie gauche de la matrice.
LeftSorted:[]t = MergeSort(Left, Compare)
# Appelez MergeSort sur la partie droite de la matrice.
RightSorted:[]t = MergeSort(Right, Compare)
# Combinez les deux matrices et renvoyez le résultat.
Merge(LeftSorted, RightSorted, Compare)
else:
# Renvoyez la matrice transmise, car nous avons atteint le scénario de base.
Tableau
# Une fonction d'aide pour MergeSort qui combine les matrices divisées dans un ordre basé sur la fonction Compare.
Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
var LeftIndex:int = 0
var RightIndex:int = 0
var MergedArray:[]t = array{}
# Parcourez en boucle tous les éléments des matrices pour les ajouter à la variable MergedArray.
loop:
if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
# Comparez l'élément contenu dans la matrice de gauche avec l'élément contenu dans la matrice de droite.
# Utilisez la fonction Compare transmise en tant qu'argument
if (Compare[LeftElement, RightElement]):
set MergedArray += array{LeftElement}
set LeftIndex += 1
else:
set MergedArray += array{RightElement}
set RightIndex += 1
else:
# À ce stade, nous avons ajouté tous les éléments de l'une des matrices.
# Vérifiez maintenant quelle matrice contient encore des éléments à fusionner et ajoutez tous les éléments restants.
if (LeftIndex >= Left.Length):
option{set MergedArray += Right.Slice[RightIndex]}
else:
option{set MergedArray += Left.Slice[LeftIndex]}
# Quittez la boucle, car nous avons fini d'ajouter tous les éléments.
break
# Renvoyez la matrice fusionnée.
MergedArray
Choisir un algorithme
De nombreux algorithmes de tri poursuivent des objectifs identiques, mais certains éléments les distinguent et peuvent avoir une incidence sur les performances de l'algorithme.
Complexité en temps
L'exécution des algorithmes prend du temps, et plus ils ont de tâches à réaliser, plus ils en utilisent. Un certain nombre de facteurs influencent la complexité du problème que l'algorithme tente de résoudre, et le temps nécessaire pour le traiter est appelé complexité en temps.
Étant donné qu'il est presque impossible de calculer le temps exact nécessaire à un algorithme en raison de divers facteurs, tels que le matériel de votre ordinateur, d'autres codes en cours d'exécution ou le type de données avec lesquelles vous travaillez, la complexité en temps est mesurée en termes d'opérations, soit le nombre d'actions qu'un algorithme doit effectuer pour s'arrêter. Chaque algorithme étant différent, le temps nécessaire au traitement d'un ensemble de données est représenté à l'aide de la comparaison asymptotique (dite "big O"). Celle-ci ne décrit pas le nombre exact d'opérations requises, mais plutôt comment ce nombre évolue à mesure que la taille de la liste que vous entrez dans l'algorithme augmente.
Par exemple, vous écrivez un algorithme pour trouver le plus petit nombre dans une liste. Vous ne savez pas si la liste est ordonnée, votre algorithme doit donc vérifier chaque nombre pour savoir s'il s'agit du plus petit. Si la liste contient trois éléments, l'algorithme effectue trois vérifications. Si elle en contient dix, l'algorithme effectue dix vérifications. Étant donné que le nombre d'opérations augmente de manière linéaire par rapport au nombre d'entrées de votre liste, la complexité en temps est linéaire, ou O(n), n correspondant au nombre d'éléments de votre liste. Si votre algorithme devait effectuer deux opérations par élément, par exemple copier chacun d'eux dans une liste différente après chaque vérification, la complexité en temps serait O(2n) puisque le nombre d'opérations est de 2 * NumberOfItems.
Et si votre algorithme voulait simplement vérifier si la liste contient des éléments ? Étant donné que votre algorithme n'effectue qu'une seule opération quelle que soit la taille de l'entrée, la complexité en temps serait constante, soit O(1). Il existe de nombreux autres exemples, tels que le temps quadratique (O(n^2)) ou le temps factoriel (O(n!)), mais ce qui importe, c'est que chacun d'eux décrit comment le nombre d'opérations effectuées augmente selon le nombre d'entrées.
Complexité du tri
Mesurer la complexité en temps des algorithmes de tri devient beaucoup plus compliqué en raison des différents états dans lesquels une liste peut se trouver avant son tri. Et si elle est déjà triée ? Et si elle est triée dans un ordre décroissant ou inverse ? Les performances d'un algorithme de tri peuvent varier considérablement en fonction de ces facteurs. Les algorithmes de tri sont donc généralement mesurés en fonction des complexités en temps des scénarios optimistes, pessimistes et moyens.
Prenons l'exemple de l'algorithme Bubble Sort. Dans le scénario optimiste, avec une liste déjà triée, l'algorithme Bubble Sort doit simplement vérifier chaque paire d'éléments, mais n'aura pas besoin de procéder à des échanges. Cela signifie que la complexité en temps dans le scénario optimiste sera O(n), ce qui est formidable. Mais qu'en est-il du scénario où la liste est triée dans l'ordre inverse ? Dans cette situation, l'algorithme Bubble Sort devra effectuer n _nombre de vérifications et échanger chaque élément de la liste _n fois, ce qui signifie que la complexité en temps du scénario pessimiste sera n * n ou O(n^2). Cela est considéré comme lent par rapport à d'autres algorithmes de tri et peut devenir très rapidement incontrôlable, car l'algorithme effectuerait au moins une centaine d'opérations pour traiter une liste de dix éléments. Alors, combien d'opérations pour une centaine d'éléments ? Et mille ?
Au lieu des scénarios optimistes et pessimistes, le fonctionnement des algorithmes de tri se situera généralement plus près de leur scénario moyen. Par exemple, la complexité du scénario moyen de l'algorithme Merge Sort est O(nlogn). Cela est considéré comme une performance convenable, car de nombreux autres algorithmes de tri courants présentent des complexités de scénarios optimistes, pessimistes et moyens à ce niveau ou très proches de celui-ci. L'algorithme Bubble Sort précédent a une complexité de cas moyen de O(n^2) il est donc toujours relativement lent, même dans le scénario moyen.
Connaître la complexité en temps est important lors du choix d'un algorithme, car vous souhaitez que votre code s'exécute rapidement et fonctionne de manière homogène, quel que soit le type d'entrée. Pour obtenir des exemples courants d'algorithmes de tri efficaces, consultez Merge Sort et Quicksort. Ces deux algorithmes présentent les mêmes complexités de scénarios optimistes, pessimistes et moyens qu'O(nlogn) et constituent un bon point de départ pour toute situation de tri.
Complexité en espace
Outre la complexité en temps, il convient également de prendre en compte la quantité d'éléments que votre algorithme doit créer pour terminer le tri. Il s'agit de la complexité en espace, soit la quantité de données supplémentaires créées à l'exécution de votre algorithme. Tout comme la complexité en temps, la complexité en espace est mesurée à l'aide de la comparaison asymptotique (ou "big O"), qui varie selon les algorithmes. Par exemple, l'algorithme Merge Sort divisant une liste en n sous-listes, sa complexité en espace est de O(n). Les algorithmes qui trient les objets sur place (ils modifient uniquement les données existantes, plutôt que d'en créer autres) ont une complexité en espace de O(1). Si vous travaillez avec des listes très volumineuses, la complexité en espace peut s'avérer un critère déterminant lors de la sélection de votre algorithme.
Verse étant un langage de programmation fonctionnel, les opérations de l'API de structure de données renvoient des versions modifiées de l'élément d'origine transmis en tant qu'entrée. Par exemple, les fonctions de matrice Insert() et RemoveElement() ne modifient pas la matrice d'origine, mais créent et renvoient une nouvelle matrice après l'exécution de la fonction. Cela peut mener à des exigences de complexité en temps et en espace plus élevées à prendre en compte lors de la création de ces nouveaux éléments.
Stabilité
Souvent, lors du tri, votre algorithme peut rencontrer des valeurs égales. Par exemple, deux joueurs ont chacun un score de cinq. Comment l'algorithme doit-il les trier ? Dans ce scénario, un algorithme stable préservera l'ordre dans lequel les éléments égaux apparaissent dans la liste après le tri. Ainsi, si avant de trier la liste, le joueur 1 apparaît avant le joueur 2, le joueur 1 apparaîtra également avant le joueur 2 dans la liste triée.
Cependant, un algorithme instable ne préservera pas cet ordre, le joueur 2 pourrait alors apparaître avant le joueur 1. Cela est important si votre code s'intéresse aux premiers éléments d'une liste, par exemple si vous souhaitez afficher les trois meilleurs joueurs selon leur score dans un classement. Dans ce cas, vous utiliserez un algorithme stable pour vous assurer que le classement indique qui a atteint ce score en premier.
Tester et profiler vos algorithmes
Même s'il est recommandé de connaître le comportement attendu de votre algorithme en tenant compte de la complexité en temps et en espace, il est encore plus important de mesurer ses performances réelles sur des entrées réelles. Développer des algorithmes de tri peut être complexe et il peut être difficile de déterminer si votre code fonctionne de manière cohérente pour toutes les entrées. C'est là que les tests entrent en jeu. En configurant une fonction de test, vous pouvez évaluer la précision de votre code et identifier son comportement à mesure que vous le développez. Vous pouvez également vérifier si les performances présentent une régression lorsque vous modifiez l'implémentation de ce que vous testez. Procédez comme suit afin de configurer un fichier de test pour vos algorithmes de tri et générer des données de sortie concernant leurs performances :
-
Créez une fonction faillible nommée
RunArrayTest.# Testez la fonction sur le tri de matrices et le profilage de code. RunArrayTest()<decides><transacts>:void= -
Ajoutez l'argument à la matrice sur laquelle vous voulez exécuter le tri et la fonction de comparaison à utiliser.
# Testez la fonction sur le tri de matrices et le profilage de code. RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Exécutez l'algorithme Merge Sort ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) -
Vous devez maintenant comparer la matrice triée avec le résultat attendu. Ajoutez l'argument de la matrice attendue à comparer avec la matrice réelle triée pour vérifier que le résultat est correct.
Comparez les éléments figurant dans
ResultArrayavec ceux figurant dansExpectedArray. La fonctionRunArrayTestest faillible, c'est-à-dire que dès qu'un élément ne correspond pas, la fonction de test échoue.# Testez la fonction sur le tri de matrices et le profilage de code. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Exécutez l'algorithme Merge Sort ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Vérifiez que le test a réussi et que la matrice est triée comme prévu. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Ajoutez une fonction d'argument pour afficher les matrices à chaque étape, afin de pouvoir les comparer si le test échoue et de déterminer comment corriger le code que vous testez.
# Testez la fonction sur le tri de matrices et le profilage de code. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Exécutez l'algorithme Merge Sort ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Affichez les matrices Actual, Expected et Result à des fins de résolution des problèmes. ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # Vérifiez que le test a réussi et que la matrice est triée comme prévu. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Votre fonction de test vérifie l'exactitude du résultat, mais votre test peut aussi vous fournir plus d'informations. L'expression de profil vous permet de mesurer les performances de vos algorithmes en enregistrant le temps nécessaire à l'exécution de l'algorithme.
Cela est utile pour comparer les performances de différents algorithmes de tri ou tester la manière dont vos algorithmes fonctionnent avec différentes entrées. Les algorithmes individuels peuvent fonctionner de manière très différente en fonction des scénarios optimistes et pessimistes, et le profilage vous permet de rechercher et de tester ces cas pour connaître les signes à surveiller. Utiliser plusieurs tests vous permet d'évaluer les performances moyennes de votre algorithme et d'estimer ses performances selon des nombres d'entrées très divers.
-
Ajoutez un argument de chaîne nommé
Descriptionqui explique l'objet du test. Vous pouvez l'ajouter à l'expressionprofilepour enregistrer la description avec la valeur chronométrée.# Testez la fonction sur le tri de matrices et le profilage de code. RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Exécutez l'algorithme Merge Sort et profilez le code. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Affichez les matrices Actual, Expected et Result à des fins de résolution des problèmes. ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # Vérifiez que le test a réussi et que la matrice est triée comme prévu. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected
Rédiger des cas de test
Commencez simplement. Isolez ce que vous testez. Testez une matrice de nombres entiers pour trier les valeurs dans l'ordre croissant.
-
Créez une fonction de comparaison pour les nombres entiers.
# Fonction de comparaison à utiliser comme argument pour trier les nombres entiers dans l'ordre croissant. IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right -
Créez une fonction d'aide pour convertir une matrice de nombres entiers en chaîne.
# Fonction d'aide pour convertir une matrice de nombres entiers en chaîne. IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" -
Créez un appareil Verse pour exécuter le test.
# Ce fichier contient des tests permettant de vérifier que l'algorithme de tri se comporte comme prévu. # Les tests incluent également le profilage du code pour afficher les performances de l'algorithme. using { /Fortnite.com/Devices } using { /UnrealEngine.com/Temporary/Diagnostics } using { /Verse.org/Simulation } using { /Verse.org/Random } my_log_channel<public> := class(log_channel): # "Logger" permettant d'afficher les messages provenant de fonctions de classes sans journal, pour tout le projet. # L'affichage sans logger est <no_rollback> et ne peut donc pas être utilisé dans une fonction <transacts>. ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # Un appareil du mode Créatif créé avec Verse qui peut être placé dans un niveau. # Placez-le dans le niveau pour exécuter des tests et profiler le code. test_sorting := class(creative_device): # S'exécute à l'activation de l'appareil dans une partie en cours. OnBegin<override>()<suspends>:void= # Exemples de matrices à utiliser pour le test. Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # Exécutez les tests et indiquez s'ils ont échoué ou réussi. if: RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("All tests passed.") else: ProjectLog("One or more tests failed.") -
À présent, entrez des valeurs dans les matrices de test.
var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): Compte Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray) -
Exécutez le test en déplaçant l'appareil Verse dans votre niveau.
Voici d'autres idées de tests à exécuter :
* Trier une matrice de nombres entiers dans l'ordre décroissant.
# Fonction de comparaison à utiliser comme argument pour trier les nombres entiers dans l'ordre décroissant.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
* Trier une matrice de nombres entiers contenant des valeurs répétitives.
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
* Trier une classe par l'un de ses champs.
# Un exemple de classe pour tester le tri.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Fonction de comparaison à utiliser comme argument pour trier les victoires dans l'ordre croissant.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
Vers la gauche
# Fonction d'aide pour convertir les valeurs de comparaison des statistiques de joueur en chaîne.
PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element.Wins}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
Script complet
# Ce fichier contient des tests permettant de vérifier que l'algorithme de tri se comporte comme prévu.
# Les tests incluent également le profilage du code pour afficher les performances de l'algorithme.
using { /Fortnite.com/Devices }
using { /UnrealEngine.com/Temporary/Diagnostics }
using { /Verse.org/Simulation }
using { /Verse.org/Random }
my_log_channel<public> := class(log_channel):
# "Logger" permettant d'afficher les messages provenant de fonctions de classes sans journal, pour tout le projet.
# L'affichage sans logger est <no_rollback> et ne peut donc pas être utilisé dans une fonction <transacts>.
ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
Logger := log{Channel := my_log_channel}
Logger.Print(Message, ?Level := Level)
# Un appareil du mode Créatif créé avec Verse qui peut être placé dans un niveau.
# Placez-le dans le niveau pour exécuter des tests et profiler le code.
test_sorting := class(creative_device):
# S'exécute à l'activation de l'appareil dans une partie en cours.
OnBegin<override>()<suspends>:void=
# Exemples de matrices à utiliser pour le test.
var ArrayLength:int = GetRandomInt(10, 100)
Test1ExpectedIntArray:[]int =
for (Count := 0..ArrayLength):
Compte
Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)
set ArrayLength = GetRandomInt(10, 100)
Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
ArrayLength - Count
Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
set ArrayLength = GetRandomInt(10, 100)
Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
player_stats:
Wins := ArrayLength - Count
RoundsPlayed := GetRandomInt(Count, Count * 30)
Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)
# Exécutez les tests et indiquez s'ils ont échoué ou réussi.
if:
RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Integer array in order from largest to smallest", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
RunArrayTest["Integer array in order from smallest to largest with repeats", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Player stats array in order from largest # wins to smallest", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
then:
ProjectLog("All tests passed.")
else:
ProjectLog("One or more tests failed.")
# Testez la fonction sur le tri de matrices et le profilage de code.
RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
# Exécutez l'algorithme Merge Sort et profilez le code.
ResultArray := profile(Description):
SortingAlgorithms.MergeSort(ActualArray, Compare)
# Affichez les matrices Actual, Expected et Result à des fins de résolution des problèmes.
ProjectLog("Actual: {ArrayToString(ActualArray)}")
ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
ProjectLog("Result: {ArrayToString(ResultArray)}")
# Vérifiez que le test a réussi et que la matrice est triée comme prévu.
for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
Result = Expected
# Fonction d'aide pour convertir une matrice de nombres entiers en chaîne.
IntArrayToString(Array:[]int)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Fonction d'aide pour convertir les valeurs de comparaison des statistiques de joueur en chaîne.
PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element.Wins}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Fonction de comparaison à utiliser comme argument pour trier les nombres entiers dans l'ordre croissant.
IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
Left < Right
# Fonction de comparaison à utiliser comme argument pour trier les nombres entiers dans l'ordre décroissant.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
# Un exemple de classe pour tester le tri.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Fonction de comparaison à utiliser comme argument pour trier les victoires dans l'ordre croissant.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
Vers la gauche
# Fonction de comparaison à utiliser comme argument pour trier les victoires dans l'ordre décroissant.
IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins > Right.Wins
Vers la gauche
À vous de jouer
-
Implémenter un algorithme de tri différent. Les implémentations d'algorithmes suivantes sont également disponibles :
-
Ajouter d'autres cas de test pour augmenter la couverture du testeur. Avez-vous des idées de cas extrêmes que le testeur ne couvre actuellement pas ? Ou des types de données plus complexes ?