AlgorithmBestBits.hpp

[詳解]

#ifndef MTTOOLBOX_ALGORITHM_BEST_BITS_HPP
#define MTTOOLBOX_ALGORITHM_BEST_BITS_HPP

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <unistd.h>
#if __cplusplus >= 201103L
#include <memory>
#else // memory
#define MTTOOLBOX_USE_TR1
#include <tr1/memory>
#endif
#include <vector>
#include <MTToolBox/AlgorithmTempering.hpp>
#include <MTToolBox/TemperingCalculatable.hpp>
#include <MTToolBox/AlgorithmEquidistribution.hpp>
#include <MTToolBox/util.hpp>

#if defined(DEBUG)
#include <sstream>
#endif

namespace MTToolBox {
    using namespace std;
#if defined(MTTOOLBOX_USE_TR1)
    using std::tr1::shared_ptr;
#else
    using std::shared_ptr;
#endif

    template<typename U>
    class temper_params {
    public:
        U * param;
        int delta;
        int size;

        temper_params(int param_num) {
            size = param_num;
            delta = 0;
            param = new U[param_num];
            for (int i = 0; i < param_num; i++) {
                param[i] = 0;
            }
        }

        ~temper_params() {
            delete[] param;
        }
#if defined(DEBUG)
        string toString() {
            stringstream ss;
            ss << "[";
            ss << dec << delta << ":";
            for (int i = 0; i < size; i++) {
                ss << hex << setw(8) << setfill('0') << param[i] << ",";
            }
            ss << "]";
            return ss.str();
        }
#endif
    };

    template<typename U, typename V = U>
    class AlgorithmBestBits : public AlgorithmTempering<U, V> {
    public:
        typedef temper_params<U> tempp;

        AlgorithmBestBits(int out_bit_length,
                          const int shift_values[],
                          int param_num,
                          int limit_v) {
            limit = limit_v;
            obSize = bit_size<U>();
            bit_len = out_bit_length;
            size = param_num;
            shifts = new int[size];
            num_pat = size * (size + 1) / 2;
            for (int i = 0; i < size; i++) {
                shifts[i] = shift_values[i];
            }
        }

        ~AlgorithmBestBits() {
            delete[] shifts;
        }

        int operator()(TemperingCalculatable<U, V>& rand,
                       bool verbose = false) {
            rand.resetReverseOutput();
            if (verbose) {
                cout << "searching from MSB" << endl;
            }
            shared_ptr<tempp> initial(new tempp(size));
            initial->delta = 0;
            for (int i = 0; i < size; i++) {
                initial->param[i] = 0;
            }
            vector<shared_ptr<tempp> > params;
            params.push_back(initial);
            int delta = 0;
#if defined(DEBUG)
            cout << "DEBUG: bit_len = " << dec << bit_len << endl;
#endif
            for (int p = 0; p < limit; p++) {
                vector<shared_ptr<tempp> > current;
                current.clear();
                for (unsigned int i = 0; i < params.size(); i++) {
                    search_best_temper(rand, p, *params[i],
                                       current, verbose);
                }
                delta = rand.bitSize() * obSize;
                for (unsigned int i = 0; i < current.size(); i++) {
                    if (current[i]->delta < delta) {
                        delta = current[i]->delta;
                    }
                }
#if defined(DEBUG)
                cout << "DEBUG: delta = " << dec << delta << endl;
#endif
                if (verbose) {
                    cout << "delta = " << dec << delta << endl;
                }
                params.clear();
                for (unsigned int i = 0; i < current.size(); i++) {
                    if (current[i]->delta == delta) {
                        params.push_back(current[i]);
                    }
                }
            }
            U mask = 0;
            mask = ~mask;
            for (int i = 0; i < size; i++) {
                rand.setTemperingPattern(mask, params[0]->param[i], i);
            }
            rand.setUpTempering();
            if (verbose) {
                cout << "delta = " << dec << delta << endl;
            }
            rand.resetReverseOutput();
            return 0;
        }

        bool isLSBTempering() const {
            return false;
        }
    private:
        int limit;
        int bit_len;
        int size;
        int obSize;
        int * shifts;
        int num_pat;

        void search_best_temper(TemperingCalculatable<U, V>& rand,
                                int v_bit,
                                const tempp& para,
                                vector<shared_ptr<tempp> >& current,
                                bool verbose) {
            int delta = rand.bitSize() * obSize;
            U mask = 0;
            mask = ~mask;
            // size が 2 なら 111, 110, 101, 100, 011, 010, 001, 000 の8パターン
            num_pat = size * (size + 1) / 2;
            for (int32_t i = (1 << num_pat) -1; i >= 0; i--) {
                if (! inRange(i, v_bit)) {
                    continue;
                }
                shared_ptr<tempp> pattern(new tempp(size));
                make_pattern(*pattern, i, v_bit, para);
#if defined(DEBUG)
                cout << "pattern:" << pattern->toString() << endl;
#endif
                for (int j = 0; j < size; j++) {
                    rand.setTemperingPattern(mask, pattern->param[j], j);
                }
                pattern->delta = get_equidist(rand, v_bit + 1);
                if (verbose) {
                    cout << "pattern->delta:" << dec << pattern->delta << endl;
                }
                if (pattern->delta <= delta) {
                    current.push_back(pattern);
                    delta = pattern->delta;
                }
            }
        }

        int get_equidist(TemperingCalculatable<U, V>& rand,
                         int bit_length) {
            AlgorithmEquidistribution<U, V> sb(rand, bit_length);
            int veq[bit_length];
            return sb.get_all_equidist(veq);
        }

        void make_pattern(tempp& result,
                          int pat, int v, const tempp& para) const {
            result.delta = 0;
            for (int i = 0; i < result.size; i++) {
                result.param[i] = para.param[i];
            }
            U para_mask = 0;
            para_mask = (~para_mask) >> v;
            int index = 0;
            int idx = 0;
            int rdx = size - 1;
            U mask = 1 << (num_pat - 1);
            int sum = 0;
            U one = 1;
            while (mask != 0) {
                if ((pat & mask) && (obSize > v + sum + 1)) {
                    result.param[index] |= (one << (obSize - v - sum - 1))
                    & para_mask;
                } else if (((pat & mask) == 0) && (obSize > v + sum + 1)) {
                    result.param[index] &= ~(one << (obSize - v - sum - 1));
                }
                mask = mask >> 1;
                index = index + 1;
                if (index >= size) {
                    sum += shifts[rdx];
                    index = idx;
                    idx++;
                    rdx--;
                }
            }

#if defined(DEBUG)
            cout << "make_pattern:" << dec << pat << ","
                 << dec << v << "," << result.toString()
                 << hex << para_mask << endl;
#endif
        }

        bool inRange(int pat, int v) const {
            int index = 0;
            int idx = 0;
            int rdx = size - 1;
            U mask = 1 << (num_pat - 1);
            int sum = 0;
            while (mask != 0) {
                if ((pat & mask) && (v + shifts[index] + sum > obSize)) {
                    return false;
                }
                mask = mask >> 1;
                index = index + 1;
                if (index >= size) {
                    sum += shifts[rdx];
                    index = idx;
                    idx++;
                    rdx--;
                }
            }
            return true;
        }
    };
}
#if defined(MTTOOLBOX_USE_TR1)
#undef MTTOOLBOX_USE_TR1
#endif
#endif // MTTOOLBOX_ALGORITHM_BEST_BITS_HPP