Joseph Wakeling wrote:
> No ... ! That was true in the original code I posted, but following
> bearophile's kind example that part of the code was updated to a form
> along the lines of,
Just for reference, here are the two pieces of code, for side-by-side
comparison. As far as I can tell the algorithms are identical; the
results are certainly identical; and the D code is significantly slower
(on the order of half the speed on my machine). I don't know what the
cause is, but my guess would be something along the lines of iterating
across or writing values to arrays in D.
The C++ code relies on the Boost libraries, another reason to like D2:
you get a lot of nice functionality built-in ... :-)
Best wishes,
-- Joe
import std.stdio: printf;
import std.math: sqrt, pow;
import std.random;
struct Rating
{
size_t user;
size_t object;
double value;
}
class ReputationAlgorithm
{
this() {}
this(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject) {}
}
class AvgWeighted : ReputationAlgorithm
{
double[] weightSum;
uint opCall(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
weightSum.length = reputationObject.length;
weightSum[] = 0;
reputationObject[] = 0;
foreach(ref const(Rating) r; ratings) {
reputationObject[r.object] += reputationUser[r.user]*r.value;
weightSum[r.object] += reputationUser[r.user];
}
foreach(size_t o, ref double r; reputationObject)
r /= weightSum[o];
return 0;
}
this() {}
this(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
opCall(ratings,reputationUser,reputationObject);
}
}
final class AvgArithmetic : AvgWeighted
{
uint opCall(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
reputationUser[] = 1;
return super.opCall(ratings,reputationUser,reputationObject);
}
this() {}
this(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
opCall(ratings,reputationUser,reputationObject);
}
}
final class Yzlm : AvgWeighted
{
double beta;
double convergenceRequirement;
double errorMin;
size_t[] userLinks;
double[] weightSum;
double[] oldReputationObject;
double objectReputationUpdate(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
double diff = 0;
double[] tmp = oldReputationObject;
oldReputationObject = reputationObject;
reputationObject = tmp;
reputationObject[] = 0;
super.opCall(ratings,reputationUser,reputationObject);
foreach(size_t object, ref const(double) r; reputationObject) {
auto aux = r - oldReputationObject[object];
diff += aux*aux;
}
return sqrt(diff);
}
void userReputationUpdate(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
reputationUser[] = 0;
foreach(ref const(Rating) r; ratings) {
auto aux = r.value - reputationObject[r.object];
reputationUser[r.user] += aux*aux;
}
foreach(size_t user, ref double r; reputationUser) {
if(userLinks[user]>0)
r = pow( (r/userLinks[user]) + errorMin, -beta);
}
}
uint opCall(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject)
{
userLinks.length = reputationUser.length;
userLinks[] = 0;
weightSum.length = reputationObject.length;
oldReputationObject.length = reputationObject.length;
foreach(ref const(Rating) r; ratings)
userLinks[r.user]++;
double diff;
uint iterations=0;
do {
userReputationUpdate(ratings,
reputationUser,
reputationObject);
diff = objectReputationUpdate(ratings,
reputationUser,
reputationObject);
++iterations;
} while(diff > convergenceRequirement);
printf("Exited in %u iterations with diff = %g < %g\n",
iterations,diff,convergenceRequirement);
return iterations;
}
this() {}
this(double b,
double c,
double e)
{
beta = b;
convergenceRequirement = c;
errorMin = e;
assert(beta>=0);
assert(convergenceRequirement>0);
assert(errorMin>=0);
}
this(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject,
double b,
double c,
double e)
{
this(b,c,e);
opCall(ratings,
reputationUser,
reputationObject);
}
}
void main()
{
Rating[] ratings;
double[] reputationObject, reputationUser;
double[] objectQuality, userError;
uint iterTotal = 0;
Mt19937 rng;
auto aa = new AvgArithmetic;
auto yzlm = new Yzlm(0.8,1e-12,1e-36);
rng.seed(1001);
reputationObject.length = 1000;
reputationUser.length = 1000;
objectQuality.length = reputationObject.length;
userError.length = reputationUser.length;
ratings.length = reputationObject.length*reputationUser.length;
for(uint i=0;i<100;++i) {
foreach(ref double Q; objectQuality)
Q = uniform(0.0,10.0,rng);
foreach(ref double sigma2; userError)
sigma2 = uniform(0.0,1.0,rng);
size_t pos = 0;
foreach(size_t object, ref double Q; objectQuality) {
foreach(size_t user, ref double sigma2; userError) {
ratings[pos++] = Rating(user,
object,
uniform((Q-sigma2), (Q+sigma2), rng));
}
}
ratings.length = pos;
printf("We now have %u ratings.\n",ratings.length);
aa(ratings,reputationUser,reputationObject);
iterTotal += yzlm(ratings,reputationUser,reputationObject);
double deltaQ = 0;
foreach(size_t object, ref const(double) r; reputationObject)
deltaQ += pow( (r-objectQuality[object]), 2.0);
deltaQ = sqrt(deltaQ/reputationObject.length);
printf("[%u] Error in quality estimate: %g\n",i,deltaQ);
}
printf("Total iterations: %u\n",iterTotal);
}
#include <iostream>
#include <vector>
#include <boost/foreach.hpp>
#include <boost/random.hpp>
using namespace std;
using namespace boost;
namespace fric
{
class Rating {
private:
size_t _user;
size_t _object;
double _value;
public:
Rating() {}
Rating(size_t u,
size_t o,
double v)
{
_user = u;
_object = o;
_value = v;
}
const size_t &user() { return _user; }
const size_t &object() { return _object; }
const double &value() { return _value; }
};
class ReputationAlgorithm {
virtual size_t reputation(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings)
{
return 0;
}
virtual size_t addRating(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings,
Rating r)
{
return 0;
}
};
namespace algorithm
{
class AvgWeighted : ReputationAlgorithm {
protected:
vector<double> weightSum;
public:
virtual size_t reputation(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings)
{
weightSum.assign(reputationObject.size(),0.0);
reputationObject.assign(reputationObject.size(),0.0);
BOOST_FOREACH(Rating &r, ratings) {
reputationObject.at(r.object()) += reputationUser.at(r.user()) * r.value();
weightSum.at(r.object()) += reputationUser.at(r.user());
}
for(size_t o=0;o!=reputationObject.size();++o)
reputationObject.at(o) /= (weightSum.at(o)>0) ? weightSum.at(o) : 1;
return 0;
}
};
class AvgArithmetic : AvgWeighted {
public:
virtual size_t reputation(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings)
{
reputationUser.assign(reputationUser.size(),1.0);
return AvgWeighted::reputation(reputationUser,reputationObject,ratings);
}
};
class Yzlm : AvgWeighted {
private:
double _beta;
double _convergence;
double _errorMin;
protected:
vector<double> oldReputationObject;
vector<size_t> userLinks;
double objectReputationUpdate(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings)
{
double diff = 0.0;
oldReputationObject.assign(reputationObject.begin(), reputationObject.end());
AvgWeighted::reputation(reputationUser, reputationObject, ratings);
for(size_t o=0;o!=reputationObject.size();++o) {
double aux = reputationObject.at(o) - oldReputationObject.at(o);
diff += aux*aux;
}
return sqrt(diff);
}
void userReputationUpdate(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings)
{
reputationUser.assign(reputationUser.size(),0.0);
BOOST_FOREACH(Rating &r, ratings) {
double aux = r.value() - reputationObject.at(r.object());
reputationUser.at(r.user()) += aux*aux;
}
for(size_t u=0;u!=reputationUser.size();++u) {
if(userLinks.at(u)!=0)
reputationUser.at(u) = pow( (reputationUser.at(u)/userLinks.at(u)) + errorMin(), -beta() );
}
}
public:
void init(double b,
double c,
double e)
{
_beta = b;
_convergence = c;
_errorMin = e;
}
const double &beta() { return _beta; }
const double &convergence() { return _convergence; }
const double &errorMin() { return _errorMin; }
virtual size_t reputation(vector<double> &reputationUser,
vector<double> &reputationObject,
vector<Rating> &ratings)
{
double diff;
size_t iterations = 0;
userLinks.assign(reputationUser.size(),0);
oldReputationObject.resize(reputationObject.size());
BOOST_FOREACH(Rating &r, ratings)
userLinks.at(r.user())++;
do {
userReputationUpdate(reputationUser,reputationObject,ratings);
diff = objectReputationUpdate(reputationUser,reputationObject,ratings);
++iterations;
} while(diff > convergence());
cout << "Exited in " << iterations << " iterations with diff = " << diff << endl;
return iterations;
}
Yzlm(double b,
double c,
double e)
{
init(b,c,e);
}
};
}
}
using namespace fric;
int main()
{
vector<double> reputationUser, reputationObject;
vector<double> userError, objectQuality;
vector<Rating> ratings;
mt19937 rng;
algorithm::AvgArithmetic aa;
algorithm::Yzlm yzlm(0.8,1e-12,1e-36);
reputationUser.resize(100);
reputationObject.resize(1);
rng.seed(1001);
for(size_t u=0;u!=reputationUser.size();++u)
ratings.push_back(Rating(u,0,u+1));
aa.reputation(reputationUser,reputationObject,ratings);
BOOST_FOREACH(double r, reputationObject)
cout << r << endl;
objectQuality.resize(1000);
userError.resize(1000);
reputationObject.resize(objectQuality.size());
reputationUser.resize(userError.size());
ratings.reserve(objectQuality.size() * userError.size());
size_t iterTotal = 0;
for(size_t i=0;i!=100;++i) {
BOOST_FOREACH(double &Q, objectQuality)
Q = uniform_real<double> (0.0, 10.0) (rng);
BOOST_FOREACH(double &err, userError)
err = uniform_real<double> (0.0, 1.0) (rng);
ratings.resize(0);
for(size_t o=0;o!=objectQuality.size();++o) {
for(size_t u=0;u!=userError.size();++u) {
ratings.push_back( Rating(u, o, uniform_real<double> (objectQuality.at(o)-userError.at(u), objectQuality.at(o)+userError.at(u)) (rng) ) );
}
}
cout << "We now have " << ratings.size() << " ratings, with capacity for " << ratings.capacity() << endl;
aa.reputation(reputationUser, reputationObject, ratings);
iterTotal += yzlm.reputation(reputationUser, reputationObject, ratings);
double deltaQ = 0.0;
for(size_t o=0;o!=objectQuality.size();++o) {
double aux = reputationObject.at(o) - objectQuality.at(o);
deltaQ += aux*aux;
}
deltaQ = sqrt(deltaQ/objectQuality.size());
cout << "[" << i << "] Error in quality estimate: " << deltaQ << endl;
}
cout << endl;
cout << "Total iterations: " << iterTotal << endl;
return 0;
}
