2016-11-08

算数 小技 -- Item追加算術平均

個人的な道具箱に入っているちょっとした変形式の話。

もちろん拙作アプリに仕込んであって、このおかげで（これだけではないけど）計算ちょっぱやというモノ。

物理的なノートに書き留めた山ほどあるうちのひとつなんだけど、権利関係関係せずそれほど難しくもないところから漏らしていこうかと。

今回の備忘は、算術平均を算出したいんだけど、CoreDataからフェッチして平均値取り直すなんてことはしたくない。

でも中央値ではちょっとって時に、新規データと過去算出された算術平均値とアイテム数があれば全アイテム舐めるのとと同値の算術平均値が出せるという式の書き置き。

もちろん場合によっては、中央値を使った方が目的にfitしていることもあるが、今回は単純に{ \displaystyle I_k }の各個性がつぶれてもいいので、代表値を測定したいというもの。今回私の目的(要求)には算術平均がfitした。

よく言われる、ひとりでもビルゲイツが混じった母集合で平均年収を算術平均で取っても、説明変数として説得力がないというのは今回は別の方法で回避してある

see.

Cocoaで統計処理 四分位数実装編 - つらつらと日々のメモを公開するブログ

。

具体的なシーンとしては、ガンガンログが飛んでくる中、とにかく1Stepでも短く全てを表現する代表値だけメモリ上でもDBの1レコードにでも書き留めておきたいといったところか。

まず基本中の基本からいくと、算術平均とは何か。これは小学校で習うやつ。

定義としては、実直に全アイテム{ \displaystyle I_1 ... I_n }の合計値をnで割った値が全I{ \displaystyle I_k }を代表する値として、利用できるという概念。

つまり丁寧に書き下すと

{ \displaystyle<br/>\overline{I_{n}} = \frac{\sum_{k=1}^{n} I_k}{n}<br/>}

となる

じゃぁ、これに{ \displaystyle I_{n+1}, I_{n+2}....}が鬼のようにむっちゃ飛んできたらどうすべきか？

災害レベル狼くらいなら、毎回全Itemを配列へフェッチしてぐるぐる回してもいいだろう。

アプローチとしてはbgスレッドに任せてしまうと言うのもありだろう。

ただ、ここで一つ考えてみて欲しい。これもし、ある程度大きなデータが割と速い速度で n -> +Infと考えたら、出荷時のちょっとしたデータなら平気で処理しきれても、そのうちスタックする。

配布された瞬間から、crashレポート受け取り準備万端にしておいた方がいい。

いや、お前はIndexingも知らん素人か、というならさらに考えてみて欲しい。

一般的なIndexとは、所謂SQLエンジンからのデータ管理の方法を代えて、検索速度を確保するアプローチだ。

普通はバイナリサーチができるようにツリー化したり、さらにキャッシュアルゴリズムを導入したりする。

そう。ツリー化するということは、データ構造が複雑になる。複雑ってことは登録に少なからず手間がいるってことやん、手間ってことは、ある程度のステップ数が登録に余計に必要ってことやん。余計に必要ってことは、鬼レベルでこのデータ登録は高コストやん。

この仕様で具体値はいらないということはないだろう。だって、具体値はDBから引っ張るんでしょ？...これもそのうち詰みます。

しかも、macOSのCoreDataはデフォルトでテンプレ組み上げると、XMLファイルでデータ振り回すので、indexという概念があるのかすら怪しい。



ということで、前振りはこのくらいにして、いきなりだが式変形してみよう。

つまり{ \displaystyle \overline{I_n}}に突如{ \displaystyle I_{n+1}}が飛んでくる。

このとき、{ \displaystyle \overline{I_{n+1}}}を算出したい。

だとすると、欲しい式は{ \displaystyle \overline{I_{n+1}}}

つまり

{ \displaystyle<br/>\overline{I_{n+1}} = \frac{\sum_{k=1}^{n+1} I_k}{ (n + 1)}<br/>}

を算出するのに、すでに解っているのは、一つ前の平均値{ \displaystyle \overline{I_n}}、とn

そして、今さっき登録されたログ{ \displaystyle I_{n+1}}

{ \displaystyle \overline{I_n}}に何か足して、{ \displaystyle \overline{I_{n+1}}}が出せないものか。

これができるとクソ遅いディスクアクセスやシーケンシャル操作はなく、CPUの算術オペレータとレジスタ、一次メモリ上だけで完結する。はず。

積極的にこうしたい・・・としよう

こういうとき私は、まずなるべく小さな具体例から考える。つまりH/Wの解析同様足場を固めて次へ進む。

ここでは、[A, B, C]という数値があって、A, Bの平均にCが飛んできたらどうしようと課題設定してみる。

ということで、たとえば (1 + 2) / 2 = 1.5 に5が飛んでくる。このときなんとかして、(1 + 2 + 5)/3 = 2.67という答えを導きたい。

{ \displaystyle \frac{A + B + C}{3 ( = N + 1)} = \frac{A + B}{2 ( = N)} + X, a.k.a 2.67 = 1.5 + X }

となるXなので、割と簡単に

{ \displaystyle X = \frac{A + B + C}{N + 1} - \frac{A + B}{N}}

つまり

{ \displaystyle X = \frac{1}{N + 1} (C - \frac{A + B}{N})} とでてくる。

具体値で言うと、{ \displaystyle X = \frac{1}{2 + 1} (5 - \frac{1 + 2}{2}) = 1.17}なので、これを1.5に足すと、ちゃんと2.67になった！

ではこれを一般化してみよう。この作業がないと現実コードには使えない。

ここで、{ \displaystyle \overline{I_n} = \frac{A + B}{N}, \overline{I_{n + 1}} = \frac{A + B + C}{N + 1} }なので、

個人的なテクニック的には、数の大小は見ない振りして、ガンガン抽象変数で代替していくといいと思う。

と、

{ \displaystyle<br/>X = \frac{1}{n + 1} (I_{n+1} - \overline{I_n}) }

ここで、

{ \displaystyle<br/>\overline{I_{n+1}} = X + \overline{I_{n}}}だったので、

{ \displaystyle<br/>\overline{I_{n+1}} = \overline{I_n} + \frac{1}{n + 1} (I_{n+1} - \overline{I_n})<br/>}

となる。つまり毎回、既にメモリ上にあるいっこ前までの平均値にXを足し続ければ、算術処理のみで平均値が出せる。

状況にも依りそうだけど、NSExpressionやら、NSPredicateで平均値だして比較してみたけど、こっちのが早いみたい。

とくにPredicateはあまり期待しない方がいい。そもそもDBというのは算術処理するものではないので。

おかげで拙作では気軽にテストできる数十万レコードくらいまでだったらスレッド気にせずへいちゃらで処理しきる

この式、GPLみたいなノリでFeedbackは欲しいけど、とくに権利は主張しないです。



投稿者 時刻:

0 件のコメント :

コメントを投稿

登録: コメントの投稿 ( Atom )