Este blog es una continuación de Estructuras de datos - Básico Parte 1

Introducción

En este blog aprenderemos trabajar con listas de forma óptima, empezaremos a utilizar métodos de búsqueda, y daremos una introducción a los enumeradores.

Cuando definimos una estructura se debe a que vamos a crear múltiples objetos de un mismo tipo para un mismo propósito, estas estructuras se suelen consumir haciendo uso de bucles, el problema es cuando necesitamos filtrar la información de la estructura para evitar tener condiciones dentro del bucle, para este tipo de tarea en .NET se suele implementar Linq, pero esto es una mala idea si lo que estamos buscando es velocidad y rendimiento, es por eso, que intentaremos explicar como crear implementaciones personalizadas de alto rendimiento.

Implementación

Imaginemos que nuestro juego tiene un lista del tipo abstracto EntityNPC, para la lógica de nuestro juego necesitamos obtener e iterar todos los NPC activos.

Estructura inicial.

public abstract class EntityNPC
{
    public bool IsActive { get; set; }
}

public class EntityContainer
{
    public List<EntityNPC> Entitys = new List<EntityNPC>();
}

Para poder filtrar información de la lista implementaremos un IEnumerable, donde el parámetro será un método encapsulado (Func<T, R>) que usaremos para crear nuestra query.

Implementación en la clase EntityContainer

public IEnumerable<EntityNPC> Where(Func<EntityNPC, bool> query)
{
  for(int i = 0; i < Entitys.Count; i++)
    if (query(Entitys[i]))
      yield return Entitys[i];
}

Ahora podemos filtrar los elementos de la lista antes de ser iterados.

foreach(EntityNPC entity in Where(x => x.IsActive))
{

}

Los IEnumerables tienen un gran potencial, es importante leer la documentación oficial.

Pruebas de rendimiento

Para poder finalizar me gustaría compartir una pequeña prueba que realice implementando este sistema. Se realizó la prueba con una lista de 100.000 elementos.

1. Utilizando Bucle FOR y filtrando el contenido dentro con un IF. (vs) Implementación personalizada.
   
   La implementación personalizada tiene un mayor costo, pero genera menos basura.
    
2. Filtrando contenido con Linq.Where (vs) Implementación personalizada.
   
   Ambos tienen el mismo costo, pero se puede apreciar que la implementación personalizada genera la mitad de basura.
    
3. Contador de elementos aplicando filtros.
   
   La primer evaluación se trata de la implementación completa con Linq, generando 200B de basura.
   La segunda evaluación se trata de la implementación de Where Personalizado y el contador de Linq, generando 128B.
   La tercer evaluación se trata de la implementación de un Contador personalizado, generando 0B.