- Vistas y acciones, ejemplos 1 (generate_n, group_by, sort, to) y 2 (filter)
- Ejemplos 3 (enumerate, shuffle, take, zip) y 4 (intersperse, tokenize)
- Ejemplos 5 (getlines, transform) y 6 (iota, set_difference, split_when)
- Ejemplo 7 (stable_partition, subrange)
- Ejemplo 8 (concat, drop, generate, take_while)
- Ejemplos 9 (cycle) y 10 (keys, values)
- Ejemplo 11 (cartesian_product)
En este post proporcionaremos dos nuevos ejemplos de programación con la biblioteca Range-v3, un subconjunto de la cual ha sido adoptada por el nuevo estándar del lenguaje C++20. Pueden consultarse los espacios de nombres utilizados por este artículo en el primer post de la serie.
Ejemplo 3: enumerate, shuffle, take, zip
Consideremos los siguientes dos vectores, que contienen los nombres de varios personajes de ficción:
auto heroes = vector<string>{
"Sherlock Holmes",
"Ulysses",
"Gandalf",
"Dr Jekyll",
"Edmond Dantes"
};
auto villains = vector<string>{
"Professor Moriarty",
"Sirens",
"Witch-king of Angmar",
"Mr Hyde",
"Fernand Mondego"
};
Si bien desde el punto de vista literario existe una correspondencia uno-a-uno entre los héroes y los villanos anteriores, planteémonos la posibilidad de barajar ambos vectores con el fin de enfrentar a tres parejas inesperadas de personajes. ¿Qué ocurriría si Gandalf el Gris tuviese que medir sus artes contra el profesor Moriarty? Una vez más, la biblioteca Range-v3 nos permite atacar este problema con un estilo de programación esencialmente funcional, a través de una concatenación de acciones y vistas. Junto a <range/v3/core.hpp>, incluiremos los siguientes ficheros de cabecera:
A continuación, implementaremos el siguiente código sencillo:
#include <range/v3/action/shuffle.hpp>
#include <range/v3/view/const.hpp>
#include <range/v3/view/enumerate.hpp>
#include <range/v3/view/take.hpp>
#include <range/v3/view/zip.hpp>
A continuación, implementaremos el siguiente código sencillo:
for (
auto gen = mt19937{random_device{}()}; // (A)
auto [idx, hv] : rv::zip( // (B)
(heroes |= ra::shuffle(gen)), // (C)
(villains |= ra::shuffle(gen)) // (D)
) | rv::take(3) // (E)
| rv::const_ // (F)
| rv::enumerate // (G)
) {
auto [hero, villain] = hv; // (H)
print("{}. {:<15} vs {}\n", ++idx, hero, villain);
}
Este bucle for basado en rango --con un nuevo formato permitido por C++20-- inicializa en primer lugar un generador de números aleatorios basado en el algoritmo Mersenne Twister, disponible en el fichero de cabecera estándar <random> (A). A continuación, los vectores de héroes y villanos son sometidos a acciones shuffle con el fin de barajar in situ sus contenidos [(C) y (D)]. La vista zip, aplicada en (B) a los dos vectores mutados, produce un nuevo rango en el que el n-ésimo elemento constituye una 2-tupla con referencias a los correspondientes elementos n-ésimos de dichos vectores [1]. Esta vista es adaptada nuevamente en (E), con el fin de seleccionar (take) las tres primeras parejas de personajes de las cinco disponibles. Dado que sólo deseamos realizar operaciones de lectura sobre los strings referenciados, hacemos uso de const_ para obtener una vista constante de los rangos fuente (F). Finalmente, enumeramos las tres parejas de personajes así producidas mediante una vista enumerate (G).
El bucle hace uso de la declaración structured binding [idx, hv] propia de C++17 para nombrar e iterar las sucesivas parejas de índices idx y 2-tuplas de strings hv a visitar. Cada 2-tupla hv es a su vez descompuesta mediante un structured binding adicional en (H) con el fin de acceder a los nombres de los personajes (héroe y villano). Un posible resultado aleatorio mostrado por la terminal podría ser, así:
1. Edmond Dantes vs Sirens
2. Sherlock Holmes vs Witch-king of Angmar
3. Gandalf vs Professor Moriarty
A modo de comentario final, indicar que puede comprobarse que el bucle anterior trabaja en todo momento con referencias a los vectores de personajes originales añadiendo aserciones como assert(&hero == &heroes[idx]) antes de la operación print.
Ejemplo 4: intersperse, tokenize
En este nuevo código de ejemplo nos proponemos determinar las frecuencias de uso de las distintas palabras en un texto. En particular, deseamos mostrar por la terminal las cinco mayores frecuencias de ocurrencia, acompañando cada una de ellas con el listado de palabras que se repiten en el texto dicho número de veces. Para ello, proporcionaremos en primer lugar una función que, de forma eficiente, traslade todo el contenido de un archivo a un string en memoria:
[[nodiscard]] auto file_to_string(char const* filename) -> string
{
auto in = ifstream{};
in.exceptions(ifstream::failbit | ifstream::badbit);
in.open(filename, ios::binary);
auto contents = string{};
in.seekg(0, ios::end);
if (auto const sz = streamoff{in.tellg()}; sz > 0) { // sz es entero con signo
contents.resize(sz); // bloque de memoria contigua desde C++11
in.seekg(0, ios::beg);
in.read(&contents[0], sz);
}
return contents;
}
Nuestro objetivo es crear un mapa freq_tokens_map que asocie a cada frecuencia de uso un vector con las palabras del texto que se repitan dicho número de veces. Escogeremos ranges::greater como política de ordenación de claves a fin de que las frecuencias queden registradas de mayor a menor:
using Freq_tokens_map = map<size_t, vector<string>, rn::greater>;
auto const freq_tokens_map = /* IILE */ []()-> Freq_tokens_map {
auto tokens = /* IILE */ []{
auto const path = /* literal de cadena que indique la dirección del texto */;
auto text = file_to_string(path)
| ra::transform([](unsigned char c){ return tolower(c); }); // (A)
return text | rv::tokenize(regex{R"([\w]+)"}) // (B)
| rn::to<vector<string>>; // (C)
}();
auto res = Freq_tokens_map{};
for (auto grp : (tokens |= ra::sort) | rv::group_by(equal_to{})) // (D)
res[rn::distance(grp)].push_back(*grp.begin()); // (E)
return res;
}();
En el código anterior, tokens es un vector de strings que recoge, una a una, las distintas palabras empleadas en el texto. Para generarlo, almacenamos el texto completo a analizar en el string text, previamente convertido a minúsculas a través de una acción transform (A). Después, el string text es tokenizado en (B) a través de una vista tokenize que usa una expresión regular para identificar las distintas palabras formadas por los caracteres a-z0-9_. Finalmente, dichas palabras en minúscula son almacenadas en el nuevo vector tokens (C). La reducida longitud de la mayoría de las palabras activará la optimización de strings cortos propia del estándar C++11 y posteriores [2]. Observemos que el motor regex ASCII definido en el código anterior podrá producir resultados inesperados al trabajar con textos codificados en UTF8. Sin embargo, consideraremos esta solución suficiente para los propósitos ilustrativos de este artículo.
A continuación, un bucle for ordena el vector tokens lexicográficamente, para someterlo después a una vista group_by que identifique el inicio y el final de cada grupo grp de palabras idénticas (D). Dichos grupos son entonces iterados por el bucle. Observemos que la longitud de cada grupo se corresponde con la frecuencia de ocurrencia de la palabra correspondiente en el texto. Dicha longitud es, pues, empleada como clave del mapa en (E), remitiendo al fondo de su vector asociado una copia del primer representante del grupo *grp.begin().
Un segundo bucle nos permitirá imprimir en la terminal las cinco mayores frecuencias de uso junto a sus palabras asociadas:
for (auto const& [freq, tokens] : freq_tokens_map | rv::take(5)) {
print("{:>6} --> ", freq);
for (auto const& tk : tokens | rv::intersperse(", "))
print("{}", tk);
print("\n");
}
Aquí, la vista intersperse introducirá una coma y un espacio entre una palabra y otra de existir más de un token para una frecuencia determinada, pero no tras la última palabra del vector. Por ejemplo, en el caso de Ulysses de James Joyce, disponible en el proyecto Gutenberg (https://www.gutenberg.org/), obtendríamos:
15131 --> the
8262 --> of
7287 --> and
6579 --> a
5040 --> to
Debiendo descender hasta la frecuencia 334 para encontrar un vector de palabras de longitud superior a la unidad:
334 --> other, where
La referencia [3] proporciona una solución alternativa al problema considerado en este ejemplo, haciendo uso de un multimapa y empleando un estilo de codificación enteramente funcional.
Llegados a este punto, resulta inmediato generar un fichero CSV con el conjunto de parejas (posición en el ranking, frecuencia de uso) para cada palabra distinta empleada en el Ulysses de Joyce. Por ejemplo, siendo 'the' el término más empleado con una frecuencia de uso de 15131, registraríamos el punto (1, 15131) en el fichero. Análogamente, siendo 'of' el segundo término en el ranking con una frecuencia de 8262, registraríamos (2, 8262) en el fichero. Si dos o más términos comparten una misma frecuencia de uso, les asignaremos posiciones de ranking consecutivas:
auto csv_file = ofstream{"ulysses_data.csv", ios::binary};
for (
auto rnk = 0;
auto const& [freq, token_vector] : freq_tokens_map
) {
for ([[maybe_unused]] auto const& _ : token_vector)
csv_file << fmt::format("{},{}\n", ++rnk, freq);
}
Podemos utilizar dicho fichero CSV para representar en un programa de software numérico la relación log(frecuencia) vs log(posición en el ranking). Se verifica en este caso la ley de Zipf, es decir, la nube de puntos obtenida sigue una línea de tendencia de tipo potencia, de la forma frecuencia = a·(posición en el ranking)-b, donde a y b son constantes reales positivas, con b ligeramente superior a la unidad (véase la figura inferior).
Este ejemplo se encuentra desarrollado en más detalle, obteniendo la gráfica a través de la biblioteca Matplot++, en un artículo posterior del blog.
Puede encontrarse el siguiente ejemplo de empleo de Range-v3 en el tercer post de esta serie.
Referencias bibliográficas:
- Eric Niebler - To Be or Not to Be (an Iterator) - https://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/
- Andrzej's C++ blog - Common optimizations - https://akrzemi1.wordpress.com/2014/04/14/common-optimizations/
- Vanand Gasparyan - A little bit of code [C++20 Ranges] - https://itnext.io/a-little-bit-of-code-c-20-ranges-c6a6f7eae401
No hay comentarios:
Publicar un comentario