Re: implementation note for scapegoat tree

On Mar 28, 3:10 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
"user923005" <dcor...@xxxxxxxxx> writes:
On Mar 28, 10:51 am, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
[scapegoat tree implementation description]
How well does your tree perform?

I don't have a performance testing framework set up, just a
correctness testing framework. Someday I need to revisit the
performance testing I did for my libavl paper and find out.
Until then, I'm pleased with the code.

If you want to look at it, here's the source:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/Attic/bt.c?rev=1...
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/Attic/bt.h?rev=1...
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/Attic/bt-test....
The dependencies on other parts of that source tree are intended
to be minimal.
--
"There's only one thing that will make them stop hating you.
And that's being so good at what you do that they can't ignore you.
I told them you were the best. Now you damn well better be."
--Orson Scott Card, _Ender's Game_

Speaking of PSPP, here is an *extremely* robust way to calculate
standard deviation (due to Knuth of course!):


// Welford standard deviation
// from TAOCP, Vol 2 page 232.
// By Dann Corbit. Explicity donated to the public domain.

#include <cmath>

template <class etype>
class WelfordStandardDeviation {
private:
etype m[2];
etype s[2];
size_t n;
public:
WelfordStandardDeviation(void);
etype GetS(void);
etype GetM(void);
etype GetN(void);
etype GetSigma(void);
void AddItem(etype x);
};

template <class etype>
WelfordStandardDeviation::WelfordStandardDeviation(void)
{
m[0] = (etype)0;
m[1] = (etype)0;
s[0] = (etype)0;
s[1] = (etype)0;
n = 0;
}

template <class etype>
etype WelfordStandardDeviation::GetS(void)
{
if (n >= 2)
return s[0];
return sqrt(-1.); /* Create a NAN */
}

template <class etype>
etype WelfordStandardDeviation::GetM(void)
{
if (n >= 2)
return s[0];
return sqrt(-1.); /* Create a NAN */
}

template <class etype>
etype WelfordStandardDeviation::GetN(void)
{
return n;
}

template <class etype>
etype WelfordStandardDeviation::GetSigma(void)
{
if (n >= 2)
return sqrt(s[0] / (n - 1.0));
return sqrt(-1.); /* Create a NAN */
}

template <class etype>
void WelfordStandardDeviation::AddItem(etype x)
{
++n;
if (n == 1) {
m[0] = x;
} else {
m[1] = m[0] + (x - m[0]) / n;
s[1] = s[0] + (x - m[0]) * (x - m[1]);
m[0] = m[1]; /* for next time */
s[0] = s[1]; /* for next time */
}
}

Here is a test driver:
#ifdef UNIT_TEST

#include <iostream>
#include <iomanip>
using namespace std;

#include "stats.hpp"
#include "welford.hpp"

int main(void)
{
WelfordStandardDeviation <double> wsd;
UnivarateStatistics <double, double > us(true);
size_t i;
for (i = 0; i < 10000; i++) {
wsd.AddItem((double) i);
us.add_pass_one((double) i);
}
us.calculate_simple_statistics();
cout << setprecision(20);
cout << "Standard deviation of the first 10000 integers is " <<
wsd.GetSigma() << " verified as " << us.get_s() << endl;
return 0;
}

/*
C:\tmp>welford
Standard deviation of the first 10000 integers is 2886.8956799071675
verified as 2886.8956799071675
*/
#endif /* UNIT_TEST */

.