読者です 読者をやめる 読者になる 読者になる

学生エンジニア小話

プログラミングのお話

ログみたいなファイルを見るスクリプトを書いた

ログみたいな、どんどんファイルの下に文字列が足されていくようなファイルを見るためのスクリプトを書いたので紹介します。

これは実際に使って見るとこんな感じです。

logviewer

仕組み

仕組みは単純で、最初にファイルの最後までファイルポインタを進めます。そのあと、ファイルポインタを閉じずにファイルのタイムスタンプが更新されるのを待って、更新されてたら標準出力に出しつつファイルポインタを最後まで進めます。これのループだけですが、Web系のフレームワークが出すログファイルをこういう感じで出力してくれるといちいちファイルを見にいく必要も無くなるので便利だと思って作りました。

Raspberry Piで作るロボット設計

f:id:takuseno:20161211175245j:plain

今大学で半期を通してチームでロボットを作るという授業をとっています。

僕がシステム設計を担当しているので、どのように設計したのかを紹介したいと思います。

どんな感じのロボットか

ものすごい初期の画像しかないのですが、ロボットの雰囲気はこんな感じです。

f:id:takuseno:20161211091217j:plain

モーターがついているだけです笑。今は以下のような構成になっています。

  • モーター
  • バッテリー
  • Raspberry Pi
  • 超音波距離センサー
  • カメラ
  • スピーカー
  • マイク

これらのものを使ってロボットにタスクをやらせます。

特に規定はなく自由に作れるのですが、このチームではなるべく多くのアプリケーションを開発しようということになりました。

設計方針

なるべく多くのアプリケーションをみんなで作るために、モジュールをうまく隠蔽してAndroidアプリケーションのような感覚で作れるようにすることを目指しました。さらにメンバーで各モジュールを動かすためのプログラムをいかにうまく組み込むかというのも考慮して以下のような設計にしました。

f:id:takuseno:20161211170155j:plain

アプリケーションが直接各モジュールを動かすのではなく、coreと名付けたOSのようなものを通してモジュールを操作します。そしてモジュールはそれぞれ独立したプロセスで動いていて、coreと標準入出力をpipeでつなぐことで通信します。これにより、各モジュールを動かすプログラムはC言語でもいいし、Pythonでもいいという感じで制限をなくすことができました。

工夫しなければならなかったこと

カメラで顔認識を行なっているのですが、Raspberry Piの性能だと顔認識をキャプチャした毎フレームで同期的に行おうとすると他の処理をブロックしてしまうため、顔認識など値を取得してくるモジュールはすべてコールバックでプログラムを書く形にしました。

アプリケーションのコード

このような設計にすることでアプリケーションのコードはこれだけシンプルになりました。

from lib import client
import time
import threading

def sensor_listener(request):
    right = request['right']
    left = request['left']
    if right < 100 or left < 100:
        if right != left:
            if right > left:
                client.move(int(left), 100)
            else:
                client.move(100, int(right))
        else:
            client.move(100, 80)
    else:
        client.move(100, 100)
    client.get_distance(distant_listener)

class MainThread(threading.Thread):
    def __init__(self):
       super(MainThread, self).__init__()
    def run(self):
        client.get_distance(sensor_listener)

thread = MainThread()
client.startListener(thread)

たったこれだけでロボットは壁を距離センサーで検知したら避けやすい方に曲がって進むということができるようになりました(100とかいう数字はこのロボット内での単位なのであまり意味はない)。アプリケーションはcoreと通信するためのインターフェースをclientとして用意しているので、アプリケーションの実装者は下のレイヤーを全く気にする必要がなくなりました。

シミュレータ

中間発表で他の班がシミュレータを実装したというのを聞いて、こっちもやってやろうということでシミュレータを実装しました。実際の様子がこれです。

simulator

これは上のコードをそのまま動かした様子です。距離センサーのための障害物と顔認識のための顔を簡単に置けるようにしています。

これは以下のような構成にすることで実現しました。

f:id:takuseno:20161211173202j:plain

coreより下の各モジュールはスタブプログラムと差し替えてcoreからのリクエストをサーバーに送っています。もともとWebやクラウドをがっつりやっているのでこのシミュレータはブラウザ上で動いていて、シミュレーションサーバーとwebsocketで通信するというなんともWeb系ぽい方法でやっています。

このシミュレータにより、ロボット実機がなくてもアプリケーションを作れるようになりました。

課題

シミュレータはちょっと理想的な動きをしてしまうので意図的にセンサーの値などにノイズを加えたりして実地環境でも耐えうるようにしないといけません。また、顔認識の精度も実地だと照明などの関係でかなり低くなることが予想されているのでその辺もアプリケーション側が対応しないといけません。

まとめ

大学の授業ではありますが、頑張り次第では新規性?はなくとも面白いことができますということでした。

PHPコードでキャッシュについて学んでみる

f:id:takuseno:20161111002236j:plain 次のコードで速いのはどちらだと思いますか?

Code A

<?php
$a = [[]];
for ($i = 0; $i < 1000; ++$i) {
    for ($j = 0; $j < 1000; ++$j) {
        $a[$i][$j] = 1;
    }
}

Code B

<?php
$a = [[]];
for ($i = 0; $i < 1000; ++$i) {
    for ($j = 0; $j < 1000; ++$j) {
        // flipped!
        $a[$j][$i] = 1;
    }
}

この記事を読めばなんとなくわかるようになると思います。

はじめに

PHPや他のスクリプト系の言語はC言語と違ってメモリの管理について気にすることはほとんどないと思います。

C言語ではメモリを確保するところから解放するところまですべて面倒を見る必要がありますが新しい言語にはガベージコレクタが実装されているので確保したヒープメモリは変数への参照がなくなった時点で解放されます。

変数の値はどこにしまってあるのか

変数の値はどんな言語であろうとメモリに格納されます。メモリに乗り切らない場合はディスクに保存されます。メモリは複数の領域に別れており、

--------- 0xffffffff
 stack
---------
 heap
---------
 static
---------
 code
--------- 0x00000000

という感じになっています。右の16進数はメモリの場所を示すアドレスです。ここでは変数の値はあるアドレスの示す場所に格納されるということがわかれば大丈夫です。

CPUにとってボトルネックとなる処理はメモリへのアクセスとディスクへのアクセスです。メモリの読み込みと書き込み速度は近年急速に早くなったため、今メモリへのアクセスする速度を気にしている人はWeb界隈では特にいないと思います。

キャッシュの登場

パソコンを買うとCPUのスペックのところにL1キャッシュやL2キャッシュという表記を見たことがあると思います。

実はCPUはキャッシュを持っていて、メモリの内容をキャッシュしています。これがL1キャッシュやL2キャッシュです。CPUがメモリへアクセスしようとするときに、キャッシュにすでに値があればメモリへアクセスせずキャッシュの値を利用します。これは書き込みの時でも同じです(write backなら)。

しかし、キャッシュは高速にアクセスできる代わりに非常に高価なので3MBや4MBほどしか持っていません。なのでCPUはあるルールに従ってキャッシュを更新していきます。

キャッシュの特徴

キャッシュは次のことを想定しています。

  • spatial locality
  • temporal locality

まずspatial localityとは一度アクセスした変数が格納されているアドレスに近いアドレスにある変数にアクセスする可能性が高いということです。例えば最初に出てきたCodeAのように配列の値は連続したアドレスに保存されるため(PHPは厳密にそうかどうかは微妙)一度配列の値にアクセスするとその周辺のアドレスの値全てをキャッシュに格納します。

次にtemporal localityとは一度アクセスしたアドレスには近いうちに再びアクセスする可能性が高いということです。コードを書くときに意識していると思いますが、一度定義した変数はその周辺で何度も使うことが多いと思います。なのでキャッシュを更新する際には最後にアクセスされたのがもっとも古いアドレスを新しくアクセスしたアドレスに置き換えます。

最初のコードを見てみる

まずCodeA,Bについて、自分のPC上(Macbook Pro Mid 2012, Intel Core i5, RAM 16GB)で実行した結果を示します。

$ php codeA.php 
0.061517953872681

$ php codeB.php 
0.12649202346802

なんと二倍も差が出ました!1000x1000の配列なんて普段あまりないとは思いますが、配列にアクセスする順番でこんなにも差が出るのは驚きだと思います。

では理由を考えてみましょう。

配列に一度アクセスするとspatial localityの考えによって、周囲のアドレスに格納されている値が決まったブロック単位でキャッシュされます。なのでCodeAでは一度配列にアクセスするとしばらくはアドレスが連続している配列の値を見に行っているのでメモリへのアクセスが少なく済んでいます。

一方、CodeBでは2次元配列を縦方向に走査しています。1000x1000の2次元配列は長さが1000000の1次元配列と見ることができます。なので毎回離れたアドレスの値にアクセスしに行ってしまっているので、キャッシュが利用されずメモリへのアクセス数が多くなってしまっています。

まとめ

PHPの簡単なコードを通してキャッシュがパフォーマンスに与える影響が分かったと思います。普段意識しないキャッシュについて少しだけ理解を深めてもらえていれば嬉しいです。

より理解を深めたければパタヘネを読むのが一番いいと思います。

https://www.amazon.co.jp/dp/4822298426

PHPで関数型ぽいイミュータブルなリストを実装してみる

f:id:takuseno:20161115152624j:plain

大学のコンパイラについての授業でOCamlを使っているのですが、そこでイミュータブルなリストを関数で定義していて感心しました。

そこで、アルバイト先で使っているPHPで同じものを再現してみました。

コード

<?php
$update = function ($var, $vl, $t) {
    return function ($x) use ($var, $vl, $t) {
        if ($x == $var) {
            return $vl;
        }
        return $t($x);
    };
};

$initTable = function () {
    return function ($x) {
        echo "no variables\n";
    };
};

$l1 = $update('a', 1, $initTable());
$l2 = $update('b', 2, $l1);

echo $l2('a')."\n";
echo $l2('b')."\n";
$l2('c');

// 1
// 2
// no variables

解説

update関数で毎回関数を返しています。その関数は値を返すかさらに関数を読んでいます。

このままではわかりにくいので、実際にリストにabが登録された時の様子var_dump($l2)を行った結果としてみてみましょう。

object(Closure)#5 (2) {
  ["static"]=>
  array(3) {
    ["var"]=>
    string(1) "b"
    ["vl"]=>
    int(2)
    ["t"]=>
    object(Closure)#4 (2) {
      ["static"]=>
      array(3) {
        ["var"]=>
        string(1) "a"
        ["vl"]=>
        int(1)
        ["t"]=>
        object(Closure)#3 (1) {
          ["parameter"]=>
          array(1) {
            ["$x"]=>
            string(10) "<required>"
          }
        }
      }
      ["parameter"]=>
      array(1) {
        ["$x"]=>
        string(10) "<required>"
      }
    }
  }
  ["parameter"]=>
  array(1) {
    ["$x"]=>
    string(10) "<required>"
  }
}

Closureオブジェクトがネストをなしているのがわかりますね。

updateを実行するたびにどんどん関数のネストを掘り下げている感じです。これで引数のリストに影響を与えずに新しいリストを生成するイミュータブルな関数型らしいリストをPHPで実装することができました。

しかし、パフォーマンスはかなり悪く、PHPでは深すぎると関数を呼びすぎてスタックがいっぱいになってしまうかもしれません。

まとめ

関数型の言語でないと実用性はないですが、普段関数型に触れないエンジニアのかたにはなかなか面白いと感じられると思います。

ちなみにOcamlでの実装はこれだけシンプルになります。

let initTable = fun x -> raise No_such_variable
let update var vl t = fun x -> if x = var then vl else t x

UC Berkeleyでコンピュータアーキテクチャの授業をとった感想

今年の6月から8月にかけてUC Berkeleyでコンピュータアーキテクチャの授業と"English as second language"というカテゴリーの授業を受けて来ました。

コンピュータアーキテクチャの授業は正確にはCS61CというコードでタイトルがThe great ideas in computer architectureというものです。内容的には

  • Bit
  • C language
  • MIPS Assembly
  • Cache
  • Datapath
  • Pipeline
  • Virtual Memory
  • Performance Programming
  • Map Reduce
  • RAID

という感じです。1時間半の講義が全30回以上と講義の後に交互にディスカッションとラボラトリが入ってきます。教科書はパタヘネでした。

ディスカッションは少人数クラスで授業内容についての問題が渡されて近くにいる人と一緒に解いて、みんなで理解について確認する感じです。ラボラトリは実際にコンピュータを使って問題をとく演習でした。

日本の授業との違い

日本の授業と扱っている内容に大きな差があるとは思いませんでした。しかし、講師のプレゼンの質が日本人と比較にならないほど高く、講義中に飽きることはまずないです。日本の1時間半の授業は拷問に感じられることがありますが、授業の構成もうまく考えられており、1時間半が一瞬ですぎました。

また、ディスカッションという形の授業も日本にはないです。講義中にも隣の人とクイズの回答を相談する時間があるのですが、一貫してみんなで理解を深めようという流れがあります。オンライン上でもみんなで質問を投稿できたり、他の生徒の質問に対して回答することができるサービスもありました。

今回はサマーセッションというものに参加したので普段よりフルタイムのバークレー生は少なかったので生徒の比較はしません。

感心したこと

日本だと座学で終わりそうなものがプロジェクトという宿題とはまた違うものとして課されてアウトプットする機会がありました。プロジェクトは複数回あり、

という感じでした。日本ではCPUについての学部の授業では座学で終わるものが、実際に自分でLogisimというものを使って組み立てました。これのおかげでかなり深くCPUについて理解することができ、全プロジェクトを終えると自分で書いたアセンブリを自分で書いたアセンブラマシン語に直して、自分で作ったリンカーで実行ファイルにして、最終的に自分で作ったCPUで実行することができます。

実際、この授業は僕の大学の授業4つ分くらいの内容を含んでいます。日本ではほとんどが週一コマの授業をたくさん取る感じですが、アメリカでは4倍くらいの重さの授業を4つか5つほどしかとりません。こうすることで僕の受けた授業のように、大きな流れを通して理解を深めるということができます。是非日本の大学もこのスタイルにしてほしいです。

アメリカの大学は卒業するのが難しい説

扱っている内容に大きな差があるとは思えず、真面目にやれば普通にAは取れると思います(英語で少し苦労しますが)。おそらくアメリカの大学入試では学力と同じくらいボランティアなど他の要素が関わってくるので、学力に大きなばらつきがあるのだと思います。なので確かに真面目にやらないと間違いなく留年しますが真面目な日本人であればむしろ楽しく学生生活を送れると思いました。

すぐに役に立ちそうなテスト問題

キャッシュの単元では、C言語が与えられて、キャッシュのヒットレートを求める問題が出題されました。以下に若干の変更を加えたものを紹介します。

We are using a 20-bit byte addressed machine.
Cache is 4-way set associative.
It has a capacity of 16 KiB and 16 B blocks. 

For the code given below,
calculate the hit rate for Cache assuming that it starts cold. 

#define ARRAY_SIZE 8192
int int_arr[ARRAY_SIZE]; // &int_arr = 0x80000
for (int i = 0; i < ARRAY_SIZE / 2; i++) {
    int_arr[i] *= int_arr[i + ARRAY_SIZE / 2];
} 

難易度としてはラッキー問題くらいと言ってもいいくらいの問題です。ですが、このような問題を通して実際のプログラミングのときにもキャッシュの存在を意識するようになりました。ちなみに答えは5/6です。

まとめ

UC Berkeleyはコンピューターサイエンスの聖地とも言える場所で歴史もあります。様々な最新技術が生まれてきた場所で、講義はとても洗練しています。間違いなく日本でコンピューターサイエンスを学ぶよりUC Berkeleyで学ぶ方が楽しくより深く身につくと思います。そう断言できるようになっただけでも言ってきた価値があると思います。

RaspberryPiとOpenCVで顔認識してパフォーマンスも改善してみる

Raspberry Pi

大学でロボットを作る機会ができたので家で埃をかぶっていたPlaystationEyeを使って顔認識を試して見た。

使ったもの

セットアップ

  • sudo apt-get install libopencv-dev
  • sudo apt-get install python-opencv
  • wget http://eclecti.cc/files/2008/03/haarcascade_frontalface_alt.xml
  • USBにカメラを挿す

簡単なコード

import cv2.cv as cv
import cv2

cv.NamedWindow("camera", 1)

capture = cv2.VideoCapture(0)
faceCascade = cv2.CascadeClassifier('haarcascade_frontalface_alt.xml')

while True:
    _, img = capture.read()
    img = cv2.resize(img, (320, 240))
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    faces = faceCascade.detectMultiScale(
        gray,
        scaleFactor=1.1,
        minNeighbors=3,
        minSize=(30, 30),
        flags=cv.CV_HAAR_SCALE_IMAGE
    )
    for (x, y, w, h) in faces:
        cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
    cv2.imshow("camera", img)
    if cv.WaitKey(10) > 0:
        break
cv.DestroyAllWindows()

ここで使われている顔認識のアルゴリズムは訓練済みデータを用いたHaar Cascadesというアルゴリズムらしいです。

qiita.com

ちょっと改善してみる

このままでも顔認識されているのが確認できますが、かなりカクカクしていると思います。

ロボットに使うことを考えて、用途によりますがリアルタイムで顔が認識されている必要はないかもしれません。そこで次の戦略でプレビューを滑らかにします。

  • 30フレームに1回顔認識する。1回認識されてから次の30フレームはそこにいると仮定する。
  • 顔認識の処理は別スレッドで行う

ビデオは大体30fpsだと思うので1秒間に一度程度で顔認識を行います。また、この程度の解像度なら1秒以内に顔認識の処理は終わるのでスレッドで溢れてしまうことはないはず。(テストなので今回はマルチスレッドのデータレースなども気にしない)

改善後コード

import cv2.cv as cv
import cv2
import threading

cv.NamedWindow("camera", 1)

capture = cv2.VideoCapture(0)

count = 0
faces = []

class DetectThread(threading.Thread):
    def __init__(self, img, faces):
        super(DetectThread, self).__init__()
        self.img = img
        self.faces = faces
    def run(self):
        gray = cv2.cvtColor(self.img, cv2.COLOR_BGR2GRAY)
        detectedFaces = cv2.CascadeClassifier('cascade.xml').detectMultiScale(
            gray,
            scaleFactor=1.1,
            minNeighbors=3,
            minSize=(30, 30),
            flags=cv.CV_HAAR_SCALE_IMAGE
        )
        self.faces[:] = detectedFaces

while True:
    _, img = capture.read()
    img = cv2.resize(img, (320, 240))
    if count == 30:
        thread = DetectThread(img, faces)
        thread.start()
        count = 0
    else:
        count += 1
    for (x, y, w, h) in faces:
        cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
    cv2.imshow("camera", img)
    if cv.WaitKey(10) > 0:
      break
cv.DestroyAllWindows()

実際にこのコードを大事な場面で行うとデータレースやエラーの処理を考えなければならないのでとりあえず先ほどの戦略でパフォーマンスが改善されているか確認だけということで。

まとめ

PythonOpenCVのおかげでかなり手軽にRaspberryPiで顔認識ができることがわかると思います。また、ロボットなど実際に動作するものを作るときにある程度精度を犠牲にしてパフォーマンスを追求するというのも一つの醍醐味だと思います。

Laravelのドキュメントはソースコード

Laravel

f:id:takuseno:20160925120317j:plain

Webでフレームワークを使おうと思うとRuby on Railsほど優れているものはないかと思いますが、僕はアルバイト先でPHPフレームワークであるLaravelを使って開発しています。

laravel.com

昔はCakePHPが多かったと思いますが、Googleトレンドを見てもLaravelがだいぶ増えてきているのがわかります。(というかPHP離れが進んでいるだけかも?)

そこで今回は、Laravelを開発するときにソースコードを見るといいよという話をします。

Laravelのドキュメント

Laravelのドキュメントは結構充実していて、全体の機能をわかりやすく説明されています。

laravel.com

最初に開発を始めるときはここを見ておけば問題なく開発を進めることができます。ただ関数ごとに返り値は何かとか、内部的な処理の説明はないので、もっと進んだアプリケーションを作ろうと思うとAPIドキュメントを見る必要があります。

Namespaces | Laravel API

このAPIドキュメントを読めば大体のことがわかるのですが、実はLaravelのソースは結構綺麗に描かれていて、このドキュメントを読むよりソースを読んだ方が実際の処理もわかるので僕はいつもソースを読んでいます。

ソースコードを読む

LaravelのGItHubリポジトリlaravel/laravelなのですが、実際のフレームワークを構成しているコードたちはこちらになります。

github.com

このリポジトリsrc/Illuminate以下が実装になります。例えば、EloquentORMを使っているときに、firstOrNewfirstOrCreateが実際にどのように違うのか気になったとします。そんなときはsrc/Illuminate/Database/Eloquent/Builder.phpを見に行きます。 すると簡単に両関数を見つけることができます。

    /**
     * Get the first record matching the attributes or instantiate it.
     *
     * @param  array  $attributes
     * @return \Illuminate\Database\Eloquent\Model
     */
    public function firstOrNew(array $attributes)
    {
        if (! is_null($instance = $this->where($attributes)->first())) {
            return $instance;
        }
        return $this->model->newInstance($attributes);
    }

    /**
     * Get the first record matching the attributes or create it.
     *
     * @param  array  $attributes
     * @param  array  $values
     * @return \Illuminate\Database\Eloquent\Model
     */
    public function firstOrCreate(array $attributes, array $values = [])
    {
        if (! is_null($instance = $this->where($attributes)->first())) {
            return $instance;
        }
        $instance = $this->model->newInstance($attributes + $values);
        $instance->save();
        return $instance;
    }

すると実際には$instance->save()をしているかしていないかだけが違うことがわかります。Laravelの関数一つ一つのコードはこのくらい短く、Railsに比べるとコードを追うのがかなり楽です。 ドキュメントを見にくよりも毎回このようにソースを見ていった方が関数の仕様と中でどんな処理をしているのかをつかむことができるのでかなりオススメです。

まとめ

文系プログラマの方はライブラリがあったときに、中を読まずになんとなく便利だなと思いながら使っている人が大半だと思いますが、それではドキュメントに載っていないようなところでつまずいたときに解決できなくなってしまいます。また、ライブラリのソースを読むことでそのライブラリにプルリクを投げる機会がやって来るかもしれません。近いうちにLaravelにプルリクを投げようかと思います。

Laravelのコードは読みやすいのでぜひ皆さんも開発しながらコードを眺めて見てください。