トップ > 手慰み

ncatで遊んでみる

手慰み 計算機

ncatという超便利コマンドを恥ずかしながらいままで知らなかった。HTTPプロトコルを学ぶには最適なおもちゃだ。

www.example.com の 80番ポートに、 / を GET するという HTTP リクエストを投げてみる。

fjk@x240:~$ ncat www.example.com 80 << END
GET / HTTP/1.1
Host: www.example.com

END

すると、以下のような HTTP レスポンスが返ってくる。200番のステータスコードが帰ってきているので、リクエストはうまいこといったようだ。いろいろヘッダーフィールドについているが、こう見ると HTTP プロトコルはテキストを送って返すだけという非常に単純なプロトコルなことが分かる。

HTTP/1.1 200 OK
Accept-Ranges: bytes
Cache-Control: max-age=604800
Content-Type: text/html
Date: Tue, 12 Jul 2016 14:47:58 GMT
Etag: "359670651"
Expires: Tue, 19 Jul 2016 14:47:58 GMT
Last-Modified: Fri, 09 Aug 2013 23:54:35 GMT
Server: ECS (rhv/818F)
Vary: Accept-Encoding
X-Cache: HIT
x-ec-custom-error: 1
Content-Length: 1270

<!doctype html>
<html>
<head>
    <title>Example Domain</title>
以下略

www.google.com に GET を投げると 302 が帰ってきた。

fjk@x240:~$ ncat www.google.com 80 << END
GET / HTTP/1.1
Host: www.google.com

END

HTTP/1.1 302 Found
Cache-Control: private
Content-Type: text/html; charset=UTF-8
Location: http://www.google.co.jp/?gfe_rd=cr&ei=-AKFV4uqMq7U8AeQ67-IBA
Content-Length: 261
Date: Tue, 12 Jul 2016 14:47:20 GMT

<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>302 Moved</TITLE></HEAD><BODY>
<H1>302 Moved</H1>
The document has moved
<A HREF="http://www.google.co.jp/?gfe_rd=cr&amp;ei=-AKFV4uqMq7U8AeQ67-IBA">here</A>.
</BODY></HTML>

http://www.google.co.jp/?gfe_rd=cr&ei=-AKFV4uqMq7U8AeQ67-IBA に移動しているらしい。この文字列の意味は ncat では分からない。

ncatはソケットにリクエストを投げるだけでなくて、リクエストを待つことができる。

fjk@x240:~$ sudo ncat -l -p 8000 << END
HTTP/1.1 200 OK

<HTML><HEAD></HEAD><BODY><H1>HELLO WORLD</H1></BODY></HTML>
END

としたら、8000番ポートに接続されたときに、 HTTPレスポンスを返す。ブラウザで http://localhost:8000/ にアクセスしたら

f:id:fjkz:20160713000501p:plain

ちゃんとWebサーバーっぽい動きをしている。

リクエスト内容は標準出力に吐かれる。

GET / HTTP/1.1
Host: localhost:8000
Connection: keep-alive
Upgrade-Insecure-Requests: 1
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8
Accept-Encoding: gzip, deflate, sdch
Accept-Language: ja,en-US;q=0.8,en;q=0.6

Google Chrome は HTTP 1.1 でリクエストを投げて、Chrome のバージョンもリクエストに乗せていることが分かる。

試してみると、HTTP はテキストベースで、すごい単純なプロトコルであることが見える。もっと良いプロトコルがあるに違いないが、現実的にはこういう単純で原始的なプロトコルを組み合わせると、今の巨大なインターネットになると思うと、なんとも感慨深いものがある。

○×ゲームの神の一手を導いてみた

計算機 手慰み Python

小さい頃にノートの隅や地面で良く遊んだ○×ゲームを計算機で解いてみた。

○×ゲーム程度であれば、スクリプト言語を用いて、かつ枝刈りとかせずに終端までミニマックス法で全探索しても十分に解ける。ミニマックス法というのは、要するに負けない手を打てば勝てるという戦法で、○×ゲームのようなゲームではミニマックス法ですべての局面を調べることができれば、最善の一手が得られることが知られている。

○×ゲームは両者が最適な手を打てば引き分けとなる。先手に関しては一手目をどこに置いても、引き分けに持ち込むことができる。二手目以降からは、正しく受けないと負けてしまう。したがって、二手目を正しく受けれない可能性があるので、微妙に後手が不利かもしれない。

一手目が中の場合は、後手は隅で受ける必要がある。

f:id:fjkz:20160529221757p:plain

初手が隅の場合は、中で受ける。

f:id:fjkz:20160529221938p:plain

初手が、辺の場合は、隣の隅か中か対辺に打てばよい。

f:id:fjkz:20160529222112p:plain

以下のPythonスクリプトを実行すると、先手後手双方が最善の一手を打ち合う

fjk@x240:~/works/ox-game$ ./oxgame.py 

   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   |   |   | 
   +---+---+---+


   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   | O |   | 
   +---+---+---+


   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   |   | O |   | 
   +---+---+---+


   +---+---+---+
   | O |   |   | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   |   | O |   | 
   +---+---+---+


   +---+---+---+
   | O |   |   | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O |   | 
   +---+---+---+


   +---+---+---+
   | O |   | O | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O |   | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O |   | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O | O | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   |   | X | X | 
   +---+---+---+
   | X | O | O | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   | O | X | X | 
   +---+---+---+
   | X | O | O | 
   +---+---+---+

特に結論とかはない。

ソースコード：

KdV方程式を解いてみた

計算機 手慰み Python

KdV方程式を数値的に解いてみた。*1

KdV方程式は、以下の式で表される方程式です。

f:id:fjkz:20160508115130p:plain

非線形の偏微分方程式だけれども、手計算で頑張ることができて、よく研究されてきた方程式です。バーガース方程式と同様の非線形項に加えて、３回微分の項がある。この項は分散項と呼ばれている。

これを解いてみて、Zabusky と Kruskal による有名な報告と同じ結果が得られることを確認した。

Phys. Rev. Lett. 15, 240 (1965) - Interaction of "Solitons" in a Collisionless Plasma and the Recurrence of Initial States

コードは記事の最後に載せる。PythonでNumPyを使った。NumPyは計算が早く、forループもなくなるので良いと思った。

空間の離散化には「擬スペクトル法」を用いた。擬スペクトル法というのは実空間と波数空間を行ったり来たりして、微分値を求める方法である。時間積分は４次の「ルンゲクッタ法」を使った。これは有名ですね。

つまり、無意味に高精度な計算をしている。

Zabusky と Kruskalが見つけたように、δ = 0.022のときに面白い動きをする。YouTubeに動画を上げた。


KdV equation

初期値にはcos波を与える。

f:id:fjkz:20160511193334p:plain

非線形項のために波が切り立って来る。

f:id:fjkz:20160511193431p:plain

波の先が崩れる。

f:id:fjkz:20160511193618p:plain

小さい波に別れる。

f:id:fjkz:20160511193722p:plain

伝播していく。

f:id:fjkz:20160511193829p:plain

波が重なりあうが、合体せずにいるようになる。

f:id:fjkz:20160511193942p:plain

この小さい波は「ソリトン」といって、かなり前に物理学界で流行ったらしい。動画を見ていると、いかにも力学的に意味がありげな動きをしていて面白い。

ソースコード

*1:先日の計算が誤っていたので再投稿

ClassクラスのClassオブジェクト

計算機 手慰み Java

具体についてのクラスはインスタンスと同じもの？ - 超ウィザード級ハッカーのたのしみ

クラスって何なのだろうと疑問に思い始めた。

さて、Javaにはjava.lang.Classクラスという変なクラスがある。Classクラスのオブジェクトはクラスそのものではないみたい。

面白いのは、ClassクラスのClassオブジェクトもあることだ。

Class<?> class2 = Class.class;

<?>でなしに、<Class>と明記することもできる。

Class<Class> class3 = Class.class;
      ^^^^^

そうすると<Class>がWarningとなる。何のクラスのClassクラスか分からないからだ。

しかし、

Class<Class<?>> class4 = Class.class;
Class<Class<?>> class5 = Class<?>.class;
Class<Class<?>> class6 = Class<Class>.class;

これらはコンパイルエラーになってしまう。

だから何という話だけれども、自己言及はパラドックスを伴うこともあるので、Javaの言語仕様はパラドックスでもなんでもないが、表現しきれないという事実がちょっと面白いなと思った。

HTMLでクールな履歴書

計算機 手慰み

職務経歴書いわゆるresume・CVというものをHTMLでかっこ良く書けないかと頑張ってテンプレート的なものを作った。何の意味があるかは知らない――単に組版が好きなので手慰みでやっているだけです。

以下がWebブラウザからのサンプル：

https://htmlpreview.github.io/?https://raw.githubusercontent.com/fjkz/web_resume/master/resume.html

使う人がいるかは知りませんが、ページをローカルに保存して、直に編集すれば使えます。

昔、以下のテンプレートを使ってLaTeXでレジュメを作ってみたことがあるが今どきLaTeXが使えたところで誰も評価してくれない。

Using the LaTeX Resume Templates

CSSを駆使して組版するのが今どきなのではないかと思ったりします。

Bootstrapを使いました。ブラウザで印刷してPDFに出力しても体裁は維持できる。こんな感じです。

f:id:fjkz:20151123223403j:plain

ステップ数を測るツール

計算機 手慰み Python

コードの行数を測るツールはいろいろあるが、diffで見ることが前提で数えるツールでいいのを知らなかったので手慰みに作った。

GitHub - fjkz/tloc: A trivial code line counter for diff.

こんな感じでファイルごとに行数を出してくれる。

$ git diff | ./tloc.py
Name          Code Comment Blank
--------------------------------
.gitignore  +    2       0     0
            -    0       0     0
LISENCE.txt +    0      16     9
            -    0       0     0
README.md   +    0      19     3
            -    0       0     0
tloc.py     +  115      35    40
            -    0       0     0
--------------------------------
Total       +  117      70    52
            -    0       0     0

昔の記事で貼り付けたシェルコマンドとやっていることはほとんど一緒です。diffの情報量を落として丸めているだけです。

開発ステップ数を測る - 超ウィザード級ハッカーのたのしみ

これだけ頑張りましたよという作業報告には便利かもね。コードの数で頑張りを管理するなんて、いわゆる技術的負債が増えるだけの愚策だと思いますが……むしろ減らしたことを評価するべきなんだけど、難しいですよね。

本当に使える見積もり技術 改訂第3版

本当に使える見積もり技術 改訂第3版

非常に単純なPaxos実装

計算機 手慰み

Paxosという分散システムでconsensusを取得するアルゴリズムがある。複数台のマシンから構成されるシステムで、単一のproposalが共有されることを保証するものである。ネットワークが不安定だったりシステムを構成するマシンが落ちたりするので、複数台のマシンが情報を共有するというのは難しいものなのだ。

Leslie Lamport*1の『Paxos Made Simple』を読んで勉強中です。

証明は非常に難しいらしいが、アルゴリズム自体は単純です*2。以下に、記事からPaxosアルゴリズムの流れを引用します。

Phase 1.

  1. A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

  2. If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Phase 2.

  1. If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

  2. If an acceptor receives an accept request for a proposal numbered n it accepts the proposal unless it has already responded a prepare request having a number greater than n.

ミソはprepare requestとaccept requestの２回に分けてproposeを行う点である。データベースでのtwo-phase commitによく似ている。詳しくないので分からないが、本質的には同じものなのかな？

練習で実装してみた。

A simple Paxos implementation for study.

特に結論とかはない。

世界でもっとも強力な9のアルゴリズム

世界でもっとも強力な9のアルゴリズム

*1:神と呼ばれる人の一人です。

*2:もっと簡単なRaftというアルゴリズムもあるらしい。