クックパッド開発コンテスト24を振り返って

クックパッドの開発コンテスト24第三回に挑戦してみて,感じたことなどをまとめていきます. 私が開発したものは,寝付きが悪い人が寝付くまでの時間を楽しむためのアプリです. 最終的に作ることができたのは,音声入力でツイートする機能(載せるの忘れてた)と,タイムラインを読み上げる機能です. 画面を見なくても操作できるように指示を全て音声でするようにして,操作は音声入力でするようにしました.

【紹介動画】http://www.youtube.com/watch?v=Ggc0\_m-eP8Y

1. 振り返る

1.1. 起床

10時半くらいに起床して,やばい!と思って飛び起きて,アイディアを頭の中で考えながら朝食作ったり,風呂入ったりしてたら,気がついたら12時に...これはやばいと思って,とりあえずマックに移動してコーヒーを飲みながらアイディアを神に書きだしていくことにした.

1.2. アイディア出し

まず,はじめに「1日の終り」「楽しくする」といったところを具体化していくことから始めた.1日の終りとして,ぱっと思いついたのは「帰宅→外食→風呂→寝る」の流れで,そのプロセスのどこかを楽しくすることが大切だと思った.つまり,夕食とか風呂とか寝る前とか改善できないかなーということ.

で,そこからなんだけど,人の欲求ベースで考えるつもりだったけど,気づいたら何故か状況ベースで考えていた.例えば,食事の時は目と耳が使えるから,それだけで楽しめるものなんかないかなーとか,寝るときは耳と口が空いているとかそういう感じ.その時にそれをしたいかなんてあまり考えなかったため,なんかよくわからんアプリになってしまったんだと思う.

1.3. 実装

全体の設計をやってリファクタリングしながら,作っていったため,割りときれいに実装ができた.適宜テストコードも書いていたので,拡張,再利用はかなりやりやすいコードになったと思う.ただし,できた機能の数は少ないし,設計の爪が甘かったためか,発生しうる壁を予測できなかった.例えば,Twitterを読み上げる機能はそのまま実装すると,特殊な文字やURLまで読み上げられてしまったり,句読点がないと音声がなまったりするため,その辺を予測するべきだった.実際に読み上げ部分を作成した時に慌てだしたのが問題だった.

1.4. 動画作成

動画作成を甘く考えていた.まず,iMovieの使い方がよくわからなかった.しっかり,事前調査をしておくべきだった.あと,動画の構成が説明的すぎて,全然ストーリーが伝わらない.もっとストーリーベースで初めから考えていって,それに必要な機能を選んで作るべきだった.最重要アウトプットの動画のできがしょぼい.

2. 良かった点と悪かった点

良かった点

  • 身近な問題点を選んだところ.気持ちの想像はしやすかった.

他の参加者が自分と違った点

  • その人が何をしたいかをベースに,ソーシャル要素を取り入れていた.
  • デザイン凝ってる.Bootstrapとか使ってた.
  • 1日の終りとして帰宅も視野に入れていた.確かに,1日の終りって感じ.
  • 表示の仕方を変えるだけってのもあった.(デザインが良ければ印象が良い?)
  • TODO系が多い.(目標を達成出来ると気持ちいい!という考え.)
  • ターゲットを絞っている人はあまりいなかった.

改善点

  • もっと早く起きるべし,そうすればもっと早く寝られます.睡眠時間を7時間くらいに抑える.
  • 僕には動画作るセンスやデザインセンスが無いことを自覚して誰かと組むべきだった.
  • 問題をもっと予測する.
  • AndroidSDKにもっと慣れておくべきだった.
  • 現実の問題と言うより,感覚ベースで考えるようにする.

あしたよほう → 他人がすることが気になる
vibee → 他人とつながっている感覚(寂しさに関連)LINEでスタンプ贈り合うのと同じ欲求. 特に秀逸だと思った動画 http://www.youtube.com/watch?v=PMJWh7JN7Rc

3. まとめ

アクションプラン

  • ソーシャルのネタを調べるために人が人とどのように関わりたいかをもっと観察するべき
  • デザイナの仲間探し
このエントリーをはてなブックマークに追加
はてなブックマーク - クックパッド開発コンテスト24を振り返って
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
クックパッド開発コンテスト24を振り返ってSawam's Page

Hello World

(ns org.zecun.android.Main
  (:gen-class :main false
              :extends android.app.Activity
              :exposes-methods {onCreate superOnCreate
                                onActivityResult superOnActivityResult})
  (:import org.zecun.android.R$layout android.widget.Toast android.view.View
           android.content.Intent))

(import '(android.speech RecognizerIntent))

(def set-content-view? (atom true))
(def SoundRecognitionCode 100)

(defn soundInput
  [context]
  (let [intent (new android.content.Intent
                    RecognizerIntent/ACTION_RECOGNIZE_SPEECH) ]
    (do 
      (. intent putExtra
       RecognizerIntent/EXTRA_LANGUAGE_MODEL
       RecognizerIntent/LANGUAGE_MODEL_FREE_FORM)
      (. intent putExtra
       RecognizerIntent/EXTRA_PROMPT
       "Please say what you want to say.")
      (. context
         startActivityForResult
         intent
         SoundRecognitionCode))))

(defn -onCreate
  [this bundle]
  (.superOnCreate this bundle)
  (when @set-content-view?
    (.setContentView this R$layout/main))
  (let [button (. this
                  findViewById
                  org.zecun.android.R$id/register_button)
        that this]
    (. button setOnClickListener
       (proxy [android.view.View$OnClickListener] []
         (onClick [view]
           (soundInput that))))))

(defn -onActivityResult
  [this requestCode resultCode intentData]
  (if (and (= requestCode SoundRecognitionCode)
           (= resultCode android.app.Activity/RESULT_OK))
    (.show (Toast/makeText
            this
            (. (nth (. intentData
                       getStringArrayListExtra
                       RecognizerIntent/EXTRA_RESULTS)
                    0)
               toString)
            Toast/LENGTH_LONG)))
  (. this superOnActivityResult requestCode resultCode intentData))
このエントリーをはてなブックマークに追加
はてなブックマーク - Hello World
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
Hello WorldSawam's Page

Guava Librariesの機能をざっと見てみる(前半)

本記事では,Javaを便利に使うためのライブラリであるGuava Libraries(以下,Guava1)について紹介する.今回はライブラリの機能の中でも特に便利そうな機能について紹介する. 

Javaで開発をしているとCollectionFrameworkに使いたいデータ構造やアルゴリズムがなかったり,繰り返し書いてしまうイディオムのような物が出てきたりする.GoogleのGuava Librariesを使えば,CollectionFrameworkにないデータ構造やアルゴリズムを使えたり,イディオムを避けたり,わかりやすいコードにすることができる.

Javaのコードを書きやすくする

Gauvaを使えば,Javaでよく書くコードを簡潔に書けたり,Javaでよく起こるバグを防いだりできる.具体的には次のような機能がある.

  1. nullによるバグを早期発見できる.
  2. メソッド呼び出し時に満たすべき条件をチェックできる.
  3. 一つのComparatorをベースに様々なソートを行える.
  4. 全オブジェクトに共通するメソッドを簡単にかける.
  5. 下位から上位への例外の伝搬を綺麗にかける.

1はnullに起因するバグを減らすための機能である.例えば,nullが何を意味するかは自明ではなく,Map.getがnullを返す場合,キーに対応する値がnullなのか,マップに登録されているキーがないのかどうかは自明ではない.Guavaではそれを自明にするための記述法などが提供されている.例えば,次のクラスでは,sortedByがnullになりうることが指定されている.

class Foo {
  @Nullable String sortedBy;
  int notSortedBy;
}

他にもOptionalクラスを使うことで,nullの代わりにabsentという状態を作ってデータがnullな状態と,データが見つからない状態を区別することも出来る.

Optional<Integer> possible = Optional.of(5);
possible.isPresent(); // returns true
possible.get(); // returns 5

2は引数チェックやクラスの状態チェックなどをメソッド呼び出し時に行うための機能です.checkNotNull(T)など,意図がきちんと伝わるようなメソッド名になっています.

3は一つのComparatorを元に様々なソートを行える機能である.例えば,あるクラスのオブジェクトのリストをソートしたい場合にこの機能を使えば簡単にソートが出来る.例えば,先ほどのクラスをsortedByの辞書順でソートしたい場合,

Ordering<Foo> ordering = Ordering.natural().nullsFirst().onResultOf(new Function<Foo, String>() {
    public String apply(Foo foo) {
      return foo.sortedBy;
    }
  });

のように書けば良い.naturalはComparableの定義を使うという意味で,nullsFirstはnullをはじめに持ってくるという意味,Functionは関数を示すオブジェクトでFooオブジェクトをsortedByの値に変換する.

4はtoStringやhashCodeを簡単に実装するための機能である.例えば,フィールド全てのhashCodeを連結した値をオブジェクトのhashCodeとする場合や,toStringにフィールドの値を簡単に表示出来るようにできる.

CollectionFrameworkをより便利に使うための機能

Guavaではコレクションフレームワークを便利に使うための機能も提供されている.具体的には次のような機能が提供されている.

  1. 不変なデータ構造
  2. JDKにはない便利なコレクション型
  3. コレクション型を操作するためのユーティリティ関数群
  4. コレクション型に機能を付与するための機能

不変なデータ構造はJDKでもunmodifiableXXXとしてあるが,こちらのほうが良いらしいです.

JDKのコレクション型のみでは不便なケースも多々存在するが,Guava Libraryの機能を使えば綺麗にかける.Multisetを使えば多重集合を簡単に扱える.例えば,ある単語がいくつ有るかをカウントする場合,これを使えば次のように書くだけで各単語の出現頻度をカウントできる.

Multiset<String> wordsMultiset = HashMultiset.create();
wordsMultiset.addAll(words);

また,SortedMultisetを使えば単語の範囲を辞書順などで指定してその範囲の単語の出現頻度を知ることができる.ヒストグラムなどを扱う際に非常に便利な機能だと思う. Multimapを使えばキーに対して複数の値を結びつけることができる.ListMultiMap.get(key)はキーに対応したリストを返し,SetMultimap.get(key)はキーに対応したSetを返す.帰ってくるのはViewなので,それなりに高速. BiMapは値が重複しないmapです. Tableはその名の通りTableで2つのキーに対して一つの値を結び付けられます. ClassToInstanceMapはキーに複数の型を入れるプログラムを簡潔にかける.

また,コレクション型に対する関数もいくつか用意されている.例えば,ある2つの集合の差集合を求めるSets.differenceや積集合を求めるSets.intersectionなどの関数が用意されている.Viewsを返すようになっていて高速な上に簡潔にかけるので即席の関数を自分で書くよりこれらを使うほうが良い.

コレクション型を簡潔に拡張するための機能も提供されている.例えば,データベースをたどるIterableなどを実装するなど,コレクションに対するメソッド呼び出しのログを取れるようにするなどの拡張が簡単にできる.

キャッシュ

キャッシュを簡単に作れるっぽい.

続きはまた今度.

このエントリーをはてなブックマークに追加
はてなブックマーク - Guava Librariesの機能をざっと見てみる(前半)
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
Guava Librariesの機能をざっと見てみる(前半)Sawam's Page

かな漢字変換器の実装

前回に引き続き日本語入力技術に関する実装をしてみました.具体的には前回実装したLOUDSベースのトライを使って,各経路が変換候補になっているグラフを生成,そのグラフから最適経路をビタビアルゴリズムを使って求めるということをしました.

よみがなから漢字への対応は例を変換出来る程度に手打ちで作成して,単語間の繋がりやすさとか,単語の出現度合いなどはも手打ちで作成しました.この辺を既存の辞書とかコーパス使って学習させる部分はまた今度作ります.

今回使ったアルゴリズムについて

今回はビタビアルゴリズムというアルゴリズムを使いました.ビタビアルゴリズムは有向で循環がないようなグラフに使える経路探索アルゴリズムです.変換のためのグラフでは,前のノードに戻る経路がないため,利用できるわけです.

テストコード

テストコードは次のようになっています.テスト用のデータを手打ちで作成するのがかなり面倒でした.単語間の繋がりやすさはbetweenCostsに定義して,単語の頻出度合いはnodeCostsに定義してあります.かなから漢字に変換するためのトライの構造は次の図のようになっています.

http://zecun.sakura.ne.jp/wp-content/uploads/2012/03/wpid-tree2.png

# -*- coding: utf-8 -*-
import random
import unittest
import trie_table
import louds_trie
import simple_kana_kanji_translation as skkt

class TestSequenceFunctions(unittest.TestCase):

    def setUp(self):
        a = 1
    def createTrie(self):
        tt = trie_table.TableTrie()
        for i in range(0, 11):
            tt.addNode()
        tt.addEdge(0, 1, u'と')
        tt.addEdge(0, 2, u'べ')
        tt.addEdge(0, 3, u'な')
        tt.addEdge(0, 4, u'い')
        tt.addEdge(0, 5, u'ぶ')
        tt.addEdge(0, 6, u'た')
        tt.addEdge(1, 7, u'べ')
        tt.addEdge(3, 8, u'い')
        tt.addEdge(4, 9, u'ぶ')
        tt.addEdge(5, 10, u'た')

        return tt;
    def testTrie(self):
        tt = self.createTrie()
        lt = louds_trie.LoudsTrie(tt)
        self.assertEqual(louds_trie.LoudsTrie.NOT_FOUND, lt.get(u'とべな'))        
    def testGraph(self):
        tt = self.createTrie()
        lt = louds_trie.LoudsTrie(tt)
        words = [u"", u"戸", u"べ", u"菜", u"胃", u"", u"田", u"飛べ",
                 u"ない", u"イブ", u"豚"]
        lt.setWords(words)
        graph = skkt.Graph(lt, u'とべないぶた')
        node = graph.first()
        toNode = node.nextInTopologicalOrder()
        self.assertEqual(u'戸', toNode.getString())
        self.assertEqual(node, toNode.previous()[0])
    def testViterbiRouting(self):
        tt = self.createTrie()
        lt = louds_trie.LoudsTrie(tt)
        words = [[u""], [u"戸"], [u"べ"], [u"菜", u'名'],
                [u"胃",u'医'],  [u""], [u"田"], [u"飛べ"],
                 [u"ない"], [u"イブ"], [u"豚"]]
        lt.setWords(words)
        graph = skkt.Graph(lt, u'とべないぶた')
        costData = skkt.CostData()
        betweenCosts = [[u'戸', u'べ', 30], [u'飛べ', u'ない', 20], 
                        [u'飛べ', u'菜', 30] ,[u'飛べ', u'名', 30], 
                        [u'べ', u'ない', 50], [u'べ', u'菜', 30] ,
                        [u'べ', u'名', 30] ,[u'菜', u'胃', 30] ,
                        [u'菜', u'医', 30] ,[u'菜', u'イブ', 30] ,
                        [u'名', u'胃', 30] ,[u'名', u'医', 30] ,
                        [u'名', u'イブ', 30] ,[u'胃', u'豚', 30] ,
                        [u'医', u'豚', 30] ,[u'ない', u'豚', 10] ,
                        [u'イブ', u'田', 30]]

        nodeCosts = [(u'戸', 35), (u'べ', 25), (u'飛べ', 32), (u'ない', 32),
                    (u'菜', 30), (u'名', 32), (u'胃', 19), (u'医', 21),
                    (u'イブ', 24), (u'豚', 14), (u'田', 50)]

        for bc in betweenCosts:
            costData.setBetweenCost(bc[0], bc[1], bc[2])
        for nc in nodeCosts:
            costData.setNodeCost(nc[0], nc[1])

        graph.printGraph()
        route = skkt.Utils.viterbiRouting(graph, costData)
        translatedString = skkt.Utils.nodesToStr(route)
        self.assertEqual(u'飛べない豚', translatedString)
if __name__ == '__main__':
    unittest.main()

グラフ構造とビタビアルゴリズムのコードについて

グラフ構造とビタビアルゴリズムは特に効率化も考えず,単純に実装しました.テスコードに書いてありますが,「とべないぶた」という文字列が「飛べない豚」に変換されます.

# -*- coding: utf-8 -*-
from louds_trie import LoudsTrie as LT
import hashlib

class Utils:
    @classmethod
    def totalCost(cls, p, n, costData, graph):
        if p == graph.first():
            betweenCost = 0
            optimalCost = 0
            nodeCost = costData.nodeCost(n.getString())
        elif n == graph.last():
            optimalCost = p.getOptimalCost()
            nodeCost = 0
            betweenCost = 0            
        else:
            optimalCost = p.getOptimalCost()
            betweenCost = costData.betweenCost(p.getString(), n.getString())
            nodeCost = costData.nodeCost(n.getString())
        return optimalCost + betweenCost + nodeCost

    @classmethod
    def minTuple(cls, tuples, comparedIndex):
        minTuple = tuples[0]
        for t in tuples:
            if t[comparedIndex] <= minTuple[comparedIndex]:
                minTuple = t
        return minTuple

    @classmethod
    def viterbiRouting(cls, graph, costData):
        node = graph.first().nextInTopologicalOrder()
        while node != Graph.NOT_FOUND:
            pns = node.previous()
            costs = [(pns[i], Utils.totalCost(pns[i], node, costData, graph)) for i in range (0, len(pns))]
            minCostNode = Utils.minTuple(costs, 1)
            node.setOptimalPrevious(minCostNode[0])
            node.setOptimalCost(minCostNode[1])
            node = node.nextInTopologicalOrder()
            if node == graph.last():
                print 'aa'
            #print node.getString()
        node = graph.last().getOptimalPrevious()
        route = []
        # is this a instance comparison??
        while node != graph.first():
            route.append(node)
            node = node.getOptimalPrevious()
        route.reverse()
        return route

    @classmethod
    def nodesToStr(cls, route):
        string = ""
        for node in route:
            string += node.getString()
        return string
class Graph:
    NOT_FOUND = None
    def __init__(self, trie, string):
        # each elements share the empty list
        #self.endAt = [[]] * (len(string) + 2)
        self.endAt = [[] for i in range(0, len(string) + 2)]
        self.endAt[0].append(Node(self, -1, None, 0, 0, u'あ'))
        self.endAt[len(string) + 1].append(Node(self, -1, None, len(string) + 1, 0, u'あ'))
        for i in range(0, len(string)):
            for j in range(1, len(string) - i + 1):
                yomi = string[i:i + j]
                wordId = trie.get(yomi)
                # print string[i:i + j] + ',' + str(wordId)
                if wordId != LT.NOT_FOUND:
                    ep = i + j
                    for candidate in trie.wordIdToStr(wordId):
                        if candidate == "":
                            break
                        node = Node(self, candidate, trie, ep, len(self.endAt[ep]), yomi)
                        self.endAt[ep].append(node)
                else:
                    break
    def first(self):
        return self.endAt[0][0]
    def last(self):
        lastElement = len(self.endAt) - 1
        return self.endAt[lastElement][0]
    def nextInTopologicalOrder(self, ep, inIndex):
        if inIndex >= len(self.endAt[ep]) - 1:
            if ep >= len(self.endAt) - 1:
                return Graph.NOT_FOUND
            return self.endAt[ep + 1][0]
        else:
            return self.endAt[ep][inIndex + 1]
    def getNodes(self, n):
        return self.endAt[n]
    def printGraph(self):
        for e1 in self.endAt:
            print '[',
            for e2 in e1:
                if e2 == self.first():
                    print "start, ",
                elif e2 == self.last():
                    print "end, ", 
                else:
                    print str(e2) + ',',
            print "]"
class CostData: 
    def __init__(self):
        self.bc = {}
        self.nc = {}
    def pairKey(self, n1, n2):
        return hashlib.sha256(n1 + ',' + n2).hexdigest()
    def betweenCost(self, n1, n2):
        print str(n1) + ',' + str(n2)
        return self.bc[self.pairKey(n1, n2)]
    def setBetweenCost(self, n1, n2, c):
        self.bc[self.pairKey(n1, n2)] = c
    def nodeCost(self, n):
        return self.nc[n]
    def setNodeCost(self, n, c):
        self.nc[n] = c

class Node:
    def __init__(self, graph, kanjiString, trie, ep, inIndex, yomi):
        self.graph = graph
        self.kanjiString = kanjiString
        self.trie = trie
        self.ep = ep
        self.inIndex = inIndex
        self.yomi = yomi
    def __str__(self):
        return self.getString()
    def nextInTopologicalOrder(self):
        return self.graph.nextInTopologicalOrder(self.ep, self.inIndex)
    def getString(self):
        return self.kanjiString
        #return self.trie.wordIdToStr(self.wordId)
    def previous(self):
        nodes = self.graph.getNodes(self.ep - len(self.yomi))
        return nodes
    def getOptimalPrevious(self):
        return self.optimalPrevious
    def setOptimalPrevious(self, n):
        self.optimalPrevious = n
    def setOptimalCost(self, value):
        self.optimalValue = value
    def getOptimalCost(self):
        return self.optimalValue
このエントリーをはてなブックマークに追加
はてなブックマーク - かな漢字変換器の実装
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
かな漢字変換器の実装Sawam's Page

失敗を恐れない姿勢を身につけるヒントから敗因分析まで

自分を変えたいと思っている人はたくさんいると思います.しかし,実際に自分を変えるのは難しいと思います.例えば,プライベートでの会話が苦手な人が会話力を上げる効率の良い方法は人と話す事ですが,そういう人にとって人と話すのはストレスになり,話す回数が減っていくという悪循環に陥ります.どうすればそのようなストレスを削減出来るのでしょうか?

「挫折力(冨山和彦)」を読めば,幾ばくかの答えが得られるように思えます.この本を読み,自分が苦手なことや自分ができること以上のことに挑戦することの重要性を再確認し,失敗した際の敗因分析のコツやストレスに対する対処法などを身につけることで自分を変えるための第一歩を踏み出せると思います.この本に書いてあった方法から一部の方法をピックアップしていきます.

挫折すること

この本での挫折の意味は幅広い意味を持っています.ここでいう挫折は上司と議論して負けるといった小さな挫折から,恋愛や大きなプロジェクトでの失敗など大きな挫折も含めます.また,この本では,挫折してから立ち直るまでのプロセスも含めて挫折であるとしています.

挫折のススメとそのメリット

  1. 上司が間違っていると思った場合,3回に2回程度は反論してみる.
  2. 中間管理職的な立場になってみる.

1の行動をすることで,自分の中で思考をまとめて反論する力が身につきますし,万が一負けてしまったとしても,新しい考え方を学べたりして成長できる.3回に2回というのは,頻繁にやり過ぎると人によっては嫌がる可能性があるからです.普段反論しない人は3回に2回くらい反論してみると良いでしょう.

2の行動をすることで,権力を使う側,使われる側を同時に経験することができる.そのため,権力を使われる側の気持ちにいながら,常に権力を使う練習ができるのです.機会があればリーダーをやってみると良いでしょう.この本の4章,5章にはリーダーに必要な権力の上手な使い方や,すでにあるものの上手な捨て方などが載っていますので,それを参考にするのも良いと思います.

挫折に対する恐れを減らす方法

  1. 市場価値のあるスキルを身につけると共に生活に必要な固定費を減らす.
  2. 背負っているものが少ないうちに挑戦する.

要点1はお金になるスキルを増やすことで,どういう状況でも稼げる最低金額を上げて,起業したり転職したりする場合における失敗(挫折)への恐怖感をなくすということです.また,稼げる最低金額以内に生活に必要な固定費を収めることで,自分の中での最低限の生活はできるということが高い確率で保証できます.一度,自分の支出を見なおして改善するとともに,自分自身のスキルの市場価値を見積もってみると良いでしょう.

要点2は家族とか恋人とかいない期間に挑戦しておくべきということである.それだと,ストレスが仕事だけなので,より大きな挫折に耐えられる.その挫折の大きさとしては,自分が耐えられるぎりぎりのことを見定めて挑戦すべきですが,その限界ラインを見つけるのは非常に難しい気がします.

挫折から復帰するまでのストレスを低減する方法

  1. 挫折仲間に話を聞いてもらう.
  2. 運命を受け入れる.

要点1は万が一挫折に負けそうな場合の対処法で,挫折を経験した人に話を聞いてもらうという方法です.他人に相談に載ってもらったことはあると思いますが,やはり特に挫折もなく行きたいた方に意見をもらっても逆効果な気がします.挫折仲間を増やすために,行動範囲を増やしてみるのはいかがでしょうか?

要点2はこの本には「運命を受け入れるべき」という言葉で書いてありましたが,つまるところ結果で判断するのではなく,過程で判断するということです.恋愛だろうが仕事だろうが,ほとんどのことは時間的制約などで全ての情報を手に入れて判断するのは困難です.ですので,要所要所で限られた情報の中から最適な選択を選ぶしかありません.それができていたかできていなかったかが重要でできていなければ反省すれば良いと思います.僕はこのことを「プログラマのための論理パズル」で,お見合い問題1を解いているときに気づきそれ以降ずっと実践しています.一度,選択の要所要所でそれを解くのがどれだけ難しいか考えてみると良いでしょう.

挫折経験を生かす方法

  1. 敗因分析をきっちりとする.

    敗因分析をしましょう.具体的には自分が失敗したと思うことを書きだして,それぞれに対する

理由を書いてみます.そして,それを改善するための方法を考えてどう改善していくかを考えれば良いと思います.過去の失敗を振り返る際に,自分を客観的に第三者視点で観察してみる事で,少しは精神的な辛さが和らぐとのことです.一度試してみてはどうでしょう.

まとめ

挫折は次の3つの行動から構成されていて,これらをぐるぐる繰り返すことで成長できると思います.

  1. 挫折を恐れずに行動を起こしてみる.
  2. ストレスに耐えて復帰する
  3. 挫折を分析して改善プランまで作る.

この3つすべてができている人はなかなかいないのではないでしょうか? 自分が苦手なところに関するヒントをこの本から探してみると,よりこのサイクルを回しやすくなると思います.

まぁ,一生挫折する機会がなければそれはそれで幸せなんですけどねぇ...

このエントリーをはてなブックマークに追加
はてなブックマーク - 失敗を恐れない姿勢を身につけるヒントから敗因分析まで
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
失敗を恐れない姿勢を身につけるヒントから敗因分析までSawam's Page

簡潔データ構造を実装してみた

前回の記事では単純なトライとダブル配列によるトライを実装した.今回は,LOUDSと呼ばれる簡潔データ構造でトライを実装してみる.簡潔データ構造とは,コンパクトかつ操作できるデータ構造である.コンパクトでありながら,一部の操作ができるという点が単に圧縮されただけのデータとは異なる点である.

LOUDSでトライを実装

テストコードは次の通りである.トライの構造は次の図のようになっている.本と同様である.ノードのIDは1を基準にしているため,各ノードの右下にあるIDが各ノードに付与されており,テストコード中のtestTreeOperationはそのIDを元に書かれている.

http://zecun.sakura.ne.jp/wp-content/uploads/2012/02/wpid-tree1.png

def createTrie(self):
    tt = trie_table.TableTrie()
    tt.addNode()
    tt.addNode()
    tt.addNode()
    tt.addNode()
    tt.addNode()
    tt.addNode()
    tt.addNode()
    tt.addEdge(0, 1, 'a')
    tt.addEdge(0, 2, 'b')
    tt.addEdge(0, 3,  'd')
    tt.addEdge(1, 4, 'b')
    tt.addEdge(1, 5, 'c')
    tt.addEdge(3, 6, 'a')
    return tt;
def testLoudsTrie(self):
    tt = self.createTrie()
    lt = louds_trie.LoudsTrie(tt)
    #lt.printBitArray()
    #self.assertEqual(5, lt.get('ab'))
def testTreeOperation(self):
    tt = self.createTrie()
    lt = louds_trie.LoudsTrie(tt)
    self.assertEqual(0, lt.getParentOf(2))
    self.assertEqual(2, lt.firstChild(0))
    self.assertEqual(2, lt.getChildOf(0, 'a'))
    self.assertEqual(6, lt.get('ab'))
def testBitOperation(self):
    tt = self.createTrie()
    lt = louds_trie.LoudsTrie(tt)
    self.assertEqual(1, lt.getBit(0))
    self.assertEqual(0, lt.getBit(1))
    self.assertEqual(1, lt.getBit(2))
    self.assertEqual(1, lt.getBit(3))
def testBitVectorOperation(self):
    tt = self.createTrie()
    lt = louds_trie.LoudsTrie(tt)
    self.assertEqual(4, lt.rank(6,1))
    self.assertEqual(4, lt.select(4,1))

トライ自体の実装は次の通りである.実装中に気づいたけど,本に書いてあるfirst_childの実装が間違っているような気がする...そのまま実装すると正しく動かない.

import sys
import trie_table

class LoudsTrie(trie_table.TableTrie):
    NOT_FOUND = -1
    def __init__(self, trie):
        self.bit_array = 0
        self.endIndex = 0
        self.edge = []

        #adding super root
        self.setNextBit(1)
        self.setNextBit(0)

        children = [trie.getRoot()]
        self.recursion(children, trie)
    # n - starting from left
    def setNextBit(self, bit):
        if bit == 0:
            self.endIndex += 1
        else:
            shift = self.endIndex + 1
            self.bit_array += (sys.maxint >> shift) + 1
            self.endIndex += 1
    def getBit(self, n):
        shift = n + 1
        if (self.bit_array & ((sys.maxint >> shift) + 1)) != 0:
            return 1
        return 0
    def recursion(self, nodeIds, trie):
        allChildrenId = []
        allChildrenEdge = []
        for nodeId in nodeIds:
            children = trie.getChildrenOf(nodeId)
            if len(children) != 0:
                allChildrenId += children[1]
                allChildrenEdge += children[0]
                for i in range(0, len(children[1])):
                    self.edge.append(children[0][i])
                    self.setNextBit(1)
            self.setNextBit(0)

        if len(allChildrenId) != 0:
            self.recursion(allChildrenId, trie)

    def printBitArray(self, val):
        #bit_array = self.bit_array
        #bit_array = 4611686018427387904
        bit_array = val
        array = []
        while bit_array >= 1:
            if bit_array % 2 != 0:
                array.append(1)
            else:
                array.append(0)
            bit_array >>= 1
        array.reverse()
        print array

    def getParentOf(self, nodeId):
        ltNodeId = nodeId # node id starts from 1
        return self.select(self.rank(ltNodeId, 0), 1)
    def firstChild(self, nodeId):
        ltNodeId = nodeId
        y = self.select(self.rank(ltNodeId, 1) + 1, 0) + 1
        if self.getBit(y) == 0:
            return self.NOT_FOUND
        else:
            return y
    def getChildOf(self, nodeId, charCode):
        child_pos = self.firstChild(nodeId)
        c = self.code(charCode)
        while self.getBit(child_pos) == 1:
            print self.edge
            if self.edge[self.rank(child_pos, 1) - 1] == c:
                return child_pos
            child_pos += 1
        return self.NOT_FOUND
    def rank(self, pos, b):
        count = 0
        for i in range(0, pos):
            if self.getBit(i) == b:
                count += 1
        return count
    def select(self, count, b):
        for i in range(0, self.endIndex):
            if self.getBit(i) == b:
                count -= 1
            if count == 0:
                return i

トライの各種実装の根底のアイディアについて

実装が出てきた発想を想像してみる.イメージが沸かない人に向けて書いてみた.

テーブルによる実装

あるノードからある文字が付いているエッジに移動した場合に移動先のノードを知るには,単純に二次元配列で情報を保持すればよい.木構造では,各ノードはひとつの親しか持たないため,テーブルのうち半分以上は使われなくなるため,非常に無駄が多い.

ダブル配列による実装

ツリー中のノード数がnのとき,子供の数はn以下なのでサイズnの配列が2つあるだけで,ツリー構造は示せるはずである.更に本に書いてある数式のお陰で,エッジにある数字も表現できてている.ノードの衝突を考慮しなければならないので実装が面倒?ただし,処理は非常に早いと思う.

LOUDSによる実装

幅優先方式で各ノードの情報を表すブロックを並べ,各ブロックには子供ノードの和だけ1が連続して,その後に0が続く形にしてあることで,たどることと,データをコンパクトにすること2つを達成している.

このエントリーをはてなブックマークに追加
はてなブックマーク - 簡潔データ構造を実装してみた
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
簡潔データ構造を実装してみたSawam's Page

トライを実装してみた

現在,”日本語入力を支える技術”1を読んでいます.ひらがなの文字列を漢字混じりの文字列に変換する過程で,あるかな文字列から漢字表現の候補を列挙する必要があります.ひらがなの文字列と漢字の候補の結びつけをするために,ハッシュテーブルとトライが有効であると紹介されていました.特にトライは効果的に候補を列挙できるため,ここではトライを実装して見ることにします.

トライの実装

トライは枝に文字が割り当てられている木構造で,この本では次のような操作ができる木構造として定義されています.

  • あるノードの親ノードと親ノードとの間の枝についた文字を取得できる.
  • あるノードの子供ノード全てと,各子供ノードとの間の枝についた文字を取得できる.

ここでは,さらにこの2つの機能をベースにして,「あるノードから,ある文字列がついた枝に進めば,どの子供ノードにたどり着くかを返す関数」を作り,これをベースにして,「ある文字列の先頭から順に文字を取り出し,その文字に対応した枝をたどっていくとどのノードにたどり着くかを返す関数」を作ります. 今回はテストファーストで開発しました.最終的にできたテストコードは次の通りです.trie_table.TableTrieクラスが,テーブルを使った単純なトライで,double_array_trie.DoubleArrayTrieクラスがダブル配列を使ったトライです.

import random
import unittest
import trie_table
import double_array_trie

class TestSequenceFunctions(unittest.TestCase):

    def setUp(self):
        self.seq = range(10)
    def testAllTest(self):
        tt = self.createTrie()
        self.assertEqual(4, tt.get('ab'))
    def createTrie(self):
        tt = trie_table.TableTrie()
        tt.addNode()
        tt.addNode()
        tt.addNode()
        tt.addNode()
        tt.addNode()
        tt.addNode()
        tt.addNode()
        tt.addEdge(0, 1, 'a')
        tt.addEdge(0, 2, 'b')
        tt.addEdge(0, 3, 'd')
        tt.addEdge(1, 4, 'b')
        tt.addEdge(1, 5, 'c')
        tt.addEdge(3, 6, 'a')
        return tt;
    def testDoubleArray(self):
        tt = self.createTrie()
        dat = double_array_trie.DoubleArrayTrie(tt)
        self.assertEqual(5, dat.get('ab'))
if __name__ == '__main__':
    unittest.main()

テーブルによる実装

本に書いてある例を一般化した実装になります.a,b,c…に対して,1,2,3…を割り当てています.木構造の条件(親がひとつ,ループがない)などを満たしているかのチェックなどはしていないです.ソースコードは次の通りです.

class TableTrie:
    NOT_FOUND = -1
    ANSI_START = 97
    def __init__(self):
        self.nmbrOfAlpha = 23;
        self.table = []
    def getRoot(self):
        return 0;
    def getParentOf(self, nodeId):
        for i in range(0, len(self.table)):
            for j in range(0, self.nmbrOfAlpha):
                if self.table[i][j] == nodeId:
                    return i
        return self.NOT_FOUND
    def getChildrenOf(self, nodeId):
        childrenEdge = []
        childrenId = []
        for i in range(0,len(self.table[nodeId]) - 1):
            if self.table[nodeId][i] != -1:
                childrenEdge.append(i)
                childrenId.append(self.table[nodeId][i])
        if len(childrenId) == 0:
            return []
        return (childrenEdge, childrenId)
    def getChildOf(self, nodeId, charCode):
        charNumber = self.code(charCode)
        if self.table[nodeId][charNumber] != -1:
            return self.table[nodeId][charNumber]
        return self.NOT_FOUND
    def get(self, key):
        parent = 0
        for c in key:
            child = self.getChildOf(parent, c)
            print str(parent) + ',' + str(c) + ',' + str(child);
            if child == self.NOT_FOUND:
                return parent
            parent = child
        return parent
    def code(self, char):
        p = 'abcdefghijklmnopqrstuvwxyz'
        i = 0;
        for c in p:
            if c == char:
                return i + 1
            i = i + 1
    def addNode(self):
        self.table.append([-1] * self.nmbrOfAlpha)
    def addEdge(self, parent, child, charCode):
        charNumber = self.code(charCode)
        self.table[parent][charNumber] = child

ダブル配列による実装

ダブル配列を使った実装です.構築法として,静的な構築方法を採用しました.ノードは親ノードを先に追加して,子ノードを一気に追加しなければなりません.木を構築する際に,木構造を渡さなければならないようです.もっと効率の良い方法があるのでしょうが,とりあえず,単純な方のトライ構造を渡すようにしました.

import trie_table

class DoubleArrayTrie(trie_table.TableTrie):
    size = 8
    NOT_FOUND = -1
    def __init__(self, trie):
        self.base_array = [-1] * self.size
        self.check_array = [-1] * self.size

        children = trie.getChildrenOf(trie.getRoot())
        m = self.firstConditionablePosition(children)
        print children
        print m
        self.base_array[trie.getRoot()] = m[0]

        for i in range(0, len(children[0])):
            childrenId = m[0] + children[0][i]
            self.check_array[childrenId] = trie.getRoot()        

        for i in range(0, len(children[0])):
            childrenId = m[0] + children[0][i]
            self.recursion(childrenId, children[1][i], trie)
            #self.recursion(, trie)
    def recursion(self, nodeId, newNodeId, trie):
        children = trie.getChildrenOf(nodeId)

        if len(children) == 0:
            #print self.base_array
            #print self.check_arrfay            
            return
        m = self.firstConditionablePosition(children)
        print children
        print m
        self.base_array[newNodeId] = m[0]

        for i in range(0, len(children[0])):
            childrenId = m[0] + children[0][i]
            self.check_array[childrenId] = newNodeId

        for i in range(0, len(children[0])):
            childrenId = m[0] + children[0][i]
            self.recursion(childrenId, children[1][i], trie)
    def getChildOf(self, parent, c):
        if self.base_array[parent] == -1:
            return self.NOT_FOUND
        m = self.base_array[parent] + self.code(c)
        if self.check_array[m] == parent:
            return m
    # ret[0] - min index
    # ret[1] - edge value of min index
    def firstConditionablePosition(self, children):
        minValue = min(children[0])
        #print len(self.check_array) - 1
        print self.check_array;
        for i in range(0, len(self.check_array) - 1):
            if self.base_array[i] != -1:
                continue
            allPuttable = True
            for child in children[0]:
                val = i + child;
                if self.check_array[val] != -1:
                    allPuttable = False
            if allPuttable == True:
                return (i, minValue)
        return self.NOT_FOUND;

さいご

久しぶりにPython使って,今回コードを書いて勘が戻った様な気がします.タプルを返す関数を作ったが,ちょっと,実装時に頭の中がこんがらがって閉まったので,タプルはひとつの関数内で完結するように使おうかな.あと,どれも非効率なので後で書き直したい.LOUDSも実装しそこなったので,また今度やろう...

Footnotes:

1 徳永拓之, “日本語入力を支える技術”

このエントリーをはてなブックマークに追加
はてなブックマーク - トライを実装してみた
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
トライを実装してみたSawam's Page

ソフトウェア開発における意思決定のプロセスを見直す

ソフトウェア開発においても精度が高く素早い意思決定のプロセスは非常に重要だと思う.職業エンジニアであれば限られた時間と人や資金などのリソースの制限内で最良のソフトウェアを開発すること目指す.また,趣味で開発する場合も,限られた時間の中でできるだけユーザが満足していくれるような物を作るべきである.文献「問題解決プロフェッショナル」はそのような制限内で何らかの意思決定をする際の精度と速度を上げるための足がかりとなる本である.ソフトウェア開発の経験があまりない人がソフトウェア開発をはじめる前に読んでおくと効率良く開発できると思う.また,すでにソフトウェア開発の経験がある人にも役立つ.この記事では,「問題解決プロフェッショナル」の各章の概要とソフトウェア開発にどう役立つかを述べる.

各章の概要とソフトウェア開発への応用

第一章では,基本的な思考態度として,ゼロベース思考と仮説思考が説明されている.ゼロベース思考とは,すでに存在する技術や知識や慣習等の既存の枠の範囲を超えて思考することであり,より良い解決策を選びとる際に重要な思考である.例えば,ドトールコーヒーは,顧客の要求を考えぬくっことで,”喫茶店には,一日数千人も来客しない”という業界の常識を破り,低価格なコーヒーを提供して営業利益を得ることに成功した.ゼロベース思考をするためには,原理に戻る必要がある.この本では,顧客の気持ちになって物事を考えれば良いと書かれている.ソフトウェア開発においても,同様に原理から考える.ソフトウェア開発においては,2つの原理が存在する.ビジネスと同様に顧客の要求を考えることでゼロベース思考をすることができるし,また,計算機の原理をベースに考えることで,実現可能なシステムを考えることができる.例えば,音声認識の技術は全然成熟しておらず,任意の発言をシステムにしたところでシステムはまともに動かない.しかし,iPhoneのSIRIなどの音声認識システムでは,顧客の視点に立ち,顧客がボタンを押している間だけ音声認識することで雑音から音声コマンドを分離できている.このようにゼロベースで考えることはソフトウェア開発でも非常に重要である.

第一章で挙げられていたもうもう一つの思考態度は仮説思考である.仮説思考とはゼロベース思考や知識を使ってアクションに結びつく仮説を作る思考である.ビジネスでは,状況の変化が激しいため,関連する情報をすべて精査してアクションを決定すると対応が遅れてしまったり,状況が変化した場合に精査した情報が無駄になったりする.そのため,仮説のアクションを立てて,それを検証して,実行する.そして,また仮説を立て直すというサイクルを繰り返す必要がある.ソフトウェア開発でも,常に新しい技術が発表されていて状況の変化が激しい.よって,その場での仮説を立て実行してく姿勢が非常に大切である.ここで挙げられている3つの点を意識すれば良いと思う.

  1. 情報収集に時間をかけすぎない.
  2. ベストではなくベターを実行する.
  3. 情報を集める前に仮説を立てる.

例えば,あるWebサービスを開発する際には,どういうサービスを作るべきかをまず考えるがその際に,議論して全てを決めるのではなく,実際にプロトタイプを作ったり,運用する中で作るべき物が定まっていくこともある.また,サービスをローンチすべきかといった話しも議論だけではわからなく,実際に運用しなければならない.その際に,上の3つのことを意識すると良い.

第二章では,基本的な技術としてMECE(ミーシー)とロジックツリーが挙げられている.MECEとは,もれなくダブりなくという意味であり,ある概念をMECEに分けることは意思決定において素早く高精度な判断を行うために便利な考えである.例えば,ソフトウェア開発の各工程を改善するために議論するときに,列挙した工程に漏れがあると,改善できるポイントを見逃す可能性がある.また,Webサービスを開発する際に,ユーザの要求だけ考えてサービスを作るとすでに競合サービスがあってユーザに使ってもらえない可能性もある.議論する際は,常にMECEに分ける様に意識すべきである.ロジックツリーは問題点の原因を分析して課題点を見つける場合や,その課題点を解決する手段を選びとる場合に役立つツールである.ソフトウェアを開発する際に開発する機能に優先順位をつける場合や,作業時間の割り当てやプロジェクトに問題が生じた際に問題解決に用いることができる.

第三章では,課題を解決するための枠組みとしてソリューションシステムが述べられている.ソリューションシステムは課題の設定と解決策,解決策の検証・評価を行うためのフレームワークである.例えば,サービスを運営している状況で,でユーザ数が現象する傾向が見られた場合,その課題を解決できるかどうかを判定し,できるならどういう方法で解決できるかを,できないならなぜ解決出来ないかを明らかにすることができる.

以上がこの本に書いてあった技術である.自らの行動を振り返ってみると,以上に述べたことは無意識のうちにやっているかもしれない.しかし,無意識にやっていることを一般化して見直すことは自分の意思決定のプロセスを見直すことにつながるため,役立つと思う.ソフトウェア開発に携わっている方にこの本を読んでもらえると良いと思う.

注意点

最後に注意点について述べる.この本はあくまで意思決定の速度と精度を向上するための足がかりに過ぎないことに注意して欲しい.この本で紹介されているツールは実際に使ってみないと身につかない.この本を読むだけでなく,自分の生活に関する問題や仕事に関する問題に対して使ってみると良いと思う.また,この本で挙げられている例は,ほとんどがマーケティングなどに関する物なのでそれらに馴染みがない人は適宜例を読み飛ばしたほうが効率良く読めると思う.僕は読み飛ばした.

このエントリーをはてなブックマークに追加
はてなブックマーク - ソフトウェア開発における意思決定のプロセスを見直す
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
ソフトウェア開発における意思決定のプロセスを見直すSawam's Page

WordPress on Amazon EC2の構築手順

WordPressとは,Content Management Systemの一種で,簡単にWebサイトを構築,管理できるアプリケーションです.僕は基本的に怠け者なので,これを使って楽にWebサイトを運営していこうと考え,導入してみました.で,サーバとして何を使うか迷ったのですが、サイトをずっと運営していけるかわからないので,Amazon EC2を使うことにしました.Amazon EC2は無料期間が長くて,無料期間後も使用量に基づいて金額が決定されるのでちょうどいいです. せっかくなので,全体的な構築手順の流れと参考サイトを載せておくことにします.

  1. Amazon EC2のアカウントを取得する. 割と適当にやってもできます. Amazon AWSに登録して,その後,Amazon EC2の利用を申し込むことになります.1 CloudFormationで簡単にWordpressを構築することもできますが, Linuxのコマンドなどを使って構築する方が楽なので, EC2を使う方法を取りました.
  2. MySQL,PHP,Apache,Wordpressのインストール このサイトが参考になります. MySQLのパスワードの設定は適当にやってください2
  3. 独自ドメインの取得,設定 独自ドメインを設定する場合は,必ず独自ドメインを通してinstall.phpを実行してください.独自ドメインの設定は簡単にできました.僕もこのページと同様にお名前.comを使いました.3
  4. 設定とか 特に設定すべきことはないのですが,テーマのダウンロードを簡単にするために,設定ファイルを次のWebサイトが示す様に変更しておいたほうがいいかもしれません.4
  5. AMIイメージを作成 サーバが停止すると,全てのデータが消えるので,念のため,AMIイメージを作成しておきます.5 以上です.
このエントリーをはてなブックマークに追加
はてなブックマーク - WordPress on Amazon EC2の構築手順
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed
WordPress on Amazon EC2の構築手順Sawam's Page