"Python for Data Analysis"を読んだ

Python for Data Analysis

Pythonによるデータ分析入門 ―NumPy、pandasを使ったデータ処理

タイトルだけ見るとnumpyの本なのかと思うが、作者はpandasの中の人で、ほぼほぼpandasの本。

最近ぼちぼちpandasを使ったブツを開発しているのだが、自分が全然numpyもpandasも理解していないまま使っていたという事がわかった…

pandasユーザー必読。それだけでなく、多分pandasとか使えると普通にありとあらゆるタスクに役立つはずなのでみんな読んだほうがいいっす。

「深層学習 (機械学習プロフェッショナルシリーズ)」を読んだ

深層学習 (機械学習プロフェッショナルシリーズ)

長年よく分かってないまま、なんとなくA君やT君の話にウンウンなるほど〜〜〜とか言ってたのを大いに恥じています。

"High-Frequency Trading" by Irene Aldridgeを読んだ

High-Frequency Trading: A Practical Guide to Algorithmic Strategies and Trading Systems (Wiley Trading)

さすがに全編ちゃんとは読めてないです…
1冊で全てをカバーするという訳ではないけれども参考文献がものすごい数しっかりと明示されているし、ここをきっかけにいろいろ調べるとっかかりがつかめて良い本だと思う。なんか米Amazonのレビューだと酷評されてるけど…
ただ如何せん読みやすい本ではないというか早足なので、個々の分野についてはそれ専門の本をしっかり読んだほうがよさそう。

「データサイエンティスト養成読本 機械学習入門編」を読んだ

データサイエンティスト養成読本 機械学習入門編 (Software Design plus)

ツールの具体例が多く挙げられており、またコードを交えた実例が多いのが良かった。

よくわかるKMP

vector<int> Build(const string& s) {
  vector<int> fail(s.size() + 1);

  int j = -1;
  fail[0] = -1;
  for (int i = 0; i < s.size(); ++i) {
    while (j >= 0 && s[i] != s[j]) j = fail[j];
    ++j;
    fail[i + 1] = j;
  }
  return fail;
}

void Match(const string& needle,
           const string& haystack,
           vector<int> *matches) {
  const vector<int> fail = Build(needle);
  matches->clear();

  int j_needle = 0;
  for (int i_haystack = 0; i_haystack < haystack.size(); ++i_haystack) {
    while (j_needle >= 0 && needle[j_needle] != haystack[i_haystack])
      j_needle = fail[j_needle];
    ++j_needle;
    if (j_needle >= needle.size()) {
      matches->push_back(i_haystack - j_needle + 1);
      j_needle = fail[j_needle];
    }
  }
}

fail配列というのを作るのがミソ。
fail配列というのは、その時点までで入力された文字列(のsuffix)と、needleのprefixが何文字一致するかというオートマトン（pattern matching automaton）を配列の形で表現したものである。

つまり1. two pointersっぽいアルゴリズムでfail配列を構築するBuildと、と 2. それを使って効率的にneedleのポインタを移動させつつhaystackとのマッチングを行うMatchからKMPのアルゴリズムは成る。

1.のBuildについてはneedleの任意地点についてneedle自身の先頭とのマッチングを線形に取っているという風にも見ることができる。したがって、例えば文字列の周期をneedle.size() - fail.back()で取るなどの用途にも使える（例: needle = "abcabc" => needle.size() - fail.back() = 3 なぜならば"abc" x 2）。

空間計算量と構築はO(|needle|)分だけ食うが検索がO(|haystack| + |needle|)になる。

よくわかる8クイーン

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

using namespace std;

void PrintQueens(const vector<int>& queens) {
  for (const int& queen : queens) {
    string s(8, '-');
    s[queen] = '*';
    cout<<s<<endl;
  }
  cout<<endl;
}

bool IsQueenPlaceable(const vector<int>& queens, int y) {
  for (int cy : queens) {
    if (cy == y) return false;
  }
  for (int cx = 0; cx < queens.size(); ++cx) {
    const int x = queens.size();
    const int cy = queens[cx];
    if (x - cx == abs(y - cy)) return false;
  }
  return true;
}

void DoCalcQueens(vector<int>& queens) {
  if (queens.size() >= 8) {
    PrintQueens(queens);
    return;
  }
  for (int i = 0; i < 8; ++i) {
    if (IsQueenPlaceable(queens, i)) {
      queens.push_back(i);
      DoCalcQueens(queens);
      queens.pop_back();
    }
  }
}

void CalcQueens() {
  vector<int> queens;
  DoCalcQueens(queens);
}

int main() {
  CalcQueens();
  return 0;
}

よくわかるヒープソート

以前のこの記事には誤ったコードが記載されておりました。自信満々に嘘コードを書いたことをお詫び申し上げます。

ぐぐって上位に出てくるコードがどれも冗長すぎる…………………

空間計算量はO(1)（追加領域を必要としない）、最悪・平均時間計算量がO(n log n)。

大体std::sortの中身になっているイントロソートは、クイックソートが深くなり過ぎたらヒープソートに切り替えるというもの。

オーダーはよいがクイックソートよりは定数項がでかい+ヒープなので空間的局所性が低くキャッシュで不利になる可能性がある？

void HeapSort(vector<int>& data) {
  // ヒープに入れていく
  // [0, i_end]
  for (int i_end = 0; i_end < data.size(); ++i_end) {
    int idx = i_end;
    while (idx > 0) {
      idx = (idx - 1) / 2;
      if (2 * idx + 1 <= i_end && data[idx] < data[2 * idx + 1]) {
        swap(data[idx], data[2 * idx + 1]);
        continue;
      }
      if (2 * idx + 2 <= i_end && data[idx] < data[2 * idx + 2]) {
        swap(data[idx], data[2 * idx + 2]);
        continue;
      }
      break;
    }
  }

  // ヒープから取り出していく
  for (int i_end = data.size() - 1; i_end >= 0; --i_end) {
    // [0, i_end]
    swap(data[0], data[i_end]);
    // now [0, i_end)
    int idx = 0;
    while (true) {
      int nidx = idx;
      if (2 * idx + 1 < i_end && data[nidx] < data[2 * idx + 1]) {
        nidx = 2 * idx + 1;
      }
      if (2 * idx + 2 < i_end && data[nidx] < data[2 * idx + 2]) {
        nidx = 2 * idx + 2;
      }
      if (idx == nidx) break;
      swap(data[idx], data[nidx]);
      idx = nidx;
    }
  }
}