embryo

エンジニアの備忘録

PWAを支える技術とPRPLパターンの実装

この記事はトレタ Advent Calendar 2017の11日目の記事です。

dev.toで最近話題になったPWA実装ですが、今日はそのPWA設計パターンの1つであるPRPLを実践するために必要な技術スタックとその実装方法についてまとめました。

PRPLパターンとは

Googleが提唱するPWAの設計パターンの1つです。

PRPL パターン  |  Web  |  Google Developers

  • (P)ush: HTTP/2 Pushを用いて初期表示に必要なリソースを配信します
  • (R)ender: 最小限の初期描画を行い、インタラクティブな状態にします
  • (P)re-cache: ServiceWorkerを用いて事前に他のルートのリソースをキャッシュします
  • (L)azy-load: ユーザー操作に合わせてオンデマンドにリソースの配信と生成を行います

これらの頭文字をとってPRPLと呼んでいるようです。

PRPLを支える技術

PRPLを実現するための重要な技術としてHTTP/2 Server PushServiceWorkerがあります。

HTTP/2 Server Push

従来のHTTP/1.1のリクエストでは

  • htmlファイルをリクエストする
  • htmlファイルを解析する
  • Javscript, cssなどのリソースが見つかったら読み込む

というステップで初期表示が行われていましたが、HTTP/2 Server Pushを用いることで1つのリクエストに対して複数のレスポンスを送信することが可能になります、つまり要求されたリソースに加えて、リソースを追加して送信することができるので一度のリクエストで初期の表示に必要なリソースを返却することが出来ます。

実装方法として後述する2つの方法があげられます。

ストリームを直接操作する方法

下記の例はnodejs+expressの実装例です。streamを操作し、レスポンスにリソースを追加しています。

gist.github.com

Linkヘッダを利用する方法

下記のようなLinkヘッダををレスポンスに追加することでServerPushのトリガーとなります。 厳密にはリソースヒントと呼ばれる仕様でH2O, nghttp2などではServerPushのトリガーとして扱っているようです。

link: <[url]>; rel=preload; as=[file type]

[url]にはリソースへのURLが、[file type]にはstyle, scriptなどのファイルタイプが入ります。

ServiceWorker

Service Workerはページ上で実行されるスクリプトとは別のスレッドでで別のスクリプトを実行することができる機能です。ネットワークプロキシとしてリクエストをコントロールしたりデータをキャッシュすることが可能です。

ライフサイクル

ServiceWorkerは登録→インストール→アクティベートの順に状態が遷移します。

登録

Service Workerスクリプトを登録します。<scope>を渡すことで特定のルート以下をコントロールすることを明示できます。

if ('serviceWorker' in navigator) {
  navigator.serviceWorker.register(‘/sw.js’, {scope: <scope>)
  .then(function(registration) {
    console.log(’Success registration’);
  })
  ;
}
インストール

登録が完了するとinstall状態へ移行します。install時に処理を登録した場合は下記のようにハンドリングできます。

self.addEventListener('install', function(event) {
  console.log(“Service worker is installed")
});
アクティベート

Workerに登録したjsの更新時、ServiceWorkerがすでにインストールされている場合はデータの不整合を防ぐために、Workerが更新可能な状態まで待つことになります(ページを閉じるなどした場合に更新可能になります)。そのため、コントロール可能な状態をハンドリングしたい場合はactivateイベントに処理を登録する必要があります。

不整合が起きないことが予めわかっている場合に、すぐにactivateな状態に移したい場合は

self.addEventListener(‘activate', function(event) {
     event.waitUntil(self.skipWaiting());
});

また、workerがコントロールするのは登録後に開かれたページなので、すぐさまページをコントロールしたい場合は

self.addEventListener(‘activate', function(event) {
    event.waitUntil(self.clients.claim());
});

のようにすることですぐにページのコントロールを開始することが出来ます。

キャッシュ戦略

Service Workerをキャシュに用いる場合、2つの方法があります。

  • Install時にキャッシュを更新する
  • オンデマンドにキャッシュを更新する
Install時にキャッシュを更新する

予めキャッシュするリソースを指定し、installイベント時にキャッシュを更新します。PreCacheを実現するためにはこの方法を用いるのが良さそうです。

var CACHE_NAME = 'cache-v1';
var urlsToCache = [
  '/',
  '/styles/main.css',
  '/script/main.js'
];

self.addEventListener('install', function(event) {
  event.waitUntil(
    caches.open(CACHE_NAME)
      .then(function(cache) {
        console.log('Opened cache');
        return cache.addAll(urlsToCache);
      })
  );
});
オンデマンドにキャッシュを更新する

fetchイベントを通してファイル単位でキャッシュを更新します。リクエストを逐次キャッシュすることが出来るため2回目のアクセスを高速化できます。streamは用途に応じて複製する必要があるため扱いに注意してください。

self.addEventListener('fetch', function(event) {
  event.respondWith(
    caches.match(event.request)

      .then(function(response) {
        if (response) {
          return response;

        }

          // キャッシュ用とリクエスト用が必要なのでclone
        var fetchRequest = event.request.clone();

        return fetch(fetchRequest).then(

          function(response) {
            // リクエストが成功しており、なおかつoriginからの要求であること
            if(!response || response.status !== 200 || response.type !== 'basic') {
              return response;

            }
            // キャッシュ用とブラウザに返却する用が必要なのでclone
            var responseToCache = response.clone();

            caches.open(CACHE_NAME)
              .then(function(cache) {
                cache.put(event.request, responseToCache);
              });

            return response;
          }
        );
      }
    )
  );
});

PRPLをReactで実装する

以下の一般的なフロントエンド技術スタックでPRPLを実装する方法を考えます。

  • react
  • react-router
  • webpack

Push

HTTP/2 Server Pushに対応した配信サーバーを構築します。

webpackを使用する場合はpreact-cliの実装を参考にするのが良さそうです。 preact-cliの実装ではビルド時にこちらのフォーマットでファイルを出力し、配信時にLinkヘッダを付加することでServerPushを実現しているようです。

https://github.com/GoogleChromeLabs/simplehttp2server#http2-push

PreCache

初期表示完了後に残りのルートに必要なファイルをServiceWorkerのinstall時にキャッシュします。Install時のキャッシュ方法に関しては前項で説明しましたが、

sw-precache-webpack-pluginを使用することでServiceWorker用のスクリプトをwebpackビルド時に自動で生成することが出来ます。キャッシュ対象としてwebpackでビルドしたリソースが自動で追加されますが、設定項目でカスタマイズが可能です。

生成されたservice-worker.jsをエントリポイントで登録します。

Lazy-Load

オンデマンドロードを実現するために、リソースの分割とロード方法について考えます。

webpackによるリソース分割

リソースを取得する際、極端な例として2つの方針が考えられます。

  • 1リクエストに対して1モジュールを返す方法
  • 1リクエストに対してバンドルされた1ファイルを返す方法

前者は必要なリソースのみを取得できますが、リクエストが多くなってしまうためリクエストのオーバーヘッドが大きくなります。 後者は1度のリクエストで済むためオーバーヘッドは小さくなりますが不要なファイルも読み込むことになります。

これに対してwebpackでは、その折衷案としてある程度のまとまり(chunk)にファイルを分割する機能が提供されています。Push, PreCacheを有効に使うためにアプリケーションのバンドルを適切に分割する必要があるため、アプリケーションのコア(AppShell)と各ルートのchunkに分割するのが良さそうです。

リソース読み込み時にrequire.ensureを呼び出すことでchunkの分割対象と見なしてくれるようになります。(webpack2以降ではDymanic Importもサポートされているようです)

ルーティング

遷移時に各ルートのリソースを取得するためにreact-routerのgetComponentを呼び出します。webpackの設定ファイルにてchunkFilenameを指定しておくことで、require.ensure で指定した名前でファイルが作成されます。

  • react-routerの設定
<Route
     path=“/list"
     getComponent={(location, callback) => {
         (require as any).ensure([], () => {
             callback(null, require("./List"))
          }, "List")
      }}
/>
  • wepackの設定
output: {
     path: outputPath,
     filename: "[name].js”,
     chunkFilename: "[name].js"
}

対応状況

ServiceWorkerに関してはまだ非対応ブラウザも多いですが、フォールバックが可能な設計になっているため、現段階で使用可能な技術です。あまりにキャッシュに頼った設計にしてしまうと、非対応ブラウザとのパフォーマンス差が大きくなってしまうため注意が必要です。

まとめ

PRPLパターンを実装する上で必要な技術スタックと設計についてまとめました。dev.toはPRPLライクな実装に加えてレンダリングのチューニングやInstantClick+SSRを利用した静的コンテンツキャッシュにより高速な遷移を実現しています。Instantly Fastを実現するためにはサービスの設計段階からパフォーマンスを考慮しておく必要がありそうです。

参考

PRPLパターン

HTTP/2

ServiceWorker

Golangの環境をつくった

goの開発環境を整えた際のメモです。

goenvでgoをインストール

golangのバージョンを管理するためにgoenvを導入しました。direnvと併用してプロジェクトごとに環境を分けることも可能ですが今回はgoenvのみをセットアップします。

GOPATHを設定する

goのワークスペースとなるGOPATHを設定します。デフォルトでは$HOME/goが設定されているようですが、go以外の作業もこちらで行う場合は他の名前にしておいた方が良さそうです。なぜgo以外の作業を考慮するかですが、後述するリポジトリ管理方法はgo開発に限らず有用であるためです。

ghq

goではgo getで依存ライブラリなどを取得するのが主流となっていますが、その場合GOPATH以下にgitのリポジトリがどんどん増えていくことになります。そこでリポジトリの管理を簡単にするためにghqを導入します。ghqはgo製のツールでgo getした時と同じ形でリポジトリを管理できます。デフォルトでは.ghq/以下で管理されているため管理するパスをGOPATHに合わせましょう。ghqの管理するパスを変更するには.gitconfigに以下のように設定を追加します。

[ghq]
     root = /Users/username/go/src

peco

ci上でテキストをインタラクティブにフィルタリングすることができます。前述のghqと連携させることで快適にリポジトリ間を行き来することができます。ghq listの結果をpecoに渡し、pecoで選択したリポジトリにcdするようにaliasを設定します。

alias g='cd $(ghq root)/$(ghq list | peco)'

エディタ

JetBrain製のGoLandを使用しています。IDE自体は割りと新しいのですがIntelliJプラットフォーム向けのPluginが使用できるため使用できるPluginの品質が高いのが魅力です。

余談ですが元々の名前はGogLandなので情報を検索する場合はGogLandで検索すると多少マシになるかもしれません。

GoLand: Capable and Ergonomic Go IDE by JetBrains

参考文献

DNSの仕組みと調査方法について

仕事で外部のエンジニアに依頼したドメイン移行が正しく動作していなかったため、良い機会と思いDNSについて調べました。

名前解決の方法

そもそも名前解決とは何かというと、ドメインIPアドレスを紐付けることです。手法として以下の2つが上げられます。

  • /etc/hostsに直接対応を記述する方法
  • /etc/resolve.confにDNSサーバーのIPアドレスを記述し、問い合わせる方法

今回はDNSサーバーによる名前解決について説明していきます。

DNSによる名前解決

ドメインツリーによる負荷分散

全世界に無数に存在するドメインの解決を一台のネームサーバーで担当するのは不可能です。そこでDNSでは下記のように、各階層に意味を持たせ、下位のドメインを管理させることで分散型の構造を構築しています。

f:id:sue71:20171121143038p:plain
ドメインツリー

キャッシュサーバーによる高速化

クライアントからDNSサーバーに対してドメインを問い合わせる場合、実際には直接情報(レコード)を保存しているサーバー(=コンテンツサーバー)に問い合わせるのではなく、それぞれのコンテンツサーバーとのやり取りを仲介するサーバー(=キャッシュサーバー)を介して行われます。

f:id:sue71:20171121152115p:plain
DNS解決の流れ

  1. クライアントからキャッシュサーバーへ問い合わせを開始する
  2. キャッシュサーバーがルートサーバーへ問い合わせる
  3. ルートサーバーからjpを管理するネームサーバーのアドレスが返却される
  4. jpを管理するネームサーバーに問い合わせる
  5. example.jpを管理するネームサーバーのアドレスが返却される
  6. example.jpを管理するネームサーバーへ問い合わせる
  7. example.jpのIPアドレス(Aレコード)が返却される

上図のようにルートサーバーから順に問い合わせていくのが基本的な流れですが、毎回この手順を踏むのでは速度面のロスがあるので、キャッシュサーバーは一度取得したレコードを一定期間保存し、キャッシュが存在している場合にはすぐさまクライアントに応答します。

f:id:sue71:20171121143044p:plain
キャッシュが存在している場合

キャッシュの生存期間としてTTLが用いられ、時間を超過すると再度権威サーバーへと問い合わせます。

プライマリ/セカンダリDNSによる冗長化

コンテンツサーバーは普通複数台存在します。プライマリ/セカンダリDNSと呼ばれ、プライマリDNSがなんらかの理由で応答しない場合にセカンダリDNSを参照します。セカンダリDNSはプライマリDNSのレコードをコピーして保持するため常に同期された状態になりますが、プライマリDNSのレコードを更新する際にシリアルナンバーを更新してセカンダリDNSに更新されていることを伝える必要があります。(異なった仕様のものもあるようです)

f:id:sue71:20171121143047p:plain
プライマリDNSとセカンダリDNS

digで名前解決してみる

digコマンドを使用して実際に名前解決してみます。nslookupコマンドでもIPアドレスを引くことは出来ますがdigコマンドの方がより詳細に情報を取得できます。 (他にもいくつか挙動が異なる点がありますが割愛します)

>>dig google.com

; <<>> DiG 9.8.3-P1 <<>> google.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 19537
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 4

;; QUESTION SECTION:
;google.com.               IN         A

;; ANSWER SECTION:
google.com.            186        IN         A          172.217.26.46

;; AUTHORITY SECTION:
google.com.            55214      IN         NS         ns3.google.com.
google.com.            55214      IN         NS         ns4.google.com.
google.com.            55214      IN         NS         ns2.google.com.
google.com.            55214      IN         NS         ns1.google.com.

;; ADDITIONAL SECTION:
ns1.google.com.        39695      IN         A          216.239.32.10
ns2.google.com.        39695      IN         A          216.239.34.10
ns3.google.com.        39695      IN         A          216.239.36.10
ns4.google.com.        39695      IN         A          216.239.38.10

;; Query time: 3 msec
;; SERVER: 192.168.2.1#53(192.168.2.1)
;; WHEN: Mon Nov  6 14:52:59 2017
;; MSG SIZE  rcvd: 180

各出力項目について

重要な出力について説明していきます。

status

名前解決の状態に関する項目です。上記出力ではNOERRORとなっているため、正常に名前解決が行われたことを意味します。 他にはNXDOMAINなどが表示されることがありますが、この場合は指定したドメインが存在しないことになります。

flags

応答の意味が表示されています。それぞれ下記の意味を示しています。上記応答はqr rd raとなっているため、サーバーからの応答で、なおかつキャッシュサーバーによる応答であり、キャッシュサーバーは再帰的問い合わせに対応している、ということがわかります。

  • aa: コンテンツサーバーからの応答であることを示します
  • qr: サーバーからの応答であることを示します。DNSでの名前解決では必ずこのフラグが付いています。
  • rd: 再帰的問い合わせの結果であることを示します
  • ra: 再帰的問い合わせが可能であることを示します

ANSWER SECTION

問い合わせに対するレスポンスになります。google.comのIPアドレスが得られている事がわかります。二列目の値が残りのTTLになります。このTTLが切れた場合に再度コンテンツサーバーに問い合わせることになります。

google.com.            186        IN         A          172.217.26.46

AUTHORITY SECTION

コンテンツサーバー(権威サーバー)のドメイン情報が表示されています。この中から1つが選択され、再帰的に問い合わせが行われます。

google.com.            55214      IN         NS         ns3.google.com.
google.com.            55214      IN         NS         ns4.google.com.
google.com.            55214      IN         NS         ns2.google.com.
google.com.            55214      IN         NS         ns1.google.com.

ADDITIONAL SECTION

付加情報が表示される項目です。ネームサーバーが返却された場合、ネームサーバーのIPアドレスなどが付加情報として返却されます。

ns1.google.com.        39695      IN         A          216.239.32.10
ns2.google.com.        39695      IN         A          216.239.34.10
ns3.google.com.        39695      IN         A          216.239.36.10
ns4.google.com.        39695      IN         A          216.239.38.10

digの使い方いろいろ

実際にどのような使い方があるのかを、今回調査に使用したものを中心に紹介します。

再帰的問い合わせ

通常digコマンドでは再帰的に問い合わせが行われていますが、+norecオプションを付加することで、たらい回す先のDNSサーバーを返すようになります。

>> dig google.com +norec

; <<>> DiG 9.8.3-P1 <<>> google.com +norec
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 42047
;; flags: qr ra; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 4

...

flagsからrdの項目が消えていることがわかります。

問い合わせるネームサーバーを指定する

@DNSサーバーアドレスを使用することで、ネームサーバーを直接指定して名前解決を行うことができます。またキャッシュサーバーではなくコンテンツサーバーを指定した場合、再帰的問い合わせを行うことはできないので、自身が管理するレコードのみを返すことになります。

>> dig google.com @ns1.google.com

; <<>> DiG 9.8.3-P1 <<>> google.com +norec @ns1.google.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 14958
;; flags: qr aa; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0

;; QUESTION SECTION:
;google.com.               IN         A

;; ANSWER SECTION:
google.com.            300        IN         A          172.217.26.46

;; Query time: 75 msec
;; SERVER: 216.239.32.10#53(216.239.32.10)
;; WHEN: Mon Nov 20 19:50:46 2017
;; MSG SIZE  rcvd: 44

flagsにaaと表示されているのがわかります。

再帰的問い合わせの状況を確認する

+traceオプションを付加することで、再帰的問い合わせの状況を追うことができます。浸透状況を疑う場合はこのコマンドを実行すると良さそうです。 下記出力ではルートサーバーから順に問い合わせている状態が確認できます。

>> dig google.com +trace

; <<>> DiG 9.8.3-P1 <<>> google.com +trace
;; global options: +cmd
.                  152273     IN         NS         f.root-servers.net.
.                  152273     IN         NS         l.root-servers.net.
.                  152273     IN         NS         e.root-servers.net.
.                  152273     IN         NS         j.root-servers.net.
.                  152273     IN         NS         d.root-servers.net.
.                  152273     IN         NS         b.root-servers.net.
.                  152273     IN         NS         g.root-servers.net.
.                  152273     IN         NS         i.root-servers.net.
.                  152273     IN         NS         h.root-servers.net.
.                  152273     IN         NS         c.root-servers.net.
.                  152273     IN         NS         a.root-servers.net.
.                  152273     IN         NS         k.root-servers.net.
.                  152273     IN         NS         m.root-servers.net.
;; Received 492 bytes from 192.168.2.1#53(192.168.2.1) in 10 ms

;; Truncated, retrying in TCP mode.
com.               172800     IN         NS         l.gtld-servers.net.
com.               172800     IN         NS         b.gtld-servers.net.
com.               172800     IN         NS         c.gtld-servers.net.
com.               172800     IN         NS         d.gtld-servers.net.
com.               172800     IN         NS         e.gtld-servers.net.
com.               172800     IN         NS         f.gtld-servers.net.
com.               172800     IN         NS         g.gtld-servers.net.
com.               172800     IN         NS         a.gtld-servers.net.
com.               172800     IN         NS         h.gtld-servers.net.
com.               172800     IN         NS         i.gtld-servers.net.
com.               172800     IN         NS         j.gtld-servers.net.
com.               172800     IN         NS         k.gtld-servers.net.
com.               172800     IN         NS         m.gtld-servers.net.
;; Received 824 bytes from 192.5.5.241#53(192.5.5.241) in 13 ms

google.com.            172800     IN         NS         ns2.google.com.
google.com.            172800     IN         NS         ns1.google.com.
google.com.            172800     IN         NS         ns3.google.com.
google.com.            172800     IN         NS         ns4.google.com.
;; Received 164 bytes from 192.54.112.30#53(192.54.112.30) in 152 ms

google.com.            300        IN         A          172.217.27.78
;; Received 44 bytes from 216.239.34.10#53(216.239.34.10) in 38 ms

ルートサーバーから順に問い合わせている様子がわかります。

プライマリDNSサーバーを確認する

soaをオプションとして付加することで、プライマリDNSサーバーを調べることができます。

>> dig google.com soa

; <<>> DiG 9.8.3-P1 <<>> google.com soa
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 47193
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 4

;; QUESTION SECTION:
;google.com.               IN         SOA

;; ANSWER SECTION:
google.com.            60         IN         SOA        ns1.google.com. dns-admin.google.com. 176366135 900 900 1800 60

;; AUTHORITY SECTION:
google.com.            151698     IN         NS         ns3.google.com.
google.com.            151698     IN         NS         ns4.google.com.
google.com.            151698     IN         NS         ns1.google.com.
google.com.            151698     IN         NS         ns2.google.com.

;; ADDITIONAL SECTION:
ns1.google.com.        324498     IN         A          216.239.32.10
ns2.google.com.        324498     IN         A          216.239.34.10
ns3.google.com.        324498     IN         A          216.239.36.10
ns4.google.com.        324498     IN         A          216.239.38.10

;; Query time: 37 msec
;; SERVER: 192.168.2.1#53(192.168.2.1)
;; WHEN: Tue Nov 21 11:48:38 2017
;; MSG SIZE  rcvd: 210

ns1.google.comがプライマリDNSサーバーであることがわかります。

TTLと浸透時間について

ドメインの移行が上手く行っていない際に「浸透時間が〜」という話を良く耳にしますが、基本的にはTTLを正しく設定していれば問題ないようです。 具体的には下記のような手順で移行することで、短時間でドメインの移行を完了することができます。

  1. 現在のTTLを確認する。例えば86400(24時間)と設定されていると仮定します。
  2. 移行前にTTLを300(5分)に設定します。
  3. 現在のTTLが86400となっているため、24時間以上の時間を置きます。
  4. キャッシュサーバーに保存されるTTLが300になっているはずなのでレコードの更新を行います。(TTLは長い時間を設定しても問題ありませんが、ミスが起きたときのために短い時間を設定しておくのが良いです)

今回の件で調査したこと

最後に今回問題を調査するにあたって、どのように問題解決に至ったかをメモしました。

キャッシュの確認

まず、キャッシュサーバーが古いドメインを返しているのではと思い、+traceオプションを使用して経路を確認しました。レコードが登録されているであろうネームサーバーまでは到達していましたが、最終的に到達するドメインが古いものになっている状態でした。しかしTTLには十分短い時間が設定されていたため、TTL設定の不備では無さそうです。

プライマリDNSの確認

次にsoaオプションを使用して到達している複数のネームサーバーの中からプライマリDNSを確認します。プライマリDNSがわかったので直接指定して確認したところ、そちらの方では新しいドメインに向いていました。そこでプライマリDNSとセカンダリDNSの同期が上手くなされていないのではと思い、担当者に調査をお願いした所、プライマリDNSのシリアルナンバーを更新していなかったことがわかりました。

まとめ

DNSの仕組みと問題が起きた際の調査方法について説明しました。DNSの仕組みを理解していればある程度問題が予測できそうです。

参考

LU分解を実装してみた

今日は連立方程式の解法などに用いられるLU分解についてです。

LU分解とは

とある正方行列Aに対して以下のような等式が成り立つ場合を考えます。

 Ax = B 

このとき A を L(下三角行列)とU(上三角行列)に分解すると三角化された行列の計算を2回行えば 解を得られることになるので計算が簡単になるというもの。

 A = LU

{ 
L = \begin{bmatrix} 
    1 & 0 & 0 & 0 \\\
    \vdots & 1 & 0 & 0 \\\ 
    \vdots & \vdots & 1 & 0 \\\ 
    l_{n1} & l_{n2} & \ldots & 1
\end{bmatrix}
}

{ 
U = \begin{bmatrix} 
    u_{11} & u_{12} & \ldots & u_{1n} \\\
    0 & u_{22} & \ldots & u_{2n} \\\ 
    0 & 0 & \ddots & \vdots \\\ 
    0 & 0 & 0 & u_{nn}
\end{bmatrix}
}

LU分解のメリット

では一体どう簡単になるかという話ですが

 Ax = B
 LUx = B
 Ly = B
 Ux = y

と変形すると結局三角行列の方程式を2つ計算すればxが求められることになります。例えば二元連立方程式の場合



\begin{bmatrix} 
    1 &  0 \\\ 
    l_{21} & 1 
\end{bmatrix}
\begin{bmatrix} 
    y_1 \\\ 
    y_2
\end{bmatrix}
=
\begin{bmatrix} 
    b_1 \\\ 
    b_2
\end{bmatrix}


 
\begin{bmatrix} 
    u_{11} & u_{12} \\\ 
    0 & u_{22}
\end{bmatrix}
\begin{bmatrix} 
    x_1 \\\ 
    x_2
\end{bmatrix}
=
\begin{bmatrix} 
    y_1 \\\ 
    y_2
\end{bmatrix}

となるため、自明なものから順に計算すれば簡単に求めることができます。

LU分解の過程について

 A = LU



\left(
    \begin{array}
      a_{11} & a_{12} & \ldots & a_{1n} \\
      a_{21} & a_{22} & \ldots & a_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      a_{n1} & a_{n2} & \ldots & a_{nn}
    \end{array}
\right)

=

\left(
    \begin{array}
      l_{11} & l_{12} & \ldots & l_{1n} \\
      l_{21} & l_{22} & \ldots & l_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      l_{n1} & l_{n2} & \ldots & l_{nn}
    \end{array}
\right)
\left(
    \begin{array}
      u_{11} & u_{12} & \ldots & u_{1n} \\
      u_{21} & u_{22} & \ldots & u_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      u_{n1} & u_{n2} & \ldots & u_{nn}
    \end{array}
\right)




\left(
    \begin{array}{c|ccc}
      a_{11} & a_{12} & \ldots & a_{1n} \\
\hline
      a_{21} & a_{22} & \ldots & a_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      a_{n1} & a_{n2} & \ldots & a_{nn}
    \end{array}
\right)
=
\left(
    \begin{array}{c|ccc}
      l_{11} & l_{12} & \ldots & l_{1n} \\
\hline
      l_{21} & l_{22} & \ldots & l_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      l_{n1} & l_{n2} & \ldots & l_{nn}
    \end{array}
\right)
\left(
    \begin{array}{c|ccc}
      u_{11} & u_{12} & \ldots & u_{1n} \\
\hline
      u_{21} & u_{22} & \ldots & u_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      u_{n1} & u_{n2} & \ldots & u_{nn}
    \end{array}
\right)


 
\begin{eqnarray}

\left( \begin{array}{c|c}
   a_{11} & a_1^T \\
   \hline
   a_1 & A_1 \\
\end{array}\right)

&=&

\left( \begin{array}{c|c}
   1 & 0 \\
   \hline
   l_{1} & L_1 \\
\end{array}\right)

\left( \begin{array}{c|c}
   u_{11} & u_1^T \\
   \hline
   0 & U_1 \\
\end{array}\right)
\\
&=&

\left( \begin{array}{c|c}
   u_{11} & u_1^T \\
   \hline
   l_1u_{11} & l_{1}u_1^T + L_1U_1 \\
\end{array}\right)

\end{eqnarray}


のように分解して計算すると、恒等式の関係より

 u_{11} = a_{11}
 u_1^T = a_1^T
 l_1 = a_1 / u_{11}
 A_1 = l_1u_1^T + L_1U_1

が成り立ちます。ここで  A_1 - l_{1}u_1^T を新たに Aとすることで、同様の操作を繰り返すことができます。つまりn次正方行列を仮定するとn回繰り返すことで全てLU成分が分かることになります。

gist.github.com

計算量について

LU分解までの処理はO(n3)になるため、一度だけ方程式を解く場合はガウスの消去法などと変わりありません。 ガウスの消去法は右辺も処理する必要がありますが、LU分解は一度分解した結果を使いまわせるのがメリットです。 右辺の値を変更して何度もLUを再利用する場合に利点がありそうです。

まとめ

LU分解を自前で実装する方法とメリットについて説明しました。 次回は単体法について説明したいと思います。

参考

Generatorと非同期処理

今日はes6の仕様であるGeneratorについてです。

es6でカスタムイテレータを作る (Iterator, Iterable, Generator) - embryo

で簡単に紹介しましたが、今回はGeneratorで非同期処理を扱ってみたいと思います。

co で非同期処理

GitHub - tj/co: The ultimate generator based flow-control goodness for nodejs (supports thunks, promises, etc)

coとはGeneratorを利用して非同期処理を同期的に記述することを目的としたライブラリです。 下記のように一連の非同期処理を同期的に実行できるため、処理をシンプルに記述できる他、同一スコープ内で非同期処理の結果を共有することも可能になります。

function asyncTask(value) {
     return new Promise(resolve => {
         setTimeout(() => {
              resolve(value);
         }, 1000)
     });
}

co(function *() {
     let result = yield asyncTask(100)
     console.log(result);
})

今回はこの実装を参考にしつつ、簡易な方法で実装していきます。

普通にGeneratorを使う

まずGeneratorを素直に使用する方法です。Generatorはnextを持っているため、このnextを非同期処理の完了時に呼び出すことで 非同期処理を順次実行することができそうです。

gist.github.com

この場合Generatorを処理の外で実行する必要がある他、Generatorを仕様側が知っている必要があります。そこで次の実装ではGeneratorを意識せずとも実行できるように書いてみます。

Generatorを内部で実行する

gist.github.com

Generatorを内部で実行する方法です。Generatorの引数にcallbackを引数として渡しており、実行側では任意のタイミングでcallbackを実行すればよいため、generatorを意識せずに使用できます。しかしこの場合仕様側はコールバックを順次呼びだす必要があるため、本質的には非同期処理的な書き方と言えます。

Promiseを使用する

gist.github.com

iteratorのresult.doneがtrueを返すまで、PromiseのonFullfilledが呼ばれる度にgenerator#nextを再帰的に呼び出します。仕様側はGeneratorやコールバックを意識すること無く、かつ同期的に非同期処理を実行することが出来るようになりました。 前述したcoも仕組みとしては大体同じです。(coではエラーハンドリングなども考慮されていますが今回は説明のため簡易の実装にとどめています)

おまけ

ちなみに現在仕様策定中の async, await を用いれば coのようなライブラリに頼らずとも標準で上記のような処理を書くことが出来ます。

https://tc39.github.io/ecmascript-asyncawait/

async function () {
     console.log(await new Promise().resolve(100));
     console.log(await new Promise().resolve(200));
     console.log(“complete”);
}

/*
100
200
complete
*/

参考

es6でカスタムイテレータを作る (Iterator, Iterable, Generator)

今日はes6の仕様であるIteratorIterableについてです。仕様を調べつつ実装して挙動を確かめていきます。

Iterator

一連の処理中において現在の処理位置を把握しつつ、コレクション中の項目へ一つずつアクセスする方法を指します。es6においては下記のnextメソッドを実装したものを指します。

※実際に下記のようなIteratorクラスが定義されているわけではありません。

class Iterator {
     next(): { done: boolean, value: any }
}

例えば以下のような実装はiteratorになります。

let iterator = {}
iterator.next = () => {
     return { done: false, value: 1 }
}

console.log(iterator.next().value) // 1
  • doneIteratorが完了したかを返す真偽値
  • valueIteratorから取り出した値

であり、donetrueで返ってくる場合、valueは省略されます。

Iterable

iteratorプロトコルとは別にiterableプロトコルというプロトコルが定義されています。iterableプロトコルを実装したオブジェクトはfor … of文が使用可能になります。

for … of 文はパラメータを列挙するオペレータで以下のように使用できます。

let iterable = [1, 2, 3]
for (item of iterable) {
     console.log(item)
}

// 1
// 2
// 3

具体的には下記の[Symbol.Iterator]メソッドを実装したものを指します。また返却値は前述したIteratorプロトコルになります。

class Iterable {
     [Symbol.Iterator](): Iterator
}

例えば以下のような実装はIterableになります。

let iterable = {}
iterable[Symbol.iterator] => {
     return next() => {
          return { done: false, value: 1 }
     }
}

Linked List構造のIterableを作る

Iterableプロトコルを実装することで、ビルトインのiterable以外のものを自前で実装可能であることがわかりました。 そこでLinkedListの構造を持ったIterableオブジェクトを作って試していきます。LinkedListの実装は下記に公開しています。

LinkedList.js · GitHub

class IterableLinkedList extends LinkedList {

  [Symbol.iterator]() {

    let node = this.head;

    return {

      next: () => {

        if (!node) {
          return {
            done: true
          };
        }

        let value = node.value;

        node = node.next;

        return {
          value: value,
          done: false
        };

      }

    };

  }

}

自身でカスタムイテレータを作る場合、やはり内部のコードは煩雑になってしまいますね。またIterable, Iteratorプロトコルを正しく理解していなければなりません。そこで次は同じくes6の仕様であるGeneratorを使って同じものを実装してみます。

Generatorを使用した実装

Generator関数はIteratorプロトコルに準拠しているため、Generator関数を用いることでよりシンプルにIterableを実装することが可能になります。メソッドに定義する場合は関数名の先頭に*をつけることでGenerator関数が私用可能になります。

class IterableLinkedList extends LinkedList {

    * [Symbol.iterator]() {

      let node = this.head;

      while (node) {
        yield node.value;
        node = node.next;
      }

    }

}

Generatorを使用することでnextメソッドの定義や、doneの制御などが不要になり、シンプルに記述することが出来ました。

参考

React+Typescriptでコンポーネント公開用のBoilerplateを作った

今日はReact製のコンポーネントを外部公開するための雛形を作成したのでその紹介です。 ソースは以下。

github.com

構成

Typescript

型が欲しいのでTypescriptを使用しています。普段も大体Typescriptで書いています。

Jest

単なるコンポーネントのテストが目的なのでシンプルなパッケージ構成で簡単にテストできる jest を使用しています。

Typescriptを設定する

テストも型安全に書きたいのでts-loaderを使用しています。package.jsonに以下の設定を追記します。

 "jest": {
    "moduleFileExtensions": [
      "ts",
      "tsx",
      "js"
    ],
    "transform": {
      "\\.(ts|tsx)$": "<rootDir>/node_modules/ts-jest/preprocessor.js"
    },
    "testRegex": "/__spec__/.*\\.(ts|tsx|js)$"
  }

レンダリング結果をテスト

Componentのレンダリング結果をテストするためにairbnb製の enzyme を使用しています React.TestUtilsでも問題ありませんがjest公式で説明されているためこちらを使用します。

GitHub - airbnb/enzyme: JavaScript Testing utilities for React

import Component from "../Component";
import * as React from "react";
import * as Enzyme from "enzyme";

describe("Component", () => {

  it("content", () => {

    // Render a component
    const component = Enzyme.shallow(<Component />);
    expect(component.text()).toEqual("Awesome component");

 });

});

Storybook

開発中の動作確認の他、StyleGuide生成のために storybook を使用しています。 他にも style-guidist, catalog など選定に上がりましたが、フレームワークとしてのルールやメンテの容易さから storybook を選定しました。

Typescriptを設定する

公式の説明通りにセットアップを済ませると、.storybook以下にファイルが生成されるのでカスタマイズしたい場合はファイルを編集します。

.storybook
├── config.js
└── webpack.config.js

私はes6で設定を記述したいのでwebpack.config.babel.jsを作成し、webpack.config.jsから読み込んでいます。実際の設定は以下のようになります。今回はts-loaderを追加し、Typescriptを使用できるようにしています。

import path from "path";
import genDefaultConfig from "@storybook/react/dist/server/config/defaults/webpack.config.js";

module.exports = function(baseConfig, env) {
  const config = genDefaultConfig(baseConfig, env);

  config.resolve.extensions.push(".ts", ".tsx");

  config.module.rules.push({
    test: /\.(ts|tsx)$/,
    include: [/stories/, /src/],
    loader: require.resolve("ts-loader")
  });

  return config;
};

Storyファイルを書く

stories配下にファイルを配置して、実際のデモを記述します。

import * as React from "react";

import { storiesOf } from "@storybook/react";
import { Component } from "../src/Component";

storiesOf("Components", module)
  .add("Awesome component", () => <Component />)

Storyファイルを読み込む

.storybook/config.jsを編集してファイルを追加します。UIや設定をカスタマイズしたい場合はオプションを設定します。

import { configure } from "@storybook/react";

const loadStories = () => {
  require("../stories/index.tsx");
}

configure(loadStories, module);

あとはnpm scriptにstorybookが追加されているので実行してブラウザで確認します。

参考