smectic_gの日記

2007-02-01

[]靴下を干す時

色違いの靴下を干そうとするとすごい間抜けなことになる.

ぬれた洋服の色って見づらいから,二つを並べないと違いがわからない.コード(Java)で書くと

class Socks {
  private final int color;
  private boolean isDamaged;

  public boolean isSameColor(Sock otherSocks) {
    return ( color == otherSocks.color);
  }

  public boolean isDamaged() {
   return isDamaged;
  }
}

しかインターフェースがないSocksクラスが入ったスタックを,

class Pair {
  private Socks a;
  private Socks b;

  Pair(Socks a, Socks b) {
    this.a = a;
    this.b = b;
  }
}

のリストにまとめるということになる.今どうやってるかと言うと,

public void hangSocks(Stack<Socks> items, List<Pair> hanger) {
  Stack temp = new Stack();

  while (!items.empty() ) {
    Socks socksA = items.pop();
    if (socksA.isDamaged()) {
      continue;  // 痛んでたら捨てて次のをとる
    }
    while (!items.empty()) {
       Socks socksB = items.pop();
       if (socksB.isDamaged() ) {
         continue;
       } else if (socksA.isSameColor(socksB)) {
         hanger.add(new Pair(socksA, socksB); // たまたま同じ色だったらハンガーにかける
         break;
       } else {
         temp.push(socksB); // 違う色だったらひとまず別のところに置く
       }
    }
    // このループを経てハンガーにかけられなかったら靴下は半端だから自動的に捨てる
    // 一時的においた靴下を元のスタックに戻す.
    for (Socks socks : temp) {
       items.push(socks);
    }
  }
}

というふうに,非常に場当たり的なかけ方をしているので死ぬほど効率が悪い.O(n^2)のはず.

最初に同じ色の靴下のリストを作ってしまう

public void hangSocks(Stack<Socks> items, List<Pair> hanger) {
  List<Socks> samples = new ArrayList<Socks>();
  List<Stack<Socks>> temp = new ArrayList<Stack<Socks>>();
  while (!items.empty()) {
    Socks socks = items.pop();
    if (socks.isDamaged()) continue;
    int i;
    for (i=0; i < samples.size(); i++) {
      if (socks.isSameColor(samples.get(i))) {
        temp.get(i).add(socks);
        break;
      }
    }
    if (i == samples.size() ) {
      samples.add(socks);
      Stack stack = new Stack();
      stack.push(socks);
      temp.add(socks);
    }
  }

  for (Stack<Socks> list : temp) {
    Socks stock;
    for (Socks socks : list) {
      if (stock == null) {
        stock = socks;
      } else {
        hanger.add(new Pair(stock, socks));
        stock = null;
      }
    }
  }
}

は色の数が少なければだいぶ効率的だが,メモリ消費量の点で採用していないのかもしれない.コードの長さ自体も長いし.

最初におもむろにPairを組んでhangerに突っ込んだあとにswapして揃える形式で効率の良いアルゴリズムがあればいいなあと思うが厳しいのかもしれない.

[]いまさらグラフ問題

高木浩光@自宅の日記 - 日常化するNHKの捏造棒グラフ

に,それなら気温も絶対温度で表示しろよと突っ込んで光栄にも小学3年生かよと突っ込まれたkhwarizmiですが,その後の展開をみるにつけどうも釈然としない.

気になるのは

  • 棒グラフだけで良いのかね?
  • ブクマコメントでいうアカデミックってどこよ?

の二つ.

確かに,高木氏の言う通り気温を棒グラフで表示するのはちょっとない.(通常は折れ線グラフ.あってせいぜい面グラフ)でも,棒グラフを途中で切った程度で印象操作されるような人は折れ線グラフを途中で切っても印象操作されると思う.つまり,工場の件数を棒グラフでなしに折れ線グラフで書けば同じような操作をしても許容されるの?ということ.個人的にそこははっきりさせるべきだと思った.

もし,これが許容されないならば気温の折れ線グラフは絶対温度で表示すべきだろうし,対数グラフはこの世に存在してはいけないことになる(紙面に自然な0を設定することが不可能だから.対数グラフでは1が0だと言う人は自然の感覚が人間本位すぎる).逆に,これが許容されるならば,誤解を招くとかNHKはひどいとか御託を並べてないで棒グラフの形式論として論じるべきだ.(つまり,ただNHKは常識がないとだけ言えばいい)

あと,ブクマでいくつかアカデミズムでは許容されないとかかかれているのがひどく疑問.高木氏が火付け役だからアカデミズムでは許容されないと言っているのだろうか?

最初の問題として自分の分野(材料とか電気とか)では論文で棒グラフをほとんど見ることがない.棒グラフにして提供できるような情報(int->double)は表として提供するのが普通だし,たとえ,棒グラフの類を見るとしてもヒストグラムがせいぜいだ(確かに,ヒストグラムをリニアかつ0始点以外で書くことはあり得ない).あとは,図の延長線としての棒グラフ(のようなもの)が時々あるけど,これには正確性は求められない.横に数字を書いておけば比率がずれてようがなんだろうが問題にはならない.

アカデミズムでは単純に見やすさのみが問題で,情報が再現可能であれば恣意的に軸を取ろうがあまり気にされない(失笑を誘うことはあるだろうが).逆に言うと相手の意図にのって印象操作されるような人はそういう世界には向いてない.

結局何が言いたいかと言うと,グラフなんて文書の一部なわけで,それに意志が含まれてて悪いかってこと.グラフから意志を取り除く暇があったらグラフにどれくらい意志が入り込む余地があるかを周知すべきだと思う.

しかし,ちょっと前に見てあまりの独創的なグラフの使い方に受けたno titleがこの話題の影響か常識的なグラフに直っていた.魚拓を取っておけば良かったと後悔.(最初に公開された時には,たとえば324秒vs325秒のグラフを320秒-330秒とかの範囲で描いていたので倍ぐらい違うように見えるグラフになっていた)