Data preferences

Вы когда-нибудь задумывались, следует ли подходить к проблеме X со структурой данных Y или Z? В этой статье рассматриваются различные темы, связанные с этими дилеммами.

Примечание

В этой статье есть ссылки на операции "[что-то] -время". Эта терминология взята из анализа алгоритмов Big O Notation.

Короче говоря, он описывает наихудший сценарий продолжительности времени выполнения. Проще говоря:

«По мере увеличения размера проблемной области время выполнения алгоритма ...»

  • Постоянное время, O(1): "...не увеличивается."

  • Логарифмическое время, O(log n): "... увеличивается с медленной скоростью."

  • Линейное время, O(n): "... увеличивается с той же скоростью."

  • И т.п.

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

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

Массив против словаря против объекта

Godot хранит все переменные в API сценариев в классе Variant. Варианты могут хранить Variant-совместимые структуры данных, такие как Array и Dictionary, а также Object.

Godot реализует массив как Vector<Variant>. Движок хранит содержимое массива в непрерывном разделе памяти, то есть они находятся в строке рядом друг с другом.

Примечание

Для тех, кто не знаком с C++, вектор - это имя объекта массива в традиционных библиотеках C++. Это "шаблонный" тип, что означает, что его записи могут содержать только определенный тип (обозначенный угловыми скобками). Так, например, a PoolStringArray будет чем-то вроде `` Vector <String>``.

Непрерывные хранилища памяти подразумевают следующую производительность операций:

  • Итерация: Самый быстрый. Отлично подходит для циклов.

    • Операции: всё, что он делает, это увеличивает счётчик, чтобы перейти к следующей записи.

  • Вставка, стирание, перемещение: В зависимости от позиции. Обычно медленно.

    • Операции: добавление/удаление/перемещение содержимого включает перемещение соседних записей (чтобы освободить место/заполнить пространство).

    • Быстрое добавление/удаление с конца.

    • Медленное добавление/удаление из произвольной позиции.

    • Самое медленное добавление/удаление спереди.

    • Если делать много вставок/удалений спереди, то ...

      1. инвертировать массив.

      2. выполнить цикл, который выполняет изменения массива в конце.

      3. повторно инвертировать массив.

      Это делает только 2 копии массива (по-прежнему с постоянным временем, но медленно) по сравнению с копированием примерно 1/2 массива, в среднем, N раз (линейное время).

  • Get, Set: Fastest by position. E.g. can request 0th, 2nd, 10th record, etc. but cannot specify which record you want.

    • Операции: 1 операция сложения от начальной позиции массива до желаемого индекса.

  • Поиск: Самый медленный. Определяет индекс/позицию значения.

    • Операции: необходимо перебирать массив и сравнивать значения, пока не будет найдено совпадение.

      • Производительность также зависит от того, нужен ли вам исчерпывающий поиск.

    • Если сохранять порядок, пользовательские операции поиска могут привести его к логарифмическому времени (относительно быстро). Однако пользователям-непрофессионалам это не понравится. Выполняется путем повторной сортировки массива после каждого редактирования и написания алгоритма поиска с упорядочением.

Godot реализует словарь как OrderedHashMap<Variant, Variant>. Движок хранит небольшой массив (инициализированный 2^3 = 8 записями) пар ключ-значение. Когда кто-то пытается получить доступ к значению, они предоставляют ему ключ. Затем он хеширует ключ, т.е. преобразует его в число. «Хеш» используется для вычисления индекса в массиве. В качестве массива OHM затем выполняет быстрый поиск в «таблице» ключей, сопоставленных со значениями. Когда HashMap становится слишком полным, он увеличивается до следующей степени 2 (так, 16 записей, затем 32 и т.д.) и перестраивает структуру.

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

  1. Хеширование каждого ключа произвольное количество раз.

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

  2. Поддержание постоянно растущего размера стола.

    • HashMaps сохраняют промежутки неиспользуемой памяти, разбросанные по таблице, с целью уменьшения хеш-коллизий и поддержания скорости доступа. Вот почему он постоянно увеличивается в размере квадратично в степени 2.

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

  • Итерация: Быстро.

    • Операции: обойти внутренний вектор хешей карты. Вернуть каждый ключ. После этого пользователи используют клавишу, чтобы перейти к желаемому значению и вернуть его.

  • Вставка, стирание, перемещение: Самый быстрый.

    • Операции: Хешировать данный ключ. Выполнить 1 операцию сложения, чтобы найти соответствующее значение (начало массива + смещение). Ход - два таких (одна вставка, одна стирание). Карта должна быть обновлена, чтобы сохранить свои возможности:

      • обновить упорядоченный список записей.

      • определить, требует ли плотность стола необходимость увеличения вместимости стола.

    • Словарь запоминает, в каком порядке пользователи вставляли его ключи. Это позволяет ему выполнять надежные итерации.

  • Получить, установить: Самый быстрый. То же, что и поиск по ключу.

    • Операции: То же, что и вставка/стирание/перемещение.

  • Поиск: Самый медленный. Определяет индекс/позицию значения.

    • Операции: необходимо перебирать записи и сравнивать значение, пока не будет найдено совпадение.

    • Обратите внимание, что Godot не предоставляет эту функцию "из коробки" (потому что она не предназначены для этой задачи).

Godot реализует Объекты как глупые, но динамические контейнеры содержимого данных. Объекты запрашивают источники данных, когда задают вопросы. Например, чтобы ответить на вопрос "есть ли у вас свойство под названием 'position'?", Он может спросить его script или ClassDB. Более подробную информацию о том, что такое объекты и как они работают, можно найти в статье Применение объектно-ориентированного подхода в Godot.

Важной деталью здесь является сложность задачи Объекта. Каждый раз, когда он выполняет один из этих запросов с несколькими источниками, он проходит через несколько итерационных циклов и поисков HashMap. Более того, запросы представляют собой линейные операции, зависящие от размера иерархии наследования объекта. Если класс, который запрашивает Object (его текущий класс), ничего не находит, запрос передается следующему базовому классу, вплоть до исходного класса Object. Хотя каждая из этих операций является быстрой по отдельности, тот факт, что она должна выполнять так много проверок, делает их медленнее, чем обе альтернативы для поиска данных.

Примечание

Когда разработчики упоминают, насколько медленным является API сценариев, они ссылаются именно на эту цепочку запросов. По сравнению с скомпилированным кодом C++, в котором приложение точно знает, куда идти, чтобы что-то найти, операции API сценариев неизбежно займут гораздо больше времени. Они должны найти источник любых соответствующих данных, прежде чем они смогут попытаться получить к нему доступ.

Причина по кторой GDScript работает медленно это потому что каждоыа операцыа дожна проходит через эту систему.

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

NativeScript C++ идет еще дальше и по умолчанию сохраняет все внутри. Вызовы во внешние структуры будут проходить через скриптовый API. В NativeScript C++ регистрация методов для предоставления их скриптовому API выполняется вручную. Именно в этот момент внешние классы, не относящиеся к C++, будут использовать API для их поиска.

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

  1. Control: С объектами появляется возможность создавать более сложные структуры. Можно накладывать абстракции на данные, чтобы гарантировать, что внешний API не изменится в ответ на изменения внутренней структуры данных. Более того, объекты могут иметь сигналы, позволяющие реагировать на них.

  2. Clarity: Объекты являются надежным источником данных, когда речь идет о данных, которые для них определяют сценарии и классы движка. Свойства могут не содержать ожидаемых значений, но не нужно беспокоиться о том, существует ли это свойство вообще.

  3. Convenience: Если кто-то уже имеет в виду аналогичную структуру данных, то расширение существующего класса значительно упрощает задачу построения структуры данных. Для сравнения: массивы и словари не подходят для всех возможных вариантов использования.

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

"Почему бы не использовать Node для древовидных структур?" можно спросить. Ну, класс Node содержит вещи, которые не имеют отношения к пользовательской структуре данных. Таким образом, при построении древовидных структур может быть полезно создать собственный тип узла.

extends Object
class_name TreeNode

var _parent : TreeNode = null
var _children : = [] setget

func _notification(p_what):
    match p_what:
        NOTIFICATION_PREDELETE:
            # Destructor.
            for a_child in _children:
                a_child.free()
// Can decide whether to expose getters/setters for properties later
public class TreeNode : Object
{
    private TreeNode _parent = null;

    private object[] _children = new object[0];

    public override void Notification(int what)
    {
        switch (what)
        {
            case NotificationPredelete:
                foreach (object child in _children)
                {
                    TreeNode node = child as TreeNode;
                    if (node != null)
                        node.Free();
                }
                break;
            default:
                break;
        }
    }
}

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

Перечисления: int vs. string

Большинство языков предлагают выбор типа перечисления. GDScript ничем не отличается, но, в отличие от большинства других языков, позволяет использовать для значений перечисления либо целые числа, либо строки (последнее только при использовании ключевого слова export в GDScript). Тогда возникает вопрос: "какой использовать?"

Короткий ответ: «то, что вам удобнее». Это особенность, специфическая для GDScript, а не для скриптов Godot в целом; Языки ставят удобство использования выше производительности.

На техническом уровне, сравнения целых чисел (время константы) будут происходить быстрее, чем сравнения строк (линейное время). Однако, если кто-то хочет сохранить конвенции других языков, то следует использовать целые числа.

Основная проблема с использованием целых чисел возникает, когда кто-то хочет распечатать значение перечисления. В качестве целых чисел при попытке вывести MY_ENUM будет выведено 5 или что-то ещё, а не что-то вроде «MyEnum». Чтобы напечатать целочисленное перечисление, нужно написать словарь, который отображает соответствующее строковое значение для каждого перечисления.

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

AnimatedTexture против AnimatedSprite против AnimationPlayer против AnimationTree

При каких обстоятельствах следует использовать каждый из классов анимации Godot? Ответ может быть не сразу понятен новым пользователям Godot.

AnimatedTexture - это текстура, которую движок рисует как анимированный цикл, а не как статическое изображение. Пользователи могут манипулировать ...

  1. скорость, с которой он перемещается по каждому участку текстуры (кадров в секунду).

  2. количество областей, содержащихся в текстуре (кадрах).

Затем VisualServer Godot'а последовательно рисует регионы с заданной скоростью. Хорошая новость заключается в том, что это не требует дополнительной логики со стороны движка. Плохая новость в том, что у пользователей очень мало контроля.

Также обратите внимание, что AnimatedTexture является Resource в отличие от других Node объектов, обсуждаемых здесь. Можно создать узел Sprite, который использует AnimatedTexture в качестве текстуры. Или (что не могут сделать другие) можно добавить AnimatedTexture в виде тайлов в TileSet и интегрировать его с TileMap для многих автоанимированных фонов, которые все визуализируют в одном вызове пакетной отрисовки.

Узел AnimatedSprite в сочетании с ресурсом SpriteFrames позволяет создавать различные последовательности анимации с помощью таблиц спрайтов, переключаться между анимациями и управлять их скоростью, региональным смещением и ориентацией. Это делает их удобными для управления 2D-анимацией на основе кадра.

Если нужно запускать другие эффекты в связи с изменениями анимации (например, создавать эффекты частиц, вызывать функции или манипулировать другими периферийными элементами помимо покадровой анимации), тогда необходимо использовать AnimationPlayer узел в сочетании с AnimatedSprite.

AnimationPlayers - это также инструмент, который необходимо использовать, если они хотят создавать более сложные системы 2D-анимации, такие как ...

  1. Cut-Out animations: редактирование преобразований спрайтов во время выполнения.

  2. 2D Mesh animations: определение области для текстуры спрайта и привязка к ней скелета. Затем анимируются кости, которые растягивают и изгибают текстуру пропорционально соотношению костей друг с другом.

  3. Смесь вышеперечисленного.

Несмотря на то, что для разработки каждой отдельной последовательности анимации для игры нужен AnimationPlayer, также может быть полезно комбинировать анимации для смешивания, то есть для обеспечения плавных переходов между этими анимациями. Также может существовать иерархическая структура между анимациями, которую человек планирует для своего объекта. Это случаи, когда светится AnimationTree. Можно найти подробное руководство по использованию AnimationTree здесь.