インデックスのセットの要素をリストから除去する

C++の場合

リストvがあって,そのリストから除去したいインデックスの集合remove_id_set(3,5,2)とかで指定する要素番号の要素を除去したい.eraseすると要素番号が一つずれるので,それも考慮して一旦集合をソートして,前から順に削除していくという方法.

#include <vector>
#include <random>
#include <algorithm>
#include <iostream>

std::random_device rnd;
std::mt19937 mt(rnd());

std::vector<int> generateUniqueRandomIntegers(size_t max, int num_random_number)
{
  std::vector<int> v(max);
  std::iota(v.begin(), v.end(), 0);
  std::shuffle(v.begin(), v.end(), mt);
  v.erase(v.begin()+num_random_number, v.end());
  return v;
}


std::vector<int> eraseSetOfIndices(std::vector<int> &erase_set, std::vector<int> &v)
{
  std::sort(erase_set.begin(), erase_set.end());
  int i=0;
  for (auto index : erase_set) {
    auto it = v.begin();
    v.erase(it+index-i);
    ++i;
  }
  return v;
}


int main()
{
  std::vector<int> v(10);
  std::iota(v.begin(), v.end(), 0);

  // remove index
  std::vector<int> remove_id_set = generateUniqueRandomIntegers(9,3);
  for (auto d : remove_id_set)
    std::cout << d;
  std::cout << " are removed" <<std::endl; 

  std::vector<int> ret = eraseSetOfIndices(remove_id_set, v);
  for (auto d : ret)
      std::cout << d;
  std::cout << std::endl; 

  return 0;
}

N以下の重複しない乱数(整数)の生成

C++

良い方法かは分からないけどiotaやeraseを使った例を見つけたのでメモ.やり方は一旦iotaで[0,1,...max]の配列を作って,それをシャッフルして,eraseで必要ない部分を消す.eraseはイテレータを2つ渡すと,開始位置から終了位置の1つ前までを消去できる.

#include <random>
#include <vector>

std::random_device rnd;
std::mt19937 mt(rnd());

std::vector<int> generateUniqueRandomIntegers(size_t max, int num)
{
  std::vector<int> v(max+1); // CAUTION "max+1" !!
  std::iota(v.begin(), v.end(), 0);
  std::shuffle(v.begin(), v.end(), mt);
  v.erase(v.begin()+num, v.end());
  return v;
}

Python

同じやり方をpythonでやる場合.sampleでシーケンスからの重複しないサンプリングが出来るのでそれを使う.

import random
def generateUniqueRandomNumbers(max, num):
    return random.sample(xrange(max+1), num)

C/C++からPythonを使う

要旨

 コンパイル方法

  • 色々なライブラリやインクルードパスを指定する必要がある.それらを確認するためのツールがpython-config.MacOSだとframework pythonとかで一式いけるみたいだ.全部は要らない場合もあるから,確認してからCMakeList.txt作るのも良いかもしれない.
gcc hoge.cpp $(python-config --cflags) $(python-config --labs)

使い方(1)

  1. Py_Initialize()でPythonインタプリタを初期化.
  2. PyRun_SimpleStirng(pythonコード文字列)でpythonコードを実行する.
  3. Py_Finalize()でインタプリタを終了.
#include <cstdio>
#include <Python.h>

int main(void)
{
  Py_Initialize();
  PyRun_SimpleString("print 'hello world'");
  Py_Finalize();
    
  return 0;
}

使い方(2)

上の例は実際はあまり使わない.使い方としては既存のスクリプトの中の関数を実行するというシーンが多いはず.これはC->Pythonの例だけど,Python->Cの例も実はほとんど変わらない.やっていることは(1)データの変換,(2)外部での実行,そして(3)データの逆変換.C->PythonPython->Cでは順番が逆なだけ. 1.

  • その他メモ

  • pythonとcどっちがトップ(どっちからどっち叩くんだろう?)なんだろう?
  • topはmainモジュール

c++のスレッド

 メモ

  • c++11からはスレッドが言語に取り込まれている.
  • コンパイルには-pthreadを付ける.
  • スレッドを一時的に止めるときにはsleepではなく,スレッド用のstd::this_thread::thread_for()を使う.
  • thread::join()をちゃんと実行して対象のスレッドの終了を待つようにする.(またはdetachする.detachはスレッドを管理対象から外す.但し実行は裏で勝手に続く.これどんな時に使うんだろう?)
  • 無限ループに入れるような場合は,外から止められるように定期的に停止フラグを見に行かせる.
  • std::threadのコンストラクタに関数を渡すことでその関数を別スレッドとして実行する.関数の引数はコンストラクタの第2引数以降で渡す.
  • クラス内でメンバ関数をスレッド化するときは特殊なので注意.リファレンスで渡すこと,第2引数にthisが要ることを忘れちゃダメ
#include <iostream>
#include <thread>
#include <unistd.h>

bool stop_flg = false;

void worker(int i, int j) {
  while (1) {
    std::cout << "I'm " << std::this_thread::get_id() << " thread." << std::endl;
    std::cout << i+j << std::endl;
    if (stop_flg)
      break;
  }
  return;
}


int main(int argc, char* argv[])
{
  std::thread th(worker, 1, 2);
  sleep(2);

  stop_flg = true;
  th.join();

  return 0;
}

情報量関連のメモ

概要

機械学習とか統計を勉強していると情報量とかエントロピーの話が出てきていつも復習をし直しているので,纏めておく.

情報量

  • 事象Aが与えられた時に,その情報量って?というものに答える.
  • 確率を使って考える.発生が稀な事象と,よくある事象があった時にどっちに遭遇した場合が情報の量が増えたと思うか?ここで,稀な事象の方がゴミみたいな事象なんだから情報は無い,と考えるんじゃなくて,めったに遭遇できない事象に出会えたらそこで知れる情報の量は大きい(価値が高いって感じ?)と考える.
  • そこで,発生確率が小さいほど大きくなるような単調減少関数で情報量を定義しよう,という発想になる.
  • 次に,どんな単調減少関数がいいかな?と考える.そこで,独立性な事象における情報の加法性を考えてみる.事象AとB,それぞれの情報量I(A),I(B)があった時に,I(A∧B)は?と考えると,独立なんだから,合わさって情報量が増えることはないでしょう,単純に和でしょ?と考える.独立な確率の同時確率はP(A)*P(B).これを情報量化すると和になってくれればいい,,,,ってことでよくある-log(P)が定義される.
  • 事象A,その発生確率をP(A)とすると,情報量I(A)は以下で定義される.定義されているということが重要.あくまでも定義なんだ
I(A) = -log(P(A))    (1)

エントロピー

  • ある情報源(事象発生源)Xが与えられた時に,その情報源のランダムさは?(逆に言うとランダムでなくて推定できる部分は?)という質問に答える.
  • 情報量の期待値をエントロピーHと定義する.
  • よって,離散系なら下記で計算される.
H(x) = sum{-logP(x) * P(x)}   (2)
  • エントロピーはP(x)が一様分布の時に最大になる.一様分布な時,つまり完全ランダムな時に最大であるということ.

相互情報量

  • 2つの情報源X,Yがあった時に,その情報源の互いの情報量は?という疑問に答える.つまり,一方の情報源Xの情報を知った時に,Yの情報をどの程度わかるかな?という問い.
  • 確率の独立性と関係があるのが直感的にもわかる.
  • 計算方法は下記.ここで,H(X,Y)はXとYの同時事象の情報量の期待値(結合エントロピーと言う.XとYの両方から知れること).式から想像できるように,それぞれの独立の時のエントロピーから,重複部分を除く,というよくあるド・モルガンの図のイメージ.
I(X,Y) = H(X) + H(Y) - H(X,Y)   (3)

それぞれのエントロピーの関係

  • ド・モルガン図でイメージすると分かりやすい.
  • 事象Xのエントロピーと事象Yのエントロピーがそれぞれあるとする.
  • 相互情報量は重なっているA&Bの部分.ここが,Xを知ってYを知れることだし,Yを知ってXを知れることだもんね.
  • 結合エントロピーはA|Bなエントロピー.つまり,重複も許して,XとYから知れること.
  • 紛らわしいのが条件付きエントロピー.意味は,Xを知っている状況でYから知れること.これは包含図でいうと,H(X)-H(X&Y)の部分.つまり,重複部分を除いた,純粋にXだけからしか知れないこと.
  • もう一つ忘れてならないのがKLダイバージェンス.2つの分布の距離を測るものらしい,が式から直感的に理解ができない.2つの分布の比の一方からみた期待値,という感じなのかな?
  • KLDとMIの関係で悩むけれど,よく分からない・・・.MIは2つの確率変数X,Yに対する定義でKLDは1つの確率変数上の2つの分布で書かれているのを目にするけど,KLDはそれに限定されているのかな?もっと勉強が必要だ.

オブジェクトの配列

概要

自分で作ったオブジェクトの配列を作りたいことはよくある.特に,vectorで管理したいことはよくある.その時に,不要なコピーコンストラクタを呼ばないようにc++11以降ではpush_backの代わりにemplace_backを使う. emplace_backの引数はコンストラクタの引数として与えられる.引数を一つも取らない場合には空で実行する.

#include <iostream>
#include <string>
#include <vector>

class Person
{
private:
  std::string name;
public:
  Person() {
    cout << "default constructor" << endl;    
  };
  Person(std::string _name) {
    name = _name;
  };
  void hello() {std::cout << "I'm " << name << std::endl;};
};

int main()
{
  std::vector<std::string> names{"Nobunaga", "Ieyasu", "Hideyosi"};
  std::vector<Person> people;
  for (auto iter=names.begin(); iter != names.end(); ++iter)
    people.emplace_back(*iter);
  
  for (auto iter=people.begin(); iter != people.end(); ++iter)
    iter->hello();
  return 0;
}

ちなみに

ひさしぶりにC++を書こうとすると,いつコンストラクタが呼ばれるのかをいつも忘れて悩んでしまう.vectorで個数を指定して宣言する場合,初期化も行われる.このときは暗黙にデフォルトコンストラクタ(引数無しのコンストラクタ)が呼ばれる.

#include <iostream>
#include <string>
#include <vector>

class Person
{
private:
  std::string name;
public:
  Person() {
    cout << "default constructor" << endl;    
  };
  Person(std::string _name) {
    name = _name;
  };
  void hello() {std::cout << "I'm " << name << std::endl;};
};

int main()
{
  std::vector<std::string> names{"Nobunaga", "Ieyasu", "Hideyosi"};
  // それぞれの要素の初期化でコンストラクタが呼ばれる.この場合は3回.
  std::vector<Person> people(names.size());
 
  return 0;
}

Euler Projecect 1

100以下の整数のうち,3か5の倍数の和.

Ruby

最もシンプルにただ全部舐めていくだけ.

sum = 0
100.times do |i|
  if i%3==0 or i%5==0
    sum += i
  end
end
p sum