数独を焼きなましてみた
Atcoder補助ツールを作った話
Atcoder
久しぶり競技プログラミングをしようと思い、atcoderを開き、コードを書いて提出する前にテストしようとしたところ、「この単純作業を自動化しないでなーにが競技プログラミングじゃ」という思いが芽生えました。自動化しました(車輪の再発明ですが気分転換なので無問題です)。
機能
- 問題サイトのhtmlから入力例と出力例を自動取得
- ログイン
- コードをコンパイルしてテスト
- テストを通ったら自動提出
beta atcoderを利用しています
ログイン
ログインするときに送られるpostリクエストをブラウザの開発者モードで眺めると、クロスサイトリクエストフォージェリ(2012年ごろに話題になったパソコン遠隔操作事件でも使われていたものです)対策の為に、csrf_tokenがpostされていることが分かります。
csrf_tokenはcookieの中に含まれていますが、(当人以外は知らないデータをpostのデータの中に含めることで、URLを踏ませることで不正なリクエストを送ることをを防いでいます。)ログインページのhtmlのなかに含まれているのでそこから取りました。
sessionの情報はpickleして保持しておきます。
感想
割とすぐできて便利なのでいい練習になりました。 自動テストされて提出されると気分がいいですね
Word文章にソースコードを貼る法
はじめに
皆さんはレポートを書くとき何を使うでしょうか。何だかんだでMicrosoft Wordという人も多いと思います。僕はMicrosoft Word を推しているのですが、Wordの欠点としてソースコードをうまく貼ることが出来ないことを上げる人もいます。
最近圧倒的解決法を知ったので紹介したいと思います。
方法
Visual Studio Code(以下VS code)はそこそこ良いエディタです。VS code でソースコードを開けばいい感じに色付けをしてくれます。
Wordを開き、1×1の表を挿入してVS codeで開いたソースコードを張り付けます。
こんなに綺麗に貼り付けることが出来ました。これからソースコードを貼り付けなければならないレポートにも積極的にWordを使っていきましょう。
なおこの方法はVS codeで無くても書式情報付きでテキストをコピーできるエディタなら適用できると思います。
まとめ
Wordは数式入力がゴミとよく言われますが、最近ではLaTex形式の数式入力にも対応しており複雑な数式も簡単に入力できます。Wordをガンガン使っていきましょう。
セルオートマトンで遊ぶ
はじめに
皆さんパソコンの背景は何にしていますか?なんか背景を変えたいなと思い、色彩センスはゼロですがいい感じの規則的な模様を勝手に生成させて背景にすることができたので紹介します。
忘れてしまう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=intelでintel構文のアセンブリを出力させることができます。
上記の計算部分に対応しているところだけを抜き出します。
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があります。これは何なのでしょうか。
以下のような関係式が成り立ちます
つまり
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倍にしかできないため
といううまい変形をすることで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
コード全文
#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; }