読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

楽天で買い物した時に出るメルマガ購読のチェックボックスを自動で外す

嫌がらせとしか思えない

// ==UserScript==
// @name        fuckin rakuten checkbox
// @namespace   cloudear8
// @description uncheck them all
// @include     https://basket.step.rakuten.co.jp/*
// @version     1
// @grant       none
// ==/UserScript==

var inputs = document.getElementsByTagName("input");

for (var i = 0; i < inputs.length; i++) {
  if (inputs[i].attributes["type"].value == "checkbox") {
    inputs[i].checked = false;
  }
}

Greasemonkey用です。

楽天は3ヶ月に1回コンタクトを買うのにしか使っていませんが、勝手にメルマガ購読させようとしてくるだけで一気に使う気が失せてきます。

PFDSを読む: Binomial Heap

Binomial Heapとは、Binomial Treeというデータ構造を使って作られるヒープです。

ここで、Binomial Treeとは、以下のようなデータ構造です。

  • rankが0であるBinomial Treeは、ただ1つのノードからなるシングルトン
  • r > 0 について、rankがrであるBinomial Treeはr個の子を持ち、それらのrankはそれぞれ0, 1, ..., r - 1

この時、rankがrのBinomial Treeは、ちょうど2^r個の子を持つことになります。

証明:
rankがrのBinomial Treeの要素数a_rとすると、
a_0 = 1
a_r = 1 + \Sigma_{k = 0}^{r - 1}a_k
したがって、
a_{r+1} - a_r = (1 + \Sigma_{k = 0}^{r}a_k) - (1 + \Sigma_{k = 0}^{r - 1}a_k)
= a_r
\therefore a_{r+1} = 2a_r
よって、a_{r} = 2^{r}a_0 = 2^r

この性質は、実際にツリーを見てみるとわかりやすいと思います。

f:id:cloudear8:20170507113403p:plain

Binomial Heapは、同じrankを持たないBinomial Treeのリストとして定義されます。rank rのBinomial Treeの要素数2^r個ですから、二進数と同じ原理で、任意個の要素を持つBinomial Heapを作ることができます。
実際、nを2進数で表した時に\Sigma_{k=0}^{m}d_k2^k (d_k \in \{0, 1\})と表せた場合、d_k = 1となるようなkをrankに持つBinomial Treeがそれぞれ1つずつあれば、それらのツリーの要素数の合計はnに等しくなるはずです。

ちなみに、Binomial Heapの操作自体も二進数のアナロジーのようになっています。

また、この時Binomial Heapが持つBinomial Treeの個数はlog_2(n + 1)個程度となります。

さらに、Binomimal Heapは、リスト内の各Binomial Treeについて、一般的なヒープが持つ性質、すなわち、その根の部分がツリーの中での最小値であるという制約も持ちます。
この制約によって、最小値の検索はヒープの各要素の根を見るだけで済むようになるので、O(logn)の計算量で済むことになります。


それでは、Binomial Heapを実装していきましょう。
最初に完成形のコードを載せておいて、後から個別に解説していきます。

module type ORDERED =
  sig
    type t

    val eq : t -> t -> bool
    val lt : t -> t -> bool
    val leq : t -> t -> bool
  end

module type HEAP =
  sig
    type t
    type elt

    val empty : unit -> t
    val is_empty : t -> bool

    val insert : elt -> t -> t
    val merge : t -> t -> t

    val find_min : t -> elt (* raises Empty if heap is empty *)
    val delete_min : t -> t (* raises Empty if heap is empty *)
  end

module BinomialHeap (Elt : ORDERED) : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type tree = Node of int * elt * tree list
    type t = tree list

    let link (Node (r, x1, c1) as t1) (Node (_, x2, c2) as t2) =
      if Elt.leq x1 x2 then Node (r + 1, x1, t2 :: c1)
      else Node (r + 1, x2, t1 :: c2)

    let rank (Node (r, _, _)) = r

    let root (Node (_, x, _)) = x

    let empty () = []

    let is_empty = function
      | [] -> true
      | _ -> false

    let rec insert_tree t heap = match heap with
      | [] -> [t]
      | t' :: ts' ->
         if rank t < rank t' then t :: heap
         else insert_tree (link t t') ts'

    let insert x h = insert_tree (Node (0, x, [])) h

    let rec merge ts1 ts2 = match ts1, ts2 with
      | _, [] -> ts1
      | [], _ -> ts2
      | t1 :: ts1', t2 :: ts2' ->
         if rank t1 < rank t2 then t1 :: merge ts1' ts2
         else if rank t2 < rank t1 then t2 :: merge ts1 ts2'
         else insert_tree (link t1 t2) (merge ts1' ts2')

    let rec remove_min_tree : t -> tree * t = function
      | [] -> raise (Failure "remove_min_trees")
      | t :: [] -> (t, [])
      | t :: ts ->
         let (t', ts') = remove_min_tree ts
         in if Elt.leq (root t) (root t') then (t, ts)
            else (t', t :: ts')

    let find_min ts =
      let (t, _) = remove_min_tree ts
      in root t

    let delete_min ts =
      let (Node (_, _, ts1), ts2) = remove_min_tree ts
      in merge (List.rev ts1) ts2
  end

まずはBinomialHeap.tree型です。

    type tree = Node of int * elt * tree list

例によってrankをメモしてあります。
これを利用してヒープ本体であるBinomialTree.t型を定義します。

    type t = tree list

注意しなければならないのは、Binomial Heapは要素のツリーのrankが昇順になっているのに対して、Binomial Treeの子のrankは降順になっているということです。
これは両者の操作方法がそれぞれ違うためです。
Binomial Heapは2進数のアナロジーのような操作を行うため、rankが昇順に、Binomial Treeは子の左端に自分と同じrankのものをくっつけるという動作が頻発するため、降順になっています。

次はこれらに対する操作を定義していきます。まずはlink関数。

    let link (Node (r, x1, c1) as t1) (Node (_, x2, c2) as t2) =
      if Elt.leq x1 x2 then Node (r + 1, x1, t2 :: c1)
      else Node (r + 1, x2, t1 :: c2)

これは2進数でいう半加算器のようなものです。rank rのBinomial Treeを2個合成し、rank (r + 1)のBinomial Treeを生成します。

次にinsert_treeを見てみましょう。

    let rec insert_tree t heap = match heap with
      | [] -> [t]
      | t' :: ts' ->
         if rank t < rank t' then t :: heap
         else insert_tree (link t t') ts'

これは2進のインクリメンタのようなものです。heapの"最下位ビット"にツリーを1つ加え、"繰り上がり"が生じれば"上の桁"にも同じ処理をしていきます。

これを各ビットに適用させることによって、2つのヒープをマージすることができます。

    let rec merge ts1 ts2 = match ts1, ts2 with
      | _, [] -> ts1
      | [], _ -> ts2
      | t1 :: ts1', t2 :: ts2' ->
         if rank t1 < rank t2 then t1 :: merge ts1' ts2
         else if rank t2 < rank t1 then t2 :: merge ts1 ts2'
         else insert_tree (link t1 t2) (merge ts1' ts2')

次にfind_min, delete_minですが、これらを実装するために補助関数delete_min_treeを定義します。

    let rec remove_min_tree : t -> tree * t = function
      | [] -> raise (Failure "remove_min_trees")
      | t :: [] -> (t, [])
      | t :: ts ->
         let (t', ts') = remove_min_tree ts
         in if Elt.leq (root t) (root t') then (t, ts)
            else (t', t :: ts')

各Binomial Treeは根が最小値になっているので、remove_min_treeの返り値の左の値の根が最小値となります。
これを利用してfind_min, delete_minを定義します。

    let find_min ts =
      let (t, _) = remove_min_tree ts
      in root t

    let delete_min ts =
      let (Node (_, _, ts1), ts2) = remove_min_tree ts
      in merge (List.rev ts1) ts2

delete_minの中でts1をrevしているのは、Binomial Treeの子のrankの並びとBinomial Heapの要素のrankの並びが逆順になっているためです。

【重要】MacBookを手に入れたら真っ先にインストールするべき最強アプリn選

いい加減研究室で貰ったMacBookの環境設定をしたくなってきたので、とりあえず必要と思われるものとその入手先をメモっておきます。
完全に自分用メモ。

日本語入力しようとしたら勝手に変換される謎機能

邪魔なので消します。
f:id:cloudear8:20170508130909p:plain
ここのライブ変換のチェックをはずせばOK

スペルチェック無効化

環境設定→キーボード→ユーザー辞書にあるいらなそうなチェックを消す

Dvorak, SKK

最近使わなくなったので省略。

git

たしか最初から入ってた……はず。
homebrewに入ってるやつを入れるとbash-completionが増えます。

Homebrew

これがないと始まりません。
brew.sh
ここに書いてある通りにインストールします。

$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Emacs

github.com
日本語環境だとこのEmacsが一番いいらしいです。面倒なので思考停止してインストールしました。

$ brew tap railwaycat/emacsmacport
$ brew install emacs-mac

最後に

$ brew linkapps

とかいうコマンドが必要。よく知らんけどたぶん.appをApplications以下にリンク貼ってよしなにしてくれるやつだと思う。

さらに、デフォルトで入っている古いEmacsを間違えて起動しないように、PATHの通っている適当なところに以下のスクリプトemacsという名前で置いておく。

#!/bin/sh

/usr/local/opt/emacs-mac/Emacs.app/Contents/MacOS/Emacs "$@"

Haskell関連

stackはbrewにあります。

$ brew install haskell-stack

ghc-modとかはそもそも使ってないので略。あとで検討するかも。

OCaml関連

homebrewから入ります。utopも忘れずに。

$ brew install ocaml opam
$ opam init
$ spam install utop

Python関連

pyenv入れたらとりあえず勝ち。
デフォルトで入ってるやつは2.7とかいうゴミなのでなかったことにしましょう。

$ brew install pyenv
$ pyenv install 3.x.x
$ pyenv global 3.x.x

環境変数の設定とかは割愛。

node.js関連

homebrewにある

Elm関連

npmから入れる(cabalではない)

Coq関連

homebrewにある
proofgeneralは自分でmake
proofgeneral.github.io
だいたい公式サイトの通りにすればいける。

Docker

docs.docker.com
公式でバイナリが用意されています。Linux版の時は全くお目にかかることのなかった可愛らしいクジラのアイコンがついてお得。
docker-composeとかも全部勝手に入ってくれるっぽいです。

Evernote, Slack

App Storeにある

githubにssh接続できない

githubのアカウントを作りなおしたついでにssh-keygenし直したら、何故かgithubに繋がらなくなってしまいました。

$ git push -u origin master
Warning: Permanently added the RSA host key for IP address '192.30.253.112' to the list of known hosts.
sign_and_send_pubkey: signing failed: agent refused operation
Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

解決策

ssh-addすると治りました。

$ ssh-add

ssh-addする前にssh-add -l -E md5してみてもちゃんと鍵が登録されていたような気がするのですが、まあとりあえず動いたので保留ということで。

PFDSを読む: Weight-biased Leftist Heap

inkar-us-i.hatenablog.com

こちらの記事でLeftist Heapの紹介をしましたが、今回はその亜種であるWeight-biased Leftist Heapを紹介します。
このデータ構造はほとんどLeftist Heapと同様ですが、rankのかわりに要素数が左に偏るようになります。すなわち、

  1. 根の部分が常に最小値となる
  2. 全てのノードについて、その左側の子の要素数は、右側の子の要素数以上である

以下が実装になります。ここで、HEAP, ORDEREDは上の記事と同様のものです。

(* Weight-biased leftist heap  *)
module WBLHeap (Elt : ORDERED)
       : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type t =
      | E
      | T of int * elt * t * t

    let size = function
      | E -> 0
      | T (s, _, _, _) -> s

    let make_t x a b =
      if size a >= size b then T (1 + size a + size b, x, a, b)
      else T (1 + size a + size b, x, b, a)

    let empty () = E

    let is_empty = function
      | E -> true
      | _ -> false

    let rec merge h1 h2 = match h1, h2 with
      | _, E -> h1
      | E, _ -> h2
      | T (_, x1, a1, b1), T (_, x2, a2, b2) ->
         if Elt.lt x1 x2
         then make_t x1 a1 (merge b1 h2)
         else make_t x2 a2 (merge h1 b2)

    let insert x h = merge (T (1, x, E, E)) h

    let find_min = function
      | T (_, x, _, _) -> x
      | E -> raise Empty

    let delete_min = function
      | T (_, _, a, b) -> merge a b
      | E -> raise Empty

    let rec from_list xs =
      let rec iter res xs = match xs with
        | a :: b :: xs -> iter (merge a b :: res) xs
        | a :: [] -> a :: res
        | [] -> res in
      let rec from_list' xs = match iter [] xs with
        | [] -> raise Empty
        | h :: [] -> h
        | xs' -> from_list' xs'
      in from_list' (List.rev_map (fun x -> T (1, x, E, E)) xs)
  end

Purely Functional Data Structures

Purely Functional Data Structures

純粋関数型データ構造

純粋関数型データ構造

PFDSを読む: Leftist Heapの実装

inkar-us-i.hatenablog.com

この記事ではLeftist Heapについて語るだけで終わっていたので、今回はバリバリ実装していきます。
その前に、Leftist Heapの定義のついてのおさらいをしておきましょう。
Leftist Heapとは、以下の性質をもつ二分木です。

  1. 根の部分が常に最小値となる
  2. 全てのノードについて、そのノードの左側の子のrankは、右側の子のrank以上である。

ここで、rankとは、ツリーの最も右をたどっていったときに、葉に到達するまでに現れたノードの個数を指します。

それでは実装していきましょう。まずはヒープの定義から。

exception Empty

module type HEAP =
  sig
    type t
    type elt

    val empty : unit -> t
    val is_empty : t -> bool

    val insert : elt -> t -> t
    val merge : t -> t -> t

    val find_min : t -> elt (* raises Empty if heap is empty *)
    val delete_min : t -> t (* raises Empty if heap is empty *)

    val from_list : elt list -> t
    val size : t -> int
  end

次に比較可能なデータ型を定義します。二分木のときに使ったのと同様のものです。

module type ORDERED =
  sig
    type t

    val eq : t -> t -> bool
    val lt : t -> t -> bool
    val leq : t -> t -> bool
  end

以下がLeftist Heapの定義になります。

module LeftistHeap (Elt : ORDERED)
       : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type t =
      | E
      | T of int * elt * t * t

    let rank = function
      | E -> 0
      | T (r, _, _, _) -> r

    (* leftist な性質を保ったまま T(r, x, a, b) に相当するものを作ってくれるやつ *)
    let make_t x a b =
      if rank a >= rank b then T (rank b + 1, x, a, b)
      else T (rank a + 1, x, b, a)

    let empty () = E
    let is_empty = function
      | E -> true
      | _ -> false

    let rec merge h1 h2 = match h1, h2 with
      | _, E -> h1
      | E, _ -> h2
      | T (_, x1, a1, b1), T (_, x2, a2, b2) ->
         if Elt.leq x1 x2 then make_t x1 a1 (merge b1 h2)
         else make_t x2 a2 (merge h1 b2)

    let insert x h = merge (T (1, x, E, E)) h
    let find_min = function
      | T (_, x, _, _) -> x
      | E -> raise Empty
    let delete_min = function
      | T (_, _, a, b) -> merge a b
      | E -> raise Empty

    (* 畳み込むより、ツリーの数が1ステップで半分になるようにマージしていったほうが効率的 *)
    let rec from_list xs =
      let rec iter res xs = match xs with
        | a :: b :: xs -> iter (merge a b :: res) xs
        | a :: [] -> a :: res
        | [] -> res in
      let rec from_list' xs = match iter [] xs with
        | [] -> raise Empty
        | h :: [] -> h
        | xs' -> from_list' xs'
      in from_list' (List.rev_map (fun x -> T (1, x, E, E)) xs)

    let size t =
      let rec size' n = function
        | E -> n
        | T (_, x, a, b) -> size' (size' (n + 1) a) b
      in size' 0 t
  end

rankを一々求めるとO(logn)のコストがかかってしまうので、Tの第一引数としてメモっておきます。

詳細はコード読んでください。

Purely Functional Data Structures

Purely Functional Data Structures

純粋関数型データ構造

純粋関数型データ構造

docker + flask の環境でホスト上にポートが公開できない

問題となったコード

app.py

from flask import Flask

app = Flask(__name__)

@app.route('/')
def hello():
    return 'hello world'

if __name__ == '__main__':
    app.run()

Dockerfile

FROM ubuntu:xenial

WORKDIR /flask

ENV PYENV_ROOT /pyenv
ENV PATH $PYENV_ROOT/shims:$PYENV_ROOT/bin:$PATH

RUN apt -y update 2>/dev/null
RUN BUILD_DEPS=" \
    git make build-essential libssl-dev zlib1g-dev libbz2-dev \
    libreadline-dev libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev \
    xz-utils tk-dev" \
    && apt -y install $BUILD_DEPS \
    && git clone https://github.com/yyuu/pyenv.git /pyenv \
    && pyenv install 3.5.3 \
    && pyenv local 3.5.3 \
    && pyenv rehash

COPY . /flask

RUN pip install -r requirements.txt

RUN apt -y autoremove

症状

$ sudo docker build -t cloudear8/flask .
$ sudo docker run -p 5000:5000 --name flask_1 cloudear8/flask python app.py

すると5000番ポートからflaskに繋がるはずが、何故か接続できません。
flask自体のログを見ても、リクエストすら届いていない模様。
というか、コンテナの5000番ポートに届かない……

$ sudo docker inspect flask_1 | grep IPAddress
            "SecondaryIPAddresses": null,
            "IPAddress": "172.17.0.2",
                    "IPAddress": "172.17.0.2",
$ telnet 172.17.0.2 5000
Trying 172.17.0.2...
telnet: Unable to connect to remote host: Connection refused

やったこと

試しにnetcatで適当なポート番号をlistenしてみた所、そちらには繋がりました。

$ sudo docker exec -it flask_1 /bin/bash
root@dd93148cb513:/flask# apt install netcat
root@dd93148cb513:/flask# nc -l -p 1234 -e /bin/cat

(別ホスト上)

$ telnet 172.17.0.2 1234
Trying 172.17.0.2...
Connected to 172.17.0.2.
Escape character is '^]'.
hello
hello
world
world
^]
telnet> Connection closed.

また、コンテナ内からはflaskに繋がるようです。

root@dd93148cb513:/flask# nc localhost 5000
GET / HTTP/1.1

HTTP/1.0 200 OK
Content-Type: text/html; charset=utf-8
Content-Length: 11
Server: Werkzeug/0.12.1 Python/3.5.3
Date: Sat, 06 May 2017 15:19:40 GMT

hello world

というわけで、netcatをプロキシ代わりにして5000番に回すようにしてみたところ…

root@dd93148cb513:/flask# mkfifo pipe
root@dd93148cb513:/flask# nc -l -p 1234 <pipe | nc localhost 5000 >pipe 

(別ホスト上)

$ telnet 172.17.0.2 1234
Trying 172.17.0.2...
Connected to 172.17.0.2.
Escape character is '^]'.
GET / HTTP/1.1

HTTP/1.0 200 OK
Content-Type: text/html; charset=utf-8
Content-Length: 11
Server: Werkzeug/0.12.1 Python/3.5.3
Date: Sat, 06 May 2017 15:23:18 GMT

hello worldConnection closed by foreign host.

つながりました。ということはflask自体の問題?

解決策

ここまで色々やってから気付いたのでアレなのですが、dockerとか関係なくflask自体の問題でした。

flaskの公式サイトによると

Externally Visible Server

If you run the server you will notice that the server is only accessible from your own computer, not from any other in the network. This is the default because in debugging mode a user of the application can execute arbitrary Python code on your computer.

If you have the debugger disabled or trust the users on your network, you can make the server publicly available simply by adding --host=0.0.0.0 to the command line:

flask run --host=0.0.0.0

This tells your operating system to listen on all public IPs.

というわけで、app.pyの最後の行を

    app.run(host='0.0.0.0')

に書き換えると、外からでも見えるようになりました。

おわり