kakts-log

programming について調べたことを整理していきます

node.jsで統計処理をするには simple-statisticsが便利

データ解析して統計処理を行う際にはRやpythonがライブラリもそろっていて便利ですが、node.jsでも簡単に統計処理を行いたい場合は、simple-statisticsというnpmモジュールが非常に便利です。

github.com

数値データを配列で持たせて、平均値や中央値、分散や標準偏差などの統計をする上で基本となる値を求める関数を呼び出せます。

'use strict'
const sta = require("simple-statistics");

const arr1 = [1, 5, -10, 100, 2];

// 最小値取得 -10
console.log(sta.min(arr1));

// 最大値取得 100
console.log(sta.max(arr1));


const arr2 = [1, 2, 3, 4, 5, 6];
// 合計値取得 21
console.log(sta.sum(arr2));


const arr3 = [2, 4, 4, 4, 5, 5, 7, 9];
// 分散 4
console.log(sta.variance(arr3));
// 標準偏差 2
console.log(sta.standardDeviation(arr3));

基本的な関数だけでなく、PerceptronModelや、BayesianClassifierも使えるので、機械学習とかにも使えるかと思います。

mac USキーボードでの英字入力がおかしいときの対処法

macで USキーボード配列を使っている際に、ダブルクオーテーション「"」を推した直後にaを打つと「à」になったり、 スペースを押すと勝手に「"」がもう一つ挿入されたり挙動がおかしいときがあります。 その場合は、macのキーボードの英語設定がおかしいことが原因で、以下の操作方法で直すことができる。

「システム環境設定」 → 「キーボード」 で、選択できる言語で英語の項目が「US. International - PC」になっている。
これは多国籍言語対応用の設定になっているため「"」の入力後の挙動が意図しない物になるので、「U.S」に変更すれば直る。

英語の設定項目で「U.S」となっていれば解決。

f:id:kakts:20161219230219p:plain

参考

http://superuser.com/questions/346142/my-windows-keyboard-is-being-clever-with-the-quote-keys-how-can-i-stop-it

Makefileでmake時に 「*** missing separator. Stop.」 と出たときの対処法

c言語で書いたプログラムをコンパイルする際にMakefileコンパイル処理をまとめて行くと便利です 。
たまにMakefileをつかってmakeすると以下のエラーが出る時があります。

Makefile:8: *** missing separator.  Stop.

この場合は、下記の最後の行の先頭でスペースを使っていることが原因。

PROGRAM = server_socket
OBJS    = server.o
SRCS    = $(OBJS:%.o=%.c)
CFLAGS  = -g -Wall
LDFLAGS =

$(PROGRAM):$(OBJS)
    $(CC) $(CFLAGS) $(LDFLAGS) -o $(PROGRAM) $(OBJS) $(LDLIBS)

スペースをタブに変更すれば解決する。

v8における配列ソートについて

この記事はJavaScript Advent Calendar 2016 - Qiitaのの18日目の投稿です。
私は業務やプライベートで、node.jsを使って開発をしています。
勉強のために、時間のあるときにv8のソースコードを読んでいて内部の実装について調べています。
先日、配列のソート周りの仕組みが面白いと感じたので今回紹介します。

V8とは

developers.google.com chromeやnode.jsで使われているjavascriptエンジンのことです。

Array.sort

v8におけるjavascriptのArray.sortのソースは https://github.com/v8/v8/blob/master/src/js/array.jsでみれます。

Array.sortの関数自体は https://github.com/v8/v8/blob/master/src/js/array.js#L1559から読み進めていくことができます。

Array.innerSortの実装について

Array.sort内や様々なところで呼び出されているinnerSort関数の実装はやや複雑ですが、sortのパフォーマンスを上げるためにかなり工夫がされています。

挿入ソートとクイックソートを組み合わせるソート戦略

Array.innerSortでは、ソートする配列の要素数に応じて、挿入ソートとクイックソートを使い分けています。
コメント上で要素数が22以下の場合挿入ソートにしたほうが効率が良いと書かれていて、実際に要素数が10以下の場合は挿入ソートをつかっています。
https://github.com/v8/v8/blob/master/src/js/array.js#L763-L767

このソート戦略については、javascript関係なく一般的に有効な戦略で、下記の「参考」項目にリンクをまとめています。

挿入ソートについて

https://github.com/v8/v8/blob/master/src/js/array.js#L726-L740

挿入ソートは平均計算量 {O(nˆ2)}で、要素数の2乗で計算量が増えていきますが。
いわゆるin-place*1アルゴリズムで、ソート中に元の配列を書き換えながらソートを行うので、ソート中に用いるメモリ量 を増やさずにソートすることができます。

(追記) 挿入ソートについて kakts-tec.hatenablog.com

クイックソートについて

https://github.com/v8/v8/blob/master/src/js/array.js#L760-L844

クイックソートは平均計算量 {O(nlog(n))}で、計算量的には挿入ソートより優秀ですが、ソート中に関数の再帰をおこなうため、オーバーヘッドが非常に多く、要素数が少ない場合、そのオーバーヘッドが無視できないため挿入ソートが勝る場合があります。
流石に膨大な要素数に対するソートとなると、 {O(nlog(n))}の計算量は強力で、挿入ソートと比較して圧倒的に性能があがります。
むしろ万以上の単位になると挿入ソートは全く使えないほどパフォーマンスが落ちます。

まとめ

v8の配列ソートにおいて、要素数に応じて挿入ソート( {O(nˆ2)})とクイックソート( {O(nlog(n))})という2つのアルゴリズムを切り替えていることを紹介しました。
アルゴリズムに関してこの記事では深くは紹介しませんが、v8においては配列ソートにおいてメモリ使用量と速度を考慮した実装が行われていることを確認できました。

次回の JavaScript Advent Calendar 2016 - Qiitawtnk - Qiitaさんの投稿になります。

参考

挿入ソートとクイックソートについて
- algorithms - Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent? - Computer Science Stack Exchange
- algorithm - Why is Insertion sort better than Quick sort for small list of elements? - Stack Overflow
- [http://www.techscore.com/blog/2014/12/06/comparison-of-sorting-algorithm/:embed:cite]

Google apps script のLock制御について

この投稿はGoogle Apps Script Advent Calendar 2016の17日の投稿です。

Google apps scriptとは

developers.google.com Googleスプレッドシートや、ドキュメントなど、Google関連のサービスにおいてGoogle apps script(以下GAS)を使ってシートの編集、 web api呼び出しなど色々なことができるようになっています。
私も特に職場でスプレッドシートを使うことが多く、GASを使ってデータ集計やサービスで使うマスタデータの入力、さらにはjson吐き出し機能など作って作業の自動化を行っています。

GASのLock機能について

スプレッドシートやドキュメントなどのリソースでGASを使う際に、複数ユーザが同じリソースに対して同時にスクリプトを走らせてしまう場合があり、場合によってこれが非常に問題になる場合があります。
共有リソースでの同時アクセス作業に対して起こりうる共通の悩みだと思うのですが、GASでは、これを防ぐためのLock機能を提供しています。

GASのLock Class と Lock Service

Lock Service  |  Apps Script  |  Google Developers
GASではこのLock機能を実現するために Lock ClassとLock Serviceを提供しています。
スクリプトに対するLockを取得したり、処理が終わったらLock状態を解除したりする基本的な機能があります。 Lockの粒度としては、以下の3が提供されているので用途に応じて自由に使えます。

GASのLock機能を使ってみる

Lock機能の便利さを実感するために実際に使ってみます。 上記の3種類のロックについてそれぞれGoogleスプレッドシートを用いて試してみます。

ドキュメントに対するLock

GoogleスプレッドシートGoogle docsなどの各リソース(ドキュメント)に対するLockをかけます。 1つのリソース全体にLockをかけるということは、Lockがかかっている間はすべてのユーザが並列にコードを実行できないことを意味しています。 ドキュメントに対するLockをかけるには、LockService.getDocumentLock()でドキュメントLock用のインスタンスを取得した後に Lock.tryLock(timeoutInMIllis) か Lock.waitLock(timeoutInMillis)を呼び出す必要があります。
ある単一のドキュメントに対するロックなので、他のドキュメントで同じスクリプトを実行している場合は問題なく実行できます。

今回はテストのために、2つのアカウントで別々に同じスプレッドシートを開いた状態でドキュメントに対するLockがかかっているかをチェックします。 ユーザA,Bがいるとして以下のアクションを行って確認します。 ①ユーザA: Datetime更新(Lock中に10秒間sleepさせる) ②ユーザB: ユーザAのアクション直後にDatetime更新ボタンを押す

スクリプトは以下のとおりです。

function onOpen() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();

  ss.addMenu("test", [
    {name: "Datetime更新", functionName: "changeDateTime"}
  ]);
}

function changeDateTime() {
  var docLock = LockService.getDocumentLock();
  // ドキュメントに対してLockがかかっているかチェック
  if (docLock.tryLock(500)) {
    var ss = SpreadsheetApp.getActiveSpreadsheet();
    var sheet = ss.getSheets()[0];

    var rangeLockStatus = sheet.getRange("A1");
    rangeLockStatus.setValue("ドキュメントロック開始");
    var range = sheet.getRange("A2");
    range.setValue(Date.now());

    // Lockかけた状態のまま10秒待つ
    Utilities.sleep(10000);

    // Lockの解放
    docLock.releaseLock();
    rangeLockStatus.setValue("ドキュメントロック終了");
  }
}

この通りに実行すると、最初にユーザAの実行に対してLockがかかり、ユーザBはLockを1秒間待っても解除されないので実行せずに終了します Lock系の処理を行う際に他の言語でも共通なのですが、Lockするべき処理が終わった場合はちゃんとLock解除は絶対必須です。

スクリプトに対するLock

続いてスクリプトに対するLockですが、複数ドキュメントで同じスクリプトを実行している場合に有効なLockです。
前述したドキュメントに対するLockと何が違うかというと、ドキュメントLockは1ドキュメント内で有効なLockですが、
スクリプトLockは、 共通ライブラリなどで複数のドキュメントが同じスクリプトを実行している場合、あるドキュメントでLockを取得している間他のドキュメントからはLock解除を待たないといけないです。

スクリプトは以下のとおりです。

function onOpen() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();

  ss.addMenu("test", [
    {name: "Datetime更新", functionName: "changeDateTime"}
  ]);
}

function changeDateTime() {
  var scriptLock = LockService.getScriptLock();
  // スクリプトに対してLockがかかっているかチェック
  if (scriptLock.tryLock(500)) {
    var ss = SpreadsheetApp.getActiveSpreadsheet();
    var sheet = ss.getSheets()[0];

    var rangeLockStatus = sheet.getRange("A1");
    rangeLockStatus.setValue("スクリプトロック開始");
    var range = sheet.getRange("A2");
    range.setValue(Date.now());

    // Lockかけた状態のまま10秒待つ
    Utilities.sleep(10000);

    // Lockの解放
    scriptLock.releaseLock();
    rangeLockStatus.setValue("スクリプトロック終了");
  }
}

ドキュメントLockと異なるのは、Lockオブジェクトを取得するときにLockService.getScriptLock()を呼び出すようになるだけです。
戻り値としてLockオブジェクトが変えるのは変わらないので、ロックをかけたり解除する操作は変わりません。

ユーザLock

最後に、ユーザに対するLockですが、同一ユーザのスクリプト実行に対するLockです。 ユーザ毎にスクリプトのLock状態をもっているため、 ユーザAとユーザBが同時にスクリプトを実行できます。

スクリプトは以下のとおりです。

function onOpen() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();

  ss.addMenu("test", [
    {name: "Datetime更新", functionName: "changeDateTime"}
  ]);
}

function changeDateTime() {
  var userLock = LockService.getUserLock();
  // ユーザに対してLockがかかっているかチェック
  if (userLock.tryLock(5000)) {
    var ss = SpreadsheetApp.getActiveSpreadsheet();
    var sheet = ss.getSheets()[0];

    var rangeLockStatus = sheet.getRange("A1");
    rangeLockStatus.setValue("ユーザロック開始");
    var range = sheet.getRange("A2");
    range.setValue(Date.now());

    // Lockかけた状態のまま10秒待つ
    Utilities.sleep(10000);

    // Lockの解放
    userLock.releaseLock();
    rangeLockStatus.setValue("ユーザロック終了");
  }
}

これもLockオブジェクトの取得にLockService.getUserLock()するところのみ変わっています。

まとめ

Google apps script が3種類の粒度でLock機能を提供していて、今回は使い方を紹介しました。
ドキュメント・スクリプトLockはかなり使えそうですが、正直ユーザLockは使いみちがイメージできなかったですが
現在業務や個人で使っているスクリプトで、Lock機能を使えそうなので導入してみます。

次回のGoogle Apps Script Advent Calendar 2016の投稿は、 @HomMarkHuntさんになります。

nginxの利点

個人環境でnginxを使うようになったので、nginxを使う上での利点について軽く整理する。

nginxの主な用途

なぜnginxはリクエストを高速にさばけるのか

一般的に、同時に複数の処理をさばくためには、ディスクやネットワークなどのI/O多重化が必要。
nginxでは、I/O多重化を実現するためにepollシステムコールを使用している。 epollにおいては、ファイルディスクリプタの状態をカーネル内部で管理するために、プログラム側で1つ1つチェックする必要が無いため、 同時リクエスト数が増えたとしても処理にかかる時間は一定になる。
以上のことから、nginxは万を超える単位のリクエストも効率よく処理することができる

Apatch httpサーバではどうなのか

Apache HTTPを代表とする、プロセス・スレッドベースのマルチプロセッシングモジュール(以下、MPM)はソケットの管理に、select pollシステムコールが使われる。 これはnginxで使われているepollとは異なり、ファイルディスクリプタをプログラムが1つ1つチェックするために、処理時間が同時リクエスト数に比例する。

同時リクエスト数とメモリ使用量に関して

nginxでは、単一プロセスでリクエストをさばくので、メモリ使用量が変化することはない。
それに対して、Apache HTTPなどのMPMでは、同時リクエストのたびにプロセスやスレッドを起動するために、使用メモリ量も比例して増加する。

markdownで表を作りたいときは markdown tables ganeratorが便利

ブログの記事や仕事でよくmarkdownを使いますが、表をmarkdownで書くのが非常にきついと感じています。

たとえば

C D
A 0 1
B

↑こんな感じの表を書く際に markdownでは以下のように書く必要があり、非常に厄介です。

|   | C  | D  |
|---|----|----|
| A | 0  | 1  |
| B | 1 | 1 |

markdown tables generatorというwebサービスがあり、これを使うと 作成した表をmarkdown形式に簡単に吐き出してくれてかなり楽です。 www.tablesgenerator.com