Send data notification to Android app with Cloud Functions for Firebase

Androidアプリがフォアグラウンドでもバックグラウンドでも、通知を受け取った後にそれを表示するかどうかをアプリ内で判断させたいときは Firebase の data message を送る必要がある。

FirebaseコンソールからはNotification Composerを使って、notification messageを送ることができる。notification messageはアプリケーションがバックグラウンドのとき、システムのトレイに入るため、アプリケーション側で表示・非表示の判断をすることができない。

data messageを送るには、独自サーバーで動いているアプリケーションかCloud Functions for Firebaseを実装しなければならない。

背景

notification messageでは要件を満たせなかった。

  • 毎日18時に、当日(深夜0時から)まだアプリを開いていないユーザー送りたい
  • ユーザーが当日ログインしたかどうかは、端末のDBに保存している
  • 端末のtimezoneが日本ではない場合は通知を表示しない
  • 災害などの緊急時はユーザーがアプリを開かなくても通知を止められる
  • 通知が届く時間は、18時ちょうどである必要はない

必要なもの

  1. Androidアプリ
  2. Firebaseプロジェクト
  3. Cloud Functions for Firebaseプロジェクト

それぞれの役割

Androidアプリ
  • FCMトークンを生成し、Fire Storeに保存
  • data messageを受け取り、通知を表示する
Firebaseプロジェクト
Cloud Functionプロジェクト
  • Fire Storeに保存されたFCMトークンを取り出す
  • httpリクエストをトリガーにして、data messageを送る
  • 有料だがcronで時間をトリガーにして、送ることもできる(Schedule functions  |  Firebase)

1. Firebaseプロジェクトを作る

Add Firebase to your Android project  |  Firebase を参考にプロジェクトを作る。

2. Cloud Functions for Firebaseを作る

時間がある人は Codelab の Cloud Functions for Firebase がおすすめ。

Firebase CLIを使ってファイルを生成する。

Get started: write and deploy your first functions  |  Firebase を参考にする。

npm -g install firebase-tools
firebase login
firebase init functions

途中でFirebaseプロジェクトと言語(JavaScript | TypeScript)を選ぶ。

functioins/index.jsを編集する。

A cloud function which sends data notification to ...

ファイルを保存したら、Firebase CLIを使ってデプロイする。

firebase deploy --only functions

Deployされたら、curlコマンドで叩いてみよう。

curl https://us-central1-MY_PROJECT.cloudfunctions.net/sendNotificationApi

DeployするとFirebaseコンソール の Functionsに登録される。

f:id:bambinya:20190430182227p:plain

3. Androidアプリの作成

Set up a Firebase Cloud Messaging client app on Android  |  Firebase を手順通りに実装する。

生成されたFCMトークンをFirestoreに保存する方法は

Get started with Cloud Firestore  |  Firebase を参考にした。

上で紹介したindex.jsでとりあえず動かしたいときはコピペして使ってください。

private fun sendRegistrationToServer(token: String?) {
  val tokenMap : HashMap<String, String> = HashMap()
  tokenMap["fcmTokens"] = token?: ""
  val db: FirebaseFirestore = FirebaseFirestore.getInstance()
  db.collection("fcmTokens")
    .document(token?:"")
    .set(tokenMap)
    .addOnSuccessListener { Log.d(tag, "token was added: ${token}") }
    .addOnFailureListener { Log.d(tag, "token was NOT added") }
}

 DBには、このように保存される。

f:id:bambinya:20190430182603p:plain

 

TODO for project:

チャンネルとtopicとバックグラウンドでの使用が制限されたアプリ(Send messages to multiple devices  |  Firebase)に関しては調査が必要。

 

おしまい。

 

【和訳】Android Architecture Components ViewModel

自分で理解するために ViewModel | Android Developers (原文) を訳しました。

サンプルコードや図を全て写していないので、原文を見ながら適宜理解を深めるのに利用してください。また、理解しやすいよう所々補足を加えています。先にアクティビティの実行時の変更処理について理解しておくと読みやすくなります。

 

ViewModel

ViewModelクラスはUIに関連するデータの保持と管理をするようデザインされています。そのため画面回転などの設定変更があってもデータは保持されます。

NOTE: ViewModelをAndroidプロジェクトにインポートするには、adding components to your project を見てください。

アクティビティやフラグメントなどのAppコンポーネントはAndroidフレームワークによって管理されるライフサイクルを持ちます。
Androidフレームワークは、開発者がコントロールできないユーザーのアクションや端末のイベントに従って、ActivityやFragmentを破棄または再生成するか決めます。
Activity/FragmentのオブジェクトがOSによって破棄または再生成されると、それらが保持していた全てのデータは破棄されます。
例えば、ユーザーのリスト(List<User>)をActivityが持っていて、設定変更によってActivityが再生成されると、新しく生成されたActivityはリストデータを取得し直さなければなりません。
データが単純ならActivity#onSaveInstanceState()メソッドを使って、Activity#onCreate()でBundleからデータを修復することができます。
しかしこの方法は、UIの状態など少量のデータに向いています。サイズが大きくなりそうなユーザーのリスト(List<User>)には向いていません。

他にも問題があります。activityやfragmentなどのUIコントローラーは戻るまでに時間のかかる非同期の処理を頻繁に呼ぶ必要があります。
UIコントローラーはそれらの非同期処理を管理する必要があります。非同期処理が中断されたら、メモリリークを避けるためそれらを片付ける必要があります。
これは多くの管理を必要とします。また、オブジェクトが設定変更によって再生成されて、同じ処理が呼ばれることはリソースの無駄使いです。

最後にこれも重要なことですが、これらのUIコントローラーはユーザーのアクションに反応したり、OSとのコミュニケーションに対応する必要があります。
そして自身が持つリソースも管理することになると、クラスは膨れ上がります。
そのような状態は、1つのクラスがアプリのすべての機能を他のクラスに委譲せずに自分自身でやろうとすることになります。このような状態はテストを難しくします。

Viewに必要なデータのオーナーシップをUIコントローラーのロジックから分離するのが簡単で効果的です。
ライフサイクルパッケージはViewModelと呼ばれる新しいクラスを提供します。これはUIコントローラー(Activity/Fragment)のためのヘルパークラスで、UIに使うデータを準備する役割を担います。
ViewModelは設定変更があっても自動的に保持されます。そのため、ViewModelが持つデータは再生成されたActivity/Fragmentですぐに利用できます。

前述しましたが、ユーザーのリスト(List<User>)を取得し保持するのはActivityやFragmentではなく、ViewModelの責任であるべきです。
もしActivityが再生成されても、再生成された新しいActivityは、前のActivityによって作られたものと同じViewModelのインスタンスを受け取ります。
Activityが破棄されると、AndroidフレームワークはViewModel#onCleared()を呼び、ViewModelのインスタンスは破棄されます。

NOTE: Activity/Fragmentの初期化時にもViewModelは生き残ることから、ViewModelはViewを参照するべきではありません。
またどんなクラスでもそれがActivityコンテクストの参照を持つ場合は、そのクラスを参照すべきではありません。
もしViewModelがApplicationコンテクストを必要とする場合は、提供されているAndroidViewModelを継承して、コンストラクタでApplicationを受け取ってください。(ApplicationクラスはContextを継承しています)

 

Sharing Data Between Fragments

2つ以上のフラグメントが1つのアクティビティの中で、連携を取り合うことはよくあることです。
2つのフラグメントがインタフェースを定義し、オーナーであるactivityが2つを結ぶことは、珍しいことではありません。
さらに2つのフラグメントはお互いが存在するか、visibleな状態であるか考えなければなりません。
このよくある問題は、ViewModelオブジェクトを使って解決できます。
よくあるmaster-detail fragmentsのケースを想像してください。アイテムリストを表示するfragmentからユーザーがアイテムを1つ選ぶと、選んだアイテムの詳細を表示するfragmentが出てくるパターンです。
この2つのfragmentは、Activityのスコープを使って、お互いのコミュニケーションを管理するためにViewModelを共有することができます。

gistbd67d578044e830ee00943b0e43145e7

2つのfragmentがVIewModelProviderを利用する際、getActivity()を使っていることに注意してください。これは2つのFragmentが同じactivityの範囲で、SharedViewModelのインスタンスを受け取ることを意味します。

このアプローチの利点：

  • Activityは何もする必要がありません。fragmentsのコミュニケーションについて知る必要もありません。
  • FragmentはViewModel以外、お互いを一切知る必要がありません。片方が消えても、もう片方はいつも通り動き続けます。
  • 各Fragmentはそれぞれのライフサイクルを持ちます。もう片方のライフサイクルの影響を受けることもありません。実際、Fragmentが他のFragmentに入れ替わっている間も、UIは問題なく機能します。

ViewModelの機能は、ViewModelを取得する際ViewModelProviderに渡したライフサイクルの範囲で利用できます。(activityを渡したら、activityがfinish()されるまで利用できます。)
ViewModelは、ライフサイクルが終了するまでメモリに置かれます。activityならActivity#finish()、fragmentならFragment#detached()が呼ばれるまで、メモリに残ります。

 

ViewModel vs SavedInstanceState

ViewModelは、設定変更があってもデータを保ち続けるための簡単な方法を提供します。しかし、アプリケーションがOSによってkillされるときは破棄されます。
例えば、ユーザーがアプリを離れて、数時間後に戻ってきたとき、すでにプロセスは終了され、Android OSが保存されたデータからActivityを復元しています。
すべてのframeworkコンポーネント(views, activities, fragments)は、saved instance state機能を使って状態を保存します。
ほとんどの場合、開発者は何もする必要がありません。開発者はonSavedInstanceStateコールバックを使ってデータをbundleに追加するだけです。

onSavedInstanceStateを使って保存されたデータは、システムのプロセスメモリに保持されます。そして、Android OSは開発者にとても少ない量のデータを保持することを許可しています。
そのため、実際のデータ(アプリが使うコンテンツデータ等)を保持させるのに適した場所ではありません。
開発者は、UIコンポーネントによって簡単に置き換えられないデータのためにプロセスメモリを使うのは控えましょう。
例えば、Country情報を見せるユーザーインターフェースがあっても、絶対にCountryオブジェクトをsaved instance stateに入れないでください。countryIdを入れることはできます。(ViewやFragment argumentにすでに保存されていなければ) 実際に利用するオブジェクトはデータベースに入るべきです。そしてViewModelが保存されたcountryIdを使って、オブジェクトを取得します。

BitcoinのBlockとTransactionのデータ構造について

BitcoinはP2P通信技術を利用している。Bitcoinネットワークに参加する各ノードはクライアントとしてもサーバーとしても動作し、データの生成と送受信を行う。各ノードが持つデータはほとんど同じである。(常にノード間でブロックとトランザクションをやり取りしているのでいつも全く同じデータではない)

 

新しいノードがBitcoinネットワークに参加する流れ

  1. Bitcoinのソフトウェアをインストールし、デーモンを起動する。
  2. Seedsから他のノードのIPアドレスを聞き出す。
  3. 他のノードに過去の取引データ(ブロックチェーン)を送ってもらう。送られたデータは主記憶装置に保存される。

https://github.com/bitcoin/bitcoin リポジトリは、CLI(コマンドラインインターフェース)を持っている。ソースをクローンし、デーモンを起動する。初めてネットワークに参加するノードは、他のノードのIPアドレスを知らない。そのため、Seedsというノードを利用する。Seedsと呼ばれるノードは常に稼働していることが期待されている。ネットワークに新しく参加したノードは、まずSeedsに他のノードのIPアドレスを聞く。Seedsのリストはbitcoin/src/chainparamsseeds.hに記載されている。

手に入れたIPアドレスを元に、他のノードに過去の取引データを送信してもらう。送られた取引履歴は主記憶装置に保存する。保存先は${HOME}/.bitcoin/以下である。取引履歴には、ブロックチェーン、トランザクションリスト、UTXOなどがある。2017年2月の時点で保存されるデータ量はMain Networkは100GB、Test Networkは40GB程度である。

 

ノード間でブロードキャストされるブロックとトランザクションのデータ構造

前述したように、各ノードが生成したトランザクションやブロックは他のノードにブロードキャストされ、常にデータの同期が行われている。では、トランザクションとブロックは実際どのようなデータ構造をしているのだろうか。

 

ブロックのデータ構造

ブロックは複数のトランザクションを含む。

先頭にネットワークを識別するマジックナンバーを持ち、ブロックのサイズ(1MByte以下でなければならない)、直前のブロックのhashなどを持つブロックヘッダー、内包するトランザクションの数と、最後にトランザクションデータを持つ。

f:id:bambinya:20170225222746p:plain

詳細はBitcoin Wikiに書かれている。

f:id:bambinya:20170304170353p:plain

 ( Block - Bitcoin Wiki )

 

ブロックヘッダーのデータ構造

ブロックヘッダーは6つの要素を持つ。

ブロックのバージョン、直前のブロックのヘッダーのHash(256bit)、ブロックが含むトランザクションのRoot Hash(256bit)、時間(秒)、ターゲット、Nonce(32bit)である。

f:id:bambinya:20170304195715p:plain

( Block hashing algorithm - Bitcoin Wiki )

 

トランザクションのデータ構造

トランザクションは取引内容を表すデータを持つ。Bitcoinは実体がないため、どれだけの量のBitcoinがどのアドレスからどのアドレスに移動したか、という内容である。

支払い者がどのアドレスからいくらのBitcoinを受け取ったかをInputと呼ぶ。そして、どのアドレスにいくら支払うかをOutputと呼ぶ。

データ構造は下記のとおりである。先頭にバージョン番号、取引に使うInputsの数、Inputsのリスト、 取引に使うOutputsの数、Outputsのリスト、最後にlock timeを持つ。

lock timeには、取引がブロックに含まれる条件を指定することができる。詳細は

前回の記事で述べた。

f:id:bambinya:20170305100110p:plain

( Transaction - Bitcoin Wiki )

BitcoinとBlockchainについて調べたこと

Bitcoin: 非中央集権型の電子通貨。非中央集権型とは、銀行などの信頼された金融機関が取引に関与しないことをさす。金融上の取引を行う際、銀行の役割は支払い者に支払いの能力があることと、取引が不正ではないことを保証することである。Bitocinは、そのような信頼される第三者を取引に必要としない。

Block: 一つ以上の取引データをまとめたものをBlockと呼ぶ。1Blockの最大容量は1MB。Bitcoinのメインネットワークでは約10分にひとつ新しいBlockが生成される。

Blockchain: Blockのつながりを指すが、Bitcoinを支える分散型台帳技術を指したり、ネットワークやソフトウェアをさすこともある。ソフトウェアはC++で開発されている。URLは下記。

GitHub - bitcoin/bitcoin: Bitcoin Core integration/staging tree

P2P(Peer to Peer): 通信技術のひとつ。対等の者同士が通信を行うモデル。通信者はサーバーにもクライアントにもなる。BlockchainはP2P通信モデルを利用している。Bitcoinのネットワークに参加したマシンは過去の全ての取引履歴(Blockchain)を主記憶装置に保存する。取引履歴のデータ容量は2017年2月の時点で、Test Networkが40GB程度、Main Networkは100GBほどある。

Blockの高さ: あるBlockが何番目に生成されたかを高さで表す。

Main/Test Network: Bitcoinには本番用とテスト用の複数のネットワークがある。やりとりする全てのメッセージの先頭4byteにMagic Valueをつけてネットワークを識別する。実際の値は下記の通り。

f:id:bambinya:20170225153554p:plain

( Protocol documentation - Bitcoin Wiki )

ソースではこのあたりがネットワークのマジックナンバー。(リトルエンディアンで送られる)

https://github.com/bitcoin/bitcoin/blob/master/src/chainparams.cpp#L110

 

Node: Bitcoin Network参加者のこと。

アドレス: ビットコインの送信先。メールアドレスのようなもの。全てのノードが全ての取引履歴を見ることができるため、取引履歴を知られないために、通常は取引毎にアドレスを発行する。

BTC: Bitcoinの量を表す単位。

Satoshi: Bitcoinの量を表す単位。1 BTC = 100,000,000 Satoshi

Wallet: 発行したアドレスと、アドレスに紐づくぷ秘密鍵を管理する仕組み。秘密鍵の情報はwallet.datファイルに収められる。同様にBitcoin Networkで秘密鍵の管理とトランザクションを作成するクライアントソフトウェアを指すこともある。

Transaction: 取引ごとにユーザーが発行するもの。Txと書くこともある。Bitcoinがどのアドレスからいくら来て、どのアドレスにいくら行くのかという情報を持つ。データ構造は下記の通り。

f:id:bambinya:20170225172850p:plain

( Transaction - Bitcoin Wiki )

ユーザーがどこからBitcoinを受け取ったかという情報はTxin、どこへ送るかという情報はTxoutに書き込まれる。lock_timeにはUnix Timeかブロックの高さを指定できる。時間が指定された場合は、マイナーが指定時間を過ぎないとtransactionをBlockに含めることができない。ブロックの高さも同様に、指定したブロックの高さにならないと、マイナーがTransactionをBlockに含められない。

UTXO(Unspent Tx Output): 未使用のBitcoin。ネットワークに参加するノードは基本的にネットワーク上の全てのUTXOをDBに保存している。Transactionに含まれるTxinで、まだ支払いに利用されていない(Txoutになっていない)BitcoinをUTXOという。

Fee: 送金にかかる手数料。Transactionのデータサイズは1byteあたり1Satoshiかかるのが相場。

Mining: Transactionの記録をBlockに追加し、新しいBlockの生成を試みること。生成に成功すると報酬としてBlockが含むTransactionの手数料の総額と成功報酬として12.5 bitcoin(2017年2月)を手に入れることができる。成功報酬の額は210,000 blocks置きに半額になる。

BIP(Bitcoin Improvement Proposals): Bitcoinの情報や新機能についてまとめた文書。Bitcoinに関するアイデアを話し合う手段として標準化されている。BIPは3種類に分けられる。

  • Standards Track BIPs - Bitcoin実装の多く、または全てに影響があるもの。またBitcoinを使うアプリケーションに影響があるもの。ネットワークプロトコルの変更や、ブロックとトランザクションのバリデーションルールの変更などが該当する。
  • Informational BIPs - デザインに関するもの、一般的なガイドライン。このタイプのBIPは新機能の提案でもコミュニティの合意を示すものでもない。BitcoinユーザーとBitcoinの開発者は自由にInformational BIPsを無視したり、アドバイスに従って良い。
  • Process BIPs - Bitcoinの実装以外に関する提案。何か実装を提案するかもしれないが、Bitcoinのcodebaseへの提案ではない。コミュニティの意思決定プロセスの変更、ガイドライン、Bitcoinの開発環境・ツールの提案がこのタイプに当てはまる。

( bips/bip-0001.mediawiki at master · bitcoin/bips · GitHub )

Merkle Tree: データ構造のひとつ。複数のTransactionをひとつのBlockに追加するときに使う。下記の図ではMerkle Treeを利用して、Tx0からTx3のハッシュを作成し、Block Headerに追加している。

f:id:bambinya:20170225183527p:plain

( https://bitcoin.org/bitcoin.pdf )

Target: Block生成時にMinersが目標とする256bitの数字。数字自体に意味はなく、2週間ごとに値が変わる。ブロックの生成は、hash関数に直前のBlockのhash値と、Blockに含めるTransactionのMerkle Treeのハッシュと、nonce(4-byteの意味を持たない数字)を入れて、関数の返り値がターゲットより小さくなるnonceを見つけることである。nonceはnumber used once(一度使われる数字)という意味。例えばターゲットが0x00000000FFFF000000......00000(64桁)ならば、hash関数に直前のBlockのhash値と、Blockに含めるTransactionのハッシュと、適当なnonceを入れ、返り値がターゲットより小さくなるようなnonceを見つければ、Blockの生成に成功したことになる。

Difficulty: あるネットワークでブロックを作る難しさをDifficultyで表す。値が高いほど、Blockの生成が難しい。値は最大ターゲット ÷ 現在のターゲットで求められる。Test NetworkではBlockが10分に1つ作られるよう、2週間に一度値が更新される。

 

参考資料

https://bitcoin.org/bitcoin.pdf (Satoshi Nakamotoが発表したオリジナル論文。情報は古い。シンプルなのでそんなに難しくない)

Bitcoin Wiki (少し情報が古い)

 

 

アルゴリズムを評価する計算量について

アルゴリズムを評価できるように、計算量(ランダウの記号)について調べた。

 

アルゴリズムの評価

アルゴリズムは、実行に必要な資源の量で評価される。

資源とは、実行にかかる時間と使用するメモリ領域を指す。一般的には資源が少ない方が評価が高いが、計算量を優先すると可読性が下がり、保守がしづらくなる。ライブラリや言語などの閲覧頻度が低く、処理速度を求められるものは計算量を優先する。アルゴリズムの用途によって決める。

 

計算量を優先したアルゴリズムの例(消費メモリは少ないが、理解に時間がかかる)

ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズ ...

 

計算量の種類

計算量は2種類ある。

時間計算量(Time Complexity)は、アルゴリズムが処理を終えるまでに実行する命令数(ステップ数)を表す。

領域(空間)計算量(Space Complexity)は、アルゴリズムが処理を終えるのに必要なメモリ領域を表す。

 

ランダウの記号

計算量の評価にはランダウの記号(Landau Symbol)を用いる。アルゴリズムの入力値のサイズが変化したとき、使われる資源の変化率を表す。

ランダウの記号は O (オー)記法(Big  O  Notation)とも呼ばれる。記号 O はOrder(程度)の O 。

一般的に O 記法は、関数の変数(この場合は入力値のサイズ)が無限に近づいたときの資源の増加率を提示する。そのため、ハードウェア依存の定数項と増加率が低い低次数の項は考慮しない。

例) あるアルゴリズムが、与えられたサイズ n のデータを処理をするのにかかる時間が次の多項式で表現できる場合、計算量は O(n^2) である。

f(n) = 4n^2 - 2n + 2

f(n) = O(n^2)

 

やってみよう

実際にアルゴリズムの計算量を考えてみよう。

isUniqueChar(String word)は、ある文字列がすべてユニークであるかどうか(重複する文字がないか)を判定する。

ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズ ...

時間計算量を考える時は、ステップ数をカウントする。そこから入力サイズ(引数wordの大きさ)に関係のあるfor文の実行回数のみ取り出す。wordの文字数分、for文が回るので時間計算量は O(n) となる。

空間計算量を考えるときは入力値の大きさは考慮しない。アルゴリズムの評価をするために、アルゴリズムが問題を解決するために必要なメモリ領域のみ考える。

isUniqueChar(String word)ではboolean[] char_set と int i とint len と int val がメモリを使用する、これらはマシンの性能や言語の型の設計に依存するため、入力値の大きさにかかわらず一定である。

よって空間計算量は O(1) となる。

 

 

実際にかかる時間を想像してみよう

CPUは私たちが書いたアルゴリズムをどのくらいのスピードで処理するのだろうか。

代表的なCPUは1つの命令を4つのステージに分けて実行する。1ステージを実行するのに1クロックかかるので、1命令を実行するのに4クロックかかる。

(1)　命令フェッチ　；　命令コードをメモリから読み込む

(2)　命令デコード　；　読み込んだ命令コードを解析し、実行の準備を行う

(3)　実行　　　　　；　CPU内部の演算ユニットで命令を実行する

(4)　ライトバック　；　実行結果をレジスタやメモリに書き込む

 

iPhone7が使用しているCPUを例にアルゴリズムが処理を終えるまでにかかる時間を想像してみる。iPhone7のCPUはARMアーキテクチャのApple A10を使用している。

ARMはRISC(Reduced Instruction Set Computer)プロセッサの１つである。RISCは1つの命令を実行するステージ数とパイプラインの数を揃えることで、見かけ上1クロックあたり1命令を実行する。

f:id:bambinya:20170126171057p:plain

上の画像は、1つの命令を { IF = 命令フェッチ、ID = 命令デコード、EX = 実行、MEM = メモリアクセス、WB = レジスタ・ライトバック } の5つのステージに分けて、5つのパイプラインで5つの命令を同時実行する。実質1クロックで1命令完了することになる。

1命令をいくつのステージで実行するかは、CPUによって異なる。(Apple A10のステージ数とパイプライン数は調べたけど分からなかった)

Apple A10の動作周波数は最大で2.34GHzなので、1秒間に2,340,000,000回のクロックを刻む。ARMアーキテクチャは1クロックあたり1命令を実行するため、1秒間に2,340,000,000命令実行する。またコア数は4つなので、理論上は1秒間に9.36G回の命令を実行する。

ものすごくシンプルに考えると10,000ステップのアルゴリズムをCPUが処理する時間は、 1000 \times \frac{10000}{2.34 \times 10^9} = 0.0042..ミリ秒となる。

ただし、実際プログラムの実行には、CPUがメインメモリ、ブリッジ、ハードディスク等と情報のやり取りを行う時間(データバス)、キャッシュメモリにキャッシュがあるかどうか、命令セットの最適化、などが時間に関係し、もっと時間がかかる。この辺りは知識が全くないので、いつか検証したい。

 

参考

f:id:bambinya:20170126213048g:plain

パソコンの基礎知識 > CPU > キャッシュメモリの仕組み

RISC - Wikipedia

命令パイプライン - Wikipedia

Q&Aで学ぶマイコン講座（1）：CISCとRISC、何が違う？ (2/3) - EDN Japan

ニュートン法を使って、平方根を求めるアルゴリズムを書いてみよう

Goのプレイグラウンドで遊んでたら、フロー制御の章でニュートン法を使って平方根を求めましょう( A Tour of Go )と言われたので調べた。

 

ニュートン法とは？

ニュートン・ラフソン法(Newton-Raphson method)ともいう。

与えられた関数 f について f(x)=0 になる x の近似解を求める方法である。

例えば、 x^2-2=0 の解である \sqrt{2} は無理数(1.41421356...)である。有効桁数があるコンピューターは、この値を誤差なく持つことは不可能であるが、ニュートン法を用いて計算を繰り返すことで、型が持つ有効桁数の範囲で解に近い値を求めることができる。

 

やってみよう

 Goの問題は、引数として与えられる数( kとする)の平方根( xとする)を求めるアルゴリズム sqrt(k float64)(x float64) を書くというものである。ニュートン法を使って解いてみよう。

引数として与えられた kの平方根 xを求めることから、

k = x^2 　より

x^2 - k = 0 という方程式を解けば平方根が求まる。

k = 2 のときを例に解法を説明する。以下は x^2 - 2 の曲線とその接線のグラフである。接線は解 x ( = \sqrt{ 2 } )よりも大きな値を適当にとり( \displaystyle x_0 とする)、引いた。

f:id:bambinya:20170124225900p:plain

 

上の図から分かるように、接線の x 切片 \displaystyle x_1 は、 {\displaystyle x_0} {\displaystyle \gt} {\displaystyle x_1} {\displaystyle \gt} x(= \sqrt{ 2 } ) という値をとる。この性質を使い、次は \displaystyle x_1 を元に曲線の接線を引き、 x 切片を求める。これを繰り返すことで、真の解に近づけていく。反復回数が多いほど精度が上がっていく。グラフでは下記のようになる。

 

f:id:bambinya:20170124231411p:plain

 

この反復処理は、 \displaystyle x_1 を \displaystyle x_0 で表す漸化式を求めるとfor文で書ける。

\displaystyle x_1 を \displaystyle x_0 で表す式を求める。

接線の傾きは微分で求められる。

f(x) = x^2 - k

f'(x) = 2x

\displaystyle x_0 の時の接線の傾きは 2\displaystyle x_0 であり、これはyの変化量をxの変化量で割ったものと等しい。下記を参照のこと。

 

f:id:bambinya:20170124223222p:plain

 

式にすると、

2\displaystyle x_0 = \frac{\displaystyle x_0^2 - k} {\displaystyle x_0 - \displaystyle x_1}

両辺に {\displaystyle x_0 - \displaystyle x_1}をかけて整理すると、以下の式が得られる。

\displaystyle x_1 = \frac{\displaystyle x_0^2 + k}{2\displaystyle x_0}

( \displaystyle x_1 を \displaystyle x_0 で表す漸化式。 k is given.)

この漸化式を用いて、Goでfor文を書くと次のようになる。

 

関数とループを使った簡単な練習として、 ニュートン法 を使った平方根の計算を実装してみましょう。( ...

 

おしまい。