面试官问：如何利用 random 计算 π

# 前言

这是基友面试 RingCenter 时被问到的一个题目

表面上考察的是概率论等基础知识，实际可能还会问到事件循环等底层知识，以及 React Fiber

# 蒙特卡洛法求 π

说蒙特卡洛可能不太理解，换个说法 -- 随机抽样

构造一个单位正方形和 1/4 单位圆，往单位正方形中投入点，根据点与原点间的距离判断点是落在圆内还是圆外，分别统计落在两个区域的点的个数 n1,n2 ，n1/(n1+n2) 即 1/4 圆的面积估计值，从而求得 π

引自 CSDN/Daniel960601

以下是 js 代码

function inCicle() {
  var x = Math.random();
  var y = Math.random();
  return Math.pow(x, 2) + Math.pow(y, 2) < 1
}
function calcPi() {
  const N = 1e+6
  let pointsInside = 0
  for(let i=0;i<N;i++){
    if(inCicle()){
      pointsInside++;
    }
  }
  return 4 * pointsInside / N
}
calcPi()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

直接在控制台运行，会发现有卡顿和掉帧发生，下面我们来谈谈如何解决

# 如何避免主线程阻塞

calcPi 是个耗时任务，会阻塞主线程，甚至导致掉帧，有什么解决方法？

提供几个思路

Web Worker
requestIdleCallback
requestAnimationFrame + MessageChannel

# Web Worker

Web Worker 是啥就不再介绍了，不懂的自行 MDN 搜索

我们新建一个 Worker 线程进行耗时任务计算，而后再把结果发送给主线程

function createWorker () {
  let text = `
  function inCicle() {
    var x = Math.random();
    var y = Math.random();
    return Math.pow(x, 2) + Math.pow(y, 2) < 1
  }
  function calcPi() {
    const N = 1e+6
    let pointsInside = 0
    for(let i=0;i<N;i++){
      if(inCicle()){
        pointsInside++;
      }
    }
    return 4 * pointsInside / N
  }
  this.addEventListener('message', (msg) => {
    let pi = calcPi()
    this.postMessage(pi);
  }, false);
  `
  let blob = new Blob([text]);
  let url = window.URL.createObjectURL(blob);
  return new Worker(url)
}

let worker = createWorker()
worker.onmessage = (evt) => {
  console.log('PI: ', evt.data)
};
worker.postMessage("calc");

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

缺点就是计算次数是固定的，同时不能看到实时计算的结果

# requestIdleCallback

利用 requestIdleCallback (opens new window) 在帧空余时间执行任务的特点进行耗时任务的计算

<!DOCTYPE html>
<html>

<head>
  <title>Scheduling background tasks using requestIdleCallback</title>
</head>

<body>
  <script>
    var requestId = 0;
    var pointsTotal = 0;
    var pointsInside = 0;

    function piStep() {
      var r = 1;
      var x = Math.random() * r;
      var y = Math.random() * r;
      return (Math.pow(x, 2) + Math.pow(y, 2) < Math.pow(r, 2))
    }
    function refinePi(deadline) {
      while (deadline.timeRemaining() > 0) {
        if (piStep())
          pointsInside++;
        pointsTotal++;
      }
      currentEstimate = (4 * pointsInside / pointsTotal);
      textElement = document.getElementById("piEstimate");
      textElement.innerHTML = "Pi Estimate: " + currentEstimate;
      requestId = window.requestIdleCallback(refinePi);
    }
    function start() {
      textElement = document.getElementById("piEstimate");
      textElement.innerHTML = "Pi Estimate: " + "loading";
      requestId = window.requestIdleCallback(refinePi);
    }
    function stop() {
      // alert(1)
      if (requestId)
        window.cancelIdleCallback(requestId);
      requestId = 0;
    }
  </script>

  <button onclick="start()">Click me to start!</button>
  <button onclick="stop()">Click me to stop!</button>
  <div id="piEstimate">Not started</div>
</body>

</html>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

几个要点

requestIdleCallback 中进行的 dom 变更，只能在下一帧的 Update Rendering 阶段进行渲染

stop 时 piEstimate innerHTML 帧渲染前后不一致

requestIdleCallback 有兼容性问题，常用 requestAnimationFrame 和 MessageChannel 去 fallback

# requestAnimationFrame + MessageChannel

requestAnimationFrame 将在事件循环中 UI Render 阶段 (opens new window)的实际渲染前执行，可以简单理解为帧渲染初期

MessageChannel 用来收发消息开启一个宏任务，相比 setTimeout 可以更快执行（4ms的原因）

我们在 requestAnimationFrame 设置一个标记时间点 markPoint ，并通过 MessageChannel 发起一个宏任务，设置该宏任务的过期时间为 markPoint + timeout(16ms) ，超过这个时间，任务不再执行

这样可以保证宏任务不会因为执行太久导致卡顿和掉帧

<!DOCTYPE html>
<html>

<head>
  <title>Scheduling background tasks using requestIdleCallback</title>
</head>

<body>
  <script>
    const timeout = 16 // 默认一帧为16ms
    var requestId = 0;
    var pointsTotal = 0;
    var pointsInside = 0;
    let currentTask = {
      startTime: 0,
      endTime: 0,
    }
    var channel = new MessageChannel();
    var sender = channel.port2; // port2 用来发消息
    channel.port1.onmessage = function (event) {
      if (performance.now() > currentTask.endTime) {
        // 可能是插入了其他宏任务导致该任务过期，直接 rAF
        requestId = requestAnimationFrame(markPoint)
        return
      }
      refinePi(currentTask.endTime)
      requestId = requestAnimationFrame(markPoint)
    }
    function piStep() {
      var r = 1;
      var x = Math.random() * r;
      var y = Math.random() * r;
      return (Math.pow(x, 2) + Math.pow(y, 2) < Math.pow(r, 2))
    }
    function refinePi(deadline) {
      while (performance.now() < deadline) {
        if (piStep()) {
          pointsInside++;
        }
        pointsTotal++;
      }
      currentEstimate = (4 * pointsInside / pointsTotal);
      textElement = document.getElementById("piEstimate");
      textElement.innerHTML = "Pi Estimate: " + currentEstimate;
    }
    function markPoint(timestamp) {
      currentTask.startTime = timestamp
      currentTask.endTime = timestamp + timeout
      // 下轮宏任务
      sender.postMessage("")
    }
    function start() {
      requestId = requestAnimationFrame(markPoint)
    }
    function stop() {
      // alert(1)
      if (requestId)
        window.cancelAnimationFrame(requestId);
      requestId = 0;
    }
    function handle() {
      let start = performance.now()
      while (performance.now() - start < 100) { }
    }
  </script>

  <button onclick="start()">Click me to start!</button>
  <button onclick="stop()">Click me to stop!</button>
  <button onclick="handle()">执行耗时任务，观察 PI 的计算情况</button>
  <div id="piEstimate">Not started</div>
</body>

</html>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

在线测试 (opens new window)

# 拓展阅读

编辑

#HTML

上次更新: 2024/09/01, 23:56:56