Selección de tipos de datos

¿Alguna vez te has preguntado si se debería abordar el problema X con la estructura de datos Y o Z? Este artículo cubre una variedad de temas relacionados con estos dilemas.

Nota

Este artículo hace referencia a las operaciones de «tiempo-[algo]». Esta terminología proviene del análisis de algoritmos “ Big O Notation.

En resumen, describe el peor de los casos de duración del tiempo de ejecución. En términos simples:

«A medida que aumenta el tamaño de un dominio problemático, la duración del tiempo de ejecución del algoritmo…»

  • Tiempo-constante, O(1): «…no aumenta.»
  • Tiempo-logarítmico, O(log n): «…aumenta a un ritmo lento.»
  • Tiempo-lineal, O(n): «…aumenta a la misma frecuencia.»
  • Etc.

Imagínate si tuvieras que procesar 3 millones de puntos de datos en un solo fotograma. Sería imposible crear esta característica con un algoritmo de tiempo-lineal, ya que el gran tamaño de los datos aumentaría el tiempo de ejecución mucho más allá del tiempo asignado. En cambio, un algoritmo de tiempo-constante podría realizar la operación sin problemas.

En general, los desarrolladores quieren evitar participar en operaciones de tiempo lineal tanto como sea posible. Pero, si uno mantiene la escala de una operación de tiempo lineal reducida, y no es necesario realizar la operación con frecuencia, entonces podría ser aceptable. Equilibrar estos requisitos y elegir el algoritmo y la estructura de datos adecuados para el trabajo es parte de lo que hace que las habilidades de los programadores sean valiosas.

Array vs. Diccionario vs. Objeto

Godot almacena todas las variables del API de scripting en la clase Variant . Las Variants pueden guardar estructuras de datos compatible con Variant como Array y Dictionary y también Object.

Godot implementa Arrays como Vector<Variant>. El motor almacena el contenido del Array en secciones contínuas de memoria, es decir, están adyacentes uno con el otro en fila.

Nota

Para los que no están familiarizados con C++, Vector es el nombre del objeto array en las librerías tradicionales de C++. Se trata de un tipo de «plantilla», lo que significa que sus registros sólo pueden contener un tipo particular (indicado mediante corchetes angulares). Así, por ejemplo, un PoolStringArray sería algo así como un Vector<String>.

Los almacenes de memoria contiguos implican el siguiente rendimiento de la operación:

  • Iterate: El más rápido. Ideal para loops.

    • Op: Lo único que hace es incrementar un contador para llegar al siguiente registro.
  • Insert, Erase, Move: Depende de la posición. En general, es lento.

    • Op: Añadir/eliminar/mover contenido implica mover los registros adyacentes (para hacer espacio / ocupar espacio).

    • Añadir/eliminar rápidamente desde el final.

    • Añadir/eliminar lentamente desde una posición arbitraria.

    • Añadir/eliminar más lentamente desde el frente.

    • Si se hacen muchas inserciones/eliminaciones desde el frente, entonces…

      1. invertir el array.
      2. haz un bucle que ejecute los cambios del Array al final.
      3. reinvierte el array.

      Esto hace solo 2 copias del array (aun en tiempo constante, pero lento) en comparación a copiar alrededor de la mitad del array, en promedio, N veces (tiempo lineal).

  • Get, Set: Más rápido por posición. Por ejemplo, puedes solicitar el registro 0º, 2º, 10º, etc., pero no puedes especificar qué registro deseas.

    • Op: Una operación de adición desde el comienzo del array hasta la posición del índice deseado.
  • Find: El más lento. Identifica el índice/posición de un valor.

    • Op: Iterar a través del array y compara los valores hasta que encuentre una coincidencia.

      • El rendimiento también depende de si uno necesita una búsqueda exhaustiva o no.
    • Cuando se mantienen ordenadas, las operaciones de búsqueda personalizada pueden llegar a tiempo logarítmico (relativamente rápido). Sin embargo, los usuarios inexpertos no se sentirán cómodos con esto. Se hace reordenando el Array después de cada edición y escribiendo un algoritmo de búsqueda ordenado.

Godot implementa el Dictionary como un OrderedHashMap<Variant, Variant>. El motor almacena un array gigante (inicializado a 1000 registros) de pares clave-valor. Cuando uno intenta acceder a un valor, se entrega una clave. Por lo tanto, la clave es «hash», es decir, se convierte en un número. El «hash» se convierte en el índice del array, lo que permite al OHM una rápida consulta del valor dentro de la «tabla» conceptual de claves asignadas a valores.

Los «Hashes» son para reducir la posibilidad de una colisión de llaves. Si se produce uno, la tabla debe recalcular otro índice para el valor que tenga en cuenta la posición anterior. En total, esto resulta en un acceso constante a todos los registros a expensas de la memoria y de una menor eficiencia operativa.

  1. Hashing de cada clave un número arbitrario de veces.

    • Las operaciones Hash son constantes, así que incluso si un algoritmo debe hacer más de una, siempre y cuando el número de cálculos hash no dependa demasiado de la densidad de la tabla, las cosas se mantendrán rápidas. Lo que lleva a…
  2. Manteniendo un gran tamaño para la tabla.

    • La razón por la que comienza con 1000 registros, y la razón por la que fuerza grandes espacios de memoria sin usar intercalados en la tabla es para minimizar las colisiones de hash y mantener la velocidad de los accesos.

Como se puede ver, los Diccionarios se especializan en tareas que los Arrays no pueden realizar. A continuación se muestra un resumen general de los detalles operativos:

  • Iterate: Rápido.

    • Op: Iterar sobre el vector interno del mapa de hashes. Devuelve cada clave. Después, los usuarios utilizan la clave para saltar y devolver el valor deseado.
  • Insert, Erase, Move: Más rápido.

    • Op: Hash de la clave devuelta. Realiza una operación de adición para buscar el valor apropiado (inicio del array + offset). El desplazamiento consta de dos de estos dos pasos (uno para insertar y otro para borrar). El mapa debe hacer algún tipo de mantenimiento para conservar sus capacidades:

      • actualización ordenada de la Lista de registros.
      • determinará si la densidad de las tablas requiere ampliar la capacidad de las mismas.
    • El Diccionario recuerda en qué orden los usuarios insertaron sus claves. Esto le permite ejecutar iteraciones de forma segura.

  • Get, Set: El más rápido. Igual que una búsqueda por clave.

    • Op: Igual que insertar/borrar/mover.
  • Find: El más lento. Identifica la clave de un valor.

    • Op: Debe iterar a través de los registros y comparar el valor hasta que se encuentre una coincidencia.
    • Hay que tener en cuenta que Godot no proporciona esta característica out-of-the-box (porque no están pensados para esta tarea).

Godot implementa Objects como tontos, pero también como contenedores dinámicos de contenido de datos. Los objetos consultan las fuentes de datos cuando se plantean preguntas. Por ejemplo, para responder a la pregunta «¿tienes una propiedad llamada “position”?», podría preguntar su script o el ClassDB. Se puede encontrar más información sobre qué son los objetos y cómo funcionan en el artículo Godot scenes and scripts are classes.

The important detail here is the complexity of the Object’s task. Every time it performs one of these multi-source queries, it runs through several iteration loops and HashMap lookups. What’s more, the queries are linear-time operations dependent on the Object’s inheritance hierarchy size. If the class the Object queries (its current class) doesn’t find anything, the request defers to the next base class, all the way up until the original Object class. While these are each fast operations in isolation, the fact that it must make so many checks is what makes them slower than both of the alternatives for looking up data.

Nota

Cuando los desarrolladores mencionan lo lenta que es la API de scripting, se refieren a esta cadena de consultas. En comparación con el código C++ compilado, en el que la aplicación sabe exactamente dónde encontrar cualquier cosa, es inevitable que las operaciones de la API de secuencias de comandos tarden mucho más tiempo. Deben localizar la fuente de cualquier dato relevante antes de intentar acceder a ella.

La razón por la cual GDScript es lento es porque cada operación que realiza pasa a través de este sistema.

C# puede procesar parte de los contenidos a mayor velocidad mediante un bytecode más optimizado. Pero, si el script C# llama al contenido de una clase de motor o si el script intenta acceder a algo externo a él, pasará por este proceso.

NativeScript C++ va aún más lejos y mantiene todo interno por defecto. Las llamadas a estructuras externas pasarán por la API de scripting. En NativeScript C++, el registro de métodos para exponerlos a la API de scripting es una tarea manual. Es en este punto donde las clases externas, que no son de tipo C++, utilizarán la API para localizarlas.

Por lo tanto, asumiendo que uno se extiende desde Reference para crear una estructura de datos, como un Array o un Dictionary, ¿por qué elegir un Object en lugar de las otras dos opciones?

  1. Control: Con objetos se tiene la capacidad de crear estructuras más sofisticadas. Se pueden realizar abstracciones en capas sobre los datos para asegurar que la API externa no cambie en respuesta a los cambios en la estructura de los datos internos. Además, los objetos pueden tener señales, lo que permite un comportamiento reactivo.
  2. Claridad: Los objetos son una fuente de datos confiable cuando se trata de los datos que los scripts y las clases de motor definen para sí mismos. Las propiedades pueden no tener los valores que uno espera, pero uno no necesita preocuparse de si la propiedad existe en primer lugar.
  3. Conveniencia: Si ya se tiene una estructura de datos similar en mente, entonces extenderse desde una clase existente hace que la tarea de construir la estructura de datos sea mucho más fácil. En comparación, los Arrays y Diccionarios no satisfacen todos los casos de uso que uno pueda tener.

Los objetos también ofrecen a los usuarios la oportunidad de crear estructuras de datos aún más especializadas. De esta forma, uno puede diseñar su propia List, Binary Search Tree, Heap, Splay Tree, Graph, Disjoint Set, y cualquier otra opción.

«¿Por qué no usar Node para estructuras de árbol?», uno podría preguntarse. Bueno, la clase Node contiene cosas que no serán relevantes para la estructura de datos personalizada de cada quien. Como tal, puede ser útil construir un tipo de nodo propio al construir estructuras de árbol.

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)
    {
        if (what == NotificationPredelete)
        {
            foreach (object child in _children)
            {
                TreeNode node = child as TreeNode;
                if (node != null)
                    node.Free();
            }
        }
    }
}

A partir de aquí, uno puede crear sus propias estructuras con características específicas, limitadas sólo por su imaginación.

Enumeraciones: int vs. string

La mayoría de los idiomas ofrecen una opción de tipo de enumeración. GDScript no es diferente, pero a diferencia de la mayoría de los otros lenguajes, permite usar enteros o strings para los valores numéricos. Entonces surge la pregunta, «¿qué se debe usar?»

La respuesta corta es: «Con el que te sientas más cómodo». Esta es una característica específica de GDScript y no de Godot scripting en general; los lenguajes priorizan la usabilidad sobre el rendimiento.

A nivel técnico, las comparaciones entre enteros (tiempo-constante) serán más rápidas que las comparaciones entre strings (tiempo-lineal). Sin embargo, si uno quiere mantener las convenciones de otros idiomas, entonces debería usar enteros.

El problema principal con el uso de enteros surge cuando uno quiere imprimir un valor numérico. Como enteros, al intentar imprimir MY_ENUM se imprimirá 5 o lo que sea, en lugar de algo como "MyEnum". Para imprimir un entero, uno tendría que escribir un Diccionario que mapea el valor de la cadena correspondiente para cada enumeración.

Si el propósito principal de usar una enumeración es para imprimir valores y uno desea agruparlos en conceptos relacionados, entonces tiene sentido usarlos como strings. De esta manera, no es necesaria una estructura de datos separada para ejecutar en la impresión.

AnimatedTexture vs. AnimatedSprite vs. AnimationPlayer vs. AnimationTree

¿Bajo qué circunstancias se debe utilizar cada una de las clases de animación de Godot? La respuesta puede no ser muy clara para los nuevos usuarios de Godot.

AnimatedTexture es una textura que el motor dibuja como un bucle animado en lugar de una imagen estática. Los usuarios pueden manipular…

  1. la velocidad a la que se mueve a través de cada sección de la textura (fps).
  2. el número de regiones que contiene la textura (frames).

Godot’s VisualServer entonces dibuja las regiones en secuencia a la tasa establecida. La buena noticia es que esto no implica ninguna lógica adicional por parte del motor. La mala noticia es que los usuarios tienen muy poco control.

Also note that AnimatedTexture is a Resource unlike the other Node objects discussed here. One might create a Sprite node that uses AnimatedTexture as its texture. Or (something the others can’t do) one could add AnimatedTextures as tiles in a TileSet and integrate it with a TileMap for many auto-animating backgrounds that all render in a single batched draw call.

The AnimatedSprite node, in combination with the SpriteFrames resource, allows one to create a variety of animation sequences through spritesheets, flip between animations, and control their speed, regional offset, and orientation. This makes them well-suited to controlling 2D frame-based animations.

Si uno necesita desencadenar otros efectos en relación a distintos cambios de animación (por ejemplo, crear efectos de particulas, llamar funciones, o manipular otros elementos periféricos ademas de las animaciones basadas en cuadros), entonces se necesita usar un nodo de AnimationPlayer en conjunto con el AnimatedSprite.

AnimationPlayers también es la herramienta que uno necesita utilizar si se desea diseñar sistemas de animación 2D mas complejos, como…

  1. Animaciones recortadas: editando las transformaciones de los sprites en el momento de la ejecución.
  2. 2D Mesh animations: defining a region for the sprite’s texture and rigging a skeleton to it. Then one animates the bones which stretch and bend the texture in proportion to the bones” relationships to each other.
  3. Una mezcla de lo de arriba.

Mientras uno necesita un AnimationPlayer para diseñar cada una de las secuencias de animaciones para un juego, también puede ser util combinar animaciones para mezclar, por ejemplo, habilitando transiciones suaves entre estas animaciones. Tambien puede haber una estructura jerárquica entre las animaciones que uno planea para su objeto, Estos son los casos donde el AnimationTree brilla. Uno puede encontrar una guía en profundidad en usar el AnimationTree en AnimationTree aquí.