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

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

長年よく分かってないまま、なんとなく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;
    }
  }
}

systemd-bootのデュアルブートで1回だけ次回起動OSを変更する（grub-reboot相当）

当然EFIでデュアルブートしててsystemd-bootを使っている場合のお話です。

systemd-boot (gummiboot) がLoaderEntryOneShotというそれそのものの変数をEFI変数として公開してくれているので、efivars経由で書き込む。

例えば次回だけ自動検出のWindows 10で起動したいとする。
自動検出のWindowsはsystemd-bootではauto-windowsという名前になるので、

$ echo -en "auto-windows\0" | iconv -f ascii -t utf-16le | hexdump -C
00000000  61 00 75 00 74 00 6f 00  2d 00 77 00 69 00 6e 00  |a.u.t.o.-.w.i.n.|
00000010  64 00 6f 00 77 00 73 00  00 00                    |d.o.w.s...|
0000001a

で相当するバイナリ列を作って、頭に\x07\x00\x00\x00をつけて、rootで書き込む。

# printf "\x07\x00\x00\x00\x61\x00\x75\x00\x74\x00\x6f\x00\x2d\x00\x77\x00\x69\x00\x6e\x00\x64\x00\x6f\x00\x77\x00\x73\x00\x00\x00" > /sys/firmware/efi/efivars/LoaderEntryOneShot-4a67b082-0a4c-41cf-b6c7-440b29bb8c4f