1. Epic GamesDeveloper
  3. Алгоритмы сортировки в Verse

Алгоритмы сортировки в Verse

Узнайте, как сортировать списки объектов, используя алгоритмы сортировки

Алгоритмы сортировки в Verse

Сортировка — это простой и вместе с тем эффективный механизм. Неупорядоченный список элементов можно выстроить в нужном порядке, используя алгоритм сортировки. При всей своей простоте сортировка является неотъемлемой частью обработки информации и встречается в самых разных ситуациях. В частности, на практике она играет важную роль в ускорении поиска. Например, ваш компьютер сортирует файлы по имени и размеру, чтобы вы могли быстро найти нужный. UEFN позволяет сортировать объекты на вкладке Структура по Типу. Благодаря этому всё содержимое группируется и проект становится упорядоченным. В Fortnite игроки во внутриигровой таблице со счётом сортируются по самым разным показателям, например по количеству устранений и времени круга, что позволяет всем знать лидеров.

Применение сортировки в коде Verse позволяет поднять игровой процесс и саму разработку игры на новый уровень. Представьте, что у вас есть возможность упорядочивать массив игроков в турнире по количеству набранных очков, устраняя в каждом раунде тех, кто получил меньше всего очков. Сортируя такой массив в конце каждого раунда, вы сможете быстро выявлять отстающих и переводить их в категорию зрителей. При этом вы так же быстро будете определять лидеров и давать им бонусы для участия в следующем раунде. Такой отсортированный список можно даже использовать для создания сохраняемых локальных таблиц лидеров, и игроки будут знать, на кого обратить особое внимание во время игры.А если у вас будет список игроков, которых вы хотели бы прославить на своём острове, для удобства можно отсортировать список по имени в алфавитном порядке.

В каждом из этих примеров сортировка выполняется по-разному, но по сути для решения конкретной задачи всегда используется т. н. алгоритм сортировки. В алгоритмах сортировки реализована определённая логика сортировки списков. Алгоритмов много, и выбор конкретного зависит от потребностей игры. При том что сортировка представляет собой эффективный инструмент, важно понимать принцип её действия, если вы хотите использовать сортировку в своих проектах. На этой странице описаны основные принципы сортировки и вам предоставляется возможность выбрать алгоритм, наиболее подходящий для вашего проекта. О том, как реализованы конкретные алгоритмы сортировки, вы сможете узнать, перейдя по ссылкам в конце этой страницы.

Сортировка с объединением

Сортировка с объединением — это алгоритм с последовательным разделением. Он разбивает группу сортируемых элементов на меньшие группы, которые и подвергаются сортировке. Далее меньшие группы объединяются, принимая во внимание, что внутри они уже отсортированы.

Реализация сортировки с объединением

Описанная ниже реализация основана на рекурсивном обращении к одной и той же функции для сортировки с объединением разделённых массивов. Если у вас есть рекурсивная функция, нужно задать базовый сценарий, чтобы избежать бесконечной рекурсии. Поскольку этот алгоритм всякий раз делит массивы пополам, базовый сценарий предусматривает наличие в массиве единственного элемента. Такой массив сразу считается отсортированным, присоединяется к другому массиву с одним элементом и так далее до получения полного массива элементов.

Следующая реализация является обобщённой, и параметры в ней имеют параметрические типы. Это означает, что вы можете использовать в качестве аргументов элементы любого типа и собственную функцию сравнения. Поэтому у вас может быть целочисленный массив для сортировки либо массив более сложного типа, например класс, который вы также можете отсортировать. Функция Compare является ещё одним параметром, с помощью которого вы можете передавать собственные пользовательские функции. Если нужно произвести сортировку по принципу «от меньшего к большему» либо по определённым полям класса, реализуйте это в своей пользовательской функции, не меняя данную обобщённую реализацию функции.

Выполните следующие действия, чтобы реализовать сортировку с объединением на языке Verse:

  1. Начнём с написания базового сценария, когда массив содержит единственный элемент. Если присутствует не больше одного элемента, возвращаем аргумент Array, переданный в эту функцию.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # Убеждаемся, что в массиве больше одного элемента, в противном случае мы вышли на базовый сценарий.
     else:
         # Возвращаем переданный массив, так как мы вышли на базовый сценарий.
         Массив

  2. Теперь разобьём массив пополам.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # Убеждаемся, что в массиве больше одного элемента, в противном случае мы вышли на базовый сценарий.
         Mid:int = Floor(Length / 2) # Получаем индекс элемента в середине массива.
         Left:[]t = Array.Slice[0, Mid] # Делим массив пополам. Здесь будут храниться элементы от начала массива до индекса Mid – 1.
         Right:[]t = Array.Slice[Mid] # Делим массив пополам. Здесь будут храниться элементы от индекса Mid до конца массива.
     else:
         # Возвращаем переданный массив, так как мы вышли на базовый сценарий.
         Массив

  3. Вызовем MergeSort для каждой половины первоначального массива и затем объединим (Merge) две половины.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 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)

         # Объединяем два массива и возвращаем результат.
         Merge(LeftSorted, RightSorted, Compare)
     else:
         # Возвращаем переданный массив, так как мы вышли на базовый сценарий.
         Массив

  4. При последующем объединении двух половин будем сравнивать элементы из каждого массива и добавлять их в итоговый массив, пока не будут добавлены все элементы. Для этого понадобится переменная индекса, чтобы отслеживать позиции в каждом массиве. При каждом успешном выполнении функции Compare добавляется элемент левого массива и его переменная индекса переходит на следующую позицию в массиве. В противном случае нужно проделать то же самое с элементом в правом массиве. Как только все элементы из одного массива будут добавлены, добавляем остальные элементы из другого массива, потому что он уже отсортирован.

     # Вспомогательная функция для MergeSort, которая объединяет разделённые массивы в порядке, определяемом функцией 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{}
    
     # Перебираем все элементы в массивах, чтобы добавить их в переменную MergedArray.
     loop:
         if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
             # Сравниваем элемент в левой половине массива с элементом в правой половине массива.
             # Используем функцию Compare, переданную в качестве аргумента
             if (Compare[LeftElement, RightElement]):
                 set MergedArray += array{LeftElement}
                 set LeftIndex += 1
             else:
                 set MergedArray += array{RightElement}
                 set RightIndex += 1
         else:
             # На данный момент мы добавили все элементы из одного из массивов.
             # Теперь проверяем, в каком из массивов ещё остаются элементы для объединения, и добавляем все оставшиеся элементы.
             if (LeftIndex >= Left.Length):
                 option{set MergedArray += Right.Slice[RightIndex]}
             else:
                 option{set MergedArray += Left.Slice[LeftIndex]}
             # Выходим из этого цикла, так как все элементы добавлены.
             break

     # Возвращаем объединённый массив.
     MergedArray

Полный сценарий

    # Алгоритм сортировки с последовательным разделением, который делит массив на два, сортирует каждый из них по отдельности, а затем объединяет их.
    # Это рекурсивная реализация, в которой функция вызывает сама себя для выполнения сортировки с объединением разделённых массивов.
    # Базовый сценарий (условие прекращения рекурсии) подразумевает наличие в массиве единственного элемента.
    # Это обобщённая реализация, в которой используются параметрические типы, чтобы в качестве аргументов вы могли передавать собственный тип и собственную функцию сравнения.
    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 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)

            # Объединяем два массива и возвращаем результат.
            Merge(LeftSorted, RightSorted, Compare)
        else:

            # Возвращаем переданный массив, так как мы вышли на базовый сценарий.
            Массив

    # Вспомогательная функция для MergeSort, которая объединяет разделённые массивы в порядке, определяемом функцией 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{}

        # Перебираем все элементы в массивах, чтобы добавить их в переменную MergedArray.
        loop:
            if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
                # Сравниваем элемент в левой половине массива с элементом в правой половине массива.
                # Используем функцию Compare, переданную в качестве аргумента
                if (Compare[LeftElement, RightElement]):
                    set MergedArray += array{LeftElement}
                    set LeftIndex += 1
                else:
                    set MergedArray += array{RightElement}
                    set RightIndex += 1
            else:
                # На данный момент мы добавили все элементы из одного из массивов.
                # Теперь проверяем, в каком из массивов ещё остаются элементы для объединения, и добавляем все оставшиеся элементы.
                if (LeftIndex >= Left.Length):
                    option{set MergedArray += Right.Slice[RightIndex]}
                else:
                    option{set MergedArray += Left.Slice[LeftIndex]}
                # Выходим из этого цикла, так как все элементы добавлены.
                break

        # Возвращаем объединённый массив.
        MergedArray

Выбор алгоритма

Многие алгоритмы сортировки построены по схожему принципу, но у них есть некоторые различия, которые существенным образом влияют на то, как они работают.

Временная сложность

Для решения задачи алгоритмам требуется определённое время, и чем больше операций нужно выполнить, тем больше времени затрачивается. На сложность задачи, которую решает алгоритм, влияет ряд факторов. Затрачиваемое время называется временной сложностью.

Поскольку рассчитать точное время, которое понадобится алгоритму для решения задачи, почти невозможно, учитывая многие факторы, такие как аппаратные возможности компьютера, выполнение другого кода и тип обрабатываемых данных, временная сложность измеряется в количестве операций, или действий, выполняемых алгоритмом для решения конкретной задачи. Поскольку все алгоритмы разные, время, затрачиваемое на обработку набора данных, описывается с помощью обозначения «О» большое. Обозначение «О» большое даёт представление не о точном количестве необходимых операций, а описывает характер изменения их количества при увеличении размера списка, обрабатываемого алгоритмом.

Пусть, например, вы пишете алгоритм поиска наименьшего числа в списке. Вы не знаете, упорядочен этот список или нет, а потому ваш алгоритм должен проверить каждое число, чтобы определить, является ли оно наименьшим. Если в списке три элемента, ваш алгоритм выполняет три проверки, а если их десять, то десять проверок. Поскольку количество операций увеличивается линейно по мере роста размера списка, временная сложность является линейной, или O(n), где n — это количество элементов в списке. Если алгоритм должен выполнять для каждого элемента две операции, например копировать каждый элемент в другой список после каждой проверки, временная сложность выражается как O(2n), потому что количество операций равно 2 * NumberOfItems.

А что если алгоритм должен просто проверить наличие элементов в списке? Так как алгоритм выполняет единственную операцию независимо от размера входных данных, временная сложность будет постоянной, или O(1). Бывают алгоритмы с квадратичным (O(n^2)) или т. н. факториальным временем (O(n!)), но главное, что каждое обозначение описывает, как увеличивается количество выполняемых операций по мере роста размера входных данных.

Сложность сортировки

Измерение временной сложности для алгоритмов сортировки усложняется ещё больше из-за того, что перед сортировкой список может находиться в разных состояниях. Может быть, он уже отсортирован? Или же отсортирован в обратном порядке? Производительность алгоритма сортировки может сильно меняться в зависимости от этих факторов, поэтому для алгоритмов сортировки обычно определяют наилучший, наихудший и средний показатели временной сложности.

Для примера рассмотрим алгоритм сортировки простыми обменами. В лучшем случае, когда список уже отсортирован, сортировка простыми обменами требует всего лишь проверки каждой пары элементов без каких-либо перестановок! То есть в лучшем случае временная сложность определяется как O(n), и это отличный результат! А как насчёт противоположного сценария, когда перед началом работы алгоритма список отсортирован в обратном порядке? При этом сортировка простыми обменами подразумевает n проверок и каждый элемент в списке переставляется n раз, то есть временная сложность в худшем случае определяется как n * n, или O(n^2). Этот алгоритм сортировки считается медленным по сравнению с другими, и он может очень быстро выйти из-под контроля, так как ему может потребоваться не меньше сотни операций для обработки списка из десяти элементов. Стоит ли говорить, сколько операций потребуется для ста элементов? А если их будет тысяча?

Обычно алгоритмы сортировки демонстрируют некоторую среднюю эффективность между худшим и лучшим случаями. Например, средняя сложность сортировки с объединением равна O(nlogn). Это считается хорошим результатом, так как многие другие распространённые алгоритмы сортировки имеют наилучший, наихудший и средний показатели сложности на таком же уровне или близко к нему. Уже упомянутая сортировка простыми обменами имеет средний показатель сложности O(n^2), поэтому даже по этому показателю она достаточно медленная.

При выборе алгоритма важно понимать временную сложность, поскольку наш код должен выполняться быстро и предсказуемо при любом виде входных данных. Ознакомьтесь с некоторыми распространёнными эффективными алгоритмами сортировки, такими как сортировка с объединением и быстрая сортировка. Оба этих алгоритма имеют одинаковые наилучший, наихудший и средний показатели сложности O(nlogn) и являются хорошей отправной точкой для решения любых задач сортировки.

Пространственная сложность

Помимо временной сложности, также важно учитывать, сколько данных должен создать алгоритм, чтобы выполнить сортировку. Это и есть пространственная сложность, или количество дополнительных данных, создаваемых во время работы алгоритма. Как и временная сложность, пространственная сложность измеряется с помощью обозначения O _большое, которое различается от алгоритма к алгоритму. Например, поскольку сортировка с объединением разделяет список на _n подсписков, её пространственная сложность — O(n). Алгоритмы, сортирующие объекты на месте (только изменяя существующие данные, а не создавая новые), имеют пространственную сложность O(1). При выборе алгоритма для сортировки очень больших списков следует обращать внимание на пространственную сложность.

Так как Verse — это функциональный язык программирования, операции API со структурами данных возвращают изменённые версии исходного элемента, переданного как входные данные. Например, функции работы с массивами Insert() и RemoveElement() не изменяют исходный массив, а создают и возвращают после выполнения новый массив. В результате создания этих новых элементов увеличивается время на обработку и повышается пространственная сложность.

Устойчивость

Зачастую во время сортировки алгоритм сталкивается с проблемными местами. Например, как должен действовать алгоритм при сортировке двух игроков, каждый из которых набрал пять очков? В этом сценарии устойчивый алгоритм после сортировки сохраняет порядок, в котором одинаковые элементы располагались в списке изначально. То есть если перед сортировкой первый игрок стоял в списке перед вторым, в отсортированном списке первый игрок останется перед вторым.

С другой стороны, неустойчивый алгоритм не сохраняет порядок, и второй игрок может оказаться перед первым. Это важно, когда имеют значение первые несколько элементов в списке, например если нужно получить трёх лидирующих по очкам игроков для отображения в таблице лидеров. В такой ситуации желателен устойчивый алгоритм, сохраняющий на определённом месте в таблице лидеров любого игрока, набравшего это количество очков первым.

Тестирование и профилирование алгоритмов

Несмотря на важность понимания работы алгоритма в показателях временной и пространственной сложности, ещё важнее измерять фактическую производительность алгоритма на реальных входных данных. Разработка алгоритмов сортировки бывает сложной, при этом не всегда понятно, работает ли алгоритм предсказуемо со всеми входными данными. И тогда на помощь приходит тестирование. Создав функцию тестирования, вы можете оценивать точность кода и проверять его эффективность по мере разработки. Кроме того, можно выявлять снижение производительности при внесении изменений в тестируемый код. Выполните следующие действия, чтобы создать файл для тестирования алгоритмов сортировки и сохранения результатов оценки их производительности:

  1. Создайте функцию RunArrayTest с неоднозначным результатом.

     # Функция тестирования для сортировки массивов и профилирования кода.
 RunArrayTest()<decides><transacts>:void=

  2. Добавьте аргументы, представляющие собой массив, подлежащий сортировке, и используемую функцию сравнения.

     # Функция тестирования для сортировки массивов и профилирования кода.
 RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
     # Выполняем сортировку с объединением
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

  3. Теперь нужно сравнить отсортированный массив с ожидаемым. Добавьте аргумент, представляющий собой ожидаемый массив для сравнения с фактическим отсортированным массивом, чтобы проверить результат.

    Сравните элементы в 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

  4. Добавьте функцию с аргументами для сохранения массивов в журнале на каждом шаге, чтобы при неудачном тестировании можно было сравнить их и понять, как исправить тестируемый код.

     # Функция тестирования для сортировки массивов и профилирования кода.
 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)

     # Выводим на экран текущий, ожидаемый и результирующий массивы, чтобы упросить исправление кода.
     ProjectLog("Текущий: {ArrayToString(ActualArray)}")
     ProjectLog("Ожидаемый: {ArrayToString(ExpectedArray)}")
     ProjectLog("Результирующий: {ArrayToString(ResultArray)}")

     # Убеждаемся, что тест пройден и массив отсортирован, как требовалось.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

  5. Функция тестирования проверяет точность результата, но вы можете получить в рамках теста и дополнительную информацию. Используя выражение profile, вы можете измерять производительность алгоритмов, регистрируя время, за которое они решают задачи.

    Это удобно при сравнении производительности различных алгоритмов сортировки или тестировании работы алгоритмов на разных входных данных. Некоторые алгоритмы могут работать очень по-разному с данными, для которых они показывают наилучшие и наихудшие результаты, и профилирование позволяет выявлять и тестировать такие сценарии, чтобы знать, на что обратить внимание. Выполнив несколько тестов, вы можете оценить среднюю производительность алгоритма и характер его работы с входными данными любого размера.

  6. Добавьте аргумент типа string с именем 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)

     # Выводим на экран текущий, ожидаемый и результирующий массивы, чтобы упросить исправление кода.
     ProjectLog("Текущий: {ArrayToString(ActualArray)}")
     ProjectLog("Ожидаемый: {ArrayToString(ExpectedArray)}")
     ProjectLog("Результирующий: {ArrayToString(ResultArray)}")
    
     # Убеждаемся, что тест пройден и массив отсортирован, как требовалось.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

Запись сценариев тестирования

Начните с простого. Изолируйте ту часть кода, которую нужно протестировать. Протестируйте сортировку массива целых чисел от наименьшего значения к наибольшему.

  1. Создайте функцию сравнения целых чисел.

     # Функция сравнения, используемая в качестве аргумента при сортировке целых чисел от наименьшего к наибольшему.
 IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
     Left < Right

  2. Создайте вспомогательную функцию, преобразующую целочисленный массив в строку.

     # Вспомогательная функция, которая преобразует массив целочисленных значений в строку.
 IntArrayToString(Array:[]int)<transacts>:string=
     var ConvertedToString:string = "["
     for (Index -> Element : Array):
         set ConvertedToString += "{Element}"
         if (Index < Array.Length - 1):
             set ConvertedToString += ", "
     set ConvertedToString += "]"

  3. Создайте устройство 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("Один или несколько тестов дали неудачный результат.")

  4. Теперь заполните тестовые массивы значениями.

     var ArrayLength:int = GetRandomInt(10, 100)
         Test1ExpectedIntArray:[]int =
             for (Count := 0..ArrayLength):
             	Количество
         Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

  5. Запустите тест, перетащив 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("Один или несколько тестов дали неудачный результат.")

    # Функция тестирования для сортировки массивов и профилирования кода.
    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)

        # Выводим на экран текущий, ожидаемый и результирующий массивы, чтобы упросить исправление кода.
        ProjectLog("Текущий: {ArrayToString(ActualArray)}")
        ProjectLog("Ожидаемый: {ArrayToString(ExpectedArray)}")
        ProjectLog("Результирующий: {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
        Слева

Самостоятельная работа

  • Реализуйте другой алгоритм сортировки. Ссылки на реализации других алгоритмов:

  • Добавьте новые сценарии тестирования, чтобы расширить возможности программы тестирования. Вы не задумывались о пограничных случаях, которые программа тестирования пока не охватывает? А ведь есть ещё более сложные типы данных!

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page