貯蔵庫サンプリング(Reservoir sampling)

algorithm

入力(数>n)からn個をランダムに選択する方法。

1. 最初のn個をI[0]...I[n-1]にコピーする。t = n - 1。
2. 入力値がなかったら、5へ。
3. ++tとし、[0, t]の一様乱数uを生成する。 u >= nならば、2へ。
4. I[u] = I[t]とし、2へ。
5. Iをソートして終了。

#include <random>
#include <iostream>
#include <vector>
#include <assert.h>
#include <algorithm>

template <typename U>
const std::vector<int>& generate(
	U& u, 
	const std::vector<int>& inputs, 
	std::vector<int>& i, 
	std::size_t n, 
	std::size_t t)
{
	if (inputs.size() <= t) {
		std::sort(i.begin(), i.end());
		return i;
	}
	std::size_t r = static_cast<std::size_t>(t * u());
	++t;
	if (r >= n) return generate(u, inputs, i, n, t);
	i[r] = inputs[t];
	return generate(u, inputs, i, n, t);
}


template <typename U>
std::vector<int> generate(
	U& u,
	const std::vector<int>& inputs,
	std::size_t n)
{
	assert(inputs.size() >= n);
	std::vector<int> results(inputs.begin(), inputs.begin() + n);
	return generate(u, inputs, results, n, n);
}


int main() 
{
	unsigned int seed = 54635;
	std::mt19937 mt(seed);
	std::uniform_real_distribution<double> d;

	std::size_t size = 100;
	std::vector<int> inputs(size);
	for (std::size_t j = 0; j < inputs.size(); ++j) {
		inputs[j] = j;
	}

	std::size_t n = 10;
	std::vector<int> r = generate([&]() {return d(mt); }, inputs, n);

	for (auto x : r) std::cout << x << std::endl;
	return 0;
}

選択サンプリング法(selection sampling technique)

algorithm

N個の中からランダムにn個のを選択するためのアルゴリズム


1. t = 0, m = 0とする。
2. [0, 1]の一様乱数uを生成する。
3. もし、 (N - t) * u >= n - m ならば5へ。それ以外ないなら4へ。
4. tを採用し、++t, ++mとする。もしm < nなら、1へ。　そうでないなら終了。
5. ++tとし、2へ。

template <typename U>
void generate(U& u, int size, int n, int t = 0, int m = 0)
{
	if ((size - t) * u() > n - m) {
		return generate(u, size, n, ++t, m);
	}
	std::cout << t << std::endl;
	if (m + 1 < n) {
		return generate(u, size, n, ++t, ++m);
	}
}


int main()
{
	unsigned int seed = 544;
	std::mt19937 mt(seed);
	std::uniform_real_distribution<double> d;

	int size = 100;
	int n = 10;
	generate([&]() {return d(mt); }, size, n);

	return 0;
}

C++のクラスをC#で継承する。swig使用。

c++ c# swig

まさかこんなことができるとは思っていなかった。

やりたいこと

  • C++で定義されたコードをC#で継承してい使用する。

参考

cpp

class Base {
public:
    virtual ~Base() {}
    virtual void tell() const = 0;
};

class Caller {
public:
   void apply(const Base& base) const {base.tell();}
};

*.i

%module (directors="1") SwigSample
%{
#include "../SwingSample.h"
%}

%feature("director") Base;

c#

    class MyBase: Base {
        public override void tell() 
        {
            Console.WriteLine("Yes!!");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Caller c = new Caller ();
            MyBase b = new MyBase();
            c.apply(b);

        }
    }

Mix-InによるCloneableの実装

c++

したいこと

  • clone関数を継承によって実装したい。
  • 下記のような感じにしたい。
  • A, Bはクラスはclone関数をオーバーライドしていないけど、Cloneableを継承することで、cloneができるようになる。
  • struct B : public Cloneable　とすることで、BはAを継承したい。
struct A : public Cloneable<A> {
public:
	virtual void tell() { std::cout << "A" << std::endl; }
};
struct B : public Cloneable<B, A> {
public:
	virtual void tell() { std::cout << "B" << std::endl; }
};
int main() {
    std::shared_ptr<A> ca(A().clone());
    std::shared_ptr<A> cb(B().clone());
}

単純にすると上手くいかない

  • 次のようにすると「'Cloneable::clone': オーバーライドする仮想関数の戻り値の型が異なり、'Cloneable::clone' の covariant ではありません。」と怒られる。
  • BはAをCloneableを通して、継承しているので、B*はA*の共変戻り値なのだが、CRTPとMixInにより、コンパイル時に判定できないっぽい。
template <typename T, typename Base = T>
struct Cloneable : public Base {
public:
	virtual T* clone() const { return new T(static_cast<const T&>(*this)); }
};

template <typename T>
struct Cloneable<T, T>{
public:
	virtual T* clone() const { return new T(static_cast<const T&>(*this)); }
};

解決方法

  • non-Templateな抽象クラスICloneBaseを定義し、virtualなdoClone()はICloneBase*を返し、non-virtualなclone()はCRTPにより判明している自分の型にstatic_castする。
struct ICloneBase {
private:
	virtual ICloneBase* doClone() const = 0;
};

template <typename T, typename Base = ICloneBase>
struct Cloneable : public Base {
public:
	T* clone() const { return static_cast<T*>(this->doClone()); }
private:
	virtual ICloneBase* doClone() const { return new T(static_cast<const T&>(*this)); }
};


struct A : public Cloneable<A> {
public: 
	virtual void tell() { std::cout << "A" << std::endl; }
};
struct B : public Cloneable<B, A> {
public:
	virtual void tell() { std::cout << "B" << std::endl; }
};
struct C : public Cloneable<C, B> {
public:
	virtual void tell() { std::cout << "C" << std::endl; }
};

int main()
{
	A a;
	B b;
	C c;
	std::shared_ptr<A> ca1(a.clone());
	std::shared_ptr<A> cb1(b.clone());
	std::shared_ptr<A> cc1(c.clone());
	ca1->tell();
	cb1->tell();
	cc1->tell();
	std::shared_ptr<A> ca2(ca1->clone());
	std::shared_ptr<A> cb2(cb1->clone());
	std::shared_ptr<A> cc2(cc1->clone());
	ca2->tell();
	cb2->tell();
	cc2->tell();
	return 0;
}

sample code

std::vector<T>をC#から使えるようにする。

c++ c# swig
  • swigを使用。
  • SwigSample.i
%include std_vector.i
%template(VectorDouble) std::vector<double>;

のようにすればよい。C#でVectorDoubleという名前でstd::vectorが使用できるようになる。

あとはいつも通り

swig -csharp -c++ SwigSample.i