Hi All,
after discussion of some aspects of performance of CL, Scheme, Dylan,
C/C++:
http://groups.google.de/groups?hl=de&lr=&ie=UTF-8&threadm=hxk7autvmg.fsf%40FernUni-Hagen.de&rnum=1&prev=/groups%3Fhl%3Dde%26lr%3D%26ie%3DUTF-8%26selm%3Dhxk7autvmg.fsf%2540FernUni-Hagen.de
a nice code snippets were presented
(see http://khamenya.ru/lisp/code-snippets/fib/ ) by:
Bruce Hoult (Dylan)
Kalle Olavi Niemitalo (CommonLisp)
Anton van Straaten (Scheme)
These code snippets I've tied up to the cliki.net at
http://www.cliki.net/Anthology page. It's a shame to have this
Antology page almost empty. It would be good if good hackers could
introduce their nice code snippets (and more practical then Fibonacci
numbers).
thank you,
Valery A.Khamenya (khamenya at mail dot ru)
········@mail.ru (Valery) wrote in message news:<····························@posting.google.com>...
> These code snippets I've tied up to the cliki.net at
> http://www.cliki.net/Anthology page. It's a shame to have this
> Antology page almost empty. It would be good if good hackers could
From that page:
> Due to space constraints, it is better if you include
> only links, not the actual code.
But Lisp code doesn't take a lot of space. Links
often get broken. People are more likely to post
code if they can just post it, without setting it up
somewhere else.
Valery wrote:
> Hi All,
>
> after discussion of some aspects of performance of CL, Scheme, Dylan,
> C/C++:
As there isn't any C++ on that page (and I hadn't been using mine for a
few months and didn't want it to go rusty), here is the equivalent C++
for the create a function (a function object in C++) and cache it
approach. Apologies for the verbosity, but that's what you have to do
the get the same effect. Please trim on follow-ups.
longFib use in-built long type;
bigFib uses the simple big natural class
directFib (trimmed from code) caches values directly, rather than
functions that provide values like this implementation and those it is
compared with.
Pete
---------------------
calling longFib(3000) 1000000 times took 93/1000s
average 93 micro seconds (fast but wrong)
calling bigFib(3000) 1000000 times took 2360/1000s
average 2360 micro seconds (dynamic function objects)
calling directFib<BigNatural>(3000) 1000000 times took 531/1000s
average 531 micro seconds (no function objects)
1GHz Pentium, NT4
---------------------
// dynamic.cpp : C++ version of solution to fibbonacci using a
// cache of dynamicaaly created function objects.
//
// It the question wasn't one of dynamically creating functions,
// then you'd cache the results, not a function that gives the result.
// Which gives about a 4x speed increase.
#include <vector>
#include <iostream>
// C++ doesn't directly support big ints; this is a simple implemetation
// that uses the first n-1 bits of each n-bit digit, watching the n'th
// bit for overflow. Assumes that the int type is at least 32 bits.
class BigNatural {
int * const digits_;
const int size_;
protected:
BigNatural (int* digits, int size) : digits_(digits), size_(size) {}
public:
BigNatural (int n) : size_(1), digits_(new int [1]) {
digits_[0] = n & 0x7fffffff;
}
BigNatural (const BigNatural& n) : size_(n.size_), digits_(new int
[n.size_]) {
/* for (int i=0; i<size_; i++) {
digits_[i] = n.digits_[i];
}*/
memcpy(digits_, n.digits_, size_*sizeof(int));
}
BigNatural operator+ (BigNatural& n) {
int carry = 0;
int sizeMin = size_ < n.size_ ? size_ : n.size_;
int sizeMax = size_ > n.size_ ? size_ : n.size_;
int* result = new int[sizeMax];
int i;
// add digits upto length of shortest
for (i=0; i<sizeMin; i++) {
int sum = digits_[i] + n.digits_[i] + carry;
carry = (sum&0x80000000) ? 1 : 0;
result[i] = sum&0x7fffffff;
}
// add remaining digits from either
for (; i<size_; i++) {
int sum = digits_[i] + carry;
carry = (sum&0x80000000) ? 1 : 0;
result[i] = sum&0x7fffffff;
}
for (; i<n.size_; i++) {
int sum = n.digits_[i] + carry;
carry = (sum&0x80000000) ? 1 : 0;
result[i] = sum&0x7fffffff;
}
// handle final overflow
if (carry) {
sizeMax++;
int* overflowResult = new int[sizeMax];
for (i=sizeMax-2; i>=0; i--) {
overflowResult[i] = result[i];
}
overflowResult[sizeMax-1] = carry;
result = overflowResult;
}
return BigNatural(result, sizeMax);
}
~BigNatural () {
delete [] digits_;
}
friend std::ostream& operator << (std::ostream& os, BigNatural& bn);
};
// print a BigNarutral
std::ostream& operator << (std::ostream& os, BigNatural& bn) {
{
int bufSize = bn.size_ * 10;
static int cachedBufSize = 0;
static int* buf;
if (bufSize>cachedBufSize) {
cachedBufSize = bufSize*2;
buf= new int[cachedBufSize];
}
int* d = new int[bn.size_];
int i;
bool noZero = false;
for (i=bn.size_-1; i>=0; i--) {
d[i] = bn.digits_[i];
noZero = noZero || d[i];
}
int j = 0;
for (j=0; noZero && (j<bufSize); j++) {
int r = 0;
int carry = 0;
noZero = false;
for (i=bn.size_-1; i>=0; i--) {
noZero = noZero || d[i];
r = d[i] % 10 + carry*8;
d[i] = (d[i] / 10) + carry*214748364 + r/10;
r = r%10;
carry = r;
}
buf[j] = r;
}
if (j>1) {
j--;
}
while (j>0) {
j--;
os << buf[j];
}
return os;
}
// need to declare function before use
template <typename T>
T fib(int n) ;
// abstract function object taking one argument
template <typename T>
class Fn1 {
public:
virtual T operator() (int n) = 0;
virtual ~Fn1 () {}
};
// function object returning constant value
template <typename T>
class FnConst : public Fn1< T> {
protected:
const T n_;
public:
FnConst (T n) : n_(n) {}
virtual T operator() (int n) {
return n_;
}
};
// function object returning fib(n)
template <typename T>
class FnFib : public Fn1<T> {
public:
virtual T operator() (int n) {
return n<=2 ? 1 : (fib<T>(n-2) + fib<T>(n-1));
}
};
// function returning a reference to a function object
// that returns fib(n)
template <typename T>
Fn1<T>& fibFunction (int n) {
static FnConst<T> fnOne(T(1));
static std::vector<Fn1<T>*> fn_cache;
if (n<=2) {
return fnOne;
}
if (n>=fn_cache.size()) {
fn_cache.resize(2*n, NULL);
}
Fn1<T>* pf = fn_cache[n];
if (pf==NULL) {
fn_cache[n] = pf = new FnConst<T>(fib<T>(n-2) + fib<T>(n-1));
}
return *pf;
}
// function returning fib(n) using above dynamic function objects
template <typename T>
T fib<T> (int n) {
Fn1<T>& fn = fibFunction<T>(n);
return fn(n);
}
int main(int argc, char* argv[])
{
FnFib<long> longFib; // creates a function that returns fib(n) using
long
FnFib<BigNatural> bigFib; // creates a function that returns fib(n)
using BigNatural
int i;
for (i=0; i<500; i+=50) {
std::cout<<"longFib("<<i<<") = "<<longFib(i)<<std::endl;
}
for (i=0; i<100000; i+=10000) {
std::cout<<"bigFib("<<i<<") = "<<bigFib(i)<<std::endl;
}
return 0;
}
pete kirkham <············@cafemosaic.co.uk> wrote in message
> As there isn't any C++ on that page [...]
thank you Pete.
Added:
http://khamenya.ru/lisp/code-snippets/fib/
--
Valery
Valery,
I recently uploaded code to Franz's site. Currently, I have 10 packages
there that deal with a wide range of topics. They are of moderate
complexity, but they don't require a defsystem to run. Each package has a
set of tests and some documentation. The indent is to have example packages
that use a number of Lisp features but do not require a defsystem to set up.
The link is:
http://examples.franz.com/index.html
- R. Scott McIntire
"Valery" <········@mail.ru> wrote in message
·································@posting.google.com...
> Hi All,
>
> after discussion of some aspects of performance of CL, Scheme, Dylan,
> C/C++:
>
http://groups.google.de/groups?hl=de&lr=&ie=UTF-8&threadm=hxk7autvmg.fsf%40FernUni-Hagen.de&rnum=1&prev=/groups%3Fhl%3Dde%26lr%3D%26ie%3DUTF-8%26selm%3Dhxk7autvmg.fsf%2540FernUni-Hagen.de
> a nice code snippets were presented
> (see http://khamenya.ru/lisp/code-snippets/fib/ ) by:
>
> Bruce Hoult (Dylan)
> Kalle Olavi Niemitalo (CommonLisp)
> Anton van Straaten (Scheme)
>
> These code snippets I've tied up to the cliki.net at
> http://www.cliki.net/Anthology page. It's a shame to have this
> Antology page almost empty. It would be good if good hackers could
> introduce their nice code snippets (and more practical then Fibonacci
> numbers).
>
> thank you,
> Valery A.Khamenya (khamenya at mail dot ru)