UZABASE開発者ブログ（旧）: 1月 2013

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) 英語発音はアルコホールである、注意しよう

現在の用法

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

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

出典三省堂大辞林

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

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

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

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

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

O記法(オーダー記法)

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

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

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

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

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

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

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

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

ソート

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

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

バブルソート

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

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

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

n番目の要素が、n + 1番目より大きければいれかえる
1.を最初から最後まで行う
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のソートはこれを使用している

アルゴリズム

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

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

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)
安定ソート*ではない*

アルゴリズム

要素の中から基準値を決める(ピボット、要素数/2番目の値が選ばれることが多い)
基準値より左側に小さい値を、大きい値を右側に入れ替えるように移動する
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. をくりかえす

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

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
ボゴソートのクソっぷりを満喫してほしい。

今回はここまで

UZABASE開発者ブログ（旧）

2013年1月11日金曜日

Web RTC

2013年1月7日月曜日

アルゴリズムって何だ

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

アルゴリズムとは

現在の用法

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

O記法(オーダー記法)

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

ソート

バブルソート

マージソート

クイックソート

ボゴソート

グラフで見る

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