L'ordinamento è un concetto semplice ma potente. Partendo da un elenco non organizzato di oggetti, puoi utilizzare un algoritmo per ordinarli come desideri. Sebbene questa idea possa sembrare basica, l'ordinamento appare in tanti aspetti e forme diverse in informatica. Una delle applicazioni più importanti è l'accelerazione della ricerca. Per esempio, il tuo computer ordina i file per nome e dimensione in modo che tu possa trovare rapidamente quello di cui hai bisogno. UEFN ti permette di ordinare gli oggetti nell'Outliner per Tipo per raggrupparli e organizzare i tuoi progetti. In Fortnite, i giocatori nella classifica del gioco vengono ordinati in base a molte statistiche diverse come le eliminazioni e il tempo sul giro in modo che chiunque sappia chi è al comando.
Applicare l'ordinamento al codice Verse ti può aiutare a far salire di livello il tuo gameplay e migliorare vari aspetti del tuo sviluppo. Per esempio, che ne pensi di ordinare un array di giocatori in base al loro punteggio in un torneo, eliminando in ogni round il giocatore con il punteggio più basso? Ordinando questo array alla fine di ogni round, puoi trovare rapidamente chi ha ottenuto i punteggi più bassi e impostarli come spettatori. Oppure puoi altrettanto rapidamente ottenere i giocatori con i punteggi migliori e assegnare loro dei bonus per il round successivo. Puoi utilizzare questo elenco ordinato anche per creare classifiche locali persistenti per sapere a chi fare attenzione durante la partita. Se hai un elenco delle persone che vuoi mettere in evidenza nella tua isola, puoi ordinare alfabeticamente i loro nomi per visualizzarli facilmente.
Ognuno di questi esempi utilizza l'ordinamento in un modo diverso, ma alla base utilizzano tutti un algoritmo di ordinamento per raggiungere l'obiettivo. L'algoritmo di ordinamento realizza la logica che ordina i tuoi elenchi e ci sono molti tipi diversi tra cui scegliere in base alle tue esigenze. Sebbene l'ordinamento sia uno strumento potente, è importante comprendere come funziona se vuoi integrarlo nei tuoi progetti. In questa pagina imparerai le idee principali alla base dell'ordinamento e come scegliere l'algoritmo più adatto per i tuoi progetti. Per la realizzazione di determinati algoritmi di ordinamento, dai un'occhiata alla fine di questa pagina.
Ordinamento per fusione
L'ordinamento per fusione è un algoritmo di ordinamento per suddivisione. Significa che suddivide il gruppo di elementi che devono essere ordinati in gruppi più piccoli e poi ordina i gruppi più piccoli. Poi combina i gruppi più piccoli insieme, sapendo che sono già ordinati.
Applicazione dell'ordinamento per fusione
La seguente applicazione richiama se stessa per eseguire l'ordinamento per fusione sugli array divisi, quindi è una funzione ricorsiva. Quando hai un funzione ricorsiva, devi indicare un caso di base per impedire una ricorsione infinita. Dato che questo algoritmo suddivide gli array a metà ogni volta, il caso di base è l'array che ha solo un elemento, quindi l'array è considerato ordinato iniziando con un elemento e può essere unito a un altro array con un solo elemento e così via fino all'intero array.
La seguente applicazione è generica utilizzando tipi parametrici per i suoi parametri. Significa che puoi utilizzare qualsiasi tipo per gli elementi e la tua funzione di confronto come argomenti. Puoi quindi avere un array di interi che ordini o un array di un tipo più complesso come una classe che puoi ordinare. La funzione Compare è un altro parametro a cui puoi passare le tue funzioni personalizzate. Se vuoi eseguire un ordinamento dal più piccolo al più grande o in base a determinati campi di una classe, puoi indicarlo nella tua funzione personalizzata senza modificare questa applicazione generica della funzione.
Segui questa procedura per applicare l'ordinamento per fusione in Verse:
-
Iniziamo scrivendo il caso di base: solo un elemento nell'array. Se ci sono uno o meno elementi, restituisce l'argomento dell'array che è stato passato alla funzione.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Verifica che ci sia più di un elemento nell'array, in caso contrario è stato raggiunto il caso di base. else: # Restituisce l'array passato perché è stato raggiunto il caso di base. Array -
Poi divide l'array a metà.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Verifica che ci sia più di un elemento nell'array, in caso contrario è stato raggiunto il caso di base. Mid:int = Floor(Length / 2) # Fornisce l'indice centrale dell'array. Left:[]t = Array.Slice[0, Mid] # Divide a metà l'array. Mantiene gli elementi dall'inizio all'indice Mid - 1. Right:[]t = Array.Slice[Mid] # Divide a metà l'array. Mantiene gli elementi dall'indice Mid alla fine dell'array. else: # Restituisce l'array passato perché è stato raggiunto il caso di base. Array -
Chiama
MergeSortsu ogni metà dell'array iniziale e poiMergele due metà.MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Verifica che ci sia più di un elemento nell'array, in caso contrario è stato raggiunto il caso di base. Mid:int = Floor(Length / 2) # Fornisce l'indice centrale dell'array. Left:[]t = Array.Slice[0, Mid] # Divide a metà l'array. Mantiene gli elementi dall'inizio all'indice Mid - 1. Right:[]t = Array.Slice[Mid] # Divide a metà l'array. Mantiene gli elementi dall'indice Mid alla fine dell'array. then: # Chiama MergeSort nella metà sinistra dell'array. LeftSorted:[]t = MergeSort(Left, Compare) # Chiama MergeSort nella metà destra dell'array. RightSorted:[]t = MergeSort(Right, Compare) # Combina i due array e restituisce il risultato. Merge(LeftSorted, RightSorted, Compare) else: # Restituisce l'array passato perché è stato raggiunto il caso di base. Array -
Unendo le due metà, confronta gli elementi di ogni array e aggiungili all'array risultante fino a quando tutti gli elementi da entrambi gli array non sono stati aggiunti. Per farlo, utilizza una variabile di indice per tenere sotto controllo le posizioni in ogni array. Ogni volta che la funzione
Compareriesce, l'elemento di sinistra dell'array deve essere aggiunto e la sua variabile dell'indice deve passare alla posizione successiva dell'array; in caso contrario, esegui queste operazioni sull'elemento di destra dell'array. Una volta aggiunti tutti gli elementi da uno degli array, aggiungi gli elementi rimanenti dall'altro array, dato che è già ordinato.# Funzione di supporto per MergeSort che combina gli array divisi in un ordine in base alla funzione Compare. Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:type)<transacts>:[]t= var LeftIndex:int = 0 var RightIndex:int = 0 var MergedArray:[]t = array{} # Esegui il loop con tutti gli elementi nell'array per aggiungerli alla variabile MergedArray. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Verifica che l'elemento nella metà sinistra dell'array con l'elemento nella metà destra dell'array. # Utilizza la funzione Compare passata come argomento if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # A questo punto, abbiamo aggiunto tutti gli elementi da uno degli array. # Ora controlla quale array ha ancora elementi da unire e aggiungi tutti gli elementi rimanenti. if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # Esci dal loop perché abbiamo finito di aggiungere tutti gli elementi. break # Restituisce l'array unito. MergedArray
Script completo
# Un algoritmo di ordinamento per suddivisione che separa un array in due parti, le ordina e quindi le combina fra loro.
# Un'applicazione ricorsiva in cui la funzione richiama se stessa per eseguire l'ordinamento per fusione sugli array divisi.
# Il caso di base (la condizione per interrompere la ricorsione) è l'array con un solo elemento.
# Questa è un'applicazione generica che utilizza tipi parametrici, quindi puoi fornire il tuo tipo e la tua funzione di confronto come argomenti.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:type)<transacts>:[]t=
Length:int = Array.Length
if:
Length > 1 # Verifica che ci sia più di un elemento nell'array, in caso contrario è stato raggiunto il caso di base.
Mid:int = Floor(Length / 2) # Fornisce l'indice centrale dell'array.
Left:[]t = Array.Slice[0, Mid] # Divide a metà l'array. Mantiene gli elementi dall'inizio all'indice Mid - 1.
Right:[]t = Array.Slice[Mid] # Divide a metà l'array. Mantiene gli elementi dall'indice Mid alla fine dell'array.
then:
# Chiama MergeSort nella metà sinistra dell'array.
LeftSorted:[]t = MergeSort(Left, Compare)
# Chiama MergeSort nella metà destra dell'array.
RightSorted:[]t = MergeSort(Right, Compare)
# Combina i due array e restituisce il risultato.
Merge(LeftSorted, RightSorted, Compare)
else:
# Restituisce l'array passato perché è stato raggiunto il caso di base.
Array
# Funzione di supporto per MergeSort che combina gli array divisi in un ordine in base alla funzione Compare.
Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:type)<transacts>:[]t=
var LeftIndex:int = 0
var RightIndex:int = 0
var MergedArray:[]t = array{}
# Esegui il loop con tutti gli elementi nell'array per aggiungerli alla variabile MergedArray.
loop:
if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
# Verifica che l'elemento nella metà sinistra dell'array con l'elemento nella metà destra dell'array.
# Utilizza la funzione Compare passata come argomento
if (Compare[LeftElement, RightElement]):
set MergedArray += array{LeftElement}
set LeftIndex += 1
else:
set MergedArray += array{RightElement}
set RightIndex += 1
else:
# A questo punto, abbiamo aggiunto tutti gli elementi da uno degli array.
# Ora controlla quale array ha ancora elementi da unire e aggiungi tutti gli elementi rimanenti.
if (LeftIndex >= Left.Length):
option{set MergedArray += Right.Slice[RightIndex]}
else:
option{set MergedArray += Left.Slice[LeftIndex]}
# Esci dal loop perché abbiamo finito di aggiungere tutti gli elementi.
break
# Restituisce l'array unito.
MergedArray
Scelta di un algoritmo
Sebbene molti algoritmi di ordinamento seguano idee simili, ci sono alcuni aspetti che li distinguono che possono avere un grande impatto sulle prestazioni dell'algoritmo.
Complessità temporale
Gli algoritmi richiedono tempo; più operazioni devono svolgere, più tempo richiedono. La complessità del problema che l'algoritmo tenta di risolvere è influenzata da diversi fattori e la quantità di tempo necessario per gestirli è chiamata complessità temporale.
Dato che calcolare il tempo esatto necessario a un algoritmo per terminare è quasi impossibile a causa di vari aspetti tra cui hardware del tuo computer, altri codici in esecuzione e tipo di dati che utilizzi, la complessità temporale è invece misurata in operazioni o il numero di azioni che un algoritmo deve eseguire per terminare. Dato che ogni algoritmo è diverso, il tempo necessario per elaborare un insieme di dati è rappresentato utilizzando la notazione big O. La notazione Big O non descrive il numero esatto di operazioni necessarie, descrive invece come cambia il numero con la dimensione dell'elenco che viene inserito nell'algoritmo.
Per esempio, immaginiamo un algoritmo per trovare il numero più piccolo di un elenco. Non sappiamo se l'elenco è ordinato, quindi l'algoritmo deve confrontare ogni numero per determinare se è il più piccolo. Se ci sono tre oggetti nell'elenco, l'algoritmo esegui tre controlli; se ci sono dieci oggetti, l'algoritmo esegue dieci controlli. Dato che il numero di operazioni aumenta linearmente con le dimensioni dell'ingresso dell'elenco, la complessità temporale è lineare o O(n), dove n è il numero di oggetti nell'elenco. Se l'algoritmo deve eseguire due operazioni per oggetto, come copiare ogni oggetto in un elenco diverso dopo ogni controllo, la complessità temporale è O(2n) dato che il numero di operazioni è 2 * NumberOfItems.
E se l'algoritmo volesse semplicemente controllare se sono presenti oggetti nell'elenco? Dato che l'algoritmo esegue solo una operazione indipendentemente dalle dimensioni dell'input, la complessità temporale è costante o O(1). Ci sono molti altri esempi, come il tempo quadratico (O(n^2)) o il tempo fattoriale (O(n!)), ma ciò che conta è che ognuno di essi descrive il modo in cui cresce il numero di operazioni al crescere delle dimensioni dell'input.
Complessità nell'ordinamento
Misurare la complessità temporale per gli algoritmi di ordinamento diventa molto più complicato per i diversi stati in cui potrebbe trovarsi un elenco prima dell'ordinamento. E se fosse già ordinato? E se fosse ordinato al contrario? Le prestazioni di un algoritmo di ordinamento possono variare notevolmente in base a questi fattori, quindi gli algoritmi di ordinamento sono di solito misurati in base alla complessità temporale dei casi migliore, peggiore e medio.
Per esempio, vediamo l'algoritmo di ordinamento a bolla. Nel caso migliore, dato un elenco già ordinato, l'ordinamento a bolla ha solo bisogno di controllare ogni coppia di elementi, senza aver bisogno di eseguire scambi! Significa che la complessità temporale del caso migliore è O(n), che è ottimo! Tuttavia, come funzionerebbe nello scenario opposti, nel quale l'elenco è ordinato al contrario? In questa situazione, l'ordinamento a bolla deve eseguire n controlli e scambiare ogni elemento nell'elenco n volte; significa che la complessità temporale del caso peggiore è n * n oppure O(n^2). Questo caso è considerato lento rispetto ad altri algoritmi di ordinamento e può sfuggire di mano molto rapidamente perché l'algoritmo richiede almeno un centinaio di operazioni per elaborare un elenco di dieci elementi. Puoi immaginare quante operazioni richiederebbero cento elementi? E mille?
Invece del caso migliore e del caso peggiore, gli algoritmi di ordinamento hanno di solito prestazioni più vicine al caso medio. Per esempio, la complessità del caso medio dell'ordinamento per fusione è O(nlogn). Questo è considerato un valido riferimento perché molti altri algoritmi comuni di ordinamento hanno complessità di caso migliore, peggiore e medio a questo livello o molto simile. L'ordinamento a bolla ha una complessità di caso medio di O(n^2), anche in caso medio, è relativamente lento.
Conoscere la complessità temporale è importante quando si deve scegliere un algoritmo, dato che si vuole che il codice venga eseguito rapidamente e abbia prestazioni simili, indipendentemente dal tipo di input. Alcuni esempi di algoritmi di ordinamento efficienti sono ordinamento per fusione e ordinamento rapido. Entrambi questi algoritmi hanno le stesse complessità di caso migliore, peggiore e medio di O(nlogn) e sono un valido punto di partenza per qualsiasi situazione di ordinamento.
Complessità spaziale
In aggiunta alla complessità temporale, è anche importante tenere in considerazione quanti dati l'algoritmo deve creare per terminare l'ordinamento. Questa è la complessità spaziale o la quantità di dati addizionali creati durante l'esecuzione dell'algoritmo. Come la complessità temporale, anche la complessità spaziale è misurata con la notazione Big O che varia da un algoritmo all'altro. Per esempio, dato che l'ordinamento per fusione divide l'elenco in n elenchi secondari, ha una complessità spaziale di O(n). Gli algoritmi che ordinano gli oggetti in posizione (nel senso che modificano solo i dati esistenti invece di crearne di nuovi) hanno una complessità spaziale di O(1). Se utilizzi elenchi molto grandi, la complessità spaziale può essere un aspetto da tenere sotto controllo quando selezioni il tuo algoritmo.
Dato che Verse è un linguaggio di programmazione funzionale, le operazioni API delle strutture di dati restituiscono versioni modificate dell'oggetto originale passato come ingresso. Per esempio, le funzioni degli array Insert() e RemoveElement() non modificano l'array originale, bensì creano e restituiscono un nuovo array dopo l'esecuzione della funzione. Ciò potrebbe portare a requisiti più elevati di complessità temporale e spaziale per tenere in considerazione la creazione dei nuovi elementi.
Stabilità
Durante gli ordinamenti, l'algoritmo si trova spesso in situazioni di uguaglianza. Per esempio, dati due giocatori con lo stesso punteggio di cinque, come deve ordinarli l'algoritmo? In questo scenario, un algoritmo stabile mantiene l'ordine in cui gli elementi uguali hanno nell'elenco dopo l'ordinamento. Se il giocatore uno viene prima del giocatore due nell'elenco prima dell'ordinamento, l'elenco ordinato avrà ancora il giocatore uno prima del giocatore due.
Tuttavia, un algoritmo instabile non mantiene l'ordine, nel senso che il giocatore due potrebbe apparire prima del giocatore uno. Questo è importante se il tuo codice controlla i primi elementi dell'elenco, per esempio per ottenere i primi tre giocatori per punteggio da visualizzare su una classifica. In questa situazione, vuoi un algoritmo stabile per garantire che chiunque ottenga il punteggio per primo rimanga nella classifica.
Test e profilazione degli algoritmi
Sebbene sia utile sapere come l'algoritmo si comporta per quanto riguarda complessità temporale e spaziale, è ancora più importante misurare le prestazioni in caso di dati reali. Lo sviluppo degli algoritmi di ordinamento può essere difficile e potrebbe essere non semplice identificare se il codice funziona in modo costante per tutti gli input. Questo è l'aspetto per cui i test sono importanti. Configurando una funzione di test, puoi misurare la precisione del codice e identificare come si comporta durante lo sviluppo. Puoi anche vedere se si presentano regressioni nelle prestazioni in caso di modifica dell'applicazione di ciò che sottoponi a test. Segui questa procedura per configurare file di test per i tuoi algoritmi di ordinamento e i tuoi dati di uscita relativi alle prestazioni:
-
Crea una funzione fallibile chiamata
RunArrayTest.# Funzione di test per l'ordinamento degli array e la profilazione del codice. RunArrayTest()<decides><transacts>:void= -
Aggiungi l'argomento dell'array su cui vuoi eseguire l'ordinamento e la funzione di confronto da utilizzare.
# Funzione di test per l'ordinamento degli array e la profilazione del codice. RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:subtype(comparable))<decides><transacts>:void= # Esegui l'ordinamento per fusione ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) -
Ora devi confrontare l'array ordinato con la previsione. Aggiungi l'argomento dell'array previsto per il confronto con l'array ordinato effettivo per verificare che il risultato sia corretto.
Confronta gli elementi in
ResultArraye gli elementi inExpectedArray. La funzioneRunArrayTestè fallibile; appena un elemento non corrisponde, la funzione di test non riesce.# Funzione di test per l'ordinamento degli array e la profilazione del codice. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t dove t:subtype(comparable))<decides><transacts>:void= # Esegui l'ordinamento per fusione ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Verifica che il test abbia esito positivo e che l'array sia stato ordinato come previsto. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Aggiungi una funzione di argomento per stampare gli array a ogni fase in modo da confrontarli in caso di test non riuscito e comprendere come sistemare il codice che stai sottoponendo a test.
# Funzione di test per l'ordinamento degli array e la profilazione del codice. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string dove t:subtype(comparable))<decides><transacts>:void= # Esegui l'ordinamento per fusione ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Stampa gli array effettivo, previsto e risultato per la risoluzione dei problemi. ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # Verifica che il test abbia esito positivo e che l'array sia stato ordinato come previsto. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
La funzione di test controlla la precisione del risultato, ma puoi ottenere altre informazioni dal test. Utilizzando l'espressione del profilo, puoi misurare le prestazioni dei tuoi algoritmi registrando il tempo necessario per il completamento l'algoritmo.
Questo è utile quando vuoi confrontare le prestazioni di diversi algoritmi di ordinamento o sottoporre a test come vengono eseguiti gli algoritmi in base ai diversi input. Singoli algoritmi potrebbero avere prestazioni molto diverse in caso di input di caso migliore e caso peggiore e la profilazione ti permette di trovare e sottoporre a test i casi per sapere cosa cercare. Dopo vari test, puoi misurare le prestazioni medie dell'algoritmo e stimarne le prestazioni in caso di input di una determinata dimensione.
-
Aggiungi un argomento stringa chiamato
Descriptionche spiega su cosa punta l'attenzione il test. Puoi aggiungerlo all'espressioneprofileper registrare la descrizione con il valore temporale.# Funzione di test per l'ordinamento degli array e la profilazione del codice. RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string dove t:subtype(comparable))<decides><transacts>:void= # Esegui l'ordinamento per fusione e la profilazione del codice. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Stampa gli array effettivo, previsto e risultato per la risoluzione dei problemi. ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # Verifica che il test abbia esito positivo e che l'array sia stato ordinato come previsto. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected
Scrittura dei casi di test
Inizia in modo semplice. Isola ciò che stai sottoponendo a test. Sottoponi a test un array di interi da ordinare dal più piccolo al più grande.
-
Crea una funzione di confronto tra interi.
# Funzione di confronto da utilizzare come argomento per l'ordinamento degli interi dal più piccolo al più grande. IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right -
Crea una funzione di supporto per convertire un array di interi in una stringa.
# Funzione di supporto per convertire un array di interi in una stringa. IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" -
Crea un dispositivo Verse per eseguire il test.
# Questo file contiene i test per verificare che l'algoritmo di ordinamento si comporti come previsto. # I test includono anche la profilazione del codice per vedere le prestazioni dell'algoritmo. 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" a livello di progetto per stampare messaggi da funzioni che non sono in una classe con un registro. # La stampa non-Logger è <no_rollback>, quindi non può essere utilizzata in una funzione <transacts>. ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # Dispositivo creativo creato da Verse che può essere posizionato in un livello. # Posiziona nel livello per eseguire i test e il codice di profilazione. test_sorting := class(creative_device): # Viene eseguito quando il dispositivo viene avviato in un gioco in esecuzione OnBegin<override>()<suspends>:void= # Esempio di array da utilizzare per il test. Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # Esegui i test e registra se il risultato è positivo o negativo. if: RunArrayTest["Array di interi in ordine dal più piccolo al più grande", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("Tutti i test superati.") else: ProjectLog("Uno o più test non superati.") -
Ora popola gli array di test con i valori.
var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): Conteggio Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray) -
Esegui il test trascinando il dispositivo Verse nel tuo livello
Queste sono altre idee di test che puoi eseguire:
* Ordina un array di interi dal più grande al più piccolo.
# Funzione di confronto da utilizzare come argomento per l'ordinamento degli interi dal più grande al più piccolo.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
* Ordina un array di interi che ha valori ripetuti.
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
* Ordina una classe in base a uno dei suoi campi.
# Esempio di classe per sottoporre a test l'ordinamento.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Funzione di confronto da utilizzare come argomento per l'ordinamento delle vittorie dalla più piccola alla più grande.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
A sinistra
# Funzione di supporto per convertire i valori di confronto delle statistiche dei giocatori in una stringa.
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 completo
# Questo file contiene i test per verificare che l'algoritmo di ordinamento si comporti come previsto.
# I test includono anche la profilazione del codice per vedere le prestazioni dell'algoritmo.
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" a livello di progetto per stampare messaggi da funzioni che non sono in una classe con un registro.
# La stampa non-Logger è <no_rollback>, quindi non può essere utilizzata in una funzione <transacts>.
ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
Logger := log{Channel := my_log_channel}
Logger.Print(Message, ?Level := Level)
# Dispositivo creativo creato da Verse che può essere posizionato in un livello.
# Posiziona nel livello per eseguire i test e il codice di profilazione.
test_sorting := class(creative_device):
# Viene eseguito quando il dispositivo viene avviato in un gioco in esecuzione
OnBegin<override>()<suspends>:void=
# Esempio di array da utilizzare per il test.
var ArrayLength:int = GetRandomInt(10, 100)
Test1ExpectedIntArray:[]int =
for (Count := 0..ArrayLength):
Conteggio
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)
# Esegui i test e registra se il risultato è positivo o negativo.
if:
RunArrayTest["Array di interi in ordine dal più piccolo al più grande", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Array di interi in ordine dal più grande al più piccolo", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
RunArrayTest["Array di interi in ordine dal più piccolo al più grande con ripetizioni", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Array delle statistiche dei giocatori in ordine dal numero più grande di vittorie al più piccolo", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
then:
ProjectLog("Tutti i test superati.")
else:
ProjectLog("Uno o più test non superati.")
# Funzione di test per l'ordinamento degli array e la profilazione del codice.
RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string dove t:subtype(comparable))<decides><transacts>:void=
# Esegui l'ordinamento per fusione e la profilazione del codice.
ResultArray := profile(Description):
SortingAlgorithms.MergeSort(ActualArray, Compare)
# Stampa gli array effettivo, previsto e risultato per la risoluzione dei problemi.
ProjectLog("Actual: {ArrayToString(ActualArray)}")
ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
ProjectLog("Result: {ArrayToString(ResultArray)}")
# Verifica che il test abbia esito positivo e che l'array sia stato ordinato come previsto.
for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
Result = Expected
# Funzione di supporto per convertire un array di interi in una stringa.
IntArrayToString(Array:[]int)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Funzione di supporto per convertire i valori di confronto delle statistiche dei giocatori in una stringa.
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 += "]"
# Funzione di confronto da utilizzare come argomento per l'ordinamento degli interi dal più piccolo al più grande.
IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
Left < Right
# Funzione di confronto da utilizzare come argomento per l'ordinamento degli interi dal più grande al più piccolo.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
# Esempio di classe per sottoporre a test l'ordinamento.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Funzione di confronto da utilizzare come argomento per l'ordinamento delle vittorie dalla più piccola alla più grande.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
A sinistra
# Funzione di confronto da utilizzare come argomento per l'ordinamento del numero di vittorie dal più grande al più piccolo.
IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins > Right.Wins
A sinistra
In autonomia
-
Applica un algoritmo di ordinamento diverso. Puoi trovare le applicazioni del seguente altro algoritmo:
-
Aggiungi altri casi di test per aumentare la copertura del test. Ti vengono in mente casi limite che non sono al momento coperti? Oppure con tipi di dati più complessi?