[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Remove some dead code, and optimize CumulativeDist f...
Update of /home/freehaven/cvsroot/doc/e2e-traffic/src
In directory moria.mit.edu:/tmp/cvs-serv9446
Modified Files:
netparams.cpp rng.cpp rng.h simmain.cpp test.cpp
Log Message:
Remove some dead code, and optimize CumulativeDist for a modest (16%) speedup in smallworlds simulations
Index: netparams.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/netparams.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- netparams.cpp 22 Nov 2003 23:32:22 -0000 1.2
+++ netparams.cpp 24 Nov 2003 00:33:27 -0000 1.3
@@ -26,7 +26,7 @@
std::pow(pSingleDelay, d) * std::pow(1.0-pSingleDelay, pathLen);
}
}
- return new CumulativeDist(p, false);
+ return new CumulativeDist(p);
}
void
@@ -60,30 +60,22 @@
}
}
- std::vector<double> pBackground(nRecipients, 0.0);
- for (int i = 0; i < nRecipients; ++i) {
- pBackground[i] = conns[i] / ((double)total);
- }
- backgroundTraffic = new CumulativeDist(pBackground);
+ // XXX Make a constructor decide to use CumulativeDist if granularity
+ // XXX is too small.
+ backgroundTraffic = new OCumulativeDist(conns);
- std::vector<double> pAlice(nRecipients, 0.0);
- double pTotalAlice = 0.0;
+ std::vector<int> pAlice(nRecipients, 0);
for (int i = 0; i < nAliceRecipients; ++i) {
int r;
do {
r = backgroundTraffic->get();
} while (pAlice[r]);
if (weightAlice) {
- pAlice[r] = pBackground[r];
- pTotalAlice += pBackground[r];
+ pAlice[r] = conns[r];
} else {
- pAlice[r] = 1.0;
- pTotalAlice += 1.0;
+ pAlice[r] = 1;
}
}
- for (int i = 0; i < nAliceRecipients; ++i) {
- pAlice[i] /= pTotalAlice;
- }
aliceRecipients = new std::vector<int>(nAliceRecipients);
int j = 0;
@@ -93,5 +85,7 @@
}
}
- aliceRecipDist = new CumulativeDist(pAlice, false);
+ // XXX Make a constructor decide to use CumulativeDist if granularity
+ // XXX is too small.
+ aliceRecipDist = new OCumulativeDist(pAlice);
}
Index: rng.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.cpp,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- rng.cpp 23 Aug 2003 19:04:29 -0000 1.3
+++ rng.cpp 24 Nov 2003 00:33:27 -0000 1.4
@@ -1,5 +1,6 @@
#include <stdlib.h>
+#include <math.h>
#include "rng.h"
#include <boost/random.hpp>
@@ -36,42 +37,18 @@
return state.norm();
}
-CumulativeDist
-CumulativeDist::fromDist(InvDist<int> &d, int max)
-{
- std::vector<double> probabilities(max);
- double total = 0.0;
- for (int i = 0; i < max; ++i) {
- total += (probabilities[i] = d.getP(i));
- }
- probabilities[max-1] += (1.0-total);
- return CumulativeDist(probabilities, false);
-}
-
-
-CumulativeDist::CumulativeDist(const std::vector<double> &dist,
- bool isCumulative)
- : prob(dist.size()), cumDist(dist.size())
+CumulativeDist::CumulativeDist(const std::vector<double> &dist)
+ : prob(dist), cumDist(dist.size())
{
int sz = dist.size();
- if (isCumulative) {
- cumDist = dist;
-
- for (int i = 0; i < sz-1; ++i) {
- prob[i] = cumDist[i+1] - cumDist[i];
- }
- prob[sz-1] = 1.0 - cumDist[sz-1];
- } else {
- prob = dist;
- double tot = 0.0;
- for (int i = 0; i < sz; ++i) {
- tot += dist[i];
- cumDist[i] = tot;
- }
- for (int i = 0; i < sz; ++i) {
- cumDist[i] /= tot;
- }
+ double tot = 0.0;
+ for (int i = 0; i < sz; ++i) {
+ tot += dist[i];
+ cumDist[i] = tot;
+ }
+ for (int i = 0; i < sz; ++i) {
+ cumDist[i] /= tot;
}
}
@@ -81,4 +58,46 @@
std::vector<double>::const_iterator it =
std::lower_bound(cumDist.begin(), cumDist.end(), rng());
return it - cumDist.begin();
+}
+
+OCumulativeDist::OCumulativeDist(const std::vector<double> &dist,
+ double granularity)
+ : prob(dist), lookupTable((int)round(1.0/granularity))
+{
+ std::vector<double> cumDist(dist.size());
+ int sz = dist.size();
+
+ double tot = 0.0;
+ for (int i = 0; i < sz; ++i) {
+ tot += dist[i];
+ cumDist[i] = tot;
+ }
+ for (int i = 0; i < sz; ++i) {
+ cumDist[i] /= tot;
+ }
+
+ for (unsigned int i = 0; i < lookupTable.size(); ++i) {
+ std::vector<double>::const_iterator it =
+ std::lower_bound(cumDist.begin(), cumDist.end(), i*granularity);
+ lookupTable[i] = it - cumDist.begin();
+ }
+}
+
+OCumulativeDist::OCumulativeDist(const std::vector<int> &dist)
+ : prob(dist.size())
+{
+ int tot = 0;
+ typedef std::vector<int>::const_iterator iter;
+ for (iter it = dist.begin(); it != dist.end(); ++it) {
+ assert(*it >= 0);
+ tot += *it;
+ }
+ lookupTable.reserve(tot);
+ int i = 0;
+ for (iter it = dist.begin(); it < dist.end(); ++it, ++i) {
+ prob[i] = ((double)(*it))/tot;
+ for (int j = 0; j < *it; ++j) {
+ lookupTable.push_back(i);
+ }
+ }
}
Index: rng.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.h,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- rng.h 22 Nov 2003 23:32:22 -0000 1.4
+++ rng.h 24 Nov 2003 00:33:27 -0000 1.5
@@ -81,8 +81,7 @@
std::vector<double> prob;
std::vector<double> cumDist;
public:
- static CumulativeDist fromDist(InvDist<int> &d, int max);
- CumulativeDist(const std::vector<double> &dist, bool isCumulative=0);
+ CumulativeDist(const std::vector<double> &dist);
CumulativeDist(const CumulativeDist &d) : prob(d.prob), cumDist(d.cumDist) {}
Dist<int> *copy() const { return new CumulativeDist(*this); }
CumulativeDist & operator=(const CumulativeDist &d)
@@ -91,6 +90,25 @@
double getP(const int &v) const
{ return (0 <= v && v <= (int)prob.size()) ? prob[v] : 0.0; }
~CumulativeDist() {}
+};
+
+class OCumulativeDist : public InvDist<int>
+{
+ private:
+ std::vector<double> prob;
+ std::vector<int> lookupTable;
+ public:
+ OCumulativeDist(const std::vector<int> &dist);
+ OCumulativeDist(const std::vector<double> &dist, double granularity);
+ OCumulativeDist(const OCumulativeDist &d) :
+ prob(d.prob), lookupTable(d.lookupTable) {}
+ Dist<int> *copy() const { return new OCumulativeDist(*this); }
+ OCumulativeDist & operator=(const OCumulativeDist &d)
+ { prob=d.prob; lookupTable = d.lookupTable; return *this; }
+ int get() const { return lookupTable[(int)(rng()*lookupTable.size())]; }
+ double getP(const int &v) const
+ { return (0 <= v && v <= (int)prob.size()) ? prob[v] : 0.0; }
+ ~OCumulativeDist() {}
};
template<class C>
Index: simmain.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/simmain.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- simmain.cpp 23 Nov 2003 06:26:23 -0000 1.5
+++ simmain.cpp 24 Nov 2003 00:33:27 -0000 1.6
@@ -64,11 +64,11 @@
s.setNRecipients(100).setNAliceRecipients(5).setPathLen(3).setPDelay(0.5)
.setExpAlice(0.5).setPMessage(0.6).setPDummy(0.2).setBGVolMean(30)
.setBGVolDev(3).setPadding(0).setGranularity(20)
- .setPartial(true).setPObserve(.9).setCutoff(1000000);
+ .setPartial(true).setPObserve(.5).setCutoff(1000000);
MixTrial trial(s);
//MixTrial trial(100, 5, 3, 0.5, true, 0.6, 0.2, 30, 3, 0, 20, true, 0.4);
percentiles p;
- getPercentile(trial, 20, p);
+ getPercentile(trial, 2, p);
cout << "======"
<< p.min << " " << p.p50 << " "
<< p.p90 << " " << p.max << "=====" << endl;
Index: test.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/test.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- test.cpp 21 Aug 2003 21:05:57 -0000 1.2
+++ test.cpp 24 Nov 2003 00:33:27 -0000 1.3
@@ -96,6 +96,7 @@
int
main(int c, char **v) {
+
test_vec();
test_comb();
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/