14

Estoy empezando a estudiar el lenguaje rust y, como suelo hacer para comparar con otros lenguajes, itento implementar el cálculo de factorial para números grandes (aka "BigInts").

Utilizo la versión rust 1.9.0 (stable), que me obliga por un lado a buscar fuera de la librería estándar el crate para usar números grandes (crate num). Por otro lado, no se pueden usar características inestables del lenguaje como son los métodos de agregación sum ó product, que hay que reimplementar mediante fold.

De momento, he implementado tres versiones:

extern crate num_bigint;
extern crate num_traits;
extern crate num_iter;

use num_bigint::BigUint;
use num_traits::{Zero, One};

use num_iter::range_inclusive;

fn fact(n: usize) -> BigUint {
    let mut res: BigUint = One::one();

    for i in 2..n + 1 {
        res = res * BigUint::from(i);
    }
    res
}

fn fact2(n: usize) -> BigUint {
    (2..n + 1).fold(One::one(), |x, y| x * BigUint::from(y))
}

fn fact3(n: usize) -> BigUint {
    range_inclusive(One::one(), BigUint::from(n)).fold(BigUint::one(), std::ops::Mul::mul)
}

Me interesa, sobre todo, la orientación funcional del lenguaje como la que aparece en las dos últimas implementaciones.

A pesar de que rust debería ser bastante rápido en ejecución, estas implementaciones resultan mucho más lentas que otras hechas en otros lenguajes (haskell, python, scala, ...). Además, el código me parece poco elegante. Por éso:

  • ¿Es posible mejorar estas implementaciones para que sean más rápidas?
  • ¿Se puede reescribir este código para que quede más elegante y/o funcional?
  • ¿Alguna implementación mejor?

  • ¿Tal vez con un macro se podría hacer más legible el código?


Añado estimación de tiempos

Sin ser nada preciso, añado los tiempos obtenidos con distintos lenguajes para el cálculo de 150000! para hacer una mejor idea:

haskell  25.68 secs
python   15.20 secs
rust[1]  17.67 secs
scala     8.36 secs
scala[2]  2.32 secs
scala[3]  0.32 secs

[1] compilado en rust con optimizaciones completas
[2] usando las colecciones paralelizables de scala
[3] algoritmo paralelizable en scala (https://github.com/chemacortes/factPar)

Además de tiempos, habría que medir el consumo de memoria. En este aspecto, sí que la versión rust destaca por la poca memoria empleada.


Edición [d: 2016-07-28]: he podido confirmar que el crate num que uso tiene algunos bugs que imposibilitan el uso del método product en iteradores BigUint que iría perfecto para la implementación del factorial. Habrá que ser paciente hasta que madure el ecosistema rust y tirar con "workarounds", aunque no resulten todo lo elegante que deberían ser.

2
  • que lastima, esperaba ver más ejemplos sobre esto y aprender sobre este lenguaje :( . Estuve compilando tus ejemplos y midiendo los tiempos de ejecución. Si lo deseas, puedo subir esa información y así aportar algo y no perder este gran post en un océano de preguntas sobre como hago mi tarea Commented el 5 jul. 2016 a las 22:23
  • Hola, Pablo. Agradezco las molestias tomadas. Si quieres, añade los tiempos como comentario. Tengo la intención de responder (al acabar la recompensa) con algunas mejoras de estilo y con versión para rust inestable, aunque no mejora en tiempos. En unos meses, cuando haya aprendido el lenguaje al completo, espero tener preparada alguna versión paralela (supongo que pondré algo en el blog que indico en mi perfil). Commented el 6 jul. 2016 a las 0:25

1 respuesta 1

3

Después de darle bastantes vueltas, he llegado a la conclusión de que el lenguaje todavía se está completando. Las versiones inestables permiten probar algunas características nuevas, pero están bastante limitadas en aplicación ya que no todas las librerías los implementan.

Por ejemplo, centrándonos en la estructura BigUint que se usan para el cálculo del factorial, ésta carece de los tratos (traits) necesarios para aplicar algunas de las nuevas extensiones como son el rango inclusivo (...) o el trato Product para poder usar el método product() con iteradores de BigUint. Espero que estas carencias se vayan añadiendo con el tiempo.

Finalmente, no he conseguido mejorar los tiempos de cálculo de factorial. Como mucho, asegurarse de compilar con las optimizaciones activadas (opción --release) y de estar usando las versiones de 64bits de las herramientas rust si es posible (por ejemplo, rustup instala por defecto las versiones de 32bits para windows, aunque sea un windows 64bits).

Por último, una versión final de factorial en rust:

extern crate num;

use num::{ One, BigUint, range_inclusive };

pub fn fact(n: usize) -> BigUint {
    range_inclusive(BigUint::one(), BigUint::from(n))
      .fold(BigUint::one(), |res, x| x * res)
}

#[test]
fn test_fact5() {
  assert_eq!(fact(5), BigUint::from(120usize));
}

#[test]
#[ignore]
fn test_factlarge {
  let s = fact(150000);
  assert_eq!(s.to_string().len(), 711273);
}

Para ejecutar el primer test:

cargo test --release

Para ejecutar el test ignorado:

cargo test --release -- --ignored

Edición: enlace al repositorio github con el código.

4
  • gracias Chema por el aporte, interesante ver estos post teóricos por acá :) Commented el 13 jul. 2016 a las 14:17
  • ¡Bien hecho! Ánimos para conseguir aún más :) Commented el 13 jul. 2016 a las 14:19
  • @ChemaCortes, por curiosidad, puedes poner las diferencias de rendimiento con Scala, Python, Haskell,...? Commented el 14 jul. 2016 a las 10:28
  • @kikocorreoso no son nada precisas las comparativas. Uso técnicas distintas, scalameter en scala, timeit en python, etc. Para rust, el benchmark está todavía en la versión inestable. Añado a la pregunta los tiempos aproximados. Aunque los tiempos de rust son buenos, habría que destacar su bajísmo consumo de memoria (que no he medido). Commented el 14 jul. 2016 a las 12:03

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.