Hatena::ブログ(Diary)

nojimaの日記

2011-10-02

gitのコマンドの出力を色分けして表示する

| 17:14

$ git config --global color.ui "auto"
$ git config --global core.pager 'less -R'

マニュアルを読む限りでは1行目だけでいけそうなんだけど,僕の環境では2行目がないとlessでエスケープシーケンスが化けました.

2011-07-29

Purely Functional Data Structures 第2章

02:16

演習問題を解いたのでメモ.

ex 2.1

suffixes :: [a] -> [[a]]
suffixes [] = [[]]
suffixes xss@(_:xs) = xss : suffixes xs

ex 2.2

data Set a = Leaf
           | Branch a (Set a) (Set a)
  deriving Show

empty :: Set a
empty = Leaf

insert :: Ord a => a -> Set a -> Set a
insert x Leaf = Branch x Leaf Leaf
insert x tree@(Branch y left right)
  | x < y     = Branch y (insert x left) right
  | x > y     = Branch y left (insert x right)
  | otherwise = tree

member :: Ord a => a -> Set a -> Bool
member x set = member' Nothing set
  where
  member' c Leaf = maybe False (>= x) c
  member' c (Branch y left right)
    | x < y     = member' c left
    | otherwise = member' (Just y) right

ex 2.3

「Establish only one handler per insertion rather than one handler per iteration」の意味がわからなかったので,この文は無視して解いた.

import Data.Maybe

data Set a = Leaf
           | Branch a (Set a) (Set a)
  deriving Show

empty :: Set a
empty = Leaf

insert :: Ord a => a -> Set a -> Set a
insert x set = fromMaybe set (insert' set)
  where
  insert' Leaf = Just (Branch x Leaf Leaf)
  insert' (Branch y left right)
    | x < y     = fmap (\new -> Branch y new right) (insert' left)
    | x > y     = fmap (\new -> Branch y left new) (insert' right)
    | otherwise = Nothing

member :: Ord a => a -> Set a -> Bool
member x set = member' Nothing set
  where
  member' c Leaf = maybe False (>= x) c
  member' c (Branch y left right)
    | x < y     = member' c left
    | otherwise = member' (Just y) right

ex 2.4

import Data.Maybe

data Set a = Leaf
           | Branch a (Set a) (Set a)
  deriving Show

empty :: Set a
empty = Leaf

insert :: Ord a => a -> Set a -> Set a
insert x set = fromMaybe set (insert' Nothing set)
  where
  insert' c Leaf
    | isNothing c || x > fromJust c = Just (Branch x Leaf Leaf)
    | otherwise                     = Nothing
  insert' c (Branch y left right)
    | x < y     = fmap (\new -> Branch y new right) (insert' c left)
    | otherwise = fmap (\new -> Branch y left new) (insert' (Just y) right)

member :: Ord a => a -> Set a -> Bool
member x set = member' Nothing set
  where
  member' c Leaf = maybe False (>= x) c
  member' c (Branch y left right)
    | x < y     = member' c left
    | otherwise = member' (Just y) right

ex 2.5

data Tree a = Empty
            | Node a (Tree a) (Tree a)
  deriving Show

makeCompleteBinaryTree :: a -> Int -> Tree a
makeCompleteBinaryTree _ 0 = Empty
makeCompleteBinaryTree x d = let subtree = makeCompleteBinaryTree x (d-1)
                             in Node x subtree subtree

makeBinaryTree :: a -> Int -> Tree a
makeBinaryTree x n = fst (make2 n)
  where
  make2 0 = (Empty, Node x Empty Empty)
  make2 n
    | n `mod` 2 == 0 = let (t1, t2) = make2 (n `div` 2 - 1)
                       in (Node x t1 t2, Node x t2 t2)
    | otherwise      = let (t1, t2) = make2 (n `div` 2)
                       in (Node x t1 t1, Node x t1 t2)

ex 2.6

import Data.Maybe

data FinateMap k v = Leaf
                   | Branch k v (FinateMap k v) (FinateMap k v)
  deriving Show

empty :: FinateMap k v
empty = Leaf

bind :: Ord k => k -> v -> FinateMap k v -> FinateMap k v
bind k v m = fromMaybe m (bind' Nothing m)
  where
  bind' c Leaf
    | isNothing c || k > fromJust c = Just (Branch k v Leaf Leaf)
    | otherwise                     = Nothing
  bind' c (Branch k' v' left right)
    | k < k'    = fmap (\new -> Branch k' v' new right) (bind' c left)
    | otherwise = fmap (\new -> Branch k' v' left new) (bind' (Just k') right)

lookup :: Ord k => k -> FinateMap k v -> Maybe v
lookup k m = lookup' Nothing m
  where
  lookup' (Just (k', v')) Leaf | k' >= k = Just v'
  lookup' c (Branch k' v' left right)
    | k < k'    = lookup' c left
    | otherwise = lookup' (Just (k', v')) right
  lookup' _ _ = Nothing

2011-07-17

ProcessingでSQLiteを使おうと思ったら "The type SQLite is ambiguous" というエラーがでた

| 19:08

ProcessingSQLiteを使おうと思ったら "The type SQLite is ambiguous" というエラーがでてしばらく困った.結局

import de.bezier.data.sql.*;

としてたのを

import de.bezier.data.sql.SQLite;

に直したらうまくいった.

2011-06-25

ICPC国内予選2011に参加しました

| 11:53

ICPC国内予選にチーム317のメンバーとして参加してきました.317のメンバーは,nojima, seikichi, qwerty の3人で,3人ともこの1年間ほとんど問題を解いていなかったので,ICPCでまともに戦えるか不安でしたが,まあ楽しめればいいやという軽い気持ちで参加しました.

以下,タイムライン

  • 開始後0分: 僕がテンプレートを打ち込んでいる間に,他のメンバーがA問題を読む.
  • 開始後2分: A問題を読み終えたらしく僕と交代してseikichiくんがコードを書き始める.僕はC問題を読む.
  • 開始後8分: A問題AC.続いてseikichi,qwertyペアがBに取りかかる.
  • 開始後17分: B問題AC. 僕がC問題のコーディングに移る.
  • 開始後30分: C問題のコーディングを終えるも,「色を1から6じゃなくて0から5で持つことにしたのに,ターゲットの色だけデクリメントを忘れる」「出力にカウントできるパネルは(0,0)から連結なパネルだけなのに,全体をカウントしていた」という2つのバグを仕込んでしまっており,デバッグに時間がかかる.
  • 開始後44分: C問題AC. すでにD問題の疑似コードを紙に書いていたseikichiくんとqwertyさんがD問題のコーディングに入る.同時に,僕はE問題を読み始める
  • 開始後70分: E問題の解法を考え終わって暇になったので,D問題のデバッグに参加する.
  • 開始後76分: D問題AC. 僕とqwertyさんがE問題のコーディングに入る.
  • 開始後105分: E問題のコーディングが終わる.グループ数はちゃんと出てるが,予備力がちゃんと出てない.予備力関係な場所は4行ぐらいしかないので,デバッグは簡単そう.
  • 開始後111分: E問題AC. 全員でG問題に取り組む.
  • 開始後150分: チーム内に絶望感が蔓延する.
  • 開始後172分: seikichiくんが「Rewrite買いに行っていい?」とか言い始める.
  • 開始後180分: 終わり.

結果は,全体7位で,学内3位でした.無事,予選通過できたようでよかったです.

リンク

2010-10-29

Affinity Propagation を書いてみた (2)

| 03:38

昨日のコードは damping=0.5 で実行してたんだけど、ここFAQを読むと、dampingの値は0.9がおすすめとか書いてあったので、dampingの値を修正してもう一度試してみた。ついでにコードの整理したので再掲。

ap.h

#pragma once
#include <vector>

std::vector<int> affinityPropagation(
    FILE* input,
    int prefType = 1,
    double damping = 0.9,
    int maxit = 1000,
    int convit = 50
);

ap.cpp

// An Implementation of Affinity Propergation
// See: Clustering by Passing Messages Between Data Points

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include "ap.h"
using namespace std;

namespace {
  struct Edge {
    int src;      // index of source
    int dst;      // index of destination
    double s;     // similarity s(src, dst)
    double r;     // responsibility r(src, dst)
    double a;     // availability a(src, dst)

    Edge(int src, int dst, double s, double r, double a)
      : src(src), dst(dst), s(s), r(r), a(a) {}
  };

  typedef vector<Edge*> Edges;

  struct Graph {
    int n;                // the number of vertices
    Edges* outEdges;      // array of out edges of corresponding vertices
    Edges* inEdges;       // array of in edges of corresponding vertices
  };

  // Build graph from sparse similarity matrix stored in COO format.
  // Input specification is following:
  // First line contains an integer standing for the size of the matrix.
  // Following lines each contain two integers and a real number standing for
  // the row index i, the column index j and the similarity s(i,j) respectively.
  // Input ends with an end-of-file.
  // Note that this function does not check any errors in the given input.
  // Parameter:
  //   input: Input file handle.
  //   prefType:
  //     1: use median of similarities as preference
  //     2: use minimum of similarities as preference
  //     3: use min - (max - min) of similarities as preference
  Graph* buildGraph(FILE* input, int prefType)
  {
    Graph* graph = new Graph;
    fscanf(input, "%d", &graph->n);
    graph->outEdges = new Edges[graph->n];
    graph->inEdges = new Edges[graph->n];

    // read similarity matrix
    int i, j;
    double s;
    vector<double> ss;
    while (fscanf(input, "%d%d%lf", &i, &j, &s) != EOF) {
      if (i == j) { continue; }
      // add small noise to avoid degeneracies
      s += (1e-16 * s + 1e-300) * (rand() / (RAND_MAX + 1.0));
      // make new edge
      Edge* e = new Edge(i, j, s, 0, 0);
      graph->outEdges[i].push_back(e);
      graph->inEdges[j].push_back(e);
      // store similarities for preference calculation
      ss.push_back(s);
    }

    // calculate preferences
    double pref;
    if (prefType == 1) {
      sort(ss.begin(), ss.end());
      int m = ss.size();
      pref = (m % 2) ? ss[m/2] : (ss[m/2 - 1] + ss[m/2]) / 2.0;
    } else if (prefType == 2) {
      pref = *min_element(ss.begin(), ss.end());
    } else if (prefType == 3) {
      double minValue = *min_element(ss.begin(), ss.end());
      double maxValue = *max_element(ss.begin(), ss.end());
      pref = 2*minValue - maxValue;
    } else {
      assert(false);      // invalid prefType
    }
    for (int i = 0; i < graph->n; ++i) {
      Edge* e = new Edge(i, i, pref, 0, 0);
      graph->outEdges[i].push_back(e);
      graph->inEdges[i].push_back(e);
    }

    return graph;
  }

  void destroyGraph(Graph* g)
  {
    for (int i = 0; i < g->n; ++i) {
      for (size_t j = 0; j < g->outEdges[i].size(); ++j) {
        delete g->outEdges[i][j];
      }
    }
    delete [] g->outEdges;
    delete [] g->inEdges;
    delete g;
  }

  inline void update(double& variable, double newValue, double damping)
  {
    variable = damping * variable + (1.0 - damping) * newValue;
  }

  void updateResponsibilities(Graph* graph, double damping)
  {
    for (int i = 0; i < graph->n; ++i) {
      Edges& edges = graph->outEdges[i];
      int m = edges.size();
      double max1 = -HUGE_VAL, max2 = -HUGE_VAL;
      double argmax1 = -1;
      for (int k = 0; k < m; ++k) {
        double v = edges[k]->s + edges[k]->a;
        if (v > max1) { swap(max1, v); argmax1 = k; }
        if (v > max2) { max2 = v; }
      }
      // update responsibilities
      for (int k = 0; k < m; ++k) {
        if (k != argmax1) {
          update(edges[k]->r, edges[k]->s - max1, damping);
        } else {
          update(edges[k]->r, edges[k]->s - max2, damping);
        }
      }
    }
  }

  void updateAvailabilities(Graph* graph, double damping)
  {
    for (int k = 0; k < graph->n; ++k) {
      Edges& edges = graph->inEdges[k];
      int m = edges.size();
      // calculate sum of positive responsibilities
      double sum = 0.0;
      for (int i = 0; i < m-1; ++i) {
        sum += max(0.0, edges[i]->r);
      }
      // calculate availabilities
      double rkk = edges[m-1]->r;
      for (int i = 0; i < m-1; ++i) {
        update(edges[i]->a, min(0.0, rkk + sum - max(0.0, edges[i]->r)), damping);
      }
      // calculate self-availability
      update(edges[m-1]->a, sum, damping);
    }
  }

  bool updateExamplars(Graph* graph, vector<int>& examplar)
  {
    bool changed = false;
    for (int i = 0; i < graph->n; ++i) {
      Edges& edges = graph->outEdges[i];
      int m = edges.size();
      double maxValue = -HUGE_VAL;
      int argmax = i;
      for (int k = 0; k < m; ++k) {
        double value = edges[k]->a + edges[k]->r;
        if (value > maxValue) {
          maxValue = value;
          argmax = edges[k]->dst;
        }
      }
      if (examplar[i] != argmax) {
        examplar[i] = argmax;
        changed = true;
      }
    }
    return changed;
  }
}

// Cluster data points with Affinity Propagation.
// Parameters:
//   input: Input file which contains sparse similarity matrix. see buildGraph().
//   prefType: Specify what kind of preference we use. see buildGraph().
//   damping: The damping factor. (0.5 <= damping < 1.0)
//   maxit: The maximum number of iterations.
//   convit: Specify how many iterations this algorithm stops when examplars
//           did not change for.
// Returns:
//   Array of examplars of corresponding data points.
vector<int> affinityPropagation(FILE* input, int prefType, double damping, int maxit, int convit)
{
  assert(0.499 < damping && damping < 1.0);

  Graph* graph = buildGraph(input, prefType);
  vector<int> examplar(graph->n, -1);

  for (int i = 0, nochange = 0; i < maxit && nochange < convit; ++i, ++nochange) {
    updateResponsibilities(graph, damping);
    updateAvailabilities(graph, damping);
    if (updateExamplars(graph, examplar)) { nochange = 0; }
  }
  
  destroyGraph(graph);
  return examplar;
}

Old Faithfulに適用してみた結果。preference を類似度の最小値に設定した場合。昨日とちがってちゃんと2つに分かれてる。

f:id:nojima718:20101030033129p:image

preferenceを類似度の中央値に設定すると多数のクラスタに分かれる。

f:id:nojima718:20101030033128p:image

Connection: close