2011-10-24
■[数学]Math.floor(x / y) は常に期待する値になるか
x, y は0以上2^32未満の整数とし、yは0でないとする。
数式上に ${...} と書いたらECMAScriptで...の部分を評価した結果の値を表すものとする。${...} の外で a + b のように何か演算を書いた場合、それは浮動小数点数の演算ではなく、数学的な実数の演算を表すものとする
${Math.floor(x / y)}} = floor(x / y) は常に成り立つか？
α = floor(x / y) とおくと α <= (x / y) < α + 1 が成り立つ
直近への丸め
ECMAScriptの四則演算は結果を直近の表現可能な値へ丸めることが定められている。すなわち ⊙を四則演算の記号(+,-,*,/)、aを任意の表現可能な値だとすると ${x ⊙ y} < a < (x ⊙ y) や (x ⊙ y) < a < ${x ⊙ y} が成り立つことはない。
α <= ${x / y} <= α + 1 を示す
- α, α + 1 はともに表現可能な値である。
- α <= (x / y) より ${x / y} < α となることはない。
- 同様に (x / y) <= α + 1 より ${x / y} > α + 1 となることもない。
- したがって α <= ${x / y} <= α + 1 である。
${x / y} != α + 1 ？
${x / y} != α + 1 の場合、α <= ${x / y} < α + 1 より${Math.floor(x / y)} = α が成り立つ。
よって、${x / y} = α + 1 となることがないことを示せばいい。
(整数) + 1 より小さい最大の浮動小数点数
1以上2未満の区間においては浮動小数点数は小数点以下の桁数が52桁の固定小数点数だと考えることができる。
同様に
- 2以上4未満では51桁
- 4以上8未満では50桁
- ......
であるから
- 2^n 以上 2^(n+1) 未満では (52 - n) 桁である (0<=n<=52)
したがって
- nを自然数、aを整数とし、0<=n<=52, 2^n <= a < 2^(n+1) であるとすると
- a + 1 より小さい表現可能な値の最大は a + ((1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n))) である
ここで
- f(n) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n)) とおく
- aを 0<=a<2^32 の整数として a + 1 より小さい表現可能な値の最大をa + g(a)とする
- a != 0 のとき g(a) = f(floor(log2(a)))
- a = 0 のとき g(0) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^53) であるから f(-1) に一致する
- したがってg(a)は f(-1), f(0), f(1), ..., f(31) のいずれか
- f(n)は単調減少であるから31以下のすべての整数nについて f(31) <= f(n) である
- よって f(31) <= g(a) は常に成り立つ。
y = 3 で確かめる
ここで y = 3 とおいて ${x / 3} = α + 1 になることがあるかどうか確かめる
(x / 3) = α + (r / 3) と表すことができる。 (r = 0,1,2)
(x / 3) = α + (r / 3)
<= α + (2 / 3)
<= α + f(31)
<= α + g(α)
< α + 1
- よって (x / 3) <= α + g(α) < α + 1 であり α + g(α) は表現可能な値であるから ${x / 3} = α + 1 となることはない。
- ここでは y = 3 としたが (y - 1) / y <= f(31) が成り立つならば ${x / 3} != α + 1 は常に成り立つ。
- 関数 (y - 1) / y は y > 0 で単調増加し f(31) = (2^21 - 1) / 2^21 であるから y <= 2^21 であるとき ${x / y} != α + 1 は常に成り立つ。
yが大きいときについて考える
y <= 2^21 については示せたから、問題はyが2^21より大きいときである。
g(α)の下界としてf(31)を使ったが、yが大きいときにはαは小さくなるから下界をもっと大きくできるはずである。
ここでf(n) を変形しておく
f(n) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n))
= Σ[k=1,52-n] (1 / 2)^k # 初項 1/2, 公比 1/2, 項数 52-n の等比数列の和
= (1 / 2) * (1 - (1 / 2) ^ (52-n)) / (1 - (1 / 2))
= 1 - (1 / 2) ^ (52-n)
= (2 ^ (52-n) - 1) / (2 ^ (52-n))
y >= 2^n とする。 (0 <= n <= 32)
α = floor(x / y)
<= (x / y)
< (2^32 / y)
<= (2^32 / 2^n)
= 2^(32-n)
よって α < 2^(32-n) すなわち α <= 2^(32-n) - 1
関数g(a)は単調減少をするから
g(α) >= g(2^(32-n) - 1)
= f(32-n-1)
= (2 ^ (52-(31-n)) - 1) / (2 ^ (52-(31-n)))
= (2 ^ (21+n) - 1) / (2 ^ (21+n))
よって y <= (2 ^ (21+n)) ならば
(x / y) = α + (r / y) # rは0以上y未満の整数
<= α + ((y - 1) / y)
<= α + (2 ^ (21+n) - 1) / (2 ^ (21+n))
<= α + g(α)
< α + 1
である。
- よってnを0以上32未満の任意の整数とするとき 2^n <= y <= 2 ^ (21+n) であるすべての整数yで ${x / y} != α + 1 が成り立つ。
- まず、y <= 2^21において常に ${x / y} != α + 1 が成り立つことは既に示した。
- n = 21 とおいて 2^21 <= y <= 2^42 で常に ${x / y} != α + 1 が成り立つ。
- よってyが1以上2^32未満のすべての整数において ${x / y} != α + 1 は常に成り立つ。
- したがって ${Math.floor(x / y)} = floor(x / y) は常に成り立つ。
- おわり
まとめ
数学難しいです！でも自分で問題を立てて考えるのは楽しいですね！
間違っているところや、ここをこうした方がいいといった指摘、もっとスマートな方法があればコメント欄に書き込んでくださるとありがたいです！
2011-09-29
■Deferredのコールバックスタイルと比較したメリット/デメリット
まだそんなに使い込んでいるわけではないけれど。
使う前はコールバックスタイルに比べてなにか利点あるの？別にコールバックスタイルで困らないんじゃない？って思っていたのでまとめてみる。
メリット
- コールバック引数が消えてすっきりする
- 処理1をやって非同期処理を挟んで、処理2をやって、処理3をやって...というときにコールバックスタイルだと汚くなるのが綺麗にかける
- 非同期処理でもエラーハンドリングが綺麗にできる
- (一部のDeferredライブラリのみ) 非同期処理を行っている最中にキャンセルできる。ちょうどスレッドの使える言語で、バックグラウンドで処理を行っているスレッドをとめるように
- ライブラリにもよるが以下のようなことをするためのユーティリティがある。コールバックスタイルでもそういうユーティリティは作れるっちゃ作れるが、あらかじめ存在するDeferredライブラリに任せちゃう方がいいよね
- 複数の非同期処理を一斉に実行して全部揃ったら次を実行する (JSDeferredのparallel)
- 非同期処理をはさむ処理を任意回数順番にやる (JSDeferredのloop)
デメリット
- Deferredを理解しないと書けない・読めない
- ライブラリにもよるが、Deferredを使った場合、何もしていないと非同期処理内で起こったエラーが握りつぶされてしまう
- エラー用のコールバックを追加して、それを表示するとか、setTimeoutして再スローするとかしないといけない
- ちなみにMochiKitのDeferredが元になっているclosure-libraryのDeferredでは捕捉されなかったエラーは再スローされるように改良されている。素晴らしい
処理1をやって非同期処理を挟んで、処理2をやって、処理3をやって...というときにコールバックスタイルだと汚くなるのが綺麗にかける
コールバックスタイルで普通に書くとこういうコールバックのネストになる
function (cont) { 処理1; someAsyncProcess(..., function () { 処理2; someAsyncProcess(..., function () { 処理3; cont(); }); }); }
関数に名前をつけてフラットにすることもできるが... この方法は東京Node学園#1「非同期プログラミングの改善」のエッセンスでは「名前でジャンプするなんてgoto文でしょ」と言われている。
個人的にはそんな悪くないと思うけど、書くのがだるいのは確か
function (cont) { phase1(); function phase1() { 処理1; someAsyncProcess(..., phase2); } function phase2() { 処理2; someAsyncProcess(..., phase3); } function phase3() { 処理3; cont(); } }
Deferred (ここではJSDeferred) を使うとこう
// someAsyncProcessはここでは上と違って // コールバック引数を受け取る関数ではなくDeferredを返す関数とする function () { return next(function () { 処理1; return someAsyncProcess(...); }). next(function () { 処理2; return someAsyncProcess(...); }). next(function () { 処理3; }); }
非同期処理でもエラーハンドリングが綺麗にできる
正直、非同期処理でエラーハンドリングしたいと思ったことがないのであんまり...
(一部のDeferredライブラリのみ) 非同期処理を行っている最中にキャンセルできる
これはJSDeferredにはない機能。MochiKitのDeferredで可能。これのためにDeferredを使い始めた。
// 0.1秒間隔で0, 1, 2, 3, 4, 5 .. と永遠に出力する function f() { return loop(0); function loop(i) { console.log(i); return MochiKit.Async.callLater(0.1, loop, i + 1); } } var deferred = f(); // 一秒後に処理を中断する // （ボタンが押されたら処理を中断、のように変えてももちろんいい） setTimeout(function () { deferred.cancel(); }, 1000);
2011-09-23
■for (var v in nantoka()) yield v とか書かなくちゃいけなくね問題
案外そうでもなかったかもしれない。一個一個の関数を扱いにくいジェネレータ関数のまま放っておくのではなく、継続を引数にとる普通の非同期関数化してしまえばいいんだ。
お題は、これを出力するたびに0.1秒のウェイトいれるようにかえるというもの
function a() { for (var i = 0; i < 3; i ++) { console.log("a"+i); } } function b() { for (var i = 0; i < 3; i ++) { console.log("b"+i); } } function main() { a(); b(); } main(); console.log("done");
runnable関数はKazuho@Cybozu Labs: JavaScript/1.7 で協調的マルチスレッドより
function runnable(generatorFunc) { var generator; var resume = function (value) { try { generator.send(value); } catch (e if e instanceof StopIteration) { } }; generator = generatorFunc(resume); resume(undefined); } function a(cont) { runnable(function (resume) { for (var i = 0; i < 3; i ++) { console.log("a"+i); setTimeout(resume, 100); yield; } cont(); }); } function b(cont) { runnable(function (resume) { for (var i = 0; i < 3; i ++) { console.log("b"+i); setTimeout(resume, 100); yield; } cont(); }); } function main(cont) { runnable(function (resume) { a(resume); yield; b(resume); yield; cont(); }); } main(function () { console.log("done"); });
まあこうするぐらいだったらdeferred-generatorの方が洗練されてるかなー
var a = Deferred.generator(function () { for (var i = 0; i < 3; i ++) { console.log("a"+i); yield Deferred.wait(0.1); } }); var b = Deferred.generator(function () { for (var i = 0; i < 3; i ++) { console.log("b"+i); yield Deferred.wait(0.1); } }); var main = Deferred.generator(function () { yield a(); yield b(); }); main().then(function () { console.log("done"); });
ちなみに普通のDeferredライブラリ (ここではMochiKit) を使うとこう
var Async = MochiKit.Async; function a() { return loop(0); function loop(i) { if (i >= 3) return Async.succeed(); console.log("a"+i); return Async.callLater(0.1, loop, i + 1); } } function b() { return loop(0); function loop(i) { if (i >= 3) return Async.succeed(); console.log("b"+i); return Async.callLater(0.1, loop, i + 1); } } function main() { var deferred = Async.succeed(); deferred.addCallback(a); deferred.addCallback(b); return deferred; // return a().addCallback(b) でもいいんだけど気分的にaとbは同じ書き方で並べたい。 } main().addCallback(function () { console.log("done"); });
■JavaScriptのジェネレータとDeferredを組み合わせたライブラリ
JavaScriptのジェネレータとDeferredを組み合わせるといい感じ！ （JS1.7のyieldでharmonyのawait式ぽいことをする) - fujidigの雑記 でいったことをライブラリにしてみました
まだ実際に使ってみていないので便利か分かりません。結局Array#forEachの中でyieldするとかできないし微妙かな...普通のDeferredライブラリ使った方がいいかも
2011-09-21
■JavaScriptのジェネレータとDeferredを組み合わせるといい感じ！ （JS1.7のyieldでharmonyのawait式ぽいことをする)
repl.it経由でtraceur-compilerを知った。そしてharmonyにはawait式というものがあるということを知った。
function deferredTimeout(delay) { var deferred = new Deferred(); setTimeout(function() { deferred.callback({ called: true }) }, delay); return deferred; } function a() { for (var i = 0; i < 4; ++i) { console.log("a"+i); await deferredTimeout(1000); } } function b() { for (var i = 0; i < 4; ++i) { console.log("b"+i); await deferredTimeout(1000); } } function main() { await a(); await b(); } main().then(function () { console.log("done"); });
ほほう。
で、これJS1.7のyieldでだいたい同じことできるよねって思ったので試した。
function deferredTimeout(delay) { var deferred = new Deferred(); window.setTimeout(function() { deferred.callback({}); }, delay); return deferred; } function generatorToDeferred(func) { return function () { var deferred = new Deferred(); var generator = func.apply(this, arguments); function loop(val) { try { var waitTask = generator.send(val); waitTask.then(loop); } catch (e if e instanceof StopIteration) { deferred.callback(); } } loop(undefined); return deferred; } } var a = generatorToDeferred(function () { for (var i = 0; i < 4; ++i) { console.log("a"+i); yield deferredTimeout(100); } }); var b = generatorToDeferred(function () { for (var i = 0; i < 4; ++i) { console.log("b"+i); yield deferredTimeout(100); } }); var main = generatorToDeferred(function () { yield a(); yield b(); }); main().then(function() { console.log("done"); });
おお、これはいいんじゃないか？
- JavaScriptのジェネレータについて思うこと - fujidigの雑記で考えた「ジェネレータで非同期処理が同期的に書けるいうてもfor (var v in nantoka()) yield v;とかしないといけないやん」って問題がyield nantoka();で済むようになってる
- waitTaskのエラーを戻り値のdeferredに伝搬させる処理は実装してないけどすぐ実装できるはず
- deferredのcancellerでwaitTaskのcancelを呼ぶようにしたら現在アイドル中のdeferredがキャンセルできるはず！
- そうすればMochiKitのDeferredのような複雑なDeferredライブラリを使わなくてよくなりそう！チェイン機能のないDeferredライブラリでOKなんじゃないだろか
で懸念点。generatorToDeferredに渡す関数内でreturnしたらその値がdeferred.callbackに渡ってほしいんだけど、ジェネレーターはStopIterationオブジェクトからreturnされた値がとれるのかと思いきやどうやらそういうのはなさそうだ...？んーreturnではなく終了することを表す特別な値をyieldするという方法で代替できるけど...
っていうかジェネレーターの関数でreturnに戻り値を書いてたらパース時にエラーになるね...
function f() { yield 1; return 2; } // TypeError: generator function f returns a value
リンク
- Traceur traceur-compilerでコンパイルした結果が見れる (await式を含む関数はステートマシンなコードに変換されていることが分かるね)
- Error 404 (Not Found)!!1 traceur-compilerのDeferredオブジェクトの実装 (とても小さい！)
- Error 404 (Not Found)!!1 await式を含むコードの変換
2011-09-08
■JavaScriptで非同期処理の途中で中断したいよぉお
JSDeferredのcancelだと目的のことはできなくて、それは構造上無理なんだろうなーと。
で、こんなのを書いてみたものの使いにくい。
https://gist.github.com/1200041
function Trampoline(func) { this.task = new Task(func); } Trampoline.prototype.step = function() { if (!this.task) return; this.task = this.task.cont(); if (this.task) this.task.nextStep = this.step.bind(this); }; Trampoline.prototype.cancel = function() { if (this.task && this.task.canceler) { this.task.canceler(); } this.task = null; } function Task(cont) { this.cont = cont; this.nextStep = null; this.canceler = null; } Task.prototype.getCallback = function() { var self = this; return function() { self.nextStep() }; }; function wait(cont, sec) { var task = new Task(cont); var timerId = setTimeout(task.getCallback(), sec * 1000); task.canceler = function() { clearTimeout(timerId) }; return task; } function f1() { console.log(1); return wait(f2, 1); } function f2() { console.log(2); return wait(f3, 1); } function f3() { console.log(3); return null; } var trampoline = new Trampoline(f1); trampoline.step(); setTimeout(function () { console.log("cancel!"); trampoline.cancel(); }, 1500);
で、どうやらMochiKitのDeferredなら目的のことができるみたい
https://gist.github.com/1202768
function main() { var d = accessAndShowEntries(); d.addCallback(function() { console.log("finish"); }); setTimeout(function() { console.log("cancel!"); d.cancel(); }, 2500); } function accessAndShowEntries() { function loop(i) { if (i >= 5) return; return accessEntry(i).addCallback(function (data) { console.log(data); return callLater(0, loop, i + 1); }); } return callLater(0, loop, 0); } // XHR で何かアクセスする代わり function accessEntry(i) { var d = new Deferred(); var cb = d.callback.bind(d, "foo"+i); var timerId = setTimeout(cb, 1000); d.canceller = function () { clearTimeout(timerId); }; return d; }
でも、JSDeferredの超絶シンプルさに比べてMochiKitのDeferredは複雑だなー。ちょっと理解しようとする気力が起きない
それから、DeferredListのcancelを呼んでも、list全部のcancelを行うっていうふうになっていないのが不思議。なんでだ？
余談
ちなみに動機はTumblrでlikeしておいたものをまとめて自動でリブログと画像の保存をするっていう変なvimperatorプラグイン https://gist.github.com/1194341
(全く関係のない話で、このプラグインは新しいタブを開いてそこのdocumentにあれこれ書き込むっていうのをやっていてなんだかマズそう。実際このタブで別のページを開くとなぜか書き込んだ要素が残っていたりするし...)
これに処理の途中で中断できるボタンとか、タブを閉じようとしたときに中断できる機能をつけたいと思ったのだ。
ところで、Vimperatorプラグインで_libly.js以外ではなにかライブラリを使っているコードとかほとんど見かけないんだけどライブラリを使うときはどうすればいいだろう...ライブラリのコードをソースに含めちゃうとか、あらかじめファイル名の先頭にアンダースコアをつけてプラグインディレクトリに保存してねって形にするとか？
でももう疲れちゃってやる気なくなったからもういいやー感