Range-v3: Una introducción a la biblioteca (Parte V)

Artículos de la serie:

1. Vistas y acciones, ejemplos 1 (generate_n, group_by, sort, to) y 2 (filter)
2. Ejemplos 3 (enumerate, shuffle, take, zip) y 4 (intersperse, tokenize)
3. Ejemplos 5 (getlines, transform) y 6 (iota, set_difference, split_when)
4. Ejemplo 7 (stable_partition, subrange)
5. Ejemplo 8 (concat, drop, generate, take_while)
6. Ejemplos 9 (cycle) y 10 (keys, values)
7. Ejemplo 11 (cartesian_product)

En este post proporcionaremos un nuevo ejemplo 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 8: concat, drop, generate, take_while

Consideremos el problema de mostrar por la terminal un rango determinado de números primos, por ejemplo todos aquellos comprendidos en el intervalo [746730, 46775). Recordemos que un número primo es un natural p > 1 cuyos únicos divisores naturales son 1 y p. En tal caso, p no puede ser expresado como producto de dos naturales más pequeños.

En nuestro estudio, haremos uso de los siguientes ficheros de cabecera de la biblioteca Range-v3:

   #include <range/v3/core.hpp>    #include <range/v3/view/concat.hpp>    #include <range/v3/view/drop.hpp>    #include <range/v3/view/generate.hpp>    #include <range/v3/view/take.hpp>    #include <range/v3/view/take_while.hpp>

Codificaremos, en primer lugar, una lambda auxiliar que determine si un número entero, impar y estrictamente mayor que 3, es primo o no [1]:

   auto is_prime_aux = [](int i) {       assert(i > 3 and i%2 != 0); // precondición       if (i%3 == 0)          return false;       for (auto j = 5; j*j <= i; j += 6)          if ((i%j == 0) or (i%(j + 2) == 0))             return false;       return true;    };

Si bien el código anterior no proporciona, ciertamente, la implementación más eficiente posible para nuestro problema (especialmente para naturales grandes) [2], sí servirá a los propósitos divulgativos de este artículo.

A continuación, definiremos dos rangos. El primero de ellos contendrá los dos primeros números primos (2 y 3):

   auto rng_1 = rv::iota(2, 4); // los dos primeros números primos: {2, 3}    

La secuencia con los restantes números primos será definida través de la vista generate y una expresión lambda nularia con estado interno:

   // restantes números primos en [5, +infty):    auto rng_2 = rv::generate([&is_prime_aux, n = 5]() mutable {       while(!is_prime_aux(n))          n += 2;       auto const p = n;       n += 2;       return p;    });    

Observemos, en particular, el uso del especificador mutable con el fin de permitir la modificación del entero n por parte de la función. generate retorna un rango formalmente infinito --salvo por el inevitable desbordamiento de enteros-- cuyos valores pueden ser generados mediante llamadas sucesivas a la función lambda.

El conjunto infinito de números primos queda entonces representado mediante la concatenación de los dos rangos definidos anteriormente, operación que llevaremos a cabo con la vista concat:

   // conjunto de números primos:    auto prime_numbers = rv::concat(rng_1, rng_2);

Denotemos como p_i al i-ésimo número primo. Como aplicación del análisis anterior, obtengamos los cinco números primos con índices comprendidos entre i = 59996 y  i = 60000 (incluido este último) [3]. Para ello, someteremos al rango prime_numbers a dos vistas consecutivas:

   for (auto const p : prime_numbers | rv::take(60'000) | rv::drop(59'995))       print("{} ", p); // output: 746737 746743 746747 746749 746773 

• En primer lugar, la vista take(60'000) se encarga de seleccionar los 60000 primeros números de la secuencia.
• La vista drop(59'995) elimina, a continuación, los primeros 59995 números del rango obtenido en el punto anterior (sobreviviendo, pues, los cinco valores deseados). Aunque no sea éste el caso, conviene indicar que drop retornaría un rango vacío si el rango fuente contuviese menos elementos que aquellos que se desea ignorar.

El bucle for materializa finalmente el rango de cinco términos resultante.

Estos valores son, de hecho, los números primos contenidos en el intervalo [746730, 746775) que mencionábamos al inicio del post, tal y como demuestra el siguiente bucle:

   auto const min_value = 746'730,               max_value = 746'775;    for (auto const p : prime_numbers | rv::take_while([&](int i){ return i < max_value; })                                      | rv::filter([&](int i){ return i >= min_value; })    ) {       print("{} ", p); // output: 746737 746743 746747 746749 746773    }

Aquí, la vista take_while retorna un rango consistente únicamente en aquellos números primos que satisfacen su predicado unario (es decir, que son menores que max_value). Dicho rango se trunca en el primer valor para el que el predicado se evalúa como falso. Observemos que es necesario aplicar esta vista antes de proceder al filtrado, dado el carácter formalmente infinito del rango prime_numbers.

---

Pueden encontrarse los siguientes ejemplos de empleo de Range-v3 en el sexto post de esta serie.

---

Referencias bibliográficas

1. Wikipedia - Primality test - https://en.wikipedia.org/wiki/Primality_test
2. T. H. Cormen, et al., Introduction to Algorithms. MIT Press, 3rd edition (2009).
3. WolframAlpha - 59996th to 60000th prime numbers - https://www.wolframalpha.com/input/?i=59996th+to+60000th+prime+numbers