野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

動的計画法とトポロジカルソート

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

を本屋で見て買おうか迷っていたところ、アルゴリズムの図解ということでふと思い出したのが、 アルゴリズムイントロダクション15章 動的計画法のスライド。ここで登場する最長共通部分列の図は目から鱗だった。

そういえば電子書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

を持っていたままあまり読んでいなかったので久々にアルゴリズムの勉強でもしてみる。 本を片手に自分で実装してみたものをそのままメモ。

なんとか理解できそうなものをかいつまみ。

DP: Longest Common Subsequence problem: LCS

動的計画法の有名な問題らしい。最長共通部分列とは、X = {a, b, c, b, d, a, b},Y = {b, d, c, a, b, a}があるとすると{b, c, b, a}。

// O(NM)
// dp[i][j] = dp[i-1][j-1]+1 //X[i]==Y[j]
//          = max(dp[i-1][j], dp[i][j-1]) //X[i]==Y[j]
// getLCSLength("abcbdab","bdcaba") // 4
int 
getLCSLength(string x, string y){
  int M = x.size();
  int N = y.size();
  int maxVal = INT_MIN;
  vector<vector<int>> dp;
  dp.resize(M,vector<int>(N,0));
  if(x[0]==y[0]){ dp[0][0] = 1; } else { dp[0][0] = 0; }
  if(x[0]==y[1]){ dp[0][1] = 1; } else { dp[0][1] = 0; }
  if(x[1]==y[0]){ dp[1][0] = 1; } else { dp[1][0] = 0; }
  for( int i = 1; i < M; i++ ){
    for( int j = 1; j < N; j++ ){
      if(x[i]==y[j]){
        dp[i][j] = dp[i-1][j-1]+1;
      } else {
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
      }
      maxVal = max(maxVal, dp[i][j]);
    }
  }
  return maxVal;
}

DP: Coin Changing Problem

これも有名。最小のコインの枚数を調べる問題。

// O(NM)
// i is index of coin [0...5]
// j is amount [0...15]
// dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]]+1);
// getMinimumCoinCount(15, 6, vector<int>{1, 2, 7, 8, 12, 50}) // 2
int getMinimumCoinCount(int total, int N, vector<int> c){
    vector<vector<int>> dp;
    int minVal = total;
    dp.resize(N,vector<int>(total+1,INT_MAX));
    for( int i = 0; i < N; i++ ){
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for( int j = 2; j <= total; j++ ){
        for( int i = 0 ; i < N; i++ ){
            dp[i][j] = (i > 0) ?  dp[i-1][j] : INT_MAX;

            if( (j - c[i]) >= 0 ) {
                dp[i][j] = min(dp[i][j], dp[i][j - c[i]] + 1);
            }
        }
    }
    for( int i = 0; i < N; i++ ){
        minVal = min(minVal, dp[i][total]);
    }
    return minVal;
}

DP: Knapsack Problem

名前は辛うじて聞いたことがあるナップザック問題。ナップザックに入る重さで価値が最大になるようなものを調べる。

// O(NW)
// i - item index
// v - item value
// w - total weight
// dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
// getMaximumValue(vector<int>{2,2,1,3},vector<int>{4,5,2,8},5)
int getMaximumValue( vector<int> w, vector<int> v, int napSize ){
    vector<vector<int>> dp;
    int N = w.size();
    dp.resize(N,vector<int>(napSize+1,0));

    for( int j = 0; j <= napSize; j++ ){
        dp[0][j]= (w[0] <= j) ? v[0] : 0;
        if(j-w[0]>=0){
            dp[0][j] = max(dp[0][j], dp[0][j-w[0]]+v[0]);
        }
    }
    for( int i = 1; i < N; i++ ){
        for( int j = 1; j <= napSize; j++ ){
            dp[i][j] = dp[i-1][j];
            if( j-w[i] >= 0 ){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    return dp[N-1][napSize];
}

DP: Longest Increasing Subsequence

今度は最長増加部分列という問題。最初に自分で考えて書いたときは

// O(N*N)
// getLISLength(vector<int>{5,5,1,3,2,4}) // 3
int getLISLength(vector<int> input){  
  vector<int> dp(input.size(),1);
  for( int i = 1; i < input.size(); i++ ){
    for( int j = i-1; j >= 0; j-- ){
      if( input[j] < input[i] ){
        dp[i]=max(dp[i], dp[j]+1);
      }
    }    
  }
  return *max_element(dp.begin(),dp.end());
}

こんな感じ。これを本に登場するより良い方法で実装すると

// O(N*logN)
// getLISLength(vector<int>{4, 1, 6, 2, 8, 5, 7, 3}) // 4
int getLISLength(vector<int> input){
    vector<int> L(input.size(),0);
    L[0]=input[0];
    int length = 1;

    for( int i = 1; i < input.size(); i++ ){
        if(L[length-1] < input[i]){
            L[length++] = input[i];
        } else {
            *lower_bound( L.begin(), L.begin()+length, input[i] ) = input[i];
        }
    }
    return length;
}

lower_boundは中で二分探索。指定した値以上の最初の要素の位置(つまり値を挿入できる位置)をイテレータで返してくれる。

Graph Topological Sort

ビルド順を考えたりする際によい(そんな仕事はしていないけど)よい方法。 以前に書いた幅優先探索

データ構造 - 計算量・グラフの走査 - 野次馬エンジニア道

がそのまま使われている。

// O(|V |+|E |)
//     vector<pair<int,int>> v{
//        make_pair(0,1),
//        make_pair(1,2),
//        make_pair(3,1),
//        make_pair(3,4),
//        make_pair(4,5),
//        make_pair(5,2)
//    };
//    getSortedNode(v, 6); // {0,3,1,4,5,2}
struct Node {
    int value;
    vector<Node*> next;
    int count;
    bool added;
    Node():value(-1),count(0),added(false){}
};

void traverseBFS( vector<int>& ret, Node* root ){
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        Node* n = q.front();
        q.pop();
        ret.push_back(n->value);
        n->added = true;
        auto it = n->next.begin();
        while( it != n->next.end()){
            Node *next = *it;
            next->count--;
            if(next->count == 0 && !next->added ){
                q.push(next);
            }
            ++it;
        }
    }
}

vector<int> getSortedNode( vector<pair<int,int>> v, int N){
    vector<Node> node(N);
    vector<int>  ret;
    for( int i = 0; i < N; i++ ){ node[i].value=i; }
    for( pair<int,int> p : v ){
        node[p.first].next.push_back(&node[p.second]);
        node[p.second].count++;
    }
    for( int i = 0; i < N; i++ ){
        if( node[i].count == 0 && !node[i].added ){
            traverseBFS(ret, &node[i]);
        }
    }
    return ret;
}

Outlook2011ユーザのためのMacBook移行

2017年は仮想マシンなどをとにかく手元で試したいがSSDの容量が逼迫しているためスキマ時間に別のマシンに移行してみた。

移行アシスタント

何はともあれ移行アシスタントでデータを移行する。容量も多いのでEthernetケーブルで2台のMacBookを直結する。

上記記事ではあまり丁寧な解説がないが、初期化*1直後のウィザードだとWIFI接続でWPA2が前提。 Ethernetの場合は一度適当なアカウントで起動してしまうこと。このとき移行アシスタントがホームディレクトリを上書くため、元のアカウント名と被らないように注意。

移行先のOSはSierra ?

普通に考えると最新のSierraだがOutlook2011との相性の問題かメールの検索が全くできなくかった。結局諦めてYosemiteにした。

MacユーザでOfficeユーザは下記のサイトを事前にチェックしてからアップデート先を決めた方が良い。

support.office.com

Yosemiteのインストール・ダウングレード

AppStoreでは最新版のOSとセキュリティアップデート等しか配布していない。ただし、一度ダウンロードしたことがあればAppStoreから再ダウンロード可能。

/Applications/Install\ OS\ X\ Yosemite.app/Contents/Resources/createinstallmedia

インストーラーがあるのでこれを使ってインストール可能なUSBメモリを作成可能*2USBメモリがない場合は外付のHDDで代用も可能。自分はDiskMaker Xの下記バージョンを使った*3。これでインストールディスクを作ればダウングレードも可能になる。

Outlookでのメール検索

Sierraではメール検索が動作せず徹底的に調査した*4

検索機能はSpotlightに依存

Microsoftのサポートのフォーラムの#KB2741535Outlookのメール検索がどのように行われるかが書いてある。

  • OSがHD上のSpotlightSearchのIndexをコントロールしていること*5
  • 2016も2011のどちらのバージョンもSpotlightの検索に依存
  • フィルタも同様
  • Outlookのタスクもフィルタを使って表示されている
  • 新しいデータが入ってきたときに場合によってIndexingは数分はかかる

とのこと。

Spotlightの再インデックス

Appleのサポート記事*6に2種類方法が紹介されている。システムの環境設定とユーティリティを使う方法。

ここでSpotlightの内部でIndexをどのようにしているのか、

apple.stackexchange.com

の記事が参考になる。

/usr/bin/mdimport -Lで利用しているSpotlightのインポーターが列挙できる。例えばOutlook 2011であれば

/Applications/Microsoft Office 2011/Microsoft Outlook.app/Contents/Library/Spotlight/Microsoft Outlook.mdimporter

がそれにあたる。さらに問題があればメッセージを指定して

/usr/bin/mdimport -d 2 ~/Documents/Microsoft\ ユーザー\ データ/Office\ 2011\ Identities/Main\ Identity/Data\ Records/Messages/0T/0B/0M/0K/x00_235.olk14Message

のようにインポートを試してみることができる。

ちなみに、このMain IdentityというのがOfficeのデータベース。不安定だったり挙動がおかしいときは自分で再構築も可能*7

ライセンス移行

最後の問題はなぜか移行後にライセンス認証を要求されたこと。下記の記事を参考にライセンスをコピー。

apple.stackexchange.com

/Applications/Microsoft Office 2011 folder (copy the entire folder, with all its contents)
/Library/LaunchDaemons/com.microsoft.office.licensing.helper.plist
/Library/PrivilegedHelperTools/com.microsoft.office.licensing.helper
/Library/Preferences/com.microsoft.office.licensing.plist

なんとか無事移行完了。新年早々嵌りまくったので今年はもう嵌りませんように。。。

*1:https://support.apple.com/ja-jp/HT204904

*2:https://support.apple.com/ja-jp/HT201372

*3:DMX_Workdiskというエラーに悩まされたため

*4:結局下記で色々調べたが動作せず。Yosemiteで解決

*5:/.Spotlight-V100/というディレクトリがインデックス

*6:https://discussions.apple.com/thread/5034126?tstart=0

*7:https://support.microsoft.com/en-us/kb/2360509

Building Microservices

2016年もあと少し。毎年恒例オライリーのカレンダー欲しさに今年も本を購入。

f:id:notta55:20161218172556j:plain

大分前に読んだが内容をまとめていなかったので気になったところをメモ書き。

マイクロサービスアーキテクチャ

マイクロサービスアーキテクチャ

マイクロサービスとは小規模で自律的なサービス。自律的とは、単独でサービスのデプロイを行いAPIを介して利用できるような状態のことを指している。

翻訳だと凝集性ということばが出てくる。原文だとCohesion。関連するコードが集まるような状態のこと。結合度と並べて比較される。結合度が高いものは凝集度も低い。

情報工学においてモジュール内のソースコードが特定の機能を提供すべく如何に協調しているかを表す度合いである。 Wikipedia 凝集度 - Wikipedia

マイクロサービスの利点とは?

  • 技術的異質性
  • 回復性
  • スケーリング
  • デプロイの容易性
  • 組織面の一致 (原文だと Organizational Alignment) - 重要なコンウェイの法則について
  • 合成可能性 (原文だと Composability) - これだけだと何のこっちゃという感じだが、

組織が、狭いチャンネルの観点での考え方からより全体的な顧客エンゲージメントの概念に移っているので、それに遅れてついて行けるアーキテクチャが必要です。

P9. より

すっきり。 - 交換可能性にするための最適化 (原文だとOptimizing for Replaceability) 、早い話が、置き換えコストの話。

原則とプラクティス・ガバナンス

2章の進化的なアーキテクトの中であった原則とプラクティスの考え方。原則を確実に実行するためのプラクティス。プラクティスは時を経て変わるかもしれないが原則は変わらない。本文中で紹介されていた例。このようなレベル分けが整理するには有効。

ガバナンスが意味するところ

ガバナンスは、利害関係者のニーズ、状況、選択肢を評価し、優先度順位付けと意思決定を通じて方向性を設定し、合意した方向性や目的に対する実績、順守、進捗の監視を行うことで企業の目的が達成されるようにすることです。

  • COBIT5 P.29より

自律した小さいサービスを複数開発するがゆえにガバナンスは特に重要となる。

境界づけられたコンテキスト (Bounded Context)

これもピンとこない。

私が好きな境界づけられた別の定義は、「明示的な境界によって強制される特定の責務」です。

P.35より

と本文中リンクを一つ紹介している

blog.sapiensworks.com

コンテキストは特定の責務のこと。境界づけられたコンテキストとはほぼIT部門や経理部門のような組織のことを指している。責務とはIT部門であれば、システムやソフトウェアの面倒を見る(責務がある)ということで、経理部門であれば給与を管理するなどである。給与の計算ソフトに何か不具合があったときに、直接経理部門の人がデバッグしたりしない。またIT部門のなかが開発部門とサーバなどのインフラ管理にわかれていることも経理の人には関係ない。ではこの二つの部門がどのように協業するのか。このリンクの例ではそれぞれの部の担当者に加えてIT部門のManagerが登場する。新機能の追加や不具合の追加など、すべてManagerを通す。

つまり二つの境界づけられたコンテキストは双方に違いの中を知る必要がなく、これら二つの境界づけられたコンテキスト通しが共通のオブジェクトを一方へ直接渡す、もしくは両者が話せる話せる特別なアダプターを用いることになるということである。少しイメージが湧く。

設計観点でのサービスとしての責務はあるが、やはり組織やチームが面倒を見る範囲という実体に則った切り口というのが自然と言える。

トランザクション境界

モノリシックなデータベースだとすべての作成や更新は一つのトランザクション境界(開始と終了)内で行われるが、データベースを分割するとそうではなくなる。その問題に対処するために後でリトライするか補正トランザクション(Compensating Transaction)を発行して操作全体の中止をするか。いずれにせよ一貫性を保ちたい対象が大きければ難しい問題となる。

分散トランザクション - 2相コミット(Two-phase commit)

本文中に出てくるトランザクションマネージャの話。ネットワーク境界を越えて通信する複数の異なるシステムに対して一貫性を保つ。 少し古い記事だがここのシーケンス図がわかりやすい*1

仕組みは簡単。投票フェーズ(コホートとも呼ばれる)で全参加者がOKだったらコミットするように指示するというもの。 f:id:notta55:20161218150803p:plain

トランザクションマネージャはダウンしない、コミット指示があるまで各参加者は停止しているため、投票フェーズで障害があると参加者はブロックされるなどいくつか制限がある。

バッチAPI

DBではなくAPI中心にした場合にレポーティングのためなどに全データの取得などのユースケースが問題になる。

顧客サービスはBatchCustomerExportリソースエンドポイントのようなものを公開できます。呼び出し側システムはBatchRequestをPOSTし、おそらく全データを含むファイルを配置できる場所に渡します。顧客サービスはHTTP 202レスポンスコードを返し、リクエストを受け付けたものの未処理であることを示します。すると呼び出し側はシステムはリクエストが実行されたことを示す201作成済み状態を受け取るまでリソースをポーリングし、それからデータを取得できます。

P.113より

他にはデータを別のレポートのDBに定期的に投入するデータポンプという仕組みも紹介されている。

CAP定理

分散システムに互いにトレードオフとなる3つの事項がある

  • 整合性 (一貫性、consistency)
  • 可用性(availability)
  • 分断耐性(partition tolerance)

全てを満たせないのは数学的に証明されている。例えば整合性を犠牲にして可用性を維持するシステムは結果整合性があるという。この場合はAPを選んでいることになる。分散システムの場合ネットワーク上で動作させなくてはならないのでCAという組み合わせはない。整合性はあるけれども構築やスケーリングが困難なCPという選択肢もある。複雑なのはそれがサービス単位で選ぶよりも細く考慮が可能なところ。

整合性がないか可用性がないかはオールオアナッシングではない、ということがあります。多くのシステムではさらに細かいトレードオフが可能です。例えば、Cassandraでは呼び出しごとに異なるトレードオフを選ぶことができます。

P.273より

コンウェイの法則

組織とアーキテクチャが一致すべきという考えで、それの根拠となる論文*2からきている。

システム(ここでは単なる情報システムよりも広く定義されたシステム)を設計するあらゆる組織は、必ずその組織のコミュニケーション構造に倣った構造を持った設計を生み出す。

P.223

チームにそのチームが担当するシステムを所有、運用させ、ライフサイクル全体を管理させる、そのために必要であれば組織構造をも変えてしまうという例が紹介されている。さらに地理的な要因やコミュニケーションの経路も同様に設計に重要なインパクトを与える。

まとめ

12章にあるまとめ(原文では、Bringing It All Together)。

  • ビジネス概念に沿ったモデル化 (Model Around Business Concepts) -
  • 自動化の文化の採用 (Adopt a Culture of Automation) たくさんの可動部を扱うために高度な自動テストと継続的なデリバリが必須なところ
  • 内部実装詳細の隠蔽 (Hide Internal Implementation Details) - モデル化とAPI
  • すべてを分散化 (Decentralize All the Things) - これはシステムのことではなく、意思決定と制御を可能な限りチームに委譲することを指している
  • 独立したデプロイ (Independently Deployable)
  • 障害の分離 (Isolate Failure) - アンチフラジャイルの概念を念頭に置いて、障壁やサーキットブレーカーなどを使って副次的な影響を最小限にする
  • 高度な観測性 (Highly Observable) - セマンティック監視や合成トランザクションの導入を通して統合的な監視を行う

最後に書きながらあれもこれとなった。この本はテンコ盛り。

感想

この本の帯にマーチン・ファウラー*3は「マイクロサービスへの道は、注意深く進まないと痛みを伴う罠がある」というコメントを寄せている。それでも構築できれば他を圧倒する優位性があるのだと思う。本書によるとその道のりはまさに旅。先人の知恵が凝縮されたそのガイド本として読み応えがある本だった。

Architecting for Scale - Two mistakes high

スキマ時間にコツコツ下記の本を読む。

Architecting for Scale: High Availability for Your Growing Applications

Architecting for Scale: High Availability for Your Growing Applications

概要としては、

  • 可用性 (availability)
  • リスク
  • サービスやマイクロサービスを用いたアプリケーション構築
  • アプリケーションと開発チームのスケーリング
  • スケーリングのためのクラウドの活用

をそれぞれ著者:Lee Atchison *1の経験に基づき詳細に解説している。早速気になったところをメモ書き。一部の章はPreview版が公開されている*2

可用性

可用性とはアプリケーションが行うべきタスクを実行し続けることができる状態にある能力のこと。信頼性とは異なる。例えば、2+3で6が返るようなことが信頼性。可用でないときは、2+3が返ってこない状態。利用可能な状態可用性の低下が起こる要因としては

  • リソースの枯渇
  • 予期せぬ負荷
  • 可動部分の増加
  • 外部の依存性
  • 技術的負債

リスク管理

リスクを特定することなしにリスク管理は行えない。全てのリスクを取り除くことは不可能なのでコストとのバランスとなる。リスクを考える上での発生の可能性(Likelihood)と深刻度(Likelihood)の両面を考えることが重要。当然、起こりやすく深刻度の高いものを解決することが必要となる。リスク管理の基本的なステップは

  • リスクの特定 - システムで考えられるリスクを全て列挙して優先度付けをする
  • 原因の除去 (Remove worst offenders) - もっとも大きい要因を特定し、それに対する対応を計画する
  • リスクの軽減 - 取り除くことができないものの発生の可能性もしくは深刻度を軽減する
  • 定期的な見直し

リスクマトリックス

紹介されていたフォーマット*3

  • リスクID
  • システム名 またはコンポーネント
  • オーナー - 個人かチームか
  • リスクの説明
  • 日付
  • 発生の可能性 ( low, medium, or high)
  • 深刻度 (low, medium, or high)
  • 軽減プラン
  • ステータス
  • ETA
  • モニタリング - このリスクが発生することをモニタリングしているかどうか。
  • 発生時のプラン - このリスクが発生したときに何をするか。インシデントの応対プランよりもマネジメントレベルでのプラン。

早速シートを作ったら関係者の見識を加えてブレスト。開発チーム・サポート・脅威ベクトル・バックログ・パフォーマンス・ビジネスオーナー ・外部のチーム・システムとプロセスとして明文化されているか・技術的負債はあるかなど。

次に発生の可能性と深刻度を設定する。そして計画を立ててタスクとして実行していく。

サービス

ここでサービスとは一つないし二つの製品を支える機能を与える境界を持ったシステムのこと。サービスは改善されたシステムと開発チームにスケーラビリティをもたらすシステム構築を可能とするアプリケーションパターン。

大規模なマイクロサービスベースのアプリケーションの一つの弱点はサービスの不具合。サービスの数が多ければ多いほど可能性が増し、また不具合のあったサービスへ依存のあるサービスも増える。

レスポンスが返ってこない場合の良いアプローチとして、Circuit breaker design pattern - Wikipedia, the free encyclopediaを紹介。

スケーリング

失敗の連鎖、カスケードした依存性を避けるために"Two mistakes high"でシステム構築を行う。ラジコンの例えで、2つ間違いを犯してもリカバリーできるぐらい十分な高さで飛ばすべきという意味。

他には内部的なSLAやサービスのTierについて。

STOSA (Single Team Owned Service Architecture)

スケーラビリティや可用性を犠牲にせずに多くのエンジニアが効率よく一つのアプリケーションを開発するための組織のあり方について。criteriaとしては、

  • サービスやマイクロサービスベースのアーキテクチャに則ったアプリケーションがある
  • 複数の開発チームがそれを開発している
  • アプリケーションの全てのサービスが開発チームにアサインされている
  • 複数の開発チームにアサインされるサービスが一つもない
  • ここの開発チームが一つ以上のサービスを担当するかもしれない
  • チームはサービスに関わる全ての側面(デザイン・デプロイ・テスト・モニタリング・インシデント管理)に責任を持つ
  • サービスはそれらの間にAPIドキュメントも含めて強い境界線が存在する
  • サービスは内部的なSLAを維持し、それらを監視し守られない場合にはサービスのオーナーにレポートする

クラウド

  • MultiAZ。別々のデータセンターとなるのは一つのアカウント内のみ。
  • CloudWatchで十分か? No.ベースラインのみ。サーバやOSの情報(メモリ使用量・スワッピング・ディスクの使用量)。パフォーマンスモニタリング。どのようにユーザに使われているか、エラーなどの情報がいる。
  • リソースのアロケーションにおける二つのカテゴリ。Allocated-capacity resources (EC2, ELB, DynamoDB)。Usage-based resources (S3, Lambda, SES, SQS, SNS) から長所・短所を考える。

Architecting for Scale とは

単に多くのユーザを裁くというだけでなく以下に留意する

  • ユーザ数とその増加に耐える
  • データ量とその増加に耐える
  • アプリケーションで達成したいことがより複雑化することに耐える
  • 開発者が増加してもスピードや効率性、品質が落ちない
  • これらの変更があっても常に可動し続けること

感想

もっとも印象に残ったのは、”Two mistakes high”という言葉。日頃から意識して取り組むと大分違うのではないかと思う。また実践としてアーキテクチャをレビューする際にはこういった項目を漏れなく自分たちのプロジェクトや組織、システム領域やゴールに合わせてチェックすることになるのだと思う。

Alexa Skills Kit を使ったAmazon Echoのカスタムスキル開発

(少し前の話だが) 6月に開かれたAWS Summit 2016*1で、気になる講演 「クラウドとマイクロサービスによる音声操作の新時代 - Amazon Echo & Alexa」があったので聴きに行ってきた。

www.youtube.com

Amazon Echoは音声でSpotifyにある楽曲を再生するデモを見てからずっと気になっていたが、日本での発売や日本語対応は残念ながら未だ*2。それにしてはかなり大体的な扱い(大袈裟)。

AWS Summitの文脈としてはその背後にあるAlexaというシステムがサーバレスアーキテクチャを活用していたりIoTの事例としても興味深いからだと思う。加えて音声のインターフェースによって「日用品を追加注文」「ピザを注文する」「音楽をかける」といった日常的なタスクを徐々に積み上げていくことで、Alexa自体が提供できるサービスが拡大していくエコシステムの完成を目指している点に惹かれる。

Alexa Skills Kit (ASK) 入門

エコシステムの実現のためには、オープンに誰でも「スキル」を開発できることが重要。音声認識自然言語処理、意図理解のような高度な処理はAlexaに任せて、JavaScriptPythonを使って実際に自分のサービスやブランドに関する「スキル」を誰でも開発できるAlexa Skills Kit(ASK) を提供している。

公式の記事としては、このチュートリアルが一番良さそう。最近は(USのEASTのリージョン限定のようだが)LambdaのテンプレートにもAlexaのスキルがいくつか登録されている。そちらを試すのもよい。

Hello Worldから

まずは何はともあれHello World。このサンプルはSDKとしても提供されているが、ZIPを作ってLambdaに上げたりと結構面倒な作業が多い。そこでAPI Gatewayを調べていたときによく紹介されていたfluctをイメージしてAlexa版のテンプレートを作ってみた。

開発のパイプライン

ES6(ES2015)でコードを書いて、mochaでテスト、そしてLambdaをデプロイして、Echo上でテスト。この一連の流れをまずは実現。

github.com

最初のLamdaのデプロイ後にはトリガの設定などが必要だが一度やってしまえば

npm test # スキルをmochaでテスト
gulp build # ES6 => ES5
gulp deploy # Lambda上にデプロイ

のように開発可能。スキルの中身は元のサンプルと全く同じ。

*1:セッション資料・動画は - https://aws.amazon.com/jp/summit2016-report/details/から閲覧可能

*2:https://echosim.io/welcome

Angular2.0とAngular1.Xからの移植について

f:id:notta55:20160327000332j:plain

3月21日に品川のマイクロソフトの本社で開かれた

ng-japan - The Angular conference in Tokyo, Japan (2016/3/21)

に参加。自分がチェックしたかった内容は

  • Angular2.0
  • Angular1.Xからの移植

非常に有益な話がたくさん聞けたので大変満足。セッションをピックアップすると

Session Slide
Angular2の失敗しない始め方 / 稲富 駿 Slide
Progressive Web Apps / 浅井 智也 Slide
Angular2を書くためのAngularJSの書き方 / 吉田 徹生 Slide
ngUpgradeと移植戦略 / 奥野 賢太郎 Slide
Angular1.4で作られた自社マイクロサービスを2へマイグレーション / 林 優一 Side

特に圧巻だったのが、Angular2の失敗しない始め方 / 稲富 駿のセッション。スライドは必見。

Angular2.0

Platform

AngularDartとかもあって、AngularがAngularJS=>Angularとなったのは知っていたがロードマップとして、サーバーサイドでも動く構想があることは知らなかった。

f:id:notta55:20160327000801p:plain

Full Stack Angular 2 – Jeff Whelpley and Patrick Stapleton - YouTube

Angular1.Xでは色々なコンセプトがあって覚えることが多いが初心者(自分)でも簡単にアプリを作ることが可能。一方Angular2.0ではWebのフロントエンド技術の革新に合わせて新しいJavaScriptのライブラリや言語の仕様を先行して取り入れるような発想になっている。

Polyfilの積極活用

それを表すのが下記のようなライブラリの活用。将来的にブラウザにネイティブに実装されるのを見越して大胆に外部のものを使っている。

  • SystemJS モジュールの動的ロード
  • RxJS - Obserbableのため
  • Zones - 変更検知のため - $scope.apply()不要。

コンポーネントでの開発

Angular1.Xでdirectiveを使ってコンポーネント化して開発をしていたが、Angular2では完全に置き換えられていることにまず驚く。WebComponentを先取りしたPolymerやとaltJSでclassでキーワードでコンポーネントで開発できる素地があるなかでここまで大きく変更されているとは思っていなかった。

Angular2.0では「TypeScript推奨」と会場でも度々言われていたが、それはAngular2が@Decoratorsのようなアノテーションの機能の型チェックを前提としたものだからのようだ。データバインディングのところの記述が汚くなりがちなので、宣言的に記述すれば可読性とメンテナンス性は明らかに向上する。

パフォーマンス向上

双方向データバインディングが画期的な仕組みだった一方で、dirty checkingとして知られるパフォーマンスの問題があった。Angular2では、DOMの変更の検知が 100000 checks / ~10ms と非常に高速。この変更検知のためのコードは現状は最初に動的生成しているらしい。今後これがデプロイ前に生成されその分高速化される見込み。

非同期処理がRxJSへ

内部でRxJSを利用。Promiseは基本的に一度切りの処理だが、RxJSはイベントのシーケンスを処理することが可能。これは決定的に大きな違い。

1.Xからの移植

移植の困難さを図解した下記の図が非常に参考になる(ngUpgradeと移植戦略 / 奥野 賢太郎 のスライドから引用)。距離が遠いほど移植は困難。

f:id:notta55:20160327000809p:plain

ngUpgradeは端的に言うとは2.0のなかで1.0の動作をエミュレーションして移植を容易にする機能のことのようだ。会場ではAngular1.5+TypeScriptで開発をしてAngular2.0に備えるという人がまだまだ多いように感じた。

まとめ

スピーカーの人も熱のある人が多く非常にいいイベントでした。変化の激しいWebのフロント周りですが、特定のフレームワークを学ぶだけではなく、言語の仕様とかインパクトのあるライブラリなどは広くチェックし続ける必要があると感じた。

ElasticSearch入門 (3) スコアの計算

フィルタリングの話の前にスコアの計算が気になったので深く見てみることにした。

基本的な知識

ベクトル空間モデル

単語を一つのベクトルとして表現して扱うベクトル空間モデルでは、ドキュメントの類似度をコサイン距離で計算する。

{\displaystyle
  cosine-similarity(q,d) = \frac{ V(q) \cdot V(d) }{ |V(q)| |V(d)| }
}

正規化することでドキュメントの長さの情報が失われてしまうのが問題点。

TF・IDF

より良い結果を得る方法として各タームを出現頻度によって重みづけるというやり方が知られている。{\displaystyle
D=\left\{ d_{1},d_{2},...,d_{n}\right\}
} をドキュメントの集合として、 各タームの {w_{j}}に対して{n_{ij}}を文書{d_{i}}における {w_{j}}の出現回数、{n_{j}}{w_{j}}が一回以上含まれる文書の数としたときに

{ \displaystyle
tf_{ij} \doteq \frac{n_{ij}}{|d_{i}|}
}

{ \displaystyle
idf_{j} \doteq \log \frac{n}{n_{j}}
}

IDFはドキュメント全体におけるタームの重要性なイメージ。{d_{i}}における{w_{j}}の重みは{ tf_{ij} \cdot idf_{j} }。 他にも定義は色々存在するようだ*1

Luceneのスコア計算

概念的なスコア計算

Luceneでは、{|V(d)|}のノルムの部分を以下のように分解している。

{
 score(q,d) = coord(q,d) * queryBoost(q) * \frac{ V(q) \cdot V(d) }{ |V(q)| } * lengthNorm(d) * docBoost(d)
}

説明
coord ドキュメントに含まれるタームの数による調整項。他のドキュメントに比べてどれだけ多くの検索タームを含むか。
queryBoost 特定のフィールドに対するクエリへのブースト
lengthNorm 正規化項、短いワードでドキュメントが構成される方がスコアが高い
docBoost 特定のドキュメントに対するブースト

実際のスコア計算

コンセプトとしては上記だが実際のLuceneではTF・IDFでも重み付けも合わせて下記のように算出している。

{ \displaystyle
score(q,d) =
}

{ \displaystyle
coord(q,d) * queryNorm(q) * \sum_{t\ in\ q}(tf(t\ in\ d)*idf(t)^2 * boost(t) * norm(t,d))
}

説明
coord ドキュメントに含まれるタームの数による調整項。他のドキュメントに比べてどれだけ多くの検索タームを含むか。
queryNorm 異なるクエリ間でスコアを比較するための正規項。{|V(q)|}の部分
boost {queryBoost(q)}の部分をターム毎に分解
norm {docBoost(d)}{lengthNorm(d)}をまとめてターム毎に分解

正規化のための項やインデックス時に計算できる項は予め別に切り出し、さらにターム毎にブーストが設定できる。 それぞれを見ていくと、

TF・IDF

Luceneでは下記の通り算出する。意味合いとしては上で見たのと同じ。ここがスコア算出の中心となる。

{ \displaystyle
tf(t\ in\ d) = frequency^{1/2}
}

{ \displaystyle
idf(t) = 1 + \log{}\frac{numDocs}{docFreq+1}
}

queryNorm, boost

{
queryNorm(q) = queryNorm(sumOfSquaredWeights) = \frac{1}{sumOfSquaredWeights^{1/2}}
}

{
sumOfSquaredWeights = q.getBoost()^{2} \cdot \sum_{t\ in\ q} \left( idf(t) \cdot t.getBoost() \right)^{2}
}

{t.getBoost()} の部分は検索時にターム毎に設定するブースト値。

norm(t.d)

インデックス時に設定するブーストと長さをまとめたもの。

{norm(t,d) = lengthNorm \cdot } \prod_{field\ f\ in\ d\ named\ as\ t} f.boost()

珍しいタームにマッチした方が高いスコアになり、フィールド内のタームの数が少ない方がスコアが高くなる。 インデックス時、検索時に双方でブーストを設定できることでより重要度の高いタームを含むドキュメントにつくスコアを調整することができる。

ElasticSearchでのスコア計算

下記のようなデータを入れる。

POST scoring/doc/1
{ "name" : "one two" }
POST scoring/doc/2
{ "name" : "one three" }
POST scoring/doc/3
{ "name" : "one two three" }
POST scoring/doc/4
{ "name" : "one two three four" }

下記で検索。

GET scoring/_search
{
  "query" : {
    "match" : {
      "name" : "one two"
    }
  }
}

スコア順だと

{
  "_index": "scoring",
  "_type": "doc",
  "_id": "1",
  "_score": 0.79143506,
  "_source": {
    "name": "one two"
  }
}
{
  "_index": "scoring",
  "_type": "doc",
  "_id": "3",
  "_score": 0.6331481,
  "_source": {
    "name": "one two three"
  }
}
{
  "_index": "scoring",
  "_type": "doc",
  "_id": "4",
  "_score": 0.6331481,
  "_source": {
    "name": "one two three four"
  }
}
{
  "_index": "scoring",
  "_type": "doc",
  "_id": "2",
  "_score": 0.14893481,
  "_source": {
    "name": "one three"
  }
}

フィールド内のタームの数が少ない方がスコアが高くなる。

explain API

下記のようにElasticSearch内部のスコア計算過程を確認できる*2

GET scoring/doc/1/_explain
{
  "query" : {
    "match" : {
      "name" : "one two"
    }
  }
}

{
  "_index": "scoring",
  "_type": "doc",
  "_id": "1",
  "matched": true,
  "explanation": {
    "value": 0.79143506,
    "description": "sum of:",
    "details": [
      {
        "value": 0.79143506,
        "description": "sum of:",
        "details": [
          {
            "value": 0.29786962,
            "description": "weight(name:one in 0) [PerFieldSimilarity], result of:",
            "details": [
              {
                "value": 0.29786962,
                "description": "score(doc=0,freq=1.0), product of:",
                "details": [
                  {
                    "value": 0.6134871,
                    "description": "queryWeight, product of:",
                    "details": [
                      {
                        "value": 0.7768564,
                        "description": "idf(docFreq=4, maxDocs=4)",
                        "details": []
                      },
                      {
                        "value": 0.7897047,
                        "description": "queryNorm",
                        "details": []
                      }
                    ]
                  },
                  {
                    "value": 0.48553526,
                    "description": "fieldWeight in 0, product of:",
                    "details": [
                      {
                        "value": 1,
                        "description": "tf(freq=1.0), with freq of:",
                        "details": [
                          {
                            "value": 1,
                            "description": "termFreq=1.0",
                            "details": []
                          }
                        ]
                      },
                      {
                        "value": 0.7768564,
                        "description": "idf(docFreq=4, maxDocs=4)",
                        "details": []
                      },
                      {
                        "value": 0.625,
                        "description": "fieldNorm(doc=0)",
                        "details": []
                      }
                    ]
                  }
                ]
              }
            ]
          },
// 途中まで

1番目のドキュメント("one two")のスコアは、

{
 0.79143506 = 0.29786962("one") + 0.49356544("two")
}

{
= (0.6134871 * 0.48553526) + (0.7897047 * 0.625)
}

のように分解される。 前半の {0.6134871 * 0.48553526} はさらに

{
 0.6134871 =  idf(docFreq=4, maxDocs=4) * queryNorm
}

{
= 0.7768564 * 0.7897047
}

{
0.48553526 = tf(freq=1.0) * idf(docFreq=4, maxDocs=4) * fieldNorm(doc=0)
}

{
= 1 * 0.7768564 * 0.625
}

になる。{idf}{queryNorm} は上の式の通り算出可能。

最後のfieldNormだけ計算が合わないが、理由は浮動小数点を限られたビット数でエンコードされているからのようだ*3

参考