草依山的Javascript世界

一个Javascript程序猿的学习纪录剩地,不仅仅是JS,还有Linux、Mac、nodeJs、吃、玩!

一次算PI的小尝试

最近看到一个算 PI 的小方法,不是很高效,但是我觉得很有意思,原理(蒙特卡罗方法)也非常简单,概括就是:

已知 1*1 正方形面积为1, 半径为 1 的圆的面积为 π,1/4 圆正好可以放在小正方形里,它的面积与正方形面积比为 π/4,假设小正方形内有 M 个随机点,存在于圆内的点为 N,那么 N/M = π/4,可得

π =  N / M * 4 

可以写一个非常简单 JS 测试一下

function calc (count) {
  var start = new Date()
  var x
  var y
  var inCount = 0
  for (var i = 0; i < count; i++) {
    x = Math.random()
    y = Math.random()
    // 判断点是否在1/4圆里
    if (Math.sqrt(x * x + y * y) <= 1) {
      inCount++
    }
  }

  var result = inCount / count * 4
  var spent = new Date() - start
  console.log('result: %d, count: %d, spent: %dms, rate: %d%', 
    result, count, spent, Math.abs((result-Math.PI)/Math.PI)*100)
}

calc(10)
calc(100)
calc(1000)
calc(10000)
calc(100000)
calc(1000000)
calc(10000000)

跑一下可以看到结果

// MacBook Pro (Retina, 13-inch, Early 2015)
result: 3.2, count: 10, spent: 0ms, rate: 1.8591635788130243%
result: 3.16, count: 100, spent: 0ms, rate: 0.5859240340778606%
result: 3.24, count: 1000, spent: 1ms, rate: 3.1324031235481886%
result: 3.132, count: 10000, spent: 3ms, rate: 0.30534364723675406%
result: 3.13108, count: 100000, spent: 3ms, rate: 0.33462815676567087%
result: 3.141116, count: 1000000, spent: 28ms, rate: 0.015172354991620658%
result: 3.14161, count: 10000000, spent: 248ms, rate: 0.0005521533858654934%

1000万次的时候误差已经比较小,如果写一个 C 的程序跑一下看看会是怎么样呢,于是我就又写了一个 C 的版本(原理一模一样,单纯用 C 实现一下)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

void calc( int count ){
  clock_t begin = clock();
  double x;
  double y;

  int inCount = 0;
  for (int i = 0; i < count; i++) {
    x = (double) rand() / RAND_MAX;
    y = (double) rand() / RAND_MAX;
    if (sqrt(x * x + y * y) <= 1) {
      inCount++;
    }
  }

  double result = (double) inCount / count * 4;
  clock_t end = clock();
  double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("result: %f, count: %d, spent:%fms, rate:%f%%\n", 
    result, count, time_spent*1000, fabs((result - M_PI)/ M_PI)*100 );
}


int main(){
  int count;
  srand((int)time(NULL));

  calc(10);
  calc(100);
  calc(1000);
  calc(10000);
  calc(100000);
  calc(1000000);
  calc(10000000);

  return 0;
}

因为好多年没写 C 了,其实 C 也不是太会,这里 search and copy 了不少代码,用 vscode 写的时候还发生了内存被吃完的囧况gcc -o calc calc.c; ./calc 运行这后得到:

result: 3.600000, count: 10, spent:0.007000ms, rate:14.591559%
result: 3.240000, count: 100, spent:0.004000ms, rate:3.132403%
result: 3.096000, count: 1000, spent:0.027000ms, rate:1.451259%
result: 3.140800, count: 10000, spent:0.261000ms, rate:0.025231%
result: 3.149760, count: 100000, spent:2.531000ms, rate:0.259975%
result: 3.141932, count: 1000000, spent:23.312000ms, rate:0.010802%
result: 3.141936, count: 10000000, spent:230.223000ms, rate:0.010916%

真是让人悲伤,这个结果居然和 JS 差不多,经过一个帅的闪光的小同事指点后,原来是编译的时候没有加优化参数,calc 其实是个 debug 版的,重新用 gcc -O3 -o calc calc.c; ./calc 运行一下:

result: 3.200000, count: 10, spent:0.004000ms, rate:1.859164%
result: 3.120000, count: 100, spent:0.002000ms, rate:0.687316%
result: 3.200000, count: 1000, spent:0.013000ms, rate:1.859164%
result: 3.144800, count: 10000, spent:0.144000ms, rate:0.102093%
result: 3.147080, count: 100000, spent:1.481000ms, rate:0.174668%
result: 3.143316, count: 1000000, spent:13.987000ms, rate:0.054856%
result: 3.141480, count: 10000000, spent:138.983000ms, rate:0.003586%

这么一看差不多是 JS 版的 2 倍,这就正常点了,最近 WebAssembly,比较火,正好可以也尝试一下,按照官方的guide clone 了源码并安装,因为安装过程要去 github 和 s3 下载几百兆的东西,会比较慢,需要翻墙外加很有耐心,安装完成后 emcc calc.c -s WASM=1 -o calc.html,会生成对应的calc.html, calc.wasm, calc.js,因为calc.html里获取 calc.wasm 是用xhr获取的,执行这个文件,需要本地起一个小静态服务,用 Firefox 52 打开之后执行的结果如下:

result: 2.800000, count: 10, spent:0.000000ms, rate:10.873232%
result: 3.120000, count: 100, spent:0.000000ms, rate:0.687316%
result: 3.208000, count: 1000, spent:0.000000ms, rate:2.113811%
result: 3.149200, count: 10000, spent:1.000000ms, rate:0.242149%
result: 3.148920, count: 100000, spent:2.000000ms, rate:0.233237%
result: 3.143232, count: 1000000, spent:13.000000ms, rate:0.052182%
result: 3.141560, count: 10000000, spent:132.000000ms, rate:0.001027%

基本上和 C 编译后的性能差不多,性能非常给力,关于 WebAssembly 更多的知识非常推荐看 a-cartoon-intro-to-webassembly

总结一下:一次小尝试,额外测试了一下 WebAssembly,性能非常好,目前 Web 上饱受性能折磨的游戏也许能从 WebAssembly 的普及中获得大量好处,但是鉴于编译后的 WebAssembly 调试工具并没有配套发展起来,同时在浏览器端需要高性能的场景也并不是特别常见,普及可能还需要些时日。

文章地址: 一次算PI的小尝试
欢迎关注我的微博与我交流:@草依山
Github上也有一些东西:[Github]
所有文章坚决抵制jb51.net的转载!
标签:
2017-03-22

相关文章

2019-09-30 深度神经网络入门
2017-02-13 new做了些什么
2016-09-29 [翻译]bash的各种文件载入执行顺序
2016-05-31 phantomjs在linux下截图中文字体问题
2016-04-24 Promise的错误处理

文章修改纪录

加载中...
Copyright © 2013. Create By 草依山, Fork