This compiles for D1. With LDC it runs about two times faster still, about
4.5-5 times faster than the original version. We can compare this to the C++
version of yours.
ldc -O5 -release -inline -enable-unsafe-fp-math -unroll-allow-partial test.d
I have also tried the faster rnd generator (R250-521), but in this program it's
not faster than Kiss, so I've kept Kiss. Note that Tango that you can use with
LDC has Kiss already.
version (Tango) {
import tango.stdc.stdio: printf;
import tango.math.Math: sqrt, pow;
} else {
import std.stdio: printf;
import std.math: sqrt, pow;
}
struct FastRandom {
uint kiss_x = 1;
uint kiss_y = 2;
uint kiss_z = 4;
uint kiss_w = 8;
uint kiss_carry = 0;
uint kiss_k, kiss_m;
void seed(uint seed) {
kiss_x = seed | 1;
kiss_y = seed | 2;
kiss_z = seed | 4;
kiss_w = seed | 8;
kiss_carry = 0;
}
uint randUint() {
kiss_x = kiss_x * 69069 + 1;
kiss_y ^= kiss_y << 13;
kiss_y ^= kiss_y >> 17;
kiss_y ^= kiss_y << 5;
kiss_k = (kiss_z >> 2) + (kiss_w >> 3) + (kiss_carry >> 2);
kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry;
kiss_z = kiss_w;
kiss_w = kiss_m;
kiss_carry = kiss_k >> 30;
return kiss_x + kiss_y + kiss_w;
}
double random() {
return this.randUint() / (uint.max + 1.0);
}
double uniform(double a, double b) {
double r = cast(double)this.randUint() / (uint.max + 1.0);
return a + (b - a) * r;
}
}
struct Rating {
uint user, object;
double value;
}
abstract class ReputationAlgorithm {
this() {}
}
final class Yzlm : ReputationAlgorithm {
double beta;
double convergenceRequirement;
double errorMin;
// uint[] userLinks; // commented out because for now it
// has a constant value for all users
double[] weightSum;
double[] oldReputationObject;
double objectReputationUpdate(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject) {
double diff = 0;
double[] temp = oldReputationObject;
// Original version had:
//
// oldReputationObject[] = reputationObject[]
//
// This version is an attempt to save effort
// by just switching round the memory the two
// arrays are pointing at -- not sure if it
// actually does what I'm expecting it to.
// Doesn't seem to improve speed. :-(
oldReputationObject = reputationObject;
reputationObject = temp;
reputationObject[] = 0;
weightSum[] = 0;
foreach (Rating r; ratings) {
reputationObject[r.object] += reputationUser[r.user] * r.value;
weightSum[r.object] += reputationUser[r.user];
}
foreach (uint object, ref double r; reputationObject) {
r /= (weightSum[object] > 0) ? weightSum[object] : 1;
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 (Rating r; ratings) {
auto aux = (r.value - reputationObject[r.object]);
reputationUser[r.user] += aux * aux;
}
foreach (uint user, ref double r; reputationUser) {
//if(userLinks[user]>0)
r = pow( (r/reputationObject.length/*userLinks[user]*/) +
errorMin, -beta);
}
}
void 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 (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);
}
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);
}
}
class AvgWeighted : ReputationAlgorithm {
double[] weightSum;
void opCall(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject) {
weightSum.length = reputationObject.length;
weightSum[] = 0;
reputationObject[] = 0;
foreach (Rating r; ratings) {
reputationObject[r.object] += reputationUser[r.user]*r.value;
weightSum[r.object] += reputationUser[r.user];
}
foreach (uint o, ref double r; reputationObject)
r /= weightSum[o];
}
this() {}
this(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject) {
opCall(ratings, reputationUser, reputationObject);
}
}
final class AvgArithmetic : AvgWeighted {
override void opCall(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject) {
reputationUser[] = 1;
super.opCall(ratings, reputationUser, reputationObject);
}
this() {}
this(ref Rating[] ratings,
ref double[] reputationUser,
ref double[] reputationObject) {
opCall(ratings, reputationUser, reputationObject);
}
}
void main() {
Rating[] ratings;
double[] reputationObject, reputationUser;
double[] objectQuality, userError;
auto aa = new AvgArithmetic;
auto yzlm = new Yzlm(0.8, 1e-12, 1e-36);
FastRandom rnd;
rnd.seed(1001);
reputationObject.length = 1_000;
reputationUser.length = 1_000;
objectQuality.length = reputationObject.length;
userError.length = reputationUser.length;
ratings.length = reputationObject.length * reputationUser.length;
for (uint i; i < 4; i++) { // 100 4 ***************
foreach (ref double Q; objectQuality)
Q = rnd.uniform(0.0, 10.0);
foreach (ref double sigma2; userError)
sigma2 = rnd.random();
int pos;
foreach (uint object, ref double Q; objectQuality)
foreach (uint user, ref double sigma2; userError)
ratings[pos++] = Rating(user, object, rnd.uniform(Q - sigma2, Q
+ sigma2));
printf("We now have %u ratings.\n", ratings.length);
aa(ratings, reputationUser, reputationObject);
yzlm(ratings, reputationUser, reputationObject);
double deltaQ = 0;
foreach (uint object, double r; reputationObject) {
auto aux = (r - objectQuality[object]);
deltaQ += aux * aux;
}
deltaQ = sqrt(deltaQ / reputationObject.length);
printf("[%u] Error in quality estimate: %g\n", i, deltaQ);
}
}
Bye,
bearophile
