2017-07-17

ストリームの作り方

本記事はストリームについて、Schemeを用いて説明しています。サンプルコードの動作確認を行ったSchemeの処理系、バージョンは以下のとおりです。

Gauche scheme shell, version 0.9.5 [utf-8,pthreads], x86_64-apple-darwin15.6.0

ストリーム

データ構造の観点からすると、ただのシーケンス
代入やミュータブルなデータを用いることなく、状態を保持できます
遅延評価を用いることで、無限を扱えます

遅延リスト

遅延リストとは構成時ではなく、選択時に実行されるリスト

上記のみだと説明不足すぎるので、一般的なシーケンスのリストの問題点から説明します。シーケンスをリストで表現すると、状態がスタックとして積まれ続けるので、計算速度、メモリの使用量的に問題があります。

以下のコードはn番目のフィボナッチ数を求めるものです。完全にリストが作成されるまで値は求まりません。１０番目のフィボナッチ数を求めるには９番目のフィボナッチ数と８番目のフィボナッチ数が求まっていなければならず、９番目のフィボナッチ数を求めるには８番目のフィボナッチ数と７番目のフィボナッチ数が求まってなければならず…

;recursive process

(define (fib-r n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib-r (- n 1))
                 (fib-r (- n 2))))))

n番目のフィボナッチ数を求めるコードをiterative processで書き直したものが以下のようになります。countを格納する場所さえ確保すればよくなりますが、シーケンスとして扱うことはできなくなります。

;iterative process

(define (fib-i n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

上のrecursive processとiterative processの両方の問題点を解決するためにストリームを用います。ストリームだと遅延評価を用いるため、リストとしてシーケンスを扱うコストを払う必要がなくなります。

まず、以下のようにcons-streamという構成子があるとします。

(cons-stream ＜a＞ ＜b＞)

＜b＞を評価するタイミングをリスト構成時ではなく、＜b＞を選択するタイミングに変更します。そうすることで、上に書いたrecursive processでフィボナッチ数を計算する際の計算速度、メモリの使用量などの問題が解決されます。以下のコードでストリームを作成します。(cons-stream ＜a＞＜b＞)の＜b＞はstream-cdrでアクセスされてはじめて実行されます。

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (memo-proc (lambda () b))))))

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

(define (force delayed-object)
  (delayed-object))

(define (memo-proc proc)
  (let ((already-run? #f) (result #f))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? #t)
                 result)
          result))))

ストリームの動き

では、実際にストリームの動きを見ていきましょう。まずはいくつか関数を簡単に説明をします。

(stream-enumerate-interval low high)はlowからhighまでの正の整数のストリームを作成しています
(stream-ref s n)はストリームのn番目まで取り出します
(stream-map proc . argstreams)はストリームにprocを適用させています
(display-line x)はストリームの流れを確認するために標準出力しています

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

(define (stream-null? stream) (null? stream))

(define the-empty-stream '())

(define (display-line x)
  (display x)
  (newline))

ストリームを構成したタイミングではリストの１番目のみ評価されます。リストの残りは呼ばれるまで、実行されません。

gosh> (define x (stream-map display-line (stream-enumerate-interval 0 10)))
0
x
gosh> (stream-ref x 5)
1
2
3
4
5
#<undef>
gosh> (stream-ref x 7)
6
7
#<undef>

無限のストリーム

ストリームは無限を定義できます。フィボナッチ数列（フィボナッチ数の無限のストリーム）を定義すると、以下のようになります。再帰で無限ループしているように見えますが、(fibgen b (+ a b))の部分は呼ばれるまでは実行されないので問題ありません。

(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))

(define fibs (fibgen 0 1))

gosh> (stream-ref fibs 10)
55

ストリームの加算

ストリーム同士の加算も容易にできます。以下のコードはストリーム同士をを加算する方法でフィボナッチ数列を定義しています。

(define (add-stream s1 s2)
  (stream-map + s1 s2))

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-stream (stream-cdr fibs)
                                        fibs))))

gosh> (stream-ref fibs 10)
55
gosh> (stream-ref fibs 100)
354224848179261915075
gosh> (stream-ref fibs 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
gosh> (stream-ref fibs 10000)
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

参考

Structure and Interpretation of Computer Programs

2017-04-17

仕事以外のコードを書き続けて半年経過してた

仕事以外でもコード書くようになって約半年経過した。去年の年末の３日間以外は継続して書いた。 f:id:Takanori11:20170416201727p:plain

github.com

やったこと

静的型付け言語に触れる
- Go
- Rust
- C
基本的なアルゴリズムとデータ構造を作る
インタプリタを作る
SICPの問題を解く
オープンソースのプロジェクトへパッチを送る

やった内容は上記のとおり、コンピューターサイエンスの基礎的な内容が中心だ。自分は情報系の学部ではなかったので、コンピューターサイエンスの基礎が足りてないことを自覚していた。RailsやJSフレームワークのAPIとか流行りのツールの使い方をたくさん覚えたりしても、基礎を疎かにしたままだといつか成長が頭打ちになるのではないか、という不安があった。このまま継続していけば、ある程度不安は軽減できそうだし、なによりコンピューターサイエンスは楽しいものだとわかった。

半年間やってみたところで、プログラミング能力が飛躍的に上がったりはしないが、プログラミング全般的なことでなんとなくわかったような気になっていることもある。下記はプログラミング自体を始めて１年半くらいのやつが書いているので、間違ってるかもしれない。

ググったり、リファレンスを見たりしない方が速く書ける

単に調べるのに時間がかかるのではなく、書くというコンテキストから調べるというコンテキストに切り替えるのにコストがかかる。予めできるだけたくさんのことを覚えておいて、ガシガシと書き続ける方が集中を持続でき、速く問題を解決できる。

コピペしてもいい

本を読んだり、コードを見てもわからないときは、コードをそのままコピペする。コピペした後、コードを書き換えて試行錯誤しながらコードを理解する。最終的に理解し、自分のものになったのであれば、いいような気がする。

他にもわかったような気になっていることはあるが、今度書く。

最後に

「難易度の高いプログラムを書く」、「仕事がめちゃ速い」みたいなことは、「単に知ってる」、「以前に類似の経験をした」ことが起因する場合もあるので、今後も継続して勉強する。実際には頭のいい人が才能で圧倒することもあるが、自分には関係のないことである。

2017-01-21

Rubyから他言語を呼んでみた

Rubyから他言語を呼んでみた

GoとRustをライブラリ化してRubyから呼んだ。ベンチマークとしてフィボナッチ数列の40番目を求めている。

きっかけ

Rubyは書きやすいが、速くない。(Rubyの処理がボトルネックになることは少ないかもしれないが…) 機械学習の人たちはPythonからCやFortranなど速い言語で実装されたライブラリを呼び、爆速で数値計算しているので、Rubyでも似たようなことができるのではないか。

使用した処理系のバージョン

➜  ~ ruby -v
ruby 2.4.0p0 (2016-12-24 revision 57164) [x86_64-darwin15]

➜  ~ go version
go version go1.7.4 darwin/amd64

➜  ~ rustc -V
rustc 1.16.0-nightly (47c8d9fdc 2017-01-08)

Rubyでフィボナッチ数を求める実装

def fib(n)
  if n <= 1
    n
  else
    fib(n - 1) + fib(n - 2)
  end
end

puts fib(40)

例

fib(4) = fib(3) + fib(2)
       = (fib(2) + fib(1)) + (fib(1) + fib(0))
       = ((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))
       = 1 + 0 + 1 + 1 + 0
       = 3

➜ time ruby main.rb
102334155
ruby main.rb  13.39s user 0.07s system 99% cpu 13.588 total

プログラム自体の処理時間
プログラムを処理するために、OSが処理をした時間
プログラムの呼び出しから終了までにかかった時間

Goでフィボナッチ数を求める実装

package main

import "fmt"

func fib(n uint32) uint32 {
    if n <= 1 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {
    fmt.Println(fib(40))
}

fmtはprint系関数のパッケージ
uint32は0から2**32-1まで

Goをライブラリ化

package main

import "C"

//export fib
func fib(n uint32) uint32 {
    if n <= 1 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {}

➜ go build -buildmode=c-shared -o fib.so lib.go

Goのビルド時に-buildmode=c-sharedオプションを渡すとライブラリとしてコンパイルでき、fib.soとfib.hが作成される。
//export fibはただのコメントではない。書かないと上記のコマンドを実行してもfib.hが作成されない。

require 'ffi'

module Fib
  extend FFI::Library
  ffi_lib 'fib.so'
  attach_function :fib, [:uint32], :uint32
end

puts Fib.fib(40)

ffiはForeign Function Interfaceの略
ffi_libの引数はパス
attach_functionの引数は関数名,[関数の引数型],戻り値型

➜ time ruby ruby_go.rb
102334155
ruby ruby_go.rb  0.89s user 0.05s system 99% cpu 0.943 total

Rustでフィボナッチ数を求める実装

fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

fn main() {
    println!("{}", fib(40));
}

u32は0から2**32-1まで

Rustをライブラリ化

#[no_mangle]
pub extern fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

Cargo.tomlに以下の内容を書く。

[lib]
name = "fib"           // 任意の名前
crate-type = ["dylib"] // dynamic libraries

➜ cargo build --release

上記コマンドを実行すると、target/release以下にlibfib.dylibが作成される。
CargoはRubyでいうBundler

require 'ffi'

module Fib
  extend FFI::Library
  ffi_lib 'fib/target/release/libfib.dylib'
  attach_function :fib, [:uint32], :uint32
end

puts Fib.fib(40)

➜ time ruby ruby_rust.rb
102334155
ruby ruby_rust.rb  0.76s user 0.04s system 98% cpu 0.811 total

計測結果

Ruby Only	Ruby + Go	Ruby + Rust
13.588s	0.943s	0.811s

参考

2016-02-10

半年ぶりくらいにチームで仕事してる

アジャイル Ruby Ruby on Rails

久しぶりにチームで働くと、新鮮で結構楽しいことがわかった。とは言っても、完全に１人で仕事してた訳ではない。直近の案件での登場人物は主に３人。

自分
進捗に興味がある人
デザイナー

自分は設計したり、RubyとかPHPとかJavaScriptでコード書いてた。

進捗に興味がある人とはプロジェクトマネージャーのことだが、ほとんどマネージしてくることはなかった。最終の納期に間に合いさえすれば、何一つ口出ししてこないタイプだった。*1毎日、「進捗に問題ないです。」とメールしていたので、結構自由にできた。

デザイナーはマジでどこの誰かわからない。HTMLとCSSとimgのファイルをプロジェクトマネージャー経由で連携してもらっただけで、コミュニケーションをとったことがない。

こんな感じだったから、ここ半年間くらいはチームで仕事してる感がまったくなかった。

次からが本題。*2チームで働くことのいい点を挙げてみた。

チームで働くとどう変わったか

周りの人たちとコミュニケーションを取る
他の人からフィードバックを受ける
他の人が書いたコードを読む時間が増える

周りの人たちコミュニケーションを取る

話す時間が長くなるというより、こまめに意思疎通しようとするようになった。エンジニアの好きな非同期のコミュニケーションをとることが多い。チャット*3とGitHubのisuuesとかPull requestsを使っている。詰まったとき、詳しい人にすぐ聞けてラッキー。

あと、当たり前だけどバージョン管理システムを正しく使おうと思うようになった。コミットメッセージを他人が読んでもわかりやすいように書いたり、チームで決められたフローでブランチを切っていったりするようになった。

他の人からフィードバックを受ける

ペアプロしたり、コードレビューしてもらったりするようになった。アジャイルだからチームで振り返る時間もたっぷり確保されている気がする。

あと、ペアプロしてると他の人が開発している様子を見れて面白い。ターミナルとかエディタとかをすごくいじってて、「今、何やったんすか？」とか「何すかそれ？」みたいなことが多発した。

他の人が書いたコードを読む時間が増える

他の人が書いたコードを読むことは単純に勉強になる。「別にGitHubでオープンソース見ればいいでしょ」って感じになるかもしれないけど、「なぜ、現在コードに至ったのか」的なことをすぐに聞けたりするのでよい。

最後に

自分なりのバリューを早めに出さないととヤバい！！

*1:まる投げともいう

*2:チームでずっと働いている人からすると当たり前のことばかり

*3:idobataを使っている

2015-10-25

はじめてRuby関西に行ってきた

Ruby Ruby on Rails

はじめてRuby関西という勉強会に参加しました。最初に私のRubyの経験を書いたあとにRuby関西の感想を書きます。

私のRuby歴
今年の９月に金融系のSIerから転職して、Ruby on Railsで約１ヶ月くらいかけてCMSを作りました。*1　大学が文系学部で、かつ前職ではプログラミングをほとんどしていないとういう初級Webエンジニアだったので、『たのしいRuby』と『パーフェクトRuby on Rails』を必死に読みまくって、なんとかCMSを作りました。最近は『メタプログラミング Ruby 第2版』を少しずつ読んでます。

Ruby関西の感想
Ruby関西に初めて行くので、会場に行くまでは「話の内容を全然理解できなかったらどうしよう・・・」みたいな気持ちになっていましたが、発表内容を聞いてみると楽しめました。発表内容が多様で自由な雰囲気だし、スピーカーの方々から技術好きオーラが伝わってきました（？）

個人的に興味を持った発表は「RubyでDI」と「Action Cable – Integrated websockets for Rails」と「Ruby 初級者向けレッスン (例外)」です。

RubyでDI
タイムテーブルを見た時にDIが何かわからなかったので、前日にDI(Dependency Injection)についてググッてました。DIの概要をふんわりと頭に入れていたので、DIの有用性とDIが並列処理に応用できることは理解できました。ただ、そもそも「どういうコードがテストしやすいか」を正確に理解できていないので、「DIでテストが容易になる」というところはあまり理解できませんでした。
正直、自分が仕事で使うにはまだ早い（使う必要もない）感じでしたが、勉強になりました。

Action Cable – Integrated websockets for Rails
「チャットアプリの作り方を説明して、デモンストレーション」という流れをNode.jsとElixirとRailsそれぞれで行っていて、わかりやすかったです。Qiitaに初学者でも理解できるくらい丁寧に書かれた記事があるので、非常にありがたいです。

WebSocket自体についてもっと知らないとなぁという気持ちになりました。

話が逸れますが、最近「Elixir」が話題になっているような気がします。実際に◯◯という企業で使っているとかは聞かないですが、TwitterとかWEB+DB PRESSとかで見かけます。私が最初に「Elixir」という言語を知ったのはrebuild.fm ep98のNaoya Itoさんの回でした。

今、勉強していることが一段落したら、関数型言語とか並列処理とかの勉強もしようと思ってます。*2

Ruby 初級者向けレッスン (例外)
エラーメッセージと例外について、おさらいできる初学者にとってありがたいやつでした。演習問題を解いている際、最初「何をすればいいの？」みたいな状態になりましたが、演習問題２までは説明を聞いて理解できました。
演習問題はGithubにあります。

あと、専門学校の人たちと話せたのが少し新鮮でした。若いうちに自分のやりたいことを明確にしてることはラッキーだと思います。*3
自分が通ってた高校は大学に進学する人ばっかりで、専門学校に進学する人はいなかったので、専門学校の人と話せて面白かったです。

最後に
今回、Ruby関西に初めて参加したわけですが、良い刺激になって良かったです。「勉強会に行く」とか「人に会う」とか「仕事で困難にぶつかる」などの刺激が継続的な学習に繋がるのではないかと考えています。これからはちょくちょく勉強会参加していきます。

*1:入社前からRubyを勉強し始めたので正確にはRuby歴２ヶ月くらい

*2:いつかはわかりません

*3:自分の場合、理系から文転したり、SIerからWeb系の企業に転職したりと遠回りしてます

2015-10-07

『チーム力をひき出すアジャイル開発』に参加してきた

アジャイル

今日は会社の人と『チーム力をひき出すアジャイル開発』というセミナーに参加してきました。その内容をまとめます。

アジャイルの定義
アジャイルとは、お客様のビジネス価値を最大化するための「考え方」や「姿勢」

アジャイルでより大切にすること
コミュニケーション　＞　　プロセス・ツール
動くソフトウェア　　＞　　包括的なドキュメント
顧客との協調　　　　＞　　契約交渉
変化への対応　　　　＞　　計画遵守
（プロセス・ツール、包括的なドキュメント、契約交渉、計画遵守が不要な訳でなく、比較したときに優先度は低いだけです。）

上記な内容はManifesto for Agile Software Developmentに書いてあります。

上記の考え方に則していれば、アジャイルです。

お客様のビジネス価値を最大化するためにアジャイルという「考え方」や「姿勢」を用いるのであって、「とりあえずアジャイル開発をしてみたい」みたいな考えは目的と手段の逆転現象が起きているんだろうなぁと考えています。チーム全員が何のためにアジャイル開発を取り入れているかを正しく認識できていないと、スクラムとかXPを実践しても効果が薄いみたいです。

明日から取り入れられそうなアジャイル
「契約形態的にアジャイルとか無理！」な方々もいると思いますが、こっちが勝手に取り入れられそうなやつがありました。KPTと呼ばれるチームでの振り返りです。

K：Keep（良かったこと、うまくいったこと）
P：Problem（問題点や課題)
T：Try（改善したいこと、次に実施したいこと）

コツはKから初めてポジティブな気持ちになることです。週に１回くらいなら余裕で続けられます。
他にはお客様の品質保証の基準の中にアジャイル開発の手法を埋め込んでいくという荒業もあるそうです。とはいえ、アジャイルは一括請負と相性が悪い場合が多いそうなので、自社開発とか１ヶ月から３ヶ月くらいの契約と相性が良さそうです。

最後にセミナーに参加した感想
自分が圧倒的に若く、３０歳半ばから自分の父親くらいの層がほどんどだったので新鮮でした（？）講師に質問している内容や話してみた感じから判断すると、アジャイルでの開発がうまくいってないからセミナーに参加しているのではなく、これからアジャイルを取り入れたいと考えている人たちが多い印象でした。

2015-09-12

Ruby on Railsのgenerateコマンドをまとめた

Ruby Ruby on Rails

Railsのプロジェクトを作成したら、次はまず、generateコマンドを使ってコードを生成することが多いと思います。

$ rails g ◯◯

例えば、◯◯のところがscaffoldだったら、MVCそれぞれのコード、migrationファイルなどが生成されます。大量に生成されるので、◯◯の部分がmodelの場合、controllerの場合、何が生成されるがRails初心者にとってわかりにくいです。うっかり不要なものまで生成していまいました。

ちなみに以下のようにと入力すると・・・

$ rails g　scaffold task content:text

f:id:Takanori11:20150912205756p:plain

こんなにも生成できます。　　

書籍やインターネットの記事を読みながらアプリ作っている時はサンプルにしたがっていれば何となくアプリができてしまいます。しかし、自分で１から作るときは「rails g ◯◯」の◯◯のところに何を入れればよいかで少し悩みます。

なので、主なgenarateコマンドを入力した場合、生成されるファイルをまとめました。

f:id:Takanori11:20150912224040p:plain

コマンドは意味を正確に理解したうえで入力しなければならないと改めて実感しました。*1

*1:当たり前