EAGLE 雑記 このページをアンテナに追加 RSSフィード

Wed February 22, 2012

はてなブログ

移行するのか使い分けるのか決めずに始めましたが,移行する気がしています.

http://eagletmt.hateblo.jp/

Thu February 09, 2012

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

でもここから先がわからない.

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

Wed January 11, 2012

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

今まで推論規則を書くときは 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
  }
\]

と書くと

f:id:eagletmt:20120111115356j:image

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


しかし,前提の部分が長すぎる場合にどう改行してよいのか不明で*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 というメッセージと共に

f:id:eagletmt:20120111120946j:image

となってしまう.


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
}

と書くと

f:id:eagletmt:20120111115358j:image

のようにレイアウトされる.まさに 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
}

f:id:eagletmt:20120111120947j:image

となる.

また,普通に \\ で改行を入れることもできる.

\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
}

f:id:eagletmt:20120111120948j:image

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

Wed January 04, 2012

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

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

f:id:eagletmt:20120104064457j:image

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

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

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

さっきの状態から <C-g> を押すと,このように必要最低限の高さになる.

f:id:eagletmt:20120104064709j:image

また,<C-t> で補完リストの表示・非表示をトグルできるようにもしてみた.

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();
    }
  });

Thu December 29, 2011

ハッシュの衝突

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;
  }
}

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

LaTeXBNF 的なものを書くときに,::= や | の記号をいいかんじに揃えたい.

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

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

f:id:eagletmt:20111229132425j:image


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

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

と書いてしまうと,途中の | の幅がかなり小さくて見栄えが悪い.

\; とか \quad とかでスペースを調整するのも面倒だし,揃ったとしてもアドホックなかんじがする.(下図は \; でスペースを入れてみた場合)

f:id:eagletmt:20111229132522j:image


そこで,\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*}

f:id:eagletmt:20111229132523j:image

いいかんじ.


参考

LaTeX 数式の縦/横の調整(Kodama’s tips page)