p.twimg.com 以下の文字列

Twitter for iPhone や Photobucket を利用して画像を上げると，画像は p.twimg.com/*.jpg というような場所に置かれる．
このパスの部分の文字列がどうやって生成されているのか気になった．


しばらく観察してわかったことは

  • 15文字固定
  • 使われる文字は英数字と _ と -
  • 最初のほうの文字はあまり変化がなく，また後に投稿されたものほど辞書順で後になっている

ということくらい．


で，15文字という点がひっかかるけど，おそらく status id あたりを Base64 でエンコードしたものじゃないかと思っていろいろ試したら，以下のコードで先頭から11文字目まで一致する文字列を生成できてるっぽい．

require 'base64'

def encode(id)
  s = []
  while id != 0
    s.unshift id&0xff
    id >>= 8
  end
  Base64.urlsafe_encode64(s.map(&:chr).join).chomp
end

でもここから先がわからない．
実はどこかにドキュメントされていたり，誰かが既に完全な法則見つけていたりするんですかね．

推論規則をレイアウトする bcprules.sty

LaTeX

今まで推論規則を書くときは proof.sty を使っていた．

\[
  \infer[\mbox{\sc T-App}]{
    \Gamma \vdash t_1\ t_2 : \tau_2
  }{
    \Gamma \vdash t_1 : \tau_1 \rightarrow \tau_2
    & \Gamma \vdash t_2 : \tau_1
  }
\]

と書くと

のようにレイアウトされる．


しかし，前提の部分が長すぎる場合にどう改行してよいのか不明で*1，

\[
  \infer[\mbox{\sc T-VeryLong}]{
    \Gamma \vdash \mbox{foo}\ t_1\ t_2 : \mbox{bar}\ \alpha\ \beta
  }{
    \Gamma \vdash t_1 : \mbox{very-long-constructor}\ \alpha
    & \Gamma \vdash t_2 : \mbox{another-very-long-constructor}\ \beta
    & \mbox{have-very-long-property}(\alpha, \beta)
  }
\]

とかが Overfull \hbox というメッセージと共に

となってしまう．


Benjamin C. Pierce 先生の bcprules.sty を最近知った．
http://www.cis.upenn.edu/~bcpierce/papers/index.shtml

\infrule[T-App]{
  \Gamma \vdash t_1 : \tau_1 \rightarrow \tau_2
  \andalso \Gamma \vdash t_2 : \tau_1
}{
  \Gamma \vdash t_1\ t_2 : \tau_2
}

と書くと

のようにレイアウトされる．まさに TAPL のレイアウトだ．


bcprules.sty の場合，先程のように前提が長い例は

\infrule[T-VeryLong]{
  \Gamma \vdash t_1 : \mbox{very-long-constructor}\ \alpha
  \andalso \Gamma \vdash t_2 : \mbox{another-very-long-constructor}\ \beta
  \andalso \mbox{have-very-long-property}(\alpha, \beta)
}{
  \Gamma \vdash \mbox{foo}\ t_1\ t_2 : \mbox{bar}\ \alpha\ \beta
}


となる．
また，普通に \\ で改行を入れることもできる．

\infrule[T-VeryLong]{
  \Gamma \vdash t_1 : \mbox{very-long-constructor}\ \alpha
  \andalso \Gamma \vdash t_2 : \mbox{another-very-long-constructor}\ \beta
  \\
  \andalso \mbox{have-very-long-property}(\alpha, \beta)
}{
  \Gamma \vdash \mbox{foo}\ t_1\ t_2 : \mbox{bar}\ \alpha\ \beta
}

*1:\vbox 作ってその中に行毎に \hbox 作ってその中に書く，という方法でそれっぽいことはできた

補完リストの高さを調節したり表示・非表示をトグルしたり

Vimperator

例えば 'autocomplete' を有効にして :ec commandl と入力すると，:ec co の段階で多くの補完候補が表示され，そのときの高さを保ったまま :ec commandl の補完候補が表示された状態になる．

これは特にページのコンテンツを見ながらコマンドラインを入力しているときに不便．かといって補完候補が変わる度に高さがかわるのも見にくい．

そこで，タイトルのようなキーマップを定義して適宜調節するようにしてみた．

mappings.addUserMap(
  [modes.COMMAND_LINE],
  ['<C-g>'],
  'Adjust height of completion list',
  function() {
    let list = commandline._completions.itemList;
    list._minHeight = 0;
    list._autoSize();
  });

さっきの状態から を押すと，このように必要最低限の高さになる．

また， で補完リストの表示・非表示をトグルできるようにもしてみた．

mappings.addUserMap(
  [modes.COMMAND_LINE],
  ['<C-t>'],
  'Toggle visibility of completion list',
  function() {
    let list = commandline._completions.itemList;
    if (list.visible()) {
      list.hide();
    } else {
      list.show();
    }
  });

記号の幅をいいかんじに揃える

LaTeX

LaTeX で BNF 的なものを書くときに，::= や | の記号をいいかんじに揃えたい．

縦に並べるだけなら eqnarray 環境でやればいいかんじに揃う．

\begin{eqnarray*}
  t &::=& x \\
    &|& t + t \\
    &|& t - t \\
    &|& t \times t \\
    &|& t \div t \\
\end{eqnarray*}


しかし一行に複数の要素を書きたいときがある．それを

\begin{eqnarray*}
  t &::=& x \\
    &|& t + t | t - t \\
    &|& t \times t | t \div t \\
\end{eqnarray*}

と書いてしまうと，途中の | の幅がかなり小さくて見栄えが悪い．
\; とか \quad とかでスペースを調整するのも面倒だし，揃ったとしてもアドホックなかんじがする．(下図は \; でスペースを入れてみた場合)


そこで，\settowidth で ::= の幅を取得して，\makebox で | の幅をそれに合わせる形にしてみた．

\newcommand{\bnfdef}{::=}
\newlength{\len}
\settowidth{\len}{$\bnfdef$}
\newcommand{\bnfor}{\makebox[\len]{$|$}}
\begin{eqnarray*}
  t &\bnfdef& x \\
    &\bnfor& t + t \bnfor t - t \\
    &\bnfor& t \times t \bnfor t \div t \\
\end{eqnarray*}


いいかんじ．

参考

http://www.math.kobe-u.ac.jp/~kodama/tips-latex-math-margin.html

ハッシュの衝突

http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html
おもしろい．
ウェブアプリケーションフレームワークのほとんどはパラメータを勝手に解析してハッシュテーブルに突っ込んでいるけど，ハッシュが衝突するようなキーを意図的に大量に送りつけると DoS が成立する，みたいな話．
どうでもいいけどたった2文字の文字列で衝突するんだなぁと思った．


スライドの30枚目くらいのを実際に Java でやってみた例．
ideone 上だと HashMap のほうがどっちも遅くなってるけど，普通は tbl1 の場合なら TreeMap より速いはず…
N = 40000 だとバリューを全部1文字にするとだいたい 86万文字なので，もうちょっと N を増やして POST で送りつけるとたしかにやばそう．
https://ideone.com/8U6JE

import java.util.*;

public class Main {
  // http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html

  public static void main(String[] args) {
    final String[] tbl1 = {"ab", "cd", "ef"};
    final String[] tbl2 = {"tt", "uU", "v6"};
    final int N = 40000;

    String[] k1 = new String[N], k2 = new String[N];
    String[] v = new String[N];
    for (int i = 0; i < N; i++) {
      v[i] = Integer.toString(i, 3);
      k1[i] = v[i].replaceAll("0", tbl1[0]).replaceAll("1", tbl1[1]).replaceAll("2", tbl1[2]);
      k2[i] = v[i].replaceAll("0", tbl2[0]).replaceAll("1", tbl2[1]).replaceAll("2", tbl2[2]);
    }

    System.out.printf("TreeMap tbl1: %d ms\n", time(new TreeMap<String, String>(), k1, v));
    System.out.printf("TreeMap tbl2: %d ms\n", time(new TreeMap<String, String>(), k2, v));
    System.out.printf("HashMap tbl1: %d ms\n", time(new HashMap<String, String>(), k1, v));
    System.out.printf("HashMap tbl2: %d ms\n", time(new HashMap<String, String>(), k2, v));
  }

  static long time(Map<String,String> m, String[] k, String[] v) {
    int N = k.length;
    long begin = System.currentTimeMillis();
    for (int i = 0; i < N; i++) {
      m.put(k[i], v[i]);
    }
    long end = System.currentTimeMillis();
    return end - begin;
  }
}

unite-haddock 書いた

Haskell Vim

http://d.hatena.ne.jp/kitokitoki/20111217/p1 の「ghc-browse-document の anything 化」が便利っぽかったので同じようなものを書いた．
https://github.com/eagletmt/unite-haddock
ghc-mod が必要．cabal install ghc-mod でインストールできる．Vim 内での $PATH に Cabal の bindir *1 が含まれていることも確認しておくこと．

:Unite haddock でモジュールの一覧が表示され，unite.vim のインターフェイスで選択できる．

デフォルトのアクション (browse_local) ではローカルのドキュメントを開く．ちなみにローカルなドキュメントは，cabal-install でパッケージをインストールする際に --enable-documentation というフラグをつけるか，$HOME/.cabal/config で documentation: True と設定しておくと $HOME/.cabal/share/doc あたりに生成される．

もうひとつ browse_remote というアクションを提供していて，こっちは Hackage 上のドキュメントを開く．

現状 max_candidates を設定していないので，インストールされているモジュールがすべて候補として表示される．
速度的な面で問題がある場合，vimrc で

call unite#custom_max_candidates('haddock', 100)

などと候補の数の最大値を設定してみてください．
自分の環境だと1200くらいモジュールが表示されて，初回こそ少し待たされるときもあるけどそれ以降はスムーズに動いているのでこのままでいいかなーと思ってます．

max_candidates を設定していても，unite のバッファ上で (unite_toggle_max_candidates) (デフォルトだと M にマッピングされている) すると max_candidates の設定の有効化・無効化をトグルできます．

*1:普通は $HOME/.cabal/bin