Ractive Programming

chimerastです。

週次LTの担当ということで、Reactive Programmingというパラダイムについて紹介しました。

Reactive Programming from Hideyuki Takeuchi

今流行りの関数型プログラミング言語では、Reactive ProgrammingというとFRP (Functional Reactive Programming)の事を指すことが多いのですが、そっちの説明を始めると若干複雑で前提として必要な知識も多くなるので、大元にある考え方にのみ焦点を当てました。

Reactive Programmingとは

JavaやRuby等の命令型プログラミング言語では

a = 10
c = a + 2
a = 1
print c

というようなプログラムがあった場合、12が出力されます。

これが、Reactive Programmingでは、cが出力される際にa+2という式が初めて評価され、3が出力されます（他の実装として、2行目ではちゃんとcに12を入れておいて、3行目のa = 1が実行されたときにcを再評価して3を代入するというものもあり得ます）。

現実にある実装

Reactive Programmingを体現した一番身近な言語（？）として、Excelがあります。

例えば、E1のセルに「=A1+A3」が入力されていたとして、A1やA3の値を変えると自動的にE1のセルも変わりますよね。

他にもFlexのMXMLにおけるデータバインディング式や、ちょっと違うかもしれませんがJavaFX(ScalaFX)もReactive Programmingが出来ると言っても良いと思います。

どういうところで便利か？

ロボット工学や、シミュレーション等いろいろと応用は効きますが、普通のプログラマにとっては上記のようにGUIプログラムで利用するというケースが一番効果が出やすいと思います。

例えば、コンボボックスが選択された時にその値に応じてテキストラベルを変えるようなプログラムをJavaもどきで書くと、

comboBox.addActionListener(new ActionListener() {
  public void actionPerformed(ActionEvent event) {
    label.text = indexToText(comboBox.index);
  }
}

というように長々と、何をやっているのか本質がぼやけてしまうプログラムとなってっしまいます。
これをReactive Programming的な書き方をすると、

label.text = indexToText(comboBox.index);

の１行で記述できてしまいます。読み方を知っていれば何をやりたいのかも非常に明確です。

これは非常に簡単な例ですが、入力に複数のコンボボックスが関わってきたり、連鎖的に複数のコンポーネントの値が変わるようなものを作る場合には、Java等で書くときとくらべて非常に簡潔に記述することが出来ます。

まとめ

Reactive Programmingを直接利用できる言語や環境はあまりないですが、この考え方を知っていると、データには流れがあるんだという事が理解でき、機能としてReactive Programmingを利用できないような言語でもプログラムの書き方が変わってくると思います。

コマンド実行結果のログ取得について

k-kawaguchiこと川口と申します。
Linux等でのコマンド実行結果のログ取得方法について、LTで発表しました。

コマンド実行結果のログ取得について from Koji Kawaguchi

ネットワークについて

k-kawaguchiこと川口と申します。
技術チーム定例社内研修会にて、ネットワークについて発表しました。

ネットワークについて from Koji Kawaguchi

Web RTC

UZABASEのYakopeliです。

2012/12/19に社内で行ったLTの内容になりますが、今回はWeb RTCについて調べてみました。


Web RTCとは

Real time Communication Beween Browsers APIの略で、JSを使用して
Webブラウザから端末のカメラやマイクにアクセスし、他のWebブラウザとの
リアルタイムなコミュニケーションを可能とするものです。

今までは音声やビデオのリアルタイムな通信を行うには専用のクライアントソフトが必要でした。
また、Webブラウザからは、プラグイン等を入れない限り、マイクやカメラなどのデバイスを
利用することはできませんでした。

しかし、Web RTCが普及すると、

・Webブラウザ上で実行されるJavaScriptで、端末のマイクやカメラなどの
 デバイスにアクセスできるようになる

・取り込んだ音声や動画をリアルタイムに他の端末のWebブラウザに送り、
　ストリーミング再生が可能になる

よって、Webアプリケーションにカメラやマイクを利用した、新しいリアルタイムな
コミュニケーション機能を組み込むことが可能になります。


Web RTCのアーキテクチャ

アーキテクチャですが、大きく分けると4要素で構成されています。

・Web API
　Webアプリケーション側から利用するためのAPI

・Session management/Abstract signaling
　セッション管理やP2Pマッチングの仕組み

・Audio/Video Engine
　オーディオ・ビデオ

・Transport
　データ転送の仕組み

上記のうち、Webアプリ開発者にとって大きく関係するのはWeb APIですが、これは単一の
APIではなく、主に下記二つのAPIから構成されます。

・Stream API
　映像や音声などのストリームデータを扱うAPI

・Peer-to-peer connections
　UDPプロトコルを用い、ブラウザ同士でダイレクトにデータを送受信するためのAPI

簡単に言うと、Stream APIでカメラやマイクにアクセスし、映像や音声をPeer-to-peer connectionsを使って互いのブラウザに送ると、テレビ電話みたいなものが作れます。


デモ

サンプルがあるので、デモで確認してみます。
http://apprtc.appspot.com/にアクセス後、画面下部に表示されるURLに別のブラウザから
アクセスするとテレビ電話が始まります。（どちらの端末もWebカメラが有効になっている必要があります）

まとめ

セキュリティ関連がどのように進められていくか気になるところですが、WebRTCによって専用のクライアントソフトを入れることなく、Webサイトを通じて音声や映像の通信ができるようになるので、何か新しいサービスが生まれてきそうな予感がしますね。

アルゴリズムって何だ

私はさんさです。

アルゴリズムとはよくいわれるものの、それって実際どんなものだ

そんな勉強会を先日開きました。

アルゴリズムとは

Al Khwarizmiというイラクらへんの人が由来。
彼は科学者であり、数学、天文学などの多くの分野において業績を残したそうだ。

ちなみに「アル」はアラビア語の定冠詞である。アラビア語由来の単語に「アル」で始まる物が多いのはそのため。他にも

• アルデバラン (Aldebaran)
• アルタイル (Altair)
• アルカイダ (Al Qaeda)
• アルジャジーラ (Al Jazeera)
• アルコール (Alcohol) 英語発音はアルコホールである、注意しよう

現在の用法

もっぱらコンピュータ業界で念仏のように唱えられるアルゴリズムだが、辞書によると

1. もとは算用数字を用いた筆算のこと
2. 計算や問題を解決するための手順、方式。特にコンピューターのプログラムに適用可能な手続き

出典 三省堂 大辞林

コンピュータでは適切な解を得るための手順を意味することが多い。
数学でもユークリッドの互除法や、エラトステネスの篩(ふるい)なんかは聞いたことがあったとしたら、それもアルゴリズム

よいアルゴリズムとわるいアルゴリズム

一般的によいアルゴリズムと呼ばれるのは以下の条件を満たしていることが多い。いや、満たしているべきだ。

• 意図する結果が得られること
• 計算時間、計算量が少なくすむこと
• 同じ作業の繰り返しでできること
• 使い方が限定されないこと

とりわけ重視されるのが計算時間、計算量が少なくすむことであり、この指標としてO記法なんてものが使われる。

O記法(オーダー記法)

ランダウの記号なんて別名があったりするが、ドヤ顔でいっても何もならない。実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するかを評価するものである。
よく見るのは

• O(1)
• O(n)
• O(n²)
• O(n * log₂n)

Oってどうやって求めるの

難しい話はさておき、このオーダーってどうやって求めるの？という話、なんと以下のようにするだけでできるのである。

1. 計算量を示す式の最大次数に着目する
2. 最大次数の係数を無視する
3. Oとカッコをつけてやる

例：(1/6)(2n³ + 3n² + n)という計算量があったとする
ちなみに自然数の二乗の値のnまでの和の式である。

1. (1/6)(2n³) ... 最大次数以外はいらない
2. n³ ... 係数はいらない
3. O(n³)

最大次数などという呼び方をしたが、実際には計算量の中で一番増加の割合が大きなものを示したものともいえる。

ソート

アルゴリズムの例として挙げられるものといえばソートそれだけ種類が多く、計算量にも違いがあるからだ。
ここでは以下のソートについて、計算量やアルゴリズムを交えて説明する。

• バブルソート
• マージソート
• クイックソート
• ボゴソート

バブルソート

隣接交換法なんて名前がある。 一般人にトランプを渡して番号通りになるようにソートして、というとたいていこれか選択ソートをする、というぐらい誰でも思いつきそうな一般的なソート。

• 平均計算時間はO(n²)
• 安定ソート

安定ソートが何かわからないあなたはwikipedia。 アルゴリズムは単純明快である。

1. n番目の要素が、n + 1番目より大きければいれかえる
2. 1.を最初から最後まで行う
3. 2.を要素の数だけくりかえす

コードにするとこんな感じ

var bubbleSort = function(numbers) {
    var i = 0;
    var j = 0;
    var length = numbers.length;
    var temp = 0;

    for(i = 0; i < length - 1; i++) {
        for(j = 0; j < length - i - 1; j++) {
            if(numbers[j] > numbers[j + 1]) {
                swap(numbers, j, j + 1);
            }
        }
    }
};

隣り合う要素の交換が行われるため、隣接交換法と呼ばれたり、大きな数字が右側に移動していくさまが泡のようだからバブルソートなんて呼ばれているわけである。

マージソート

要素を分割、統合しながらソートする。安定した早さでソートできる。

• 平均計算時間はO(nlog₂n)
• 分割、統合のしかた次第で安定ソートになる
• javaのソートはこれを使用している

アルゴリズム

1. 要素をn分割する(一般的にはn = 2)
2. 1. を繰り返し、分割できなくなるまで分割する
3. それらをマージする。マージの際にソートする

ただし、このソートには弱点があり、一時的に配列を別の場所に記憶しなければならない。
速度はそこそこである一方、記憶領域は消費するソートといえる。

var mergeSort = function(numbers) {
    var sort = function(start, end) {
        var i = 0;
        var j = 0;
        var k = 0;
        var temp = [];

        if(start >= end) {
            return;
        }

        var mid = Math.floor((start + end) / 2);
        sort(Math.floor(start), mid);
        sort(mid + 1, Math.floor(end));
        for(i = start; i <= mid; i++) {
            temp[i] = numbers[i];
        }
        for(i = mid + 1, j = end; i <= end; i++, j--) {
            temp[i] = numbers[j];
        }
        i = start;
        j = end;
        for(k = start; k <= end; k++) {
            if(temp[i] <= temp[j]) {
                numbers[k] = temp[i];
                i++;
            }
            else {
                numbers[k] = temp[j];
                j--;
            }
        }
    };
    sort(0, numbers.length - 1);
};

クイックソート

その名の通り早いソート、ただし弱点があり、遅くなるとバブルソートと大して変わらない。

• 平均計算時間はO(nlog₂n)
• 安定ソート*ではない*

アルゴリズム

1. 要素の中から基準値を決める(ピボット、要素数/2番目の値が選ばれることが多い)
2. 基準値より左側に小さい値を、大きい値を右側に入れ替えるように移動する
3. 1., 2.を再帰的に繰り返す

このアルゴリズムの説明よりも、コードを見た方が早いと思う。

var quickSort = function(numbers) {
    var sort = function(start, end) {
        var pivot = numbers[Math.floor((start + end) / 2)];
        var i = start;
        var j = end;

        while(true) {
            while(numbers[i] < pivot) {
                i++;
            }
            while(pivot < numbers[j]) {
                j--;
            }
            if(i >= j) {
                break;
            }
            swap(numbers, i, j);
            i++;
            j--;
        }
        if(start < i - 1) {
            sort(start, i - 1);
        }
        if(j + 1 < end) {
            sort(j + 1,end);
        }
    };

    sort(0, numbers.length - 1);
};

ボゴソート

とにかく遅くてダメなソート。バブルソート以下。
一般人にトランプを渡して番号通りになるようにソートして、といっても誰もやったことがないほどのソート。

• 平均計算時間はO(n * n!)
• 安定ソートではない

アルゴリズム

1. 要素をシャッフルする
2. 要素がソートされていたら終了、されていない場合は1. をくりかえす

ソートしろといっているのにいきなりシャッフルするのがこのソートのすばらしいところである。

var bogoSort = function(numbers) {
    var shuffle = function(array) {
        var i = 0;
        var length = array.length;

        for(i = 0; i < length; i++) {
            var pos = Math.floor(Math.random() * (array.length - i)  + i);
            swap(array, i, pos);
        }
    };

    var isAscending = function(array) {
        var i = 0;
        var length = array.length;

        for(i = 0; i < length - 1; i++) {
            if(array[i] > array[i + 1]) {
                return false;
            }
        }
        return true;
    };
    var sort = function() {
        while(true) {
            if(isAscending(numbers)) {
                return;
            }
            shuffle(numbers);
        }
    }

    sort();
};

グラフで見る

計算量をグラフで比較するとこんな感じである。

縦軸がy, 横軸がxとなってしまっているが、件数xが増えるとどのぐらい計算量の目安が増えるかというのがよくわかる。
特にボゴソート(赤線)、君は真っ先に天を目指しすぎだ。

ソートをグラフィカルに見る

Jsdo.itにヨサゲなソートをしてくれるものがあったので紹介。
http://jsdo.it/norahiko/oxIy/fullscreen
ボゴソートのクソっぷりを満喫してほしい。

今回はここまで

Lua

技術ミーティングでLTをしたので、ブログでも書きます。
テーマはLuaです。


Luaとは
リオデジャネイロ・カトリカ大学で開発されたスクリプト言語です。
もともとC言語などに組み込まれることを想定しているため、高速な動作、高い移植性、組み込みが容易な事が特徴として挙げられます。

実用例

・アイドルマスター2

・World Of Warcraft

・FF14←もはや()

・Baldur’s Gate

・Playstation Home

・Photoshop lightroom

・VOCALOID3←残念ながら我らがミクさんはVOCALOID2です。

・Wireshark

・ヤマハのルータ

などで使われています。

Luaはスクリプト言語としては速度が速く、組み込みもしやすいのでゲーム制作で活躍しています。

（キャラクターの移動であったり、AIの思考ルーチンだったり……変更が多い箇所で活躍）

どれくらい早いのかは下記を参照してください

http://www.akazah.com/lang-run/

特徴

・Rubyなんかでおなじみの連想配列

・関数が変数として扱えるJavascriptのような機能

・ガベージコレクションが採用されておりメモリ管理も楽ちん

更に、今回紹介したい面白機能として「コルーチン」があります。
「スクリプト言語による効率的ゲーム開発 新訂版」によれば協調的マルチスレッドを実現する機能で平たく言えば実行を途中で止めたり、途中から再開したりできるような関数が作れます！

実例
[コード]

function func(x)
    for i=0,3 do
        print(x..i)
        coroutine.yield()
    end
end

co1 = coroutine.create(func)
co2 = coroutine.create(func)

while true do
    r1 = coroutine.resume(co1, "A")
    r2 = coroutine.resume(co2, "B")
    if (r1 and r2) == false then
        break
    end
end

--

coroutine.yieldで関数を抜けて

coroutine.resumeで再開するんですが……

[実行結果]

A0

B0

A1

B1

A2

B2

A3

B3

おぉ……ちゃんと途中で切って途中からプログラムが走ってる……

風……なんだろう吹いてきてる確実に、着実に、俺たちのほうに！

なんだかおもしろいことができそうでwktkします。

--
[参照]

※スクリプト言語による効率的ゲーム開発 新訂版

http://www.sbcr.jp/products/4797361667.html

第一回、合同技術勉強会を開催しました

はじめまして。
技術チームのtomochangです。

先日、ユーザベースとして初めて外部の方をお招きして技術勉強会を行いました！
社内外から5人のスピーカーにご登壇いただき、それぞれとても刺激的なテーマでお話いただきました。
プレゼン資料と当日の様子を載せておきますので、是非ご覧下さい。

1. 榎本 紘二（弊社インフラチームリーダー）

弊社SPEEDAの紹介と、過去経験した障害への対応策@インフラ

この発表の資料は検閲されました。

お察しください・・・

2. 神尾 隆昌さん(株式会社マインドパレット Co-Founder & CTO)

写真共有アプリSnapeeeのアーキテクチャ、がっつり使うAWS

この発表の資料は検閲されました。

お察しください・・・

3. 矢野 勉さん(株式会社シェルフ代表取締役)

分散JVMマイクロサーバの構築 from Tsutomu Yano

4. Mr. X(某巨大BtoCサービスインフラチームリーダー)
大人の事情で非公開となります。


5. 竹内 秀行 (弊社チーフテクノロジスト)
広域不可分散ファイル配信システム KARATACHI-PORTUS

karatachi-portus from Hideyuki Takeuchi

勉強会の後は場を移し、もつ鍋をつつきながらの懇親会へ。
やったお酒が飲め(ry

発表内容についてのディスカッションはもちろん、Snapeeeが全世界で大ヒットしている理由、某巨大BtoCサービスならではのデータセンターの選び方、Javaの今後や最適な開発体制のあり方などなど、超貴重でコアな話が飛び交う素敵な会でした。


今後もユーザベース技術チームでは、定期的に合同勉強会を行う予定でいます。
楽しそうだなと思った技術者の方は、是非一度遊びにきて下さい。
スピーカーとして話してやるぜ！という素敵な方も随時募集中です。


ご連絡は下記までお願い致します。
technology@uzabase.com