Select Git revision
fib-solve.py
-
Martin Mareš authoredMartin Mareš authored
splay_experiment.cpp 4.93 KiB
#include <algorithm>
#include <functional>
#include <string>
#include <utility>
#include <vector>
#include <iostream>
#include <cmath>
#include "splay_operation.h"
#include "random.h"
using namespace std;
/*
* A modified Splay tree for benchmarking.
*
* We inherit the implementation of operations from the Tree class
* and extend it by keeping statistics on the number of splay operations
* and the total number of rotations. Also, if naive is turned on,
* splay uses only single rotations.
*
* Please make sure that your Tree class defines the rotate() and splay()
* methods as virtual.
*/
class BenchmarkingTree : public Tree {
public:
int num_operations;
int num_rotations;
bool do_naive;
BenchmarkingTree(bool naive=false)
{
do_naive = naive;
reset();
}
void reset()
{
num_operations = 0;
num_rotations = 0;
}
void rotate(Node *node) override
{
num_rotations++;
Tree::rotate(node);
}
void splay(Node *node) override
{
num_operations++;
if (do_naive) {
while (node->parent)
rotate(node);
} else {
Tree::splay(node);
}
}
// Return the average number of rotations per operation.
double rot_per_op()
{
if (num_operations > 0)
return (double) num_rotations / num_operations;
else
return 0;
}
};
bool naive; // Use of naive rotations requested
RandomGen *rng; // Random generator object
void test_sequential()
{
for (int n=100; n<=3000; n+=100) {
BenchmarkingTree tree = BenchmarkingTree(naive);
for (int x=0; x<n; x++)
tree.insert(x);
for (int i=0; i<5; i++)
for (int x=0; x<n; x++)
tree.lookup(x);
cout << n << " " << tree.rot_per_op() << endl;
}
}
// An auxiliary function for generating a random permutation.
vector<int> random_permutation(int n)
{
vector<int> perm;
for (int i=0; i<n; i++)
perm.push_back(i);
for (int i=0; i<n-1; i++)
swap(perm[i], perm[i + rng->next_range(n-i)]);
return perm;
}
void test_random()
{
for (int e=32; e<=64; e++) {
int n = (int) pow(2, e/4.);
BenchmarkingTree tree = BenchmarkingTree(naive);
vector<int> perm = random_permutation(n);
for (int x : perm)
tree.insert(x);
for (int i=0; i<5*n; i++)
tree.lookup(rng->next_range(n));
cout << n << " " << tree.rot_per_op() << endl;
}
}
/*
* An auxiliary function for constructing arithmetic progressions.
* The vector seq will be modified to contain an arithmetic progression
* of elements in interval [A,B] starting from position s with step inc.
*/
void make_progression(vector<int> &seq, int A, int B, int s, int inc)
{
for (int i=0; i<seq.size(); i++)
while (seq[i] >= A && seq[i] <= B && s + inc*(seq[i]-A) != i)
swap(seq[i], seq[s + inc*(seq[i] - A)]);
}
void test_subset_s(int sub)
{
for (int e=32; e<=64; e++) {
int n = (int) pow(2, e/4.);
if (n < sub)
continue;
// We will insert elements in order, which contain several
// arithmetic progressions interspersed with random elements.
vector<int> seq = random_permutation(n);
make_progression(seq, n/4, n/4 + n/20, n/10, 1);
make_progression(seq, n/2, n/2 + n/20, n/10, -1);
make_progression(seq, 3*n/4, 3*n/4 + n/20, n/2, -4);
make_progression(seq, 17*n/20, 17*n/20 + n/20, 2*n/5, 5);
BenchmarkingTree tree = BenchmarkingTree(naive);
for (int x : seq)
tree.insert(x);
tree.reset();
for (int i=0; i<10000; i++)
tree.lookup(seq[rng->next_range(sub)]);
cout << sub << " " << n << " " << tree.rot_per_op() << endl;
}
}
void test_subset()
{
test_subset_s(10);
test_subset_s(100);
test_subset_s(1000);
}
vector<pair<string, function<void()>>> tests = {
{ "sequential", test_sequential },
{ "random", test_random },
{ "subset", test_subset },
};
int main(int argc, char **argv)
{
if (argc != 4) {
cerr << "Usage: " << argv[0] << " <test> <student-id> (std|naive)" << endl;
return 1;
}
string which_test = argv[1];
string id_str = argv[2];
string mode = argv[3];
try {
rng = new RandomGen(stoi(id_str));
} catch (...) {
cerr << "Invalid student ID" << endl;
return 1;
}
if (mode == "std")
naive = false;
else if (mode == "naive")
naive = true;
else
{
cerr << "Last argument must be either 'std' or 'naive'" << endl;
return 1;
}
for (const auto& test : tests) {
if (test.first == which_test)
{
cout.precision(12);
test.second();
return 0;
}
}
cerr << "Unknown test " << which_test << endl;
return 1;
}