tomabouの日記

勉強したことなどを書いていきます

数独を焼きなましてみた

はじめに

数独という9*9のマスに数字を入れていく有名なパズルがあります。
飛行機に乗っている間、機内ゲームの数独で遊んでいたのですが、一番レベルが高いものがなかなか解けませんでした。
足元を見るとカバンにパソコンが入っていたのでパソコンで答えを見つけることにしました。

アルゴリズムの選択

dfs

選択肢が少ないマスを選択して、深さ優先探索するというアルゴリズムがすぐ思いつきます。それを実装するとほぼ問題ないのですが、ワクワク感が無いのが難点です。

焼きなまし

アニーリングとも呼びます。このアルゴリズムは厳密解を求めるには向いていませんが、数独ぐらいなら解けそうな気もします。ワクワク感があるので実装してみることにします。

続きを読む

Atcoder補助ツールを作った話

Atcoder

久しぶり競技プログラミングをしようと思い、atcoderを開き、コードを書いて提出する前にテストしようとしたところ、「この単純作業を自動化しないでなーにが競技プログラミングじゃ」という思いが芽生えました。自動化しました(車輪の再発明ですが気分転換なので無問題です)。

機能

  • 問題サイトのhtmlから入力例と出力例を自動取得
  • ログイン
  • コードをコンパイルしてテスト
  • テストを通ったら自動提出

beta atcoderを利用しています

ログイン

ログインするときに送られるpostリクエストをブラウザの開発者モードで眺めると、クロスサイトリクエストフォージェリ(2012年ごろに話題になったパソコン遠隔操作事件でも使われていたものです)対策の為に、csrf_tokenがpostされていることが分かります。

csrf_tokenはcookieの中に含まれていますが、(当人以外は知らないデータをpostのデータの中に含めることで、URLを踏ませることで不正なリクエストを送ることをを防いでいます。)ログインページのhtmlのなかに含まれているのでそこから取りました。

sessionの情報はpickleして保持しておきます。

感想

割とすぐできて便利なのでいい練習になりました。 自動テストされて提出されると気分がいいですね

GitHub - tomabou/sports: sports programing utility

Word文章にソースコードを貼る法

はじめに

皆さんはレポートを書くとき何を使うでしょうか。何だかんだでMicrosoft Wordという人も多いと思います。僕はMicrosoft Word を推しているのですが、Wordの欠点としてソースコードをうまく貼ることが出来ないことを上げる人もいます。
最近圧倒的解決法を知ったので紹介したいと思います。

方法

Visual Studio Code(以下VS code)はそこそこ良いエディタです。VS code でソースコードを開けばいい感じに色付けをしてくれます。
f:id:tomabou:20171227232817p:plain

Wordを開き、1×1の表を挿入してVS codeで開いたソースコードを張り付けます。
f:id:tomabou:20171227233225p:plain

こんなに綺麗に貼り付けることが出来ました。これからソースコードを貼り付けなければならないレポートにも積極的にWordを使っていきましょう。
なおこの方法はVS codeで無くても書式情報付きでテキストをコピーできるエディタなら適用できると思います。

まとめ

Wordは数式入力がゴミとよく言われますが、最近ではLaTex形式の数式入力にも対応しており複雑な数式も簡単に入力できます。Wordをガンガン使っていきましょう。

セルオートマトンで遊ぶ

はじめに

皆さんパソコンの背景は何にしていますか?なんか背景を変えたいなと思い、色彩センスはゼロですがいい感じの規則的な模様を勝手に生成させて背景にすることができたので紹介します。

続きを読む

AIの「語彙力」を制御する

「よくある単語」判定

りんなというMicrosoftの作ったチャットAIがあります。りんなにしりとりを挑むと「そんな単語知るかよ」という単語を連発してきて人間はとてもではないですが勝てません。しりとりのような言葉を用いた遊びをするAIを作成するには適切にAIの語彙力を制限する必要があります。今回は日本語コーパスを利用することで「簡単な単語」かどうかを簡単に判定できる、ということを紹介したいと思います。

続きを読む

忘れてしまうsegment木

競技プログラミングは忘れたころにやりたくなります
セグメント木は便利なので忘れたころに使いたくなります
しかしライブラリを作ろうにも使いたくなるころには忘れているので紛失してしまいます。
なので備忘録変わりにセグメント木をあげておきます

普通のセグメント木

プログラミングコンテストチャレンジブックに書いてあるセグメント木は以下のようなものです。
数列と、結合法則が成り立ち零元が存在する(モノイドという)演算に対して次のことが出来ます。(例えば最小値をとる演算とします)

  • ある区間の最小値をとる
  • ある値を更新する
#include<algorithm>
#include<functional>
#include<vector>

template<typename T>
class segtree {
public:
	segtree(int n) {//数列の長さを指定してセグメント木を作る
		for (size = 1; size < n; size *= 2);
		vec.resize(2 * size -1, zero);
	}
	segtree(std::vector<T> v) {//vectorで数列を与えてセグメント木を作る
		int n = v.size();
		for (size = 1; size < n; size *= 2);
		vec.resize(2 * size -1, zero);
		for (int i = 0; i < n; i++) {
			vec[i + size-1] = v[i];
		}
		for (int i = size - 2; i >= 0; i--) {
			vec[i] = func(vec[i * 2 + 1], vec[i * 2 + 2]);
		}
	}
	void set(int n, T x) {//値の更新
		n += size - 1;
		while (n >= 0) {
			vec[n] = func(vec[n], x);
			n = (n + 1) / 2 - 1;
		}
	}
	int get(int a, int b) {//値の取得([a,b)で指定)
		return get_func(0, 0, size, a, b);
	}
private:
	T zero =2147483647;//モノイドの零元 ここを下の関数と一緒に適切なものに変えればよい
	std::function<T(T, T)> func = [](T a, T b) {return std::min(a, b); };//演算
	std::vector<T> vec;
	int size;
	
	int get_func(int n, int p, int q, int x, int y) {
		if (q - p == 1)return vec[n];
		if (x == p && q == y) return vec[n];
		int mean = (p + q) / 2;
		T l = zero;
		T r = zero;
		if (x < mean)l = get_func(n * 2 + 1, p, mean, x, std::min(y,mean));
		if (mean < y)r = get_func(n * 2 + 2, mean, q, std::max(x,mean), y);
		return func(l, r);
	}
};

普通のセグメント木の双対

数列と可換なモノイドに対して次のことが出来ます(例えば和とるとします)

  • ある区間全体に同じ数字を足す
  • ある値を取得する

これは普通のセグメント木のデータの流れを逆向きにすると実装できます(このコードはその双対が分かりやすいと思います)

template<typename T>
class segtree2 {
public:
	segtree2(int n) {
		for (size = 1; size < n; size *= 2);
		vec.resize(2 * size - 1, zero);
	}
	segtree2(std::vector<T> v) {
		int n = v.size();
		for (size = 1; size < n; size *= 2);
		vec.resize(2 * size - 1, zero);
		for (int i = 0; i < n; i++) {
			vec[i + size - 1] = v[i];
		}
		for (int i = size - 2; i >= 0; i--) {
			vec[i] = func(vec[i * 2 + 1], vec[i * 2 + 2]);
		}
	}
	T get(int n) {
		T ans = zero;
		n += size - 1;
		while (n >= 0) {
			ans = func(vec[n], ans);
			n = (n + 1) / 2 - 1;
		}
		return ans;
	}
	void set(int a, int b, T x) {
		return set_func(0, 0, size, a, b,x);
	}
private:
	T zero = 0;
	std::function<T(T, T)> func = [](T a, T b) {return a+ b; };
	std::vector<T> vec;
	int size;

	void set_func(int n, int p, int q, int x, int y, T val) {
		if (q - p == 1) {
			vec[n] = func(vec[n],val);
			return;
		}
		if (x == p && q == y) {
			vec[n] = func(vec[n], val);
			return ;
		}
		int mean = (p + q) / 2;
		if (x < mean)set_func(n * 2 + 1, p, mean, x, std::min(y, mean),val);
		if (mean < y)set_func(n * 2 + 2, mean, q, std::max(x, mean), y,val);
		return;
	}
};

c++コンパイラの頭の良さの比較

はじめに

windows10は、bash on ubuntu on windows なるものが登場し簡単にgccが導入できます。
visual studio で使用しているマイクロソフトコンパイラ(以下vc++と呼称)とどちらが高速なコードを生成できるのか調べてみたくなりました。
簡単なコードを比較し、どちらが高速か比較してみましょう

計算させるもの

次のような計算をさせたいと思います。(大体一秒程度で終わるように調整しました)

    auto start = chrono::system_clock::now();

    /*unsigned */long long x=0;
    for(/*unsigned */long long i=0;i< 1+(1ll<<28);i++){
        x+=i;
        x%=13;
    }
    auto end = chrono::system_clock::now();
    
    cout<<x<<endl;
コンパイラ かかった時間(10回平均)(signed) かかった時間(10回平均)(unsigned)
g++ on bash 914 ms 811 ms
vc++ 1089 ms 896 ms

符号付きの場合2割近く符号なしの場合一割ほどvc++が遅いです。また、符号なしの場合が符号付きの場合に比べて早くなっています。なぜこのような差が生まれたのかアセンブリを出力させて調べてみます。

vc++とg++の違い

g++では -S オプションで、vc++では /FA オプションでアセンブリを出力させることができます。
アセンブリにはAT&T構文とintel構文があるようですが、個人的にはintel構文の方が読みやすいです。g++では-masm=intelintel構文のアセンブリを出力させることができます。
上記の計算部分に対応しているところだけを抜き出します。

vc++(unsigned)のアセンブリ


ループの内部のアセンブリを抜き出すと以下のようになります(レジスタを0に初期化したりしているところは省略)

	mov	r8, 5675921253449092805	 ; 謎の数字
$LL64@main:
; Line 11
	add	rsi, rcx     ; rcxはiに対応 rsiはxに対応 この行は x+=i
; Line 12
	mov	rax, r8      ; r8に入っている謎の数字をraxに格納
	mul	rsi          ; mulはraxとの積を上位64bitをrdx、下位64bitをraxに格納
	inc	rcx          ; iをインクリメント
	shr	rdx, 2       ; 上位64bitを右に2ビットシフトし、掛け算の結果の上位66bitを求める
	imul	rax, rdx, 13 ; 掛け算の結果の上位66bitを13倍
	sub	rsi, rax     ; xから上で計算した数字を引いている
	cmp	rcx, 268435457    ; for文の条件文
	jb	SHORT $LL64@main

謎の数字 5675921253449092805があります。これは何なのでしょうか。
以下のような関係式が成り立ちます
5675921253449092805 * 13 = 2^{66} + 1
つまり
\displaystyle \frac{5675921253449092805}{2^{66}}  \approx \frac{1}{13}
2のべき乗での割り算はビットシフトで行うことが出来るため、時間のかかるdiv命令を使わなくて済むという高速化です。

上のアセンブリは以上のテクニックを生かして13で割った商を高速に求め、
その商を13倍して元の数から引くという方法であまりを計算していることがわかります。
頭いい…

g++(unsigned)のアセンブリ

ではそのvc++のコードより一割早いg++の生成したコードは何が違うのでしょうか

	movabs	rdi, 5675921253449092805 ; 同じ
.L2:
	lea	rsi, [r12+rcx]   ; r12+rcxをrsiに格納 x+=i
	add	rcx, 1           ;インクリメント
	mov	rax, rsi         ; xをraxに移して
	mul	rdi              ; 謎の数をかける
	shr	rdx, 2           ; 上位66bitをとる
	lea	rax, [rdx+rdx*2] ; raxにrdxの3倍を格納
	lea	rax, [rdx+rax*4] ; raxにrdx+rax*4を格納 つまり13倍している
	sub	rsi, rax         ; xから商の13倍を引いて
	cmp	rcx, 268435457   ; 1+(1<<28)と比較する
	mov	r12, rsi
	jne	.L2

13倍するコードを素直にmul命令を使わずlea命令に置き換えています。
lea命令はもともとアドレス計算用の命令ですが、算術演算にも使用でき、
フラグを立てず、使用する演算ユニットが違うため、*1もろもろ良いみたいです。
1,2,4倍にしかできないため
13 = 1+ 4*(1+2*1)
といううまい変形をすることでlea命令で計算できるようにしています。
めっちゃ頭いい…
なおjumpする命令が違ったりしますが、それはcmp命令が建てたフラグのうちどれを使っているかが違うだけです。

結論

どちらも頭が良いが、gccの方が頭がいい

unsignedとsignedの違い

なぜ符号付きにすると大幅に遅くなってしまうのでしょうか。
符号付き整数を表現するために2の補数表現を用いているということ、ビットシフトには論理シフトと算術シフトがあることを思い出します。

vc++の出力アセンブリ
	mov	r8, -5675921253449092805		
$LL64@main:
; Line 11
	add	rsi, rcx
; Line 12
	mov	rax, r8
	imul	rsi
	inc	rcx
	sar	rdx, 2
	mov	rax, rdx       ;rdxをrdaにコピー
	shr	rax, 63    ;63ビットシフトするという謎の処理が挟み込まれている 
	add	rdx, rax       ;63ずらしたものを足している
	imul	rax, rdx, 13
	add	rsi, rax
	cmp	rcx, 268435457	
	jl	SHORT $LL64@main

63右に論理シフトすると、もともとの数の最上位のビットが1つまり負であれば1、正であれば0です。
商が負であるときに1足すという処理をしています。

g++の出力したアセンブリ
	movabs	rdi, 5675921253449092805

.L2:
	lea	rsi, [r12+rcx]
	add	rcx, 1
	mov	rax, rsi
	imul	rdi
	mov	rax, rsi
	sar	rax, 63         ;同じく63右にビットシフトしている
	sar	rdx, 2
	sub	rdx, rax
	lea	rax, [rdx+rdx*2]
	lea	rax, [rdx+rax*4]
	sub	rsi, rax
	cmp	rcx, 268435457
	mov	r12, rsi
	jne	.L2

sarは算術シフトです。(shift arithmetic right)最上位ビットが1のとき、63ビットシフトすると全部1のビットが立った数字になり、2の補数表現では-1です。
つまり割られる数xが負ならば-1を引くという処理です

これらの計算はc++の余りの計算の仕様が数学的に不自然なため生じた処理です。c++で商が負のときは0に近い方に切り捨て、余りは負になると定められています(c++03までは処理系依存でした)これは余りが正になったり負になったりして不自然です。
割り算を掛け算に変更するテクニックを用いると、商が負のときも数学的に自然な商を超えない最大の整数が求まり、c++の求める答えと1ずれます。
そこのずれを修正するために無駄な計算をしているようです。

結論

人間の定めた仕様は頭悪い

Appendix

環境
CPU core i7-4510U
memory 8GB
OS windows 10
コード全文
#include<iostream>
#include<chrono>

using namespace std;

int main(){
    auto start = chrono::system_clock::now();

    long long x=0;
    for(long long i=0;i<1 + (1ll<<28);i++){
        x+=i;
        x%=13;
    }
    auto end = chrono::system_clock::now();
    
    cout<<x+2<<endl;

    auto diff = end - start;
    std::cout << "elapsed time = "
              <<chrono::duration_cast<std::chrono::milliseconds>(diff).count()
              << " msec."
              << endl;

    return 0;
}