よくわかる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

情報系の人が株をやってみたくなった時にまず読むべき10冊

情報系の学生さんなどが株をやってみたくなるというのはTLを見ていてもよくあることだと思います。
しかし、情報系の方が予備知識なく株や為替の取引に手を出そうとすると、ついつい時系列データをニューラルネットワークにぶちこんで予測をはじめたりなど、気がつけばコンピュータ占星術の世界に突入してしまうことが多いようです。

教授が、「株をやりたいんだったらまず10冊本を読んでください。読み終わったら好きにやってもいいです。」と言っていましたが本当にそのとおりです。それに、プログラマなんだから、車輪の再発明は避けたいです。

そこで今日は皆さんが占星術の誘惑を跳ね除け、株投資をはじめるまでに読むべき10冊をピックアップしました。

ウォール街のランダム・ウォーカー

ウォール街のランダム・ウォーカー <原著第10版>―株式投資の不滅の真理

ウォール街のランダム・ウォーカー <原著第10版>―株式投資の不滅の真理

この本は端的に言えば、どんなにがんばって激しく取引をしても、ランダムに選んだ株を持ち続けたほうが儲かる!というのが主題の本です。いきなりトレード全否定!

ホントかよ、って感じですが、これは実はかなり主流に近い立場です。

マルキールという有名な学者さんの書いた一般向けの株の本で、紹介される逸話も多く、全体の世界観を把握するには格好の一冊です。(Palm株の話とかドットコムバブルの話も出てくるよ!)

また、手段としてインデックス投資を取るかは別にしても、効率市場仮説がおよそ成り立つというのはまともな教科書上では大前提なので、ここに書いてあることをベースとして知識を広げていくと良いと思います。

個人が手数料も込みでアクティブに取引して利益を上げるのはむずかしい、というのが基本的な主張なので、例えばここの批判は的外れです。

インベストメント 上・下 (Bodie, Kane, Marcus)

インベストメント<第8版>(上)

インベストメント<第8版>(上)

インベストメント<第8版>(下)

インベストメント<第8版>(下)

MBAのひとたちが投資の基礎を勉強する時に使う教科書です。

そもそも金融市場ではどんな物が売られているのか知っていますか?ぼくは知りませんでした・・・(オプション・先物 etc.)
そういった基本的なことがわかる本です。
分厚い割には記述が雑であまり好きにはなれませんが、下手な株本よりはいいのかなと思います。

金融工学入門 (Investment Science)

金融工学入門 第2版

金融工学入門 第2版

たぶん情報系の学生が一番楽しめる本だと思います。
金融工学の入門レベルの教科書ですが、完全に理論の世界なので歯切れも良く、かっこいいです。
読んでる最中ずっとspace catみたいな顔してました(債券のイミュニゼーションのあたりとか)。
インベストメントを読んだ後だと実務と比較対象して読めると思いますが、僕はこちらを先に読みました。

Quantitative Trading by Ernest Chan

ここまで読んだらすでに結構分量があってだいぶ息切れしてると思いますが、いよいよコンピュータ取引に関する本です。

分量の割に高いとか、別に儲かる方法は書いてないとかいう意見もあるようですが、この順番で読んだ限りでは楽しく読めました。

ここまでの本で学んだ、市場がほぼ効率的という話といかに矛盾しないで儲けるかというのが主題です。

この本の最後にさらっと書いてある結論としては、このような個人のトレーダーは、小規模な流動性の供給者になり、その分の報酬を得ている、そういったニッチ市場だから大規模なヘッジファンド共存できる、とのことでしたが、本当かどうかはしりません。

また、個人トレーダーは取引戦略をおおむね公にしたほうが有利だからネットにも情報が転がってるって書いてあってなるほど〜って思いましたが本当かどうかは知りません。

Algorithmic Trading & DMA by Barry Johnson

Algorithmic Trading and DMA: An Introduction to Direct Access Trading Strategies

Algorithmic Trading and DMA: An Introduction to Direct Access Trading Strategies

Quantitative Tradingは軽めの本でしたが、この分野に関する教科書的な本です。
DMAといってもメモリにデータを転送したりはしないです。

この教科書を採用している授業の授業スライドを見つけたので貼っておきます。雰囲気が分かるかもしれません。

FE 670 - Algorithmic Trading

経済・ファイナンスデータの計量時系列分析 (沖本 竜義)

経済・ファイナンスデータの計量時系列分析 (統計ライブラリー)

経済・ファイナンスデータの計量時系列分析 (統計ライブラリー)

自分で新しい取引アルゴリズムを構築するには、一つは市場経済に関する正しい知識と、もう一つは正しい統計学の知識が必要だと思いますが、その統計学サイドの本です。

Trading and Exchanges by Larry Harris

以降は金融の分野での教科書です。さらに理解を深めたい人向けといった感じです。

市場の効率性や流動性といった他の教科書でごまかされがちなテーマについての本だと思います。すばらしいことにPDFが公式でネットあります!

Trading and Exchanges by Larry Harris

Modern Portfolio Theory and Investment Analysis

Modern Portfolio Theory and Investment Analysis

Modern Portfolio Theory and Investment Analysis

金融工学入門でも現代ポートフォリオ理論についてはそこそこ触れられていましたが、それに関するより詳しい教科書です。

ファイナンシャルエンジニアリング(Options, Futures, and Other Derivatives)

フィナンシャルエンジニアリング―デリバティブ取引とリスク管理の総体系

フィナンシャルエンジニアリング―デリバティブ取引とリスク管理の総体系

邦題があたかも金融工学全般の本かのようですが、原題はOptions, Futures and Other Derivativesです。
たしかにデリバティブの価格付けは金融工学の重要分野かもしれませんが・・・

すごく分厚くてヤバイです。

おまけ: 経済学編

以上は投資の分野に関する本でしたが、本当は経済全体に対する理解があった上で投資できるに越したことはありません。

バフェットなどアメリカの著名な投資家の多くは、バリュー株(安く評価されている株)を買って持ち続けることで財を成しましたが、ソロスなど、マクロ経済に対する深い考察から、アクティブ運用で財を成した投資家もいます。マクロ経済に深い洞察があればおかねもちになれるかも・・・!

クルーグマン ミクロ経済学マクロ経済学

クルーグマン ミクロ経済学

クルーグマン ミクロ経済学

クルーグマンマクロ経済学

クルーグマンマクロ経済学

言わずと知れたクルーグマンのマクミクです。読むと経済学部のひとに自慢できます。

マクロはスティグリッツを読めとかも聞きますがどうなんですか?

クルーグマン 国際経済学 上・下

クルーグマンの国際経済学 上 貿易編

クルーグマンの国際経済学 上 貿易編

クルーグマンの国際経済学 下 金融編

クルーグマンの国際経済学 下 金融編

国際分散投資を考えるなら、国際経済についての知識も必要ですね!

ファスト&スロー 上・下

いろんな所で体のいい言い訳に使われてかわいそうな、行動経済学の本です。(体のいい言い訳の例
FXのひとたちが「テクニカル分析や行動ファイナンスの応用を・・・」とか言い始めたときにはどうしようかとおもいましたが、たぶん行動ファイナンスがそういうもの
じゃないって分かる本なんだとおもいます。たぶん。

一般書なので読みやすいと思います。



以上の本を極めて、最強のアルゴリズムトレーダーになろう!
ぼくはあきらめてインデックスETF買いました。

「Quantitative Trading」を読んだ

なんかAmazon.comのレビューでけなされているが、言われてるほど悪く無いと思う。たしかに薄いが。
内容としての浅さはあるが、おかしな立場は取っておらず、出典も明示されているので、基本的な教科書を読んだ後の息抜きの一冊に。

「インベストメント<第8版>」(BKM)を読んだ

インベストメント<第8版>(上)

インベストメント<第8版>(上)

インベストメント<第8版>(下)

インベストメント<第8版>(下)

実務の教科書。MBA行った人は大体これをやるらしい。

金融工学入門と比べると歯切れが悪い。多方面の立場に配慮しているような印象がある。また記述が雑な印象があり、「これがブラック・ショールズ方程式です」とか言いつつ、いきなりヨーロピアンコールオプションの解のみ書いてきたりする。しかし、全体を俯瞰するにあたっては良い本だと思う。

「ウォール街のランダム・ウォーカー」「金融工学入門(Investment Science)」を読んだ

ウォール街のランダム・ウォーカー <原著第10版>―株式投資の不滅の真理

ウォール街のランダム・ウォーカー <原著第10版>―株式投資の不滅の真理

金融工学入門 第2版

金融工学入門 第2版

ランダム・ウォーカーは多分この分野では一番有名な一般書。教科書的ではない逸話などが多く書かれており楽しい。また、基本的な事項が網羅されており、全体を俯瞰するにあたってまず読んでおいて損はない1冊ではないか。

金融工学入門は理工系の学生で興味があれば予備知識無しで読んでもそれなりに楽しめるように思う。