En nuestras aplicaciones, es relativamente frecuente tener que buscar una serie de valores dentro de un conjunto de datos. Existen muchos escenarios, como cuando tenemos que buscar una serie de palabras dentro de un texto largo, o comprobar si todos los caracteres de un string pertenecen a un conjunto de caracteres válidos.

Por ejemplo, centrándonos en este último caso, imaginad que queremos comprobar si el contenido de una cadena de texto de tamaño arbitrario contiene únicamente una serie de caracteres válidos (por ejemplo, las vocales). La implementación que se nos ocurriría de forma natural sería muy simple: recorrer la cadena de texto de entrada, y, por cada carácter, comprobar si está en el conjunto de caracteres permitidos. ¿Fácil, no?

Sin embargo, como veremos en este post, hay formas mucho más eficientes de hacerlo.

Vamos a llegar a ellas partiendo de la implementación con la que muchos de nosotros daríamos por solucionado el problema:

var onlyVowels = "aaeeiioouu";
var notOnlyVowels = "aaeeiioouuXX";

Console.WriteLine(StringHasOnlyVowelsUsingLoop(onlyVowels)); // True
Console.WriteLine(StringHasOnlyVowelsUsingLoop(notOnlyVowels)); // False

bool StringHasOnlyVowelsUsingLoop(string stringToCheck)
{
    foreach (var c in stringToCheck)
    {
        if (c != 'a' && c != 'e' && c != 'i' && c != 'o' && c != 'u') return false;
    }
    return true;
}

O, si tenemos una tendencia más funcional, quizás podríamos haber escrito la siguiente implementación:

public bool StringHasOnlyVowelsUsingLinq(string stringToCheck)
{
    return stringToCheck.All(c => c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

Ambas implementaciones podrían ser válidas para búsquedas sobre conjuntos muy pequeños y conocidos de antemano, como en el ejemplo que estamos implementado. Sin embargo, son claramente insuficientes si nuestras necesidades crecen, porque, entre otras cosas, son poco escalables y difíciles de mantener (no en el caso de las vocales, pero sí si el conjunto de caracteres permitidos es más grande).

Con esto en mente, sin duda parece una buena idea almacenar los caracteres permitidos en un array o lista y buscarlos ahí, en lugar de tener que ir haciendo la comprobación manualmente por cada elemento.

Y probablemente llegaríamos también a la conclusión de que es mejor generalizar estas funciones un poco, haciendo que el conjunto de caracteres permitidos sea también un parámetro de entrada. De esta forma, podríamos reutilizar la función para buscar cualquier conjunto de caracteres en la cadena de texto de entrada:

bool StringHasOnlyValidCharsUsingLoop(string stringToCheck, char[] validChars)
{
    foreach (var c in stringToCheck)
    {
        if (!validChars.Contains(c)) return false;
    }
    return true;
}

O la versión equivalente con LINQ:

bool StringHasOnlyValidCharsUsingLinq(string stringToCheck, char[] validChars)
{
    return stringToCheck.All(c => validChars.Contains(c));
}

Ambas opciones cumplirían sobradamente nuestros requisitos funcionales, pero en ese punto es interesante hacer una parada para compararlas con BenchmarkDotNet y ver cuál es la más eficiente:

| Method                           | StringToCheck | Mean     | Error    | StdDev   | Allocated |
|--------------------------------- |-------------- |---------:|---------:|---------:|----------:|
| StringHasOnlyValidCharsUsingLoop | aaeeiioouu    | 53.22 ns | 0.363 ns | 0.283 ns |         - |
| StringHasOnlyValidCharsUsingLinq | aaeeiioouu    | 71.34 ns | 1.033 ns | 0.967 ns |      96 B |
| StringHasOnlyValidCharsUsingLoop | aaeeiioouuXX  | 58.20 ns | 0.515 ns | 0.481 ns |         - |
| StringHasOnlyValidCharsUsingLinq | aaeeiioouuXX  | 83.64 ns | 0.996 ns | 0.931 ns |      96 B |

Como se puede observar, la implementación con un loop es más eficiente en términos de CPU y uso de memoria que la implementación con LINQ, tanto cuando pasamos un string que sólo tiene vocales como cuando no es así. Por tanto, en este momento podríamos llegar a la conclusión de que esta es la mejor implementación posible... ¿o no?

Búsquedas con spans

Introducida con .NET Core 2.1, la estructura Span<T>, está diseñada para trabajar con datos contiguos en memoria de forma segura y muy eficiente. Por ejemplo, dispone de métodos (extensores, en su mayor parte) que permite realizar búsquedas muy optimizadas, principalmente porque puede utilizar las características avanzadas del hardware donde está corriendo la aplicación, como vectorización o SIMD (Single Instruction, Multiple Data) para acelerar las operaciones.

De hecho, usando esta estructura podemos conseguir mejorar la eficiencia del método anterior de forma significativa:

bool StringHasOnlyValidCharsUsingSpans(string stringToCheck, char[] validChars)
{
    return stringToCheck.AsSpan().IndexOfAnyExcept(validChars) == -1;
}

El método AsSpan() retorna una referencia de sólo lectura a la memoria donde se encuentra almacenada la cadena de texto a comprobar. Luego, usamos el método IndexOfAnyExcept() para buscar la primera ocurrencia de un carácter que no esté en el conjunto de caracteres permitidos. Si no encuentra ninguno, retorna -1, lo que significa que todos los caracteres de la cadena de texto pertenecen al conjunto de caracteres permitidos.

Sorprendentemente, esta implementación es como mínimo siete veces más rápida que la más óptima de las opciones que vimos antes y no usa memoria adicional como se puede comprobar en los resultados, de nuevo obtenidos con BenchmarkDotNet:

| Method                           | StringToCheck | Mean     | Error   | StdDev  | Allocated |
|--------------------------------- |-------------- |---------:|--------:|--------:|----------:|
| StringHasOnlyValidCharsUsingLoop | aaeeiioouu    | 53.69 ns | 0.49 ns | 0.46 ns |         - |
| StringHasOnlyValidCharsUsingSpan | aaeeiioouu    |  7.75 ns | 0.05 ns | 0.04 ns |         - |
| StringHasOnlyValidCharsUsingLoop | aaeeiioouuXX  | 58.36 ns | 0.90 ns | 0.84 ns |         - |
| StringHasOnlyValidCharsUsingSpan | aaeeiioouuXX  |  8.09 ns | 0.07 ns | 0.07 ns |         - |

¿Aún se puede superar esto?

La clase SearchValues

.NET 8 introdujo la clase SearchValues, una estructura que permite almacenar valores que después buscaremos en un conjunto de datos. Al igual Span<T>, este tipo es muy eficiente y está optimizado para trabajar con datos almacenados en memoria utilizando características avanzadas de los procesadores actuales, pero, al estar especializada en búsquedas, puede ser aún más eficiente que Span<T> en este tipo de operaciones.

La forma de utilizarlo es bien sencilla: basta crear una instancia de la clase SearchValues usando su método estático Create() y pasarle los valores que queremos buscar. Esto retornará la instancia configurada expresamente para usar la opción más eficiente en función de los valores que le hemos pasado y el hardware disponible (podéis verlo echando un vistazo a su código fuente).

SearchValues<char> searchValues = SearchValues.Create("aeiou");

Ojo, porque estas comprobaciones previas se realizan al construir la instancia de SearchValues y tienen un coste de proceso, pero se amortiza rápidamente si vamos a realizar varias búsquedas de los mismos valores en diferentes conjuntos de datos.

Una vez creada la instancia de SearchValues, podremos utilizarla tantas veces como necesitemos para buscar esos valores en cualquier conjunto de datos. Por ejemplo, podemos crear una nueva iteración del método con el que venimos trabajando:

bool StringHasOnlyValidCharsUsingSearchValues(string stringToCheck, SearchValues searchValues)
{
    return stringToCheck.AsSpan().IndexOfAnyExcept(searchValues) == -1;
}

Vamos a comparar su eficiencia con las implementaciones anteriores:

| Method                                   | StringToCheck | Mean     | Error   | StdDev  | Allocated |
|----------------------------------------- |---------------|---------:|--------:|--------:|----------:|
| StringHasOnlyValidCharsUsingLoop         | aaeeiioouu    | 52.68 ns | 3.18 ns | 0.17 ns |         - |
| StringHasOnlyValidCharsUsingSpan         | aaeeiioouu    |  7.64 ns | 0.50 ns | 0.02 ns |         - |
| StringHasOnlyValidCharsUsingSearchValues | aaeeiioouu    |  2.01 ns | 0.22 ns | 0.01 ns |         - |
| StringHasOnlyValidCharsUsingLoop         | aaeeiioouuXX  | 58.01 ns | 8.05 ns | 0.44 ns |         - |
| StringHasOnlyValidCharsUsingSpan         | aaeeiioouuXX  |  8.16 ns | 0.31 ns | 0.01 ns |         - |
| StringHasOnlyValidCharsUsingSearchValues | aaeeiioouuXX  |  2.67 ns | 0.34 ns | 0.01 ns |         - |

¡Uau! Prácticamente cuatro veces más rápido que la implementación con Span<T>, lo que quiere decir que es más de veinticinco veces mejor que el método que todos habríamos implementado para resolver el problema inicial, usando un simple bucle. Brutal, ¿eh? 🙂

Consideraciones finales

Aunque en este post hemos visto cómo usar SearchValues para buscar caracteres en una cadena de texto, esta estructura permite también realizar búsquedas en spans de bytes, y, desde .NET 9, incluso buscar cadenas de texto completas.

También, hemos utilizado el método IndexOfAnyExcept() para buscar caracteres que no estén en el conjunto de caracteres permitidos, pero SearchValues puede utilizarse otros métodos de Span<T> como IndexOfAny(), IndexOf() o LastIndexOf(), entre otros, por lo que su ámbito de utilización es mucho más amplio.

¿Y quiere todo esto decir que tenemos que usar Span o SearchValues siempre que estemos ante estos escenarios? Por supuesto que no. Las implementaciones "tradicionales" son válidas en la mayoría de los casos y, en general, son más fáciles de entender y mantener por la mayoría de los desarrolladores.

Sin embargo, si estamos trabajando en un escenario donde la eficiencia es crítica, sí que son herramientas que deberíamos tener en cuenta. Por ejemplo, SearchValues es utilizada extensivamente en la propia implementación de .NET y frameworks como ASP.NET Core, aportando su granito de arena a las espectaculares mejoras de rendimiento que vamos viendo versión tras versión.

Publicado en Variable not found.