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.