Re: Request to review code for best practices
Ambush Commander wrote:
A while back I posted a Fibonacci sequence calculator on this group,
and asked people to critique it. I received many helpful comments, and
made the program a lot better.
Now, I've converted it to use GMP so there's a bit of pointer work and
dynamic memory allocation going on. Can I, once again, have comments
on whether or not the code does "good practices", and where it could
be better? Thanks!
P.S. I am especially interested in comments for the fibonacci()
function; not so much for the processArgs() one.
----
/**
* Exercise #2.1
*
* Create a program that takes one argument and prints the
corresponding
* term from the Fibonacci series. There are also a number of extra
* features.
*/
#include <iostream>
#include <vector>
#include <boost/program_options.hpp>
#include <gmp.h>
There is a c++ version: <gmpxx.h>. It proves a nice integer class mpz_class
that integrates nicely with operators and stuff. Moreover, it gets rid of
all the pointers.
/**
* Defines a whole number type (non-negative integer) that indexes the
* Fibonacci sequence. This type determines the nth term we can
calculate,
* though it has no bearing on the actual value of that term.
*/
typedef unsigned long WholeNumber;
/**
* Recursively calculates a term of the Fibonacci series.
* @param result Variable to write result to, no pointer necessary
* @param term Index of term in sequence
* @todo Convert code to use C++ GMP API
* @warning There is no way to free the internal cache
* @note I'm doing something very funky here: I'm using malloc in
order
to get the pointers to the arrays to persist... but GMP
also
has this sort of stuff going behind the scenes! So malloc
is being called twice! I don't know how to get around
this.
*/
void fibonacci(mpz_t result, WholeNumber term) {
static std::vector<mpz_t*> cache;
if (cache.empty()) {
// initialize cache with some (required) preloaded values
mpz_t *val0 = (mpz_t*) malloc(sizeof(mpz_t));
mpz_t *val1 = (mpz_t*) malloc(sizeof(mpz_t));
mpz_init(*val0);
cache.push_back(val0);
mpz_init(*val1);
mpz_set_ui(*val1, 1);
cache.push_back(val1);
}
Hm. The check is executed each time.
if (cache.size() > term) {
// cache hit, return that value
mpz_init(result);
mpz_set(result, *cache[term]);
} else {
// cache miss, generate it
mpz_t val1, val2; // previous two values
fibonacci(val2, term - 2);
fibonacci(val1, term - 1);
mpz_t *valr = (mpz_t*) malloc(sizeof(mpz_t));
mpz_init(*valr);
mpz_add(*valr, val2, val1);
cache.push_back(valr);
mpz_init(result);
mpz_set(result, *valr);
}
The above uses recursion. There is no need for that. You can replace the
whole thig with one
while ( n >= cache.size() ) {
compute next term
}
I would suggest to use a local class:
mpz_class const & fibonacci ( WholeNumber n ) {
class fib_cache {
std::vector< mpz_class > the_data;
public:
fib_cache ( void )
: the_data ()
{
the_data.push_back( mpz_class(0) );
the_data.push_back( mpz_class(1) );
}
mpz_class const & get ( std::vector< mpz_class >::size_type n ) {
while ( n >= the_data.size() ) {
the_data.push_back
( the_data[ the_data.size() - 1 ]
+
the_data[ the_data.size() - 2 ] );
}
assert( n < the_data.size() );
return ( the_data[n] );
}
};
static fib_cache dummy;
return ( dummy.get(n) );
}
Note how using mpz_class makes the code look like you would do it with
unsigned long.
[command line parsing snipped]
Best
Kai-Uwe Bux