include/lshkit/eval.h

Go to the documentation of this file.

/* 
    Copyright (C) 2008 Wei Dong <wdong@princeton.edu>. All Rights Reserved.
  
    This file is part of LSHKIT.
  
    LSHKIT is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    LSHKIT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with LSHKIT.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef __LSHKIT_EVAL__
#define __LSHKIT_EVAL__

#include <cmath>
#include <limits>
#include <vector>
#include <algorithm>
#include <fstream>
#include <boost/random.hpp>
#include <lshkit/topk.h>


namespace lshkit {


template <typename RNG>
void SampleQueries (std::vector<unsigned> *qry, unsigned max, RNG
        &rng)
{
    boost::variate_generator<RNG &, UniformUnsigned> gen(rng, UniformUnsigned(0,
                max-1));
    for (unsigned i = 0; i < qry->size(); ++i)
    {
        for (;;)
        {
            qry->at(i) = gen();
            unsigned j;
            for (j = 0; j < i; j++) if (qry->at(i) == qry->at(j)) break;
            if (j >= i) break;
        }
    }
}



template <typename KEY = unsigned>
class Benchmark
{
    unsigned Q_;

    std::vector<unsigned> queries_;
    std::vector<Topk<KEY> > topks_;
public:
    Benchmark(): Q_(0) {}

    void resize(unsigned Q, unsigned K = 0)
    {
        Q_ = Q;
        queries_.resize(Q);
        topks_.resize(Q);
        if (K > 0) {
            BOOST_FOREACH(Topk<KEY> &knn, topks_) {
                if (knn.size() < K) throw std::runtime_error("BENCHMARK NOT LARGE ENOUGH");
                knn.resize(K);
            }
        }
    }

    // Random initialization
    void init(unsigned Q, unsigned maxID) {
        Q_ = Q;
        queries_.resize(Q);
        topks_.resize(Q);

        DefaultRng rng;
        SampleQueries(&queries_, maxID, rng);
    }

    ~Benchmark() {}

    void load (std::istream &is)
    {
        std::string line;
        queries_.clear();
        topks_.clear();
        for (;;) {
            unsigned q, k;
            is >> q;
            if (!is) break;
            queries_.push_back(q);
            is >> k;
            topks_.push_back(Topk<KEY>());
            topks_.back().resize(k);
            for (unsigned j = 0; j < k; j++) {
                is >> topks_.back()[j].key;
                is >> topks_.back()[j].dist;
            }
        }
        Q_ = queries_.size();
    }

    void save (std::ostream &os) const
    {
        for (unsigned i = 0; i < Q_; i++) {
            os << queries_[i] << '\t' << topks_[i].size() << '\t';
            for (unsigned j = 0; j < topks_[i].size(); j++) {
                os << '\t' <<  topks_[i][j].key;
                os << '\t' <<  topks_[i][j].dist;
            }
            os << std::endl;
        }
    }

    void load (const std::string &path)
    {
        std::ifstream is(path.c_str());
        load(is);
        is.close();
    }

    void save (const std::string &path) const
    {
        std::ofstream os(path.c_str());
        save(os);
        os.close();
    }

    unsigned getQ () const { return Q_; }

    unsigned getQuery (unsigned n) const {  return queries_[n]; }

    const Topk<KEY> &getAnswer (unsigned n) const { return topks_[n]; }

    Topk<KEY> &getAnswer (unsigned n) { return topks_[n]; }
};



class Stat
{
    int count;
    float sum;
    float sum2;
    float min;
    float max;
public:
    Stat () : count(0), sum(0), sum2(0), min(std::numeric_limits<float>::max()), max(-std::numeric_limits<float>::max()) {
    }

    ~Stat () {
    }

    void reset () {
        count = 0;
        sum = sum2 = 0;
        min = std::numeric_limits<float>::max();
        max = -std::numeric_limits<float>::max();
    }

    void append (float r)
    {
        count++;
        sum += r;
        sum2 += r*r;
        if (r > max) max = r;
        if (r < min) min = r;
    }

    Stat & operator<< (float r) { append(r); return *this; }

    int getCount() const { return count; }
    float getSum() const { return sum; }
    float getAvg() const { return sum/count; }
    float getMax() const { return max; }
    float getMin() const { return min; }
    float getStd() const
    {
        if (count > 1) return std::sqrt((sum2 - (sum/count) * sum)/(count - 1)); 
        else return 0; 
    }

    void merge (const Stat &stat)
    {
        count += stat.count;
        sum += stat.sum;
        sum2 += stat.sum2;
        if (stat.min < min) min = stat.min;
        if (stat.max > max) max = stat.max;
    }
};

/*
class Timer
{
    struct  timeval start; 
public:
    Timer () {}
    void tick ()
    {
        gettimeofday(&start, 0); 
    }
    float tuck (const char *msg) const
    {
        struct timeval end;
        float   diff; 
        gettimeofday(&end, 0); 

        diff = (end.tv_sec - start.tv_sec) 
                + (end.tv_usec - start.tv_usec) * 0.000001; 
        if (msg != 0) {
            std::cout << msg << ':' <<  diff << std::endl;
        }
        return diff;
    }
};
*/

}

#endif

---