ソートはシンプルですが強力なコンセプトです。アルゴリズムを使用し、未整理のアイテムのリストを特定の順番でソートすることができます。この考え方は基本的なものに思えるかもしれませんが、ソートはコンピュータ サイエンス全体でさまざまな側面や形で現れます。最も重要な用途の 1 つは、検索の高速化です。たとえば、コンピュータはファイルを名前やサイズでソートし、必要なファイルを素早く見つけられるようにします。UEFN では、さまざまなものをグループ化し、プロジェクトを整理するため、アウトライナー 内のオブジェクトを タイプ 別にソートできます。フォートナイトでは、誰がトップか誰もが分かるように、インゲームのスコアボード上のプレイヤーが、脱落回数やラップタイムなどさまざまな統計データでソートされます。
Verse コードにソートを適用することで、ゲームプレイを向上し、開発の要素を強化できます。たとえば、各ラウンドで最もスコアが少なかったプレイヤーが脱落するトーナメントでプレイヤーの配列をスコア別に並べるのはどうでしょうか？各ラウンドの最後にこの配列をソートすることで、最もスコアが少ないプレイヤーを素早く見つけ、観戦者に設定することができます。一方、最高スコアのプレイヤーを素早く集め、次のラウンドのボーナスを与えることもできます。 このソートしたリストを使用して、永続的ローカル ランキングを作成し、プレイヤーがゲーム中に注意しなくてはならないのは誰かを知ることができるようにさえできます。自分の島でお礼を言いたい人のリストがある場合、表示しやすいように名前をアルファベット順にソートできます。
それぞれの例は、異なる方法でソートを使用しますが、すべての例において目的を達成するために内部で ソート アルゴリズム を使用しています。ソート アルゴリズムは、リストをソートするロジックを実装し、必要に応じてさまざまな種類から選ぶことができます。ソートは強力なツールですが、プロジェクトに組み込むにはどのように機能するかを理解することが重要です。このページは、ソートの背後にある主要な考え方とプロジェクトに最適なアルゴリズムの選び方を網羅しています。特定のソート アルゴリズムの実装については、このページの最後のリンクを確認してください。
マージ ソート
マージ ソートは、分割統治のソート アルゴリズムです。これは、ソートする必要がある要素のグループを小グループに分割し、小グループをソートすることを意味します。そして、小グループはソートされていると認識したうえで、小グループを統合します。
マージ ソートを実装する
以下の実装は、分割された配列をマージ ソートするために実装自体を呼び出します。つまり、これは再帰関数です。再帰関数がある場合、無限再帰を防ぐため、ベース ケースを指定する必要があります。このアルゴリズムは毎回配列を半分に分割するため、配列が 1 つの要素から始まるようソートされているとみなされ、他の単一要素配列と統合して要素の完全な配列に戻すことができるよう、ベース ケースは要素が 1 つのみの配列です。
以下の実装は、パラメータの パラメトリック型 を使用することで汎用的になっています。つまり、要素には必要に応じた型を、引数には独自の比較関数を使用することができます。そのため、ソートする整数配列、またはソートできるクラスなど、より複雑な型の配列を持つことができます。Compare 関数は、独自のカスタム関数を渡すことができる別のパラメータです。昇順にソートする場合やクラスの特定のフィールドでソートする場合は、この汎用的な関数の実装を変更することなくカスタム関数で指定できます。
以下の手順に従って、Verse でマージ ソートを実装します。
-
配列の唯一の要素、ベース ケースを書くことから始めましょう。要素が 1 以下の場合、関数に渡された配列引数を返します。
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: 長さ > 1 # 配列に複数の要素があることを確認し、そうでなければベース ケースに到達しています。 else: # ベース ケースに到達したため、渡された配列を返します。 配列 -
次に、配列を半分に分割します。
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: 長さ > 1 # 配列に複数の要素があることを確認し、そうでなければベース ケースに到達しています。 Mid:int = Floor(Length / 2) # 配列の中央インデックスを取得します。 Left:[]t = Array.Slice[0, Mid] # 配列を半分に分割します。これは、最初から Mid - 1 インデックスまでの要素を保持します。 Right:[]t = Array.Slice[Mid] # 配列を半分に分割します。これは、Mid インデックスから配列の最後までの要素を保持します。 else: # ベース ケースに到達したため、渡された配列を返します。 配列 -
初期配列の各半分に
MergeSortを呼び出し、半分 2 つをMergeします。MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: 長さ > 1 # 配列に複数の要素があることを確認し、そうでなければベース ケースに到達しています。 Mid:int = Floor(Length / 2) # 配列の中央インデックスを取得します。 Left:[]t = Array.Slice[0, Mid] # 配列を半分に分割します。これは、最初から Mid - 1 インデックスまでの要素を保持します。 Right:[]t = Array.Slice[Mid] # 配列を半分に分割します。これは、Mid インデックスから配列の最後までの要素を保持します。 then: # 配列の左半分に MergeSort を呼び出します。 LeftSorted:[]t = MergeSort(Left, Compare) # 配列の右半分に MergeSort を呼び出します。 RightSorted:[]t = MergeSort(Right, Compare) # 2 つの配列を結合し、結果を返します。 Merge(LeftSorted, RightSorted, Compare) else: # ベース ケースに到達したため、渡された配列を返します。 配列 -
半分 2 つをマージする場合、各配列からの要素を比較し、両方の配列からのすべての要素が追加されるまで結果の配列に追加します。これを行うには、各配列で位置をトラックするためのインデックス変数が必要です。
Compare関数が成功するたび、左配列要素が追加され、そのインデックス変数を配列の次の位置に進ませる必要があります。そうでない場合、右配列要素で同様に行います。配列の 1 つからのすべての要素が追加されたら、すでにソートされているため、もう 1 つの配列からの残りの要素を追加します。# Compare 関数に基づいた順序で分割された配列を結合する MergeSort のヘルパー関数。 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{} # MergedArray 変数に追加するために、配列のすべての要素をループします。 loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # 右半分の配列の要素で左半分の配列の要素を確認します。 # 引数として渡された Compare 関数を使用します if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: MergedArray += array{RightElement} set RightIndex += 1 else: # この時点で配列の 1 つからのすべての要素を追加しています。 # 次に、どちらの配列にマージする要素がまだあるかを確認し、すべての残りの要素を追加します。 if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # すべての要素を追加し終えたため、ループを終了します。 break # マージした配列を返します。 MergedArray
完全なスクリプト
# 配列を 2 つに分割し、分割された各配列をソートして、配列をマージする、分割統治のソート アルゴリズム。
# これは、分割された配列をマージ ソートするために関数がそれ自体を呼び出す再帰的実装です。
# ベース ケース (再帰を停止する条件) は 1 つだけ要素がある配列です。
# これは、パラメトリック型を使用する汎用的な実装であるため、引数として独自の型と比較関数を提供できます。
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
Length:int = Array.Length
if:
長さ > 1 # 配列に複数の要素があることを確認し、そうでなければベース ケースに到達しています。
Mid:int = Floor(Length / 2) # 配列の中央インデックスを取得します。
Left:[]t = Array.Slice[0, Mid] # 配列を半分に分割します。これは、最初から Mid - 1 インデックスまでの要素を保持します。
Right:[]t = Array.Slice[Mid] # 配列を半分に分割します。これは、Mid インデックスから配列の最後までの要素を保持します。
then:
# 配列の左半分に MergeSort を呼び出します。
LeftSorted:[]t = MergeSort(Left, Compare)
# 配列の右半分に MergeSort を呼び出します。
RightSorted:[]t = MergeSort(Right, Compare)
# 2 つの配列を結合し、結果を返します。
Merge(LeftSorted, RightSorted, Compare)
else:
# ベース ケースに到達したため、渡された配列を返します。
配列
# Compare 関数に基づいた順序で分割された配列を結合する MergeSort のヘルパー関数。
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{}
# MergedArray 変数に追加するために、配列のすべての要素をループします。
loop:
if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
# 右半分の配列の要素で左半分の配列の要素を確認します。
# 引数として渡された Compare 関数を使用します
if (Compare[LeftElement, RightElement]):
set MergedArray += array{LeftElement}
set LeftIndex += 1
else:
MergedArray += array{RightElement}
set RightIndex += 1
else:
# この時点で配列の 1 つからのすべての要素を追加しています。
# 次に、どちらの配列にマージする要素がまだあるかを確認し、すべての残りの要素を追加します。
if (LeftIndex >= Left.Length):
option{set MergedArray += Right.Slice[RightIndex]}
else:
option{set MergedArray += Left.Slice[LeftIndex]}
# すべての要素を追加し終えたため、ループを終了します。
break
# マージした配列を返します。
MergedArray
アルゴリズムを選択する
多くのソート アルゴリズムは同じような考え方に従っていますが、それぞれに異なる点があり、それがアルゴリズムの動作に大きな影響を与える可能性があります。
時間的複雑度
アルゴリズムは時間がかかり、しなければならないことが増えるほど、時間がかかります。アルゴリズムが解決しようとしている問題の複雑さに影響する要因の数とそれを処理するのに要する時間量は 時間的複雑度 と呼ばれます。
コンピュータのハードウェア、他の実行中のコード、扱っているデータの種類などさまざまな要因で、アルゴリズムが終了するのにかかる正確な時間を計算するのはほぼ不可能であるため、時間的複雑度は代わりに 演算 数、またはアルゴリズムが終了するために行う必要があるアクション数で計ります。それぞれのアルゴリズムは異なるため、データセットを処理するのに必要な時間量は Big O 記法を用いて表します。Big O 記法は、正確な必要演算数は記述しませんが、代わりに、アルゴリズムに入力するリストのサイズが大きくなるにつれてその数値がどのように変化するかを記述します。
たとえば、リストで最も小さい数を検索するアルゴリズムを書いたとします。リストが順番に並んでいるか分からないため、アルゴリズムは最も小さい数を認識するためにはすべての数をチェックする必要があります。アイテムが 3 つあれば、アルゴリズムは 3 つのチェックを行い、10 のアイテムがあれば、アルゴリズムは 10 のチェックを行います。 演算数はリストの入力サイズに比例して増加するため、時間的複雑度は線形、または n がリストのアイテム数を表す O(n) です。使用するアルゴリズムで、アイテムごとに 2 つの操作を行う必要がある場合 (各チェックの後に各アイテムを別のリストにコピーする、など)、操作の数は「2 * NumberOfItems」であるため、時間的複雑度は O(2n) になります。
リストにアイテムがあるかどうかをチェックするだけのアルゴリズムではどうでしょうか。そのアルゴリズムでは、入力サイズに関係なく 1 つの操作のみを行うため、時間的複雑度は一定、つまり O(1) になります。2 次時間 (O(n^2)) や階乗時間 (O(n!)) など、他にも多くの例がありますが、重要なのは、それぞれで、行われる操作の数が入力サイズによってどのように増大するかが説明されていることです。
ソートの複雑度
ソート アルゴリズムの時間的複雑度を測定することは、ソートする前のリストの状態がさまざまである可能性があるため、かなり複雑になります。すでにソート済みであればどうでしょうか。逆順でソートされていればどうでしょうか。ソート アルゴリズムのパフォーマンスは、それらの要因によって劇的に変動する可能性があるため、ソート アルゴリズムは通常、ベストケース、ワーストケース、および平均ケースの時間的複雑度によって測定されます。
たとえば、バブル ソート アルゴリズム の場合を見てみましょう。ベストケースでは、リストはソート済みであり、バブル ソートでは要素のすべてのペアをチェックする必要がありますが、要素の入れ替えを行う必要はありません。そのため、ベストケースの時間的複雑度は O(n) であり、優れた結果となります。では、逆のシナリオではどうでしょうか。リストが逆順でソートされている場合です。その場合、バブル ソートでは n 回のチェックを行い、リスト内のすべての要素を n 回入れ替える必要があるため、ワーストケースの時間的複雑度は「n * n」、つまり O(n^2) になります。これは、他のソート アルゴリズムと比べて遅いと見なされ、このアルゴリズムでは、要素数が 10 個のリストを処理するのに 100 回以上の操作が必要になるため、すぐに手に負えなくなる可能性があります。要素数が 100 個のリストだとどれだけの操作が必要になるかわかりますか。1000 個ではどうでしょうか。
ソート アルゴリズムでは通常、ベストケースやワーストケースではなく、平均ケースに近いパフォーマンスになります。たとえば、マージ ソートの平均ケースの複雑度は O(n log n) です。これは良好なベンチマークと見なされます。よく使われる他の多くのソート アルゴリズムのベストケース、ワーストケース、平均ケースの複雑度は、この水準か、かなり近い水準です。バブル ソートの平均ケースの複雑度は前述のように O(n^2) であるため、平均ケースでもまだ比較的遅いアルゴリズムです。
コードが高速に実行され、入力の型に関係なく同様のパフォーマンスになることが望ましいため、アルゴリズムを選択する際に時間的複雑度を把握しておくことが重要です。よく使われる効率的なソート アルゴリズムの例については、「マージ ソート」と「クイックソート」を参照してください。どちらのアルゴリズムも、ベストケース、ワーストケース、平均ケースの複雑度は O(n log n) であり、どのような状況のソートでも良好な開始点となります。
空間的複雑度
時間的複雑度に加えて、使用するアルゴリズムで、ソートを完了するためにどれだけのものを作成する必要があるかを考慮することも重要です。これは、空間的複雑度 と呼ばれ、アルゴリズムの実行時に作成される追加データの量のことです。時間的複雑度と同様に、空間的複雑度は Big O 記法で測定され、アルゴリズムによって異なります。たとえば、マージ ソートでは、リストを n 個のサブリストに分割するため、その空間的複雑度は O(n) です。オブジェクトを (新しいオブジェクトを作成するのではなく、既存のデータのみを変更するような) その場でソートするアルゴリズムの空間的複雑度は O(1) です。非常に大きいリストを操作するとき、空間的複雑度は、アルゴリズムの選択時に気を付けるべきものとなる場合があります。
Verse は 関数型プログラム言語 であるため、データ構造 API 操作は、入力としてわたされた元のアイテムの変更されたバージョンを返します。たとえば、配列関数 Insert() と RemoveElement() はどちらも、元の配列を変更しませんが、関数の実行後に新規配列を作成して返します。そのため、このような新規要素の作成が原因で、時間的複雑度と空間的複雑度の要件が高くなることにつながります。
安定性
ソート時に、アルゴリズムで同点になることはよくあります。たとえば、2 人のプレイヤーのスコアがそれぞれ 5 である場合に、アルゴリズムでどのようにソートされるでしょうか。このシナリオで、安定したアルゴリズム では、同点の要素がソート後のリストに現れる順序は維持されます。そのため、ソート前のリストでプレイヤー 1 がプレイヤー 2 より前にあれば、ソート後のリストでもプレイヤー 1 がプレイヤー 2 より前になります。
しかし、不安定なアルゴリズム では、この順序が維持されず、プレイヤー 2 がプレイヤー 1 より前に現れることがあります。このことは、スコアが上位 3 人のプレイヤーをランキングに表示する場合など、コードでリストの先頭にあるいくつかの要素を気にかける場合に重要です。そのような状況では、そのスコアを最初に達成したプレイヤーがランキングに表示され続けるようにする、安定したアルゴリズムが望ましいでしょう。
アルゴリズムのテストとプロファイリング
使用するアルゴリズムが所定の時間的複雑度と空間的複雑度でどのように実行されると予想されるかを知っておくのは良いことですが、より重要なのは、実際の入力に対してアルゴリズムのパフォーマンスがどのようになるかを測定することです。ソート アルゴリズムを開発するのは難しいことがあり、コードがすべての入力に対して確実に動作するかどうかを判断するのは困難である場合があります。そこでテストが役に立ちます。テスト関数をセットアップすることで、コードの正確さを評価でき、その開発時にどのように動作するかを特定できます。また、テスト対象とするコードの実装を変更した場合に、パフォーマンスが低下しているかどうかを確認できます。以下の手順に従って、ソート アルゴリズム用のテスト ファイルとそのパフォーマンスに関する出力データをセットアップします。
-
RunArrayTestという、失敗する可能性がある関数を作成します。# 配列をソートし、コードをプロファイリングするためのテスト関数。 RunArrayTest()<decides><transacts>:void= -
ソートの実行対象とする配列と、使用する比較関数を引数として追加します。
# 配列をソートし、コードをプロファイリングするためのテスト関数。 RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # マージ ソートを実行します。 ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) -
次に、ソート済みの配列を、想定されたものと比較する必要があります。ソート済みの実際の配列と比較して結果が正しいかどうかを確認する、想定された配列の引数を追加します。
ResultArray内の要素をExpectedArray内の要素と比較します。関数RunArrayTestは失敗する可能性があるため、要素が一致しなかったらすぐに、このテスト関数は失敗します。# 配列をソートし、コードをプロファイリングするためのテスト関数。 RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # マージ ソートを実行します。 ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # テストが成功したこと、およびソートされた配列が想定どおりであることを確認します。 for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
テストが失敗した場合にテスト対象のコードをどのように修正すべきかを把握できるように、各ステップで配列を出力する関数を引数として追加します。
# 配列をソートし、コードをプロファイリングするためのテスト関数。 RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # マージ ソートを実行します。 ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # トラブルシューティング用に、ActualArray、ExpectedArray、ResultArray を出力します。 ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # テストが成功したこと、およびソートされた配列が想定どおりであることを確認します。 for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
テスト関数は、結果の正確さをチェックしますが、テストからさらに詳細な情報を取得することもできます。profile 式 を使用して、アルゴリズムの完了にかかる時間をログ記録することで、アルゴリズムのパフォーマンスを測定することができます。
これは、さまざまなソート アルゴリズムのパフォーマンスを比較する場合や、さまざまな入力に対してアルゴリズムがどのように実行されるかをテストする場合に役立ちます。個々のアルゴリズムは、所定のベストケースとワーストケースの入力に対してパフォーマンスが大きく異なることがあり、プロファイリングによって、それらのケースを見つけてテストし、気を付けるべきものを把握することができます。複数のテストを行うことで、アルゴリズムの平均的パフォーマンスを評価し、任意のサイズの入力に対してどのようなパフォーマンスになるかを推定することができます。
-
何に重点を置いているテストであるかを説明する、
Descriptionという文字列引数を追加します。これをprofile式に追加して、測定時間値とともにその説明をログ記録することができます。# 配列をソートし、コードをプロファイリングするためのテスト関数。 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= # マージ ソートを実行し、コードをプロファイリングします。 ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # トラブルシューティング用に、ActualArray、ExpectedArray、ResultArray を出力します。 ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # テストが成功したこと、およびソートされた配列が想定どおりであることを確認します。 for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected
テスト ケースを記述する
単純なものから始め、何をテストするかを分けます。整数の配列の昇順のソートをテストします。
-
整数用の比較関数を作成します。
# 整数を昇順にソートするための引数として使用する比較関数。 IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right -
整数の配列を文字列に変換するヘルパー関数を作成します。
# 整数の配列を文字列に変換するヘルパー関数。 IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" -
テストを実行する Verse の仕掛けを作成します。
# このファイルには、ソート アルゴリズムが想定どおりに動作することを確認するためのテストが入っています。 # これらのテストには、アルゴリズムのパフォーマンスを確認するための、コードのプロファイリングも含まれています。 using { /Fortnite.com/Devices} using { /UnrealEngine.com/Temporary/Diagnostics} using { /Verse.org/Simulation} using { /Verse.org/Random} my_log_channel<public> := class(log_channel): # ログのあるクラスに属していない関数からのメッセージを出力するための、プロジェクト全体の「ロガー」。 # ロガー以外の Print は <no_rollback>であるため、 <transacts> 関数内では使用できません。 ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # レベルに配置できる、Verse で作成したクリエイティブの仕掛け。 # テストを実行し、コードをプロファイリングするために、レベルに配置します。 test_sorting := class(creative_device): # 実行中のゲームで仕掛けが開始されたときに実行します OnBegin<override>()<suspends>:void= # テストに使用するサンプル配列。 Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # テストを実行し、失敗したか成功したかを報告します。 if: RunArrayTest["昇順の整数の配列", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("すべてのテストに合格しました。") else: ProjectLog("1 つ以上のテストに失敗しました。") -
次に、テスト配列に値を投入します。
var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): 回数 Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray) -
Verse の仕掛けをレベルにドラッグすると、テストが実行されます。
実行できる他のテストのアイデアを以下に示します。
* 整数の配列を降順にソートします。
# 整数を降順にソートするための引数として使用する比較関数。
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
* 繰り返されている同じ値がある、整数の配列をソートします。
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
* いずれかのフィールドでクラスをソートします。
# ソートをテストするためのサンプル クラス。
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# 勝利数の昇順にソートするための引数として使用する比較関数。
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
左
# プレイヤー統計データの比較値を文字列に変換するヘルパー関数。
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 += "]"
完全なスクリプト
# このファイルには、ソート アルゴリズムが想定どおりに動作することを確認するためのテストが入っています。
# これらのテストには、アルゴリズムのパフォーマンスを確認するための、コードのプロファイリングも含まれています。
using { /Fortnite.com/Devices}
using { /UnrealEngine.com/Temporary/Diagnostics}
using { /Verse.org/Simulation}
using { /Verse.org/Random}
my_log_channel<public> := class(log_channel):
# ログのあるクラスに属していない関数からのメッセージを出力するための、プロジェクト全体の「ロガー」。
# ロガー以外の Print は <no_rollback>であるため、 <transacts> 関数内では使用できません。
ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
Logger := log{Channel := my_log_channel}
Logger.Print(Message, ?Level := Level)
# レベルに配置できる、Verse で作成したクリエイティブの仕掛け。
# テストを実行し、コードをプロファイリングするために、レベルに配置します。
test_sorting := class(creative_device):
# 実行中のゲームで仕掛けが開始されたときに実行します
OnBegin<override>()<suspends>:void=
# テストに使用するサンプル配列。
var ArrayLength:int = GetRandomInt(10, 100)
Test1ExpectedIntArray:[]int =
for (Count := 0..ArrayLength):
回数
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)
# テストを実行し、失敗したか成功したかを報告します。
if:
RunArrayTest["昇順の整数の配列", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["降順の整数の配列", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
RunArrayTest["繰り返しがある昇順の整数の配列", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["勝利数 # の降順のプレイヤー統計データの配列", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
then:
ProjectLog("すべてのテストに合格しました。")
else:
ProjectLog("1 つ以上のテストに失敗しました。")
# 配列をソートし、コードをプロファイリングするためのテスト関数。
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=
# マージ ソートを実行し、コードをプロファイリングします。
ResultArray := profile(Description):
SortingAlgorithms.MergeSort(ActualArray, Compare)
# トラブルシューティング用に、ActualArray、ExpectedArray、ResultArray を出力します。
ProjectLog("Actual: {ArrayToString(ActualArray)}")
ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
ProjectLog("Result: {ArrayToString(ResultArray)}")
# テストが成功したこと、およびソートされた配列が想定どおりであることを確認します。
for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
Result = Expected
# 整数の配列を文字列に変換するヘルパー関数。
IntArrayToString(Array:[]int)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# プレイヤー統計データの比較値を文字列に変換するヘルパー関数。
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 += "]"
# 整数を昇順にソートするための引数として使用する比較関数。
IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
Left < Right
# 整数を降順にソートするための引数として使用する比較関数。
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
# ソートをテストするためのサンプル クラス。
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# 勝利数の昇順にソートするための引数として使用する比較関数。
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
左
# 勝利数の降順にソートするための引数として使用する比較関数。
IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins > Right.Wins
左