Skip to content
Snippets Groups Projects
Select Git revision
  • 3ce298879a9661ed77246db413bcc6bd834c3ab5
  • master default
  • zs-dobrichovice
3 results

update-users.py

Blame
  • 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;
    }