野次馬エンジニア道

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

Android アプリ設計パターン入門 を読む

たまにAndroidを触るぐらいでアプリ開発からは完全に遠ざかってしまって久しい。

Android アプリ設計パターン入門

Android アプリ設計パターン入門

  • 著者:日高 正博,小西裕介,藤原聖,吉岡 毅,今井 智章,
  • 製本版,電子版
  • PEAKSで購入する

AndroidStudioを落としてきて起動したぐらいで「そもそもどうやってアプリを作るのがよいのだろうか」「教えて貰える機会もないしなー」と思っていた矢先にたまたま知った本。 バリバリ書いているエンジニアの人にもそうでない人にもオススメの内容。以下感想。

MVVM (Model-View-Model View)、MVP (Model-View-Presenter)

本書はまず背景となる知識や歴史を振り返った後に、下記のTODOアプリを詳細に見ていくところから始まる(画像は全て下記リポジトリから)。

https://github.com/googlesamples/android-architecture/wiki/images/mvvm-databinding.png

https://github.com/googlesamples/android-architecture/wiki/images/mvp.png

読み進めていく上では、DIの知識が必須。Dependency Injectionと聞いて個人的に思い浮かぶのがこの動画。基本的には大規模なソースコード上でのテストの話なのだが*1その前提としてDIはテスタブルにしておくために必要な書き方となる。

f:id:notta55:20180402233338p:plain

DIをアプリのインフラに導入したことで、単体テストが容易になり品質や開発スピードにも寄与しているということが繰り返し主張されている。

差分開発の問題, Daggar2とRxJavaの導入

メルカリのUSアプリのリニューアル*2を事例にチームが直面した問題を惜しみなく紹介している。

チームの拡大とコードベースの肥大化によるメンテナンスの困難さをアーキテクチャや実装的な問題として捉えて分析。具体的な人員の数も克明に書かれていて相当生々しい。。。が非常に読み応えあり。

その解決方法としてDaggar2とRxJavaを導入して得られた効果は

  • 非同期処理がRxJavaにより統一される、RxJavaはテストを書きやすい
  • Daggar2によりComponentとモジュールから機能全体の依存関係をチームメンバーに分かりやすくシェアできる

Fluxアーキテクチャ、ReactNative

FluxなんかはWebでReactを使って開発している人たちの共通理解のようだが、それをAndroidに当てはめるとどのようになるかを紹介。

そしてReactNativeとNativeのハイブリッドアプリの取り組みについて紹介。「3年間運用されたアプリを3ヶ月で書き直すには?」から着想し、採用の理由はシンプルで、「Web開発者がNative開発に参画できる」「マルチプラットフォーム開発ができる」。

このぐらいまでは想像がつくが「プレイストアを介さずにOn The Air配信が可能」というところまで到達しているのが本当に凄い。また、どんな画面がNative向きでどんな画面が不向きなのか、しっかりとチームのリソースやスキル、中身までを知った上で使いこなしているから素晴らしい。

そして最後の章でAndroid Architecture Componentsのモジュールとここまで紹介してきた内容との対応を紹介。

おしまいに

「新しいから使う」「便利だから使う」ではなくて、レガシーのコードに対峙しながら問題点を意識的に探り、プロダクトとして必要な品質を限られたリソースで作り上げる。そのために最新の設計やライブラリを駆使していかにして具現化していくか、その土台となるようなアーキテクチャを泥臭い実例を交えて紹介している貴重な本だった。

*1:かなり古い動画ですが、Facebookが過去どのようにAndroidをテストしてきたかを紹介していてオススメ。自分の知識も古い。。。

*2:http://tech.mercari.com/entry/2017/07/19/123443

Google Home + Actions SDKでMediaResponseを使ったMP3再生

f:id:notta55:20180325155524j:plain

先日専用のマウントも購入したGoogle Home Mini。開発者向けのサイトを眺めているとMediaResponseを発見。独自に音楽再生ができそうなので早速試してみる。上手くいくとこのような画面になるはず。

f:id:notta55:20180325180714p:plain:w200

これはAssistantの画面だがGoogle Homeでも動作する。

プロジェクトの作成

選択肢が三つあるので、Action SDKを選択。適当に名前をつける。

f:id:notta55:20180325153414p:plain

アクションの作成

gactionのバイナリをとってきて

./gactions init

action.jsonが生成されるので編集。

  • アプリの終了のためにactions.intent.CANCEL *1もいれてしまう。
  • https://your_firebase_domain/fullfilmentのところは次に作成。
{
  "actions": [
    {
      "description": "Media Response Sample",
      "name": "MAIN",
      "fulfillment": {
        "conversationName": "MediaResponseSample"
      },
      "intent": {
        "name": "actions.intent.MAIN"
      }
    }
  ],
  "conversations": {
    "MediaResponseSample": {
      "name": "MediaResponseSample",
      "url": "https://your_firebase_domain/fullfilment",
      "fulfillmentApiVersion": 2,
      "inDialogIntents": [
        {
          "name": "actions.intent.CANCEL"
        }
      ]
    }
  },
  "locale": "ja"
}

Fulfillmentのエンドポイント作成

簡単なのでFirebaseを使う。

npm install -g firebase-tools #CLIをいれる
firebase login #ログイン

functionの雛形を作ってしまう

firebase init functions
cd functions
npm install 

github.comを追加

npm install actions-on-google --save
vi index.js

Actionの中身

さっそく動作を書いてみる

const functions = require('firebase-functions');
const ActionsSdkApp = require('actions-on-google').ActionsSdkApp;

exports.fullfilment = functions.https.onRequest( (req,res) => {

    const app = new ActionsSdkApp({request: req, response: res});

    function responseHandler (app) {
        let intent = app.getIntent();
        switch (intent) {
            case app.StandardIntents.MAIN:
                app.ask('プログラム名を教えてください。');
                break;
            case app.StandardIntents.TEXT: {
                let text = app.getArgument('text');
                const mediaResponse = app.buildMediaResponse()
                mediaResponse.addMediaObjects([
                    app.buildMediaObject("Test MP3", "https://your_test_content/test.mp3")
                        .setDescription("Spoken Word(interviews, reading, etc)")
                        .setImage("https://your_test_content/program.png", app.Media.ImageType.LARGE)
                ]);
                const richResponse =
                    app.buildRichResponse()
                        .addSimpleResponse(text + 'が見つかりました。')
                        .addMediaResponse(mediaResponse)
                        .addSuggestions(["前の回を聞く"]);
                app.ask(richResponse);
                break;
            }
            case app.StandardIntents.CANCEL:
                app.tell('終了します。');
                break;
            case app.StandardIntents.MEDIA_STATUS: {
                app.tell('再生が終わりました。');
                break;
            }
        }
    }
    app.handleRequest(responseHandler);
});

デプロイとアクションの更新

firebase deploy --only functions

実行後に表示されるURLをaction.jsonに入れて

./gactions update --action_package action.json --project PROJECT_ID

後は、Action On GoogleのコンソールからTEST DRAFTをすればOK。App Informationは適当に設定。今回は「マイラジオ」という名前に設定。

動作確認

Action On GoogleのコンソールのSimulatorで動作確認。

f:id:notta55:20180325154021p:plain:w400

Google Home + Raspberry PiでHome Automation入門

昨年の半額セールで購入したGoogle Home Mini。まずは家のリビングのTVとエアコンと照明をオンオフできるような機能を自分で作ってみる*1

準備

赤外線の学習リモコンの類やIoT対応した照明など、機器は色々あるが、レビューを見て評判のよさそうな以下をセレクト。飽きたら別の用途に使ってもよいので汎用性の高そうなRaspberry Pi 3 の Model Bを購入。OSはRaspbianにして付属のマニュアルに沿ってインストール。インストールにはUSBとマウスが必要。

ビット・トレード・ワン USB赤外線リモコンアドバンス ADIR01P

ビット・トレード・ワン USB赤外線リモコンアドバンス ADIR01P

とりあえず全部つなぐ

赤外線モジュールはUSBのmini-USBという一昔前の端子であることに注意。大きい100円ショップで辛うじて売られているものを救出して今回は利用。

f:id:notta55:20180105222934j:plain

コマンドラインツールのビルド

の記事を参考にする。公式にサポートされているのはWindows環境用のC#の実装のようだが、それをlinux上で動作するように ポートしている模様。下記からダウンロードしてセルフビルドしてmake installしておく。

そのままだと実行にはroot権限が必要となるため追加で設定*2。刺した状態でlsusbをしてVendorとidProductをメモして

#sudo vi /etc/udev/rules.d/bittrade.rules
SUBSYSTEM=="usb", ATTRS{idVendor}=="22ea", ATTRS{idProduct}=="003a", MODE="0666"

こんな感じで記述してsudo udevadm control --reload-rulesで設定を読み込み。

IFTTTの設定

ifttt.com

こちらも記事が多く見つかるが、単純なon/offであれば、"Say a phrase with a text ingredient"を選んでWebHookを設定すればOK。 f:id:notta55:20180105231409p:plain

Dynamic DNSの設定

WebHookを設定する際に環境的にグローバルIPとルータのDMZの設定などをする必要がある場合は追加で設定。 Raspberry Pi 3でもDDClientが利用可能*3。 自分の環境ではeth0はローカルのIPになってしまうのでグローバルのIPを設定。

# sudo vi /etc/ddclient.conf
#use=if, if=wlan0
use=web, web=checkip.dyndns.org
ssl=yes

/etc/init.d/ddclient restartで正しく更新されるかテスト。

WebHookの実装

学習したリモコンデータはコマンドラインツールでローカルにファイルで出力されるのでそれをそのまま使ってしまう(手抜き)。 ポイントとしては、IFTTTで設定されたTextの処理。

  • スペースが入っている場合があるのでtrimしてしまう

  • シノニム的な言い換え('電気','ライト','明かり')に備えてマップを持ってしまう

var fs = require('fs');
var express = require("express");
var bodyParser = require("body-parser");
var exec = require('child_process').exec;
var app = express();

app.use(bodyParser.urlencoded({ extended: true }));
app.use(bodyParser.json());

var server = app.listen(3000, function(){
    console.log("Node.js is listening to PORT:" + server.address().port);
});

var targetNameMap = {
    'light' : ['電気','ライト','明かり'],
    'tv' : ['TV','テレビ'],
    'aircon' : ['エアコン','暖房','冷房']
};

function execBTO(path){
    exec('/usr/local/bin/bto_advanced_USBIR_cmd -d `cat '+__dirname+'/'+path+'`',
        function (error, stdout, stderr) {
            if(stdout){
                console.log('stdout: ' + stdout);
            }
            if(stderr){
                console.log('stderr: ' + stderr);
            }
            if (error !== null) {
                console.log('Exec error: ' + error);
            }
    });
}

function processAction(target, cmd){
    Object.keys(targetNameMap).forEach(function(target_){
        if( targetNameMap[target_].indexOf(target) === -1 && target_ !== target){
            return;
        }
        var path = 'data/'+target_+'/'+cmd;
        fs.access(__dirname+'/'+path, (fs.constants || fs).R_OK, function(error){
            if (error) {
                if (error.code === "ENOENT") {
                    console.log('ENOENT error '+__dirname+'/'+path);
                }
            }
            execBTO(path);
        });
    });
}

app.post("/api/action", function(req, res, next){
    if( !req.body.target || !req.body.cmd ) {
        res.json({status:'NG'});
        return;
    }
    processAction(req.body.target.trim(), req.body.cmd);
    res.json({status:'OK'});
});

あとはNodejsの起動スクリプトに入れてforeverを使って常駐化すると良い。

動作確認

  • OK Google リビングのエアコンをつけて
  • OK Google リビングのTVをつけて
  • OK Google リビングの電気をつけて

といった感じで赤外線モジュール経由でコントロールが可能。

所感

一通り動作したので、Raspberry Pi Zero Wへ乗せ変えて暫く運用予定*4。が、やはりインテリア的な見た目やメンテナンスを考えると

Nature Remo

Nature Remo

が欲しい。室内に置くものなので機能観点だけでは割り切れないということなのだろう。

*1:本当はNature Remoが欲しい

*2:c++ - libusb cannot open USB device, permission isse. NetBeans/Ubuntu - Stack Overflow

*3:Dynamic DNSの例 https://support.google.com/domains/answer/6147083?hl=ja

*4:抽選らしいので当たるといいですが

モックインタビューのサービスGainloのブログの問題を1日1問

gainloというサービスを紹介しているブログを発見。

このモックインタビューのサービスは有料らしいが、ブログも中々読み応えがある。毎日一問ずつ解いてみたのでその記録を。

blog.gainlo.co まずは愚直に解く。この"Sub"というのがポイント。つまり複数のウィンドウに切って処理するので 「どこまで切るか」「どこから切るか」で何回もforループを書く必要があるが、そこをウィンドウをスライドするイメージで計算量を減らす工夫をするテクニックを解説している。

vector<vector<int>> getSubArray(vector<int> num, int sum){
    vector<vector<int>> ret;
    int i = 0;
    int j = 0;
    int s = num[0];
    while( i < num.size() && j < num.size()) {
        if( i!=j ){
            s+=num[j];
        }
        if ( s > sum ){
            s -= num[i];
            i++;
        }
        if( s == sum ){
            ret.push_back(getRange(num,i,j));
            s -= num[i];
            i++;
        }
        j++;
    }
    return ret;
}

もしくは動的計画法でメモ化を使ったやり方。

void getSubArrayDP( vector<vector<int>>& result, vector<int> sub, vector<int> num, int sum, int remaining, int i ){

    if( remaining == 0 ) {
        auto it = find(result.begin(),result.end(),sub);
        if(it == result.end())
            result.push_back(sub);
        return;
    }

    if( i == num.size() || remaining < 0 ) return;

    sub.push_back(num[i]);
    getSubArrayDP(result, sub, num, sum, remaining - num[i], i+1);

    getSubArrayDP(result, vector<int>(), num, sum, sum, i+1);

    return;
}

続いてアナグラムWikipediaによると

blog.gainlo.co

なんだ、一旦並べ替えて数えるだけか。

vector<vector<string>>  getAnagramGroup( vector<string> input ){
    vector<vector<string>> ret;
    unordered_map<string,vector<string>> anagramMap;

    for( string s : input ){
        string key = s;
        sort(key.begin(),key.end());
        auto it = anagramMap.find(key);
        if( it != anagramMap.end()){
            it->second.push_back(s);
        } else {
            anagramMap.insert(make_pair(key,vector<string>{s}));
        }
    }

    for( auto it = anagramMap.begin(); it != anagramMap.end(); ++it) {
        if(it->second.size() > 1)
            ret.push_back(it->second);
    }
    return ret;
}

blog.gainlo.co

いわゆる最小の編集距離を求める問題。と聞くと難しそうだが前回紹介した動的計画法がそのまま使える。 積み上げていく感じをイメージするとわかりやすい。

int Solution::minDistance(string word1, string word2) {
    vector<vector<int>> distance(word1.length() + 1, vector<int>(word2.length() + 1, 0));
    for (int i = 0; i < distance.size(); i++) {
        for (int j = 0; j < distance[0].size(); j++) {
            if (i == 0)
                distance[i][j] = j;
            else if (j == 0)
                distance[i][j] = i;
        }
    }

    for (int i = 1; i < distance.size(); i++) {
        for (int j = 1; j < distance[0].size(); j++) {
            if (word1[i - 1] == word2[j - 1])
                distance[i][j] = distance[i - 1][j - 1];
            else
                distance[i][j] = 1 + min(distance[i - 1][j - 1], min(distance[i - 1][j], distance[i][j - 1]));
        }
    }
    return distance[word1.length()][word2.length()];    
}

blog.gainlo.co 続いて木の問題。ブログでも書かれているStackを使ったDFSの走査を試しに書いてみる。

struct TreeNode2 {
    TreeNode2* left;
    TreeNode2* right;
    string value;
    bool visited;
    TreeNode2() : left(NULL),right(NULL),value(""),visited(false){}
};

void printDFS(TreeNode2 *root){
    if(root == NULL) return;

    stack<pair<TreeNode2*,string>> s;
    s.push(make_pair(root,""));

    while(!s.empty()){
        TreeNode2 *n = s.top().first;
        string     p = s.top().second;
        p += n->value;
        s.pop();
        n->visited = true;
        if(n->right && !n->right->visited){

            s.push(make_pair(n->right,p+"->"));
        }
        if(n->left && !n->left->visited){
            s.push(make_pair(n->left,p+"->"));
        }
        if(n->left == NULL && n->right ==NULL ){
            cout << p << endl;
        }
    }
}

blog.gainlo.co 今度はリストの並び替え。

struct LinkedList {
    LinkedList *next;
    LinkedList *down;
    int        value;
    LinkedList(int v) : next(NULL),down(NULL),value(v){}
};

void flattenList(vector<vector<LinkedList*>>& result, LinkedList *root, int level){
    if(root==NULL) return;
    queue<pair<LinkedList*,int>> q;
    q.push(make_pair(root,0));

    while(!q.empty()){
        LinkedList* n = q.front().first;
        int level = q.front().second;
        q.pop();
        result[level].push_back(n);
        if(n->next) q.push(make_pair(n->next,level));
        if(n->down) q.push(make_pair(n->down,level+1));
    }
}

blog.gainlo.co これも最初に紹介したスライドウィンドウに似てる。

string findLongestK2( int K, string input ){
    string maxStr = "";
    int    maxLen = 0;
    int    left   = 0;
    int    right  = 0;
    unordered_set<char> h;
    while(left < input.size() && right < input.size()){
        h.insert(input[right]);
        if( h.size() == K ) {
            int len = right-left+1;
            if(  len > maxLen ){
                maxLen = len;
                maxStr = input.substr(left, len);
            }
        }
        else if( h.size() > K ){
            char c = input[left];
            while(input[left]==c){
                left++;
            }
            h.erase(c);
        }
        right++;
    }
    return maxStr;
}

blog.gainlo.co グラフの二つのノードから共通の親を返すものを見つけるもの。

bool findNode(TreeNode *root, TreeNode *target){
    if( root == NULL) return false;
    if( root->val == target->val) return true;
    return findNode(root->left, target) || findNode(root->right, target);
}

TreeNode* getCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){
    if( root == NULL || root == p || root == q ){
        return root;
    };
    bool pIsLeft = findNode(root->left, p);
    bool qIsLeft = findNode(root->left, q);
    if(pIsLeft != qIsLeft){
        return root;
    }
    TreeNode *child = pIsLeft ? root->left : root->right;
    return getCommonAncestor(child, p, q);
}


int getLCA(TreeNode *root, TreeNode *p, TreeNode *q){
    if( !findNode(root,p) || !findNode(root,q) ){
        return -1;
    }
    TreeNode* node = getCommonAncestor(root, p, q);
    return  (node) ? node->val : -1;
}

blog.gainlo.co これも有名な問題のようだ。

int countMaximumMeetingRoom(vector<pair<int,int>> interval){
    struct Event{
        int  time;
        bool in;
        Event(): time(-1),in(false){}
        bool operator< ( const Event& right) const {
            return time < right.time;
        }
    };
    vector<Event> ev(interval.size()*2);
    for( int i = 0; i < interval.size(); i++ ){
        ev[2*i].time   = interval[i].first;
        ev[2*i].in     = true;
        ev[2*i+1].time = interval[i].second;
        ev[2*i+1].in = false;

    }
    sort(ev.begin(),ev.end());
    int count = 0;
    int maxCount = 0;
    for( int i = 0; i < ev.size(); i++ ){
        count += ev[i].in ? 1 : -1;
        maxCount = max(count, maxCount);
    }
    return maxCount;
}

blog.gainlo.co

string getLongestSubStr2(string s){
    string maxStr = "";
    unordered_set<char> dup;
    int start = 0;
    int end = 0;
    while(start < s.size() && end < s.size()){
        if(dup.find(s[end])==dup.end()){
            dup.insert(s[end]);
            string sub = s.substr(start,(end-start)+1);
            if(sub.size()>maxStr.size()){
                maxStr = sub;
            }
            end++;
        } else {
            while(start<end){
                dup.erase(dup.find(s[start]));
                if(s[start]==s[end]){
                    start++;
                    break;
                }
                start++;
            }
        }
    }
    return maxStr;
}

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

アルゴリズム図鑑 絵で見てわかる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は「マイクロサービスへの道は、注意深く進まないと痛みを伴う罠がある」というコメントを寄せている。それでも構築できれば他を圧倒する優位性があるのだと思う。本書によるとその道のりはまさに旅。先人の知恵が凝縮されたそのガイド本として読み応えがある本だった。