-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
2008 lines (821 loc) · 170 KB
/
index.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html class="theme-next muse use-motion" lang="zh-Hans">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />
<link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
<link href="/css/main.css?v=5.1.2" rel="stylesheet" type="text/css" />
<meta name="keywords" content="Hexo, NexT" />
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.2" />
<meta name="description" content="大前端">
<meta name="keywords" content="React,Flutter">
<meta property="og:type" content="website">
<meta property="og:title" content="前路漫漫 唯风作伴">
<meta property="og:url" content="https://github.com/OPY-bbt/index.html">
<meta property="og:site_name" content="前路漫漫 唯风作伴">
<meta property="og:description" content="大前端">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="前路漫漫 唯风作伴">
<meta name="twitter:description" content="大前端">
<script type="text/javascript" id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Muse',
sidebar: {"position":"left","display":"post","offset":12,"offset_float":12,"b2t":false,"scrollpercent":false,"onmobile":false},
fancybox: true,
tabs: true,
motion: true,
duoshuo: {
userId: '0',
author: '博主'
},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
hits: {"per_page":10},
labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
}
};
</script>
<link rel="canonical" href="https://github.com/OPY-bbt/"/>
<title>前路漫漫 唯风作伴</title>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<div class="container sidebar-position-left
page-home
">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-wrapper">
<div class="site-meta ">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">前路漫漫 唯风作伴</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<p class="site-subtitle">脚踏大地 仰望星空</p>
</div>
<div class="site-nav-toggle">
<button>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon fa fa-fw fa-home"></i> <br />
首页
</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section">
<i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
归档
</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section">
<i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
标签
</a>
</li>
</ul>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://github.com/OPY-bbt/2021/05/09/光栅图形学-扫描转换算法/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="山石岩">
<meta itemprop="description" content="">
<meta itemprop="image" content="https://avatars3.githubusercontent.com/u/16717283?s=460&v=4">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="前路漫漫 唯风作伴">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2021/05/09/光栅图形学-扫描转换算法/" itemprop="url">光栅图形学-扫描转换算法</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2021-05-09T22:37:05+08:00">
2021-05-09
</time>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2021/05/09/光栅图形学-扫描转换算法/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2021/05/09/光栅图形学-扫描转换算法/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>本文介绍了直线段、圆弧、多边形扫描转换算法。使用 Javascript 实现多边形扫描算法。</p>
<h2 id="直线段的的扫描转换算法"><a href="#直线段的的扫描转换算法" class="headerlink" title="直线段的的扫描转换算法"></a>直线段的的扫描转换算法</h2><p>记得在上大学的时候，刚开始学单片机。老爸让我在液晶屏上实现画出一次方程直线的功能，当时捣鼓了一上午才搞定一条歪歪扭扭的线。这几年时间过去，又在看如何画直线，果然是轮回。<br>主要有三种方式 数值微分(DDA)法、中点画线法、布雷森汉姆（Bresenham）算法</p>
<h4 id="DDA算法"><a href="#DDA算法" class="headerlink" title="DDA算法"></a>DDA算法</h4><p>求出直线斜率 k。当 |k| <= 1 时，x每递增1时，y递增k。当 |k| > 1 时，y 每增加1，x 增加 1 / k。这样才能保证点是连续的。<br>在这个算法中，y 和 k 必须用浮点数表示，而且每一步都要对 y 进行四舍五入取整，效率不高。因为是对每个像素进行处理，所以在图形学中效率非常重要，后面也会有对浮点数以及乘除的优化。<br>当 |k| <= 1 时，伪代码如下</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">DDALine</span><span class="params">(<span class="keyword">int</span> x0, <span class="keyword">int</span> y0, <span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> color)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> x;</span><br><span class="line"> <span class="keyword">float</span> dx, dy, y, k,</span><br><span class="line"> dx = x1 - x0,</span><br><span class="line"> dy = y1 - y0,</span><br><span class="line"> k = dy / dx,</span><br><span class="line"> y = y0;</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">for</span> (x = x0; x <= x1; x++) {</span><br><span class="line"> drawpixel(x, <span class="keyword">int</span>(y + <span class="number">0.5</span>), color);</span><br><span class="line"> y = y + k;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h4 id="中点画线法"><a href="#中点画线法" class="headerlink" title="中点画线法"></a>中点画线法</h4><p>通过观察下图可以看到，假如当前点为 P，则下一个像素点有两种情况，P1和P2。<br>M点为P1，P2中点，Q点为理想直线上的点。当 M 在 Q 下方，P2 应为下一个像素点，当 M 在 Q 上方，P1 应为下一个像素点。所以可以通过比较F(Mx, My) 和 0 的大小，可以确定下个像素点位置。</p>
<p><code>d = F(M) = F(Px + 1, Py + 0.5) = a(Px + 1) + b(Py + 0.5) + c;</code></p>
<p><img src="../images/computer_graphic_mid.png" alt="mid"></p>
<p>对于过 （x0, y0）(x1, y1) 两点的直线L来说，采用方程 F(x, y) = ax+ by + c = 0表示。其中 a = y0 - y1, b = x1 - x0, c = x0y1 - x1y0;</p>
<p>利用此方程可以画出直线，但是这种方式需要进行 4 个加法和两个乘法。事实上，d 是 Px, Py的线性函数，所以可以使用增量计算的方法优化。<br>若 d >= 0，则取正右方像素 P1,那么判断下一个像素位置就是<code>d1 = F(Px + 2, Py + 0.5) = d + a;</code>,增量为 a.<br>若 d < 0，则取右上方像素P2，那么判断下一个像素位置就是 <code>d1 = F(Px + 2, Py + 1.5) = d + a + b;</code>增量为 a + b<br>设从点（x0， y0）开始画线，d的初值为<code>d0 = F(x0 + 1, y0 + 0.5) = F(x0， y0) + a + 0.5b = a + 0.5b</code><br>由于使用的只是 d 的符号，而 d 的增量都是整数，只有初始值包含小数，所以用 2d 代替 d 来摆脱浮点运算。优化过后的伪代码如下：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> Midpoint <span class="title">Line</span><span class="params">(<span class="keyword">int</span> x0, <span class="keyword">int</span> y0, <span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> color)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> a, b, d1, d2, d, x, y;</span><br><span class="line"> a = y0 - y1, b = x1 - x0, d = <span class="number">2</span> * a + b;</span><br><span class="line"> d1 = <span class="number">2</span> * a, d2 = <span class="number">2</span> * (a + b);</span><br><span class="line"> x = x0, y = y0;</span><br><span class="line"> drawpixel(x, y, color;</span><br><span class="line"> <span class="keyword">while</span>(x < x1) </span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (d < <span class="number">0</span>)</span><br><span class="line"> { x++, y++, d += d2;}</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {x++, d += d1;}</span><br><span class="line"> drawpixel(x, y, color);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h4 id="Bresenham"><a href="#Bresenham" class="headerlink" title="Bresenham"></a>Bresenham</h4><p>类似于中点画线法，通过偏移量d与0.5的比较来确定像素点所在的位置，其中d1 = d0 + k;</p>
<p><img src="../images/computer_graphic_bresenham.png" alt="bresenham"></p>
<h2 id="圆弧的的扫描转换算法"><a href="#圆弧的的扫描转换算法" class="headerlink" title="圆弧的的扫描转换算法"></a>圆弧的的扫描转换算法</h2><p>圆有四条对称轴，所以已知圆弧上一点（x, y），可以得到其关于4条对称轴的其他 7 个点，这种性质被称为八对称性。因此，只要扫描转换 1/8 圆弧，就可以用八对称性求出整个圆的像素集.具体算法也是类似于中点画线法，只不过函数方程变为圆。</p>
<p><img src="../images/computer_graphic_circle.png" alt="circle"></p>
<h2 id="多边形的的扫描转换算法"><a href="#多边形的的扫描转换算法" class="headerlink" title="多边形的的扫描转换算法"></a>多边形的的扫描转换算法</h2><p>在计算机图形学中，多边形有顶点和点阵两种表现方式。<br>顶点表示直观，几何意义强，占内存少，易于进行几何变换。但不利于着色。<br>点阵表示丢失了许多几何信息，但便于帧缓冲器表示图形。光栅图形学的本质问题是把多边形的顶点表示转换为点阵表示，这种转换被称为多边形的扫描转换。其中有两种方法，扫描线算法和边界标志算法，下方会用 javascript 在 canvas 中实现扫描线算法。</p>
<h4 id="扫描线算法"><a href="#扫描线算法" class="headerlink" title="扫描线算法"></a>扫描线算法</h4><p>通过计算扫描线与多边形的相交区间，再用要求的颜色显示这区间的像素，以完成填充工作。区间的端点通过计算扫描线与多边形的边界线交点获得。<br>对于一条扫描线，主要分为下面四个步骤：</p>
<ol>
<li>求交。计算扫描线与多边形各边的交点</li>
<li>排序。把所有交点按 x 值的递增顺序排序</li>
<li>配对。将1和2，3和4等等配对</li>
<li>填色。相交区间内的像素置为多边形的颜色</li>
</ol>
<p><img src="../images/computer_graphic_poly.png" alt="circle"></p>
<p>由于反复求交运算效率低下，为了优化这个问题，将引入两个概念AET和NET。<br>将与当前扫描线相交的边称为活性边(AET)。如果某边的较低端点为ymin，则改边就放在扫描线 ymin 的新边表(NET)中。边在 AET 和 NET 中存储使用单链表的形式。每个节点包含三个信息，1、存当前扫描线与边的交点坐标x值，2、从当前扫描线到下一条扫描线间x的增量 dx；3、存该边所交的最高扫描线号ymax。<br>有了NET之后，就可以通过 NET 来维护 AET，如果当前扫描线在 NET中 有值时，就加入到 AET中，每次扫描线加一，就在原来x的基础上增加dx。当扫描线号大于 ymax时，将其从AET中删除。伪代码如下</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">polyfill</span><span class="params">(polygon, color)</span></span></span><br><span class="line"><span class="function"><span class="keyword">int</span> color</span></span><br><span class="line">多边形 polygon</span><br><span class="line">{</span><br><span class="line"> <span class="keyword">for</span> (各条扫描线 i) {</span><br><span class="line"> 初始化新边表头指针 NET[i]</span><br><span class="line"> 把 ymin = i 的边放进 NET[i]</span><br><span class="line"> }</span><br><span class="line"> y = 最低扫描线号</span><br><span class="line"> 初始化活性边表为空</span><br><span class="line"> <span class="keyword">for</span> (各条扫描线i) {</span><br><span class="line"> 把 NET[i] 中的边结点用插入排序法插入 AET, 使之按 x 坐标递增顺序排列</span><br><span class="line"> 若允许多边形的边自相交，则用冒泡排序法对 AET 重新排序</span><br><span class="line"> 遍历 AET， 把配对交点区间（左闭右开）上的像素（x，y），用 drawpixel(x, y, color) 改写像素颜色值</span><br><span class="line"> 遍历 AET，把 ymax = i 的结点从 AET 中删除，并把 ymax > i 结点的 x 值递增 dx;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>使用 javascript 实现此算法:</p>
<figure class="highlight html"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"><!DOCTYPE html></span></span><br><span class="line"><span class="tag"><<span class="name">html</span> <span class="attr">lang</span>=<span class="string">"en"</span>></span></span><br><span class="line"><span class="tag"><<span class="name">head</span>></span></span><br><span class="line"> <span class="tag"><<span class="name">meta</span> <span class="attr">charset</span>=<span class="string">"UTF-8"</span>></span></span><br><span class="line"> <span class="tag"><<span class="name">meta</span> <span class="attr">name</span>=<span class="string">"viewport"</span> <span class="attr">content</span>=<span class="string">"width=device-width, initial-scale=1.0"</span>></span></span><br><span class="line"> <span class="tag"><<span class="name">title</span>></span>Document<span class="tag"></<span class="name">title</span>></span></span><br><span class="line"><span class="tag"></<span class="name">head</span>></span></span><br><span class="line"><span class="tag"><<span class="name">body</span>></span></span><br><span class="line"> <span class="tag"><<span class="name">canvas</span> <span class="attr">width</span>=<span class="string">"400"</span> <span class="attr">height</span>=<span class="string">"400"</span>></span><span class="tag"></<span class="name">canvas</span>></span></span><br><span class="line"> <span class="tag"><<span class="name">script</span>></span><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> WIDTH = <span class="number">400</span>;</span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> HEIGHT = <span class="number">400</span>;</span></span><br><span class="line"><span class="javascript"> <span class="comment">// 输入三角形中的三个顶点</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> POINTS = [[<span class="number">200</span>, <span class="number">50</span>], [<span class="number">150</span>, <span class="number">300</span>], [<span class="number">300</span>, <span class="number">350</span>]];</span></span><br><span class="line"><span class="undefined"> </span></span><br><span class="line"><span class="undefined"> </span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> AET = []; <span class="comment">// 活性边</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> NET = {}; <span class="comment">// 新边表，这里为了方便使用数组</span></span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> ctx = <span class="built_in">document</span>.body.querySelector(<span class="string">'canvas'</span>).getContext(<span class="string">'2d'</span>);</span></span><br><span class="line"><span class="javascript"> <span class="comment">// 将 canvas 中的坐标系与笛卡尔坐标系保持一致，方便绘制</span></span></span><br><span class="line"><span class="undefined"> ctx.translate(0, HEIGHT);</span></span><br><span class="line"><span class="undefined"> ctx.scale(1, -1);</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> POINTS.forEach(<span class="function"><span class="params">p</span> =></span> {</span></span><br><span class="line"><span class="javascript"> drawPixel(p[<span class="number">0</span>], p[<span class="number">1</span>], <span class="string">'#F00'</span>, <span class="number">3</span>);</span></span><br><span class="line"><span class="undefined"> })</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 初始化 NET</span></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 如果某边的较低端点为ymin,则该边就放在扫描线ymin的新边表中。</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i < POINTS.length; i++) {</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 由 point 和 next_point 组成的边</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> point = POINTS[i];</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> j = i === POINTS.length - <span class="number">1</span> ? <span class="number">0</span> : i + <span class="number">1</span>;</span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> next_point = POINTS[j];</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> minY_point = point[<span class="number">1</span>] <= next_point[<span class="number">1</span>] ? point : next_point;</span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> maxY_point = point[<span class="number">1</span>] <= next_point[<span class="number">1</span>] ? next_point : point;</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> newNode = {</span></span><br><span class="line"><span class="undefined"> x: minY_point[0],</span></span><br><span class="line"><span class="javascript"> <span class="comment">// <span class="doctag">TODO:</span> 没有考虑水平的情况</span></span></span><br><span class="line"><span class="undefined"> dx: (maxY_point[0] - minY_point[0]) / (maxY_point[1] - minY_point[1]),</span></span><br><span class="line"><span class="undefined"> ymax: maxY_point[1],</span></span><br><span class="line"><span class="javascript"> next: <span class="literal">null</span>,</span></span><br><span class="line"><span class="undefined"> points: [i, j],</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> ymin = minY_point[<span class="number">1</span>];</span></span><br><span class="line"><span class="undefined"> </span></span><br><span class="line"><span class="javascript"> <span class="comment">// 将点存在新边表中，如果新边表中已经存在值则放在链表尾部</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">if</span> (NET[ymin]) {</span></span><br><span class="line"><span class="javascript"> <span class="keyword">let</span> current = NET[ymin];</span></span><br><span class="line"><span class="javascript"> <span class="keyword">while</span> (current.next) {</span></span><br><span class="line"><span class="undefined"> current = current.next;</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> current.next = newNode;</span></span><br><span class="line"><span class="javascript"> } <span class="keyword">else</span> {</span></span><br><span class="line"><span class="undefined"> NET[ymin] = newNode;</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="javascript"> <span class="built_in">console</span>.log(<span class="string">'NET'</span>, NET);</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 遍历所有扫描边，绘制图形</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i < HEIGHT; i++) {</span></span><br><span class="line"><span class="javascript"> <span class="comment">// 假如新边表有值，将节点插入 AET 中</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">if</span> (NET[i]) {</span></span><br><span class="line"><span class="javascript"> <span class="keyword">let</span> current = NET[i];</span></span><br><span class="line"><span class="javascript"> <span class="keyword">while</span> (current) {</span></span><br><span class="line"><span class="javascript"> <span class="comment">// NET 插入排序法 进 AET</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">let</span> j = <span class="number">0</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">for</span> (; j < AET.length; j++) {</span></span><br><span class="line"><span class="javascript"> <span class="keyword">if</span> (AET[j].x > current.x) {</span></span><br><span class="line"><span class="javascript"> <span class="keyword">break</span>;</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> AET.splice(j, 0, current);</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="undefined"> current = current.next;</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 遍历 AET 表，如果扫描边等于节点 ymax 值，</span></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 则说明已经超出此线段范围，从 AET 中删除。</span></span></span><br><span class="line"><span class="javascript"> <span class="comment">// 否则，x 值递增 dx</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j < AET.length; j++) {</span></span><br><span class="line"><span class="javascript"> <span class="keyword">const</span> node = AET[j];</span></span><br><span class="line"><span class="javascript"> <span class="keyword">if</span> (node.ymax === i) {</span></span><br><span class="line"><span class="javascript"> <span class="comment">// 删除此节点</span></span></span><br><span class="line"><span class="undefined"> AET.splice(j, 1);</span></span><br><span class="line"><span class="undefined"> j--;</span></span><br><span class="line"><span class="javascript"> } <span class="keyword">else</span> <span class="keyword">if</span> (node.ymax >= i) {</span></span><br><span class="line"><span class="undefined"> node.x = node.x + node.dx</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> </span></span><br><span class="line"><span class="javascript"> <span class="comment">// 将 AET 中的节点，两两配对，绘制两点之间的线段</span></span></span><br><span class="line"><span class="javascript"> <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j < AET.length; j += <span class="number">2</span>) {</span></span><br><span class="line"><span class="javascript"> <span class="keyword">if</span> (AET[j] && AET[j + <span class="number">1</span>]) {</span></span><br><span class="line"><span class="undefined"> drawPixels(AET[j].x, AET[j + 1].x, i);</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="built_in">console</span>.log(<span class="string">'AET'</span>, AET);</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="function"><span class="keyword">function</span> <span class="title">drawPixels</span>(<span class="params">x1, x2, y</span>) </span>{</span></span><br><span class="line"><span class="javascript"> <span class="keyword">for</span> (<span class="keyword">let</span> i = x1; i < x2; i++) {</span></span><br><span class="line"><span class="undefined"> drawPixel(i, y);</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"></span></span><br><span class="line"><span class="javascript"> <span class="function"><span class="keyword">function</span> <span class="title">drawPixel</span>(<span class="params">x, y, color = <span class="string">'#000'</span>, size = <span class="number">1</span></span>) </span>{</span></span><br><span class="line"><span class="undefined"> ctx.fillStyle = color;</span></span><br><span class="line"><span class="javascript"> ctx.fillRect(<span class="built_in">Math</span>.round(x), <span class="built_in">Math</span>.round(y), size, size);</span></span><br><span class="line"><span class="undefined"> }</span></span><br><span class="line"><span class="undefined"></span><span class="tag"></<span class="name">script</span>></span></span><br><span class="line"><span class="tag"></<span class="name">body</span>></span></span><br><span class="line"><span class="tag"></<span class="name">html</span>></span></span><br></pre></td></tr></table></figure>
<p>结果如下：</p>
<p><img src="../images/computer_graphic_effect.png" alt="circle"></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://github.com/OPY-bbt/2021/04/15/Chrome浏览器工作原理/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="山石岩">
<meta itemprop="description" content="">
<meta itemprop="image" content="https://avatars3.githubusercontent.com/u/16717283?s=460&v=4">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="前路漫漫 唯风作伴">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2021/04/15/Chrome浏览器工作原理/" itemprop="url">Chrome 浏览器原理</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2021-04-15T22:37:05+08:00">
2021-04-15
</time>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2021/04/15/Chrome浏览器工作原理/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2021/04/15/Chrome浏览器工作原理/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="Part-1-浏览器架构"><a href="#Part-1-浏览器架构" class="headerlink" title="Part 1 浏览器架构"></a>Part 1 浏览器架构</h3><p>CPU, GPU, Memory, 多进程架构, 通过 IPC(Inter Process Communication)通信。包含的几个进程及内容:</p>
<ul>
<li>Browser process: 地址栏，书签，前进，后退，网络请求和文件</li>
<li>Render process: 控制所有 tab 中显示的内容</li>
<li>Plugin: 例如 flash</li>
<li>GPU: 处理 GPU 任务</li>
</ul>
<p>通过 Chrome 右上角-更多工具-任务管理器, 可以查看进程, 一般情况下，每个 Tab 页都是一个 render process，使得页面之间互不影响，并且更加安全。如果多个tab页，但网站之间是同域的，还是会共享一个 render process。</p>
<p>Site Isolation 技术实现了即使是跨域的 iframe，也会使用不同的 render process。这意味着一个 Tab 页，可能对应多个 render process。此技术是里程碑式的，没有想象的这么简单，比如 Ctrl + F 必须在多个Render process中搜索。</p>
<h3 id="Part-2-在导航期间发生了什么"><a href="#Part-2-在导航期间发生了什么" class="headerlink" title="Part 2 在导航期间发生了什么"></a>Part 2 在导航期间发生了什么</h3><p>导航从 Browser process开始，Browser process 中包含了 UI thread（绘制按钮和搜索框）、Network thread（请求数据）、Storage thread（文件）。</p>
<ul>
<li>（处理输入）当用户在地址栏输入文字时，UI thread 会解析字符串，判断是搜索文字还是URL地址。</li>
<li>（开始导航）当用户点击 Enter 按键，UI thread 会初始化网络请求获取内容。Network thread 会进行 DNS查询、建立 TLS连接。</li>
<li>（读响应数据）当获取到 Response body时，Network thread 会通过 Content-Type 选择合适的处理方式。如果请求是HTML file，会将数据传递给 Renderer process，如果是 zip 或者其他下载文件，会传递给下载管理器。</li>
<li>（找到 renderer process）如果请求返回数据通过了安全检查，Network thread 会通知 UI thread，UI thread 会使用 Renderer process 渲染页面。</li>
<li>（提交 navigation）数据会通过IPC从 Browser process 发到 Renderer process。如果 navigation 已经完成，Renderer process 会通知 Browser [Page loaded], 地址栏旁边的spinner将会消失。提交导航后，Renderer process 将会继续加载资源和渲染页面，具体细节，会在后面说到。</li>
</ul>
<h3 id="Part-3-渲染器进程"><a href="#Part-3-渲染器进程" class="headerlink" title="Part 3 渲染器进程"></a>Part 3 渲染器进程</h3><p>渲染器进程处理tab页中所有的事情。main thread处理大部分代码，一些web worker 和 service worker相关的代码会交给 worker thread。compositor thread 和 raster thread 负责渲染页面更有效率和流畅。</p>
<p>renderer process 核心工作是将 HTML，CSS， JS 转变成可交互页面。</p>
<p>main thread 解析HTML文件为 DOM 结构，HTML解析器遇到 script 标签会停止解析，直到加载，解析，执行 js 代码完成之后。因为 js 可能会导致 DOM 结构改变。</p>
<p>得到DOM之后，main thread 解析 CSS 得到每个 DOM Node 的 computed style。</p>
<p>得到 computed style 之后，准备生成 layout tree，获取元素的几何结构，例如元素 x，y坐标，盒尺寸等。</p>
<p>然后是 paint 步骤，决定绘制顺序，比如 z-index。结果是生成绘制指令不是真的绘制。main thread 会遍历 layout tree 生成 paint records(类似 “background first, then text, then rectangle”.)。</p>
<p>得到 paint 指令之后，将这些信息转变为屏幕上的像素被称为栅格化(rasterizing)。在 Chrome 早期的时候，初始化时栅格化 viewport 中的内容，当用户滚动之后，在对新内容进行栅格化。在后期版本中，又增加了一个 合成(compositing)步骤。</p>
<p>Compositing 会将页面分为不同的层，并且对每一层进行栅格化。当有滚动、动画发生时，仅通过合成来获得新的帧。为了判断元素应该被放在哪一层里，主线程会通过遍历 layout tree 去创建 layer tree（可以通过will-change生成新的layer）。</p>
<p>一旦 layer tree 和 paint order 准备就绪，主线程会将信息提交给 compositor thread。然后在栅格化每一层。layer 可能会是整个页面大小，所以 compositor thread 会把layer切分成瓦片(tile)。然后栅格进程对tile进行栅格化，并将结果保存在 GPU中。</p>
<p>当 tile 被栅格化之后，compositor thread 收集 tile 信息，draw quads 和 compositor frame（draw quads 集合）。然后合成帧被提交给浏览器进程。然后被发送给GPU。合成的好处就是不需要主线程参与，就可以生成合成帧，保证动画流畅。</p>
<h3 id="Part-4-处理用户事件输入"><a href="#Part-4-处理用户事件输入" class="headerlink" title="Part 4 处理用户事件输入"></a>Part 4 处理用户事件输入</h3><p>当用户touch事件发生时，Browser process 首先接收到，然后发送事件类型和坐标给 Renderer process 中合成线程，然后通知 main thread，其查找事件目标元素和运行事件监听器。</p>
<p>合成线程会将页面中带有事件监听器的区域标记为 Non-Fast Scrollable Region，如果事件在这个区域发生，合成线程会发送给 main thread。如果这个区域没有时间发生，则不需要等待 main thread。所以，大量的事件代理，也会影响性能，因为这样会导致标记区域变大。为了防止这种事情发生，通过设置 passive：true(表示永远不会调用 preventDefault)，可以告诉浏览器虽然需要主线程监听，但是合成线程可以继续生成合成帧，不必等待，可以使得滚动更加顺滑。</p>
<p>main thread 通过 x，y 坐标和查找 paint records 来确定事件目标</p>
<p>屏幕一般刷新率为60hz，而move事件一般为 60-120hz，所以 Chrome会合并持续事件（wheel，mousewheel，mousemove，touchmove）到下一个requestAnimationFrame 之前触发，避免无效的事件触发。但是，如果你需要精确的用户事件坐标，如果绘图软件等，那么就需要使用 getCoalescedEvents。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">window</span>.addEventListener(<span class="string">'pointermove'</span>, event => {</span><br><span class="line"> <span class="keyword">const</span> events = event.getCoalescedEvents();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> event <span class="keyword">of</span> events) {</span><br><span class="line"> <span class="keyword">const</span> x = event.pageX;</span><br><span class="line"> <span class="keyword">const</span> y = event.pageY;</span><br><span class="line"> <span class="comment">// draw a line using x and y coordinates.</span></span><br><span class="line"> }</span><br><span class="line">});</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://github.com/OPY-bbt/2021/04/11/最小生成树MST的两种算法/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="山石岩">
<meta itemprop="description" content="">
<meta itemprop="image" content="https://avatars3.githubusercontent.com/u/16717283?s=460&v=4">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="前路漫漫 唯风作伴">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2021/04/11/最小生成树MST的两种算法/" itemprop="url">计算最小生成树MST的两种算法</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2021-04-11T22:37:05+08:00">
2021-04-11
</time>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2021/04/11/最小生成树MST的两种算法/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2021/04/11/最小生成树MST的两种算法/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>MST(minimum-spanning-tree)算法，用于计算在加权无向连通图中，生成最小权重的树。</p>
<p><img src="../images/mit.png" alt="MIT"></p>
<p>使用邻接矩阵表示上图：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> graph = [</span><br><span class="line"> [<span class="number">0</span>, <span class="number">2</span>, <span class="number">4</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>],</span><br><span class="line"> [<span class="number">2</span>, <span class="number">0</span>, <span class="number">2</span>, <span class="number">4</span>, <span class="number">2</span>, <span class="number">0</span>],</span><br><span class="line"> [<span class="number">4</span>, <span class="number">2</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">3</span>, <span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>, <span class="number">4</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">3</span>, <span class="number">2</span>],</span><br><span class="line"> [<span class="number">0</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">3</span>, <span class="number">0</span>, <span class="number">2</span>],</span><br><span class="line"> [<span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">2</span>, <span class="number">2</span>, <span class="number">0</span>],</span><br><span class="line">];</span><br></pre></td></tr></table></figure>
<p>主要有两种算法：</p>
<ul>
<li>Prim（普里姆） 算法</li>
<li>Kruskal（克鲁斯卡尔） 算法</li>
</ul>
<h3 id="Prim（普里姆）算法：每次从未遍历的节点中选择最小权重点连线"><a href="#Prim（普里姆）算法：每次从未遍历的节点中选择最小权重点连线" class="headerlink" title="Prim（普里姆）算法：每次从未遍历的节点中选择最小权重点连线"></a>Prim（普里姆）算法：每次从未遍历的节点中选择最小权重点连线</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">prim</span>(<span class="params"></span>) </span>{</span><br><span class="line"> <span class="keyword">var</span> parent = [],</span><br><span class="line"> key = [],</span><br><span class="line"> visited = [],</span><br><span class="line"> length = graph.length,</span><br><span class="line"> i;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 把所有顶点 key 设置为无限大，未访问</span></span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < length; i++) {</span><br><span class="line"> key[i] = <span class="built_in">Number</span>.MAX_SAFE_INTEGER;</span><br><span class="line"> visited[i] = <span class="literal">false</span>;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// 选择第一个 key 作为第一个顶点</span></span><br><span class="line"> key[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// 第一个顶点为 MST 根结点，所以 parent 为 -1</span></span><br><span class="line"> parent[<span class="number">0</span>] = <span class="number">-1</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 对所有顶点求 MST</span></span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < length - <span class="number">1</span>; i++) {</span><br><span class="line"> <span class="comment">// 从未处理集合中选出最小的key</span></span><br><span class="line"> <span class="keyword">var</span> u = minKey(key, visited);</span><br><span class="line"> <span class="comment">// 设置未true，避免重复计算</span></span><br><span class="line"> visited[u] = <span class="literal">true</span>;</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// 遍历所有点，如果得出更小的权重，则在 parent 中 保存路径</span></span><br><span class="line"> <span class="comment">// 并且更新顶点权重值 key</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">var</span> v = <span class="number">0</span>; v < length; v++) {</span><br><span class="line"> <span class="keyword">if</span> (graph[u][v] &&</span><br><span class="line"> visited[v] === <span class="literal">false</span> &&</span><br><span class="line"> graph[u][v] < key[v]) {</span><br><span class="line"> parent[v] = u;</span><br><span class="line"> key[v] = graph[u][v];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> parent;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">minKey</span>(<span class="params">key, visited</span>) </span>{</span><br><span class="line"> <span class="keyword">var</span> min = <span class="built_in">Number</span>.MAX_SAFE_INTEGER,</span><br><span class="line"> minIndex = <span class="number">-1</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">var</span> v = <span class="number">0</span>; v < key.length; v++) {</span><br><span class="line"> <span class="keyword">if</span> (visited[v] == <span class="literal">false</span> && key[v] <= min) {</span><br><span class="line"> min = key[v];</span><br><span class="line"> minIndex = v;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">return</span> minIndex;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="Kruskal（克鲁斯卡尔）-算法-每次从未遍历的边中选择最小权重的边"><a href="#Kruskal（克鲁斯卡尔）-算法-每次从未遍历的边中选择最小权重的边" class="headerlink" title="Kruskal（克鲁斯卡尔） 算法: 每次从未遍历的边中选择最小权重的边"></a>Kruskal（克鲁斯卡尔） 算法: 每次从未遍历的边中选择最小权重的边</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">kruskal</span>(<span class="params"></span>) </span>{</span><br><span class="line"> <span class="keyword">const</span> INF = <span class="built_in">Number</span>.MAX_SAFE_INTEGER;</span><br><span class="line"> <span class="keyword">var</span> length = graph.length;</span><br><span class="line"> <span class="keyword">var</span> parent = [];</span><br><span class="line"> <span class="keyword">var</span> ne = <span class="number">0</span>,</span><br><span class="line"> a,</span><br><span class="line"> b,</span><br><span class="line"> u,</span><br><span class="line"> v,</span><br><span class="line"> i,</span><br><span class="line"> j,</span><br><span class="line"> min;</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// 拷贝 graph 到 cost 中，方便修改和保留原始值</span></span><br><span class="line"> <span class="keyword">var</span> cost = initializeCost(graph);</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 当 MST 的边数小于顶点总数 - 1 时</span></span><br><span class="line"> <span class="keyword">while</span> (ne < length - <span class="number">1</span>) {</span><br><span class="line"> <span class="comment">// 选出权重最小边</span></span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>, min = INF; i < length; i++) {</span><br><span class="line"> <span class="keyword">for</span> (j = <span class="number">0</span>; j < length; j++) {</span><br><span class="line"> <span class="keyword">if</span> (cost[i][j] < min) {</span><br><span class="line"> min = cost[i][j];</span><br><span class="line"> u = i;</span><br><span class="line"> v = j;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// 分别找出 u，v 的祖先节点，看是否为同一节点，如果是，则跳过</span></span><br><span class="line"> <span class="comment">// 避免环路</span></span><br><span class="line"> <span class="keyword">if</span> (union(find(u, parent), find(v, parent), parent)) {</span><br><span class="line"> <span class="built_in">console</span>.log(<span class="string">"edge"</span>, u, v, graph[u][v]);</span><br><span class="line"> ne++;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// 避免重复计算</span></span><br><span class="line"> cost[u][v] = cost[v][u] = INF;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="keyword">var</span> find = <span class="function"><span class="keyword">function</span> (<span class="params">i, parent</span>) </span>{</span><br><span class="line"> <span class="keyword">while</span> (parent[i] !== <span class="literal">undefined</span>) {</span><br><span class="line"> i = parent[i];</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> i;</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="keyword">var</span> union = <span class="function"><span class="keyword">function</span> (<span class="params">i, j, parent</span>) </span>{</span><br><span class="line"> <span class="keyword">if</span> (i != j) {</span><br><span class="line"> parent[j] = i;</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="keyword">var</span> initializeCost = <span class="function"><span class="keyword">function</span>(<span class="params">graph</span>) </span>{</span><br><span class="line"> <span class="keyword">const</span> cost = [];</span><br><span class="line"> <span class="keyword">const</span> { length } = graph;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i < length; i++) {</span><br><span class="line"> cost[i] = [];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j < length; j++) {</span><br><span class="line"> <span class="keyword">if</span> (graph[i][j] === <span class="number">0</span>) {</span><br><span class="line"> cost[i][j] = INF;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> cost[i][j] = graph[i][j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> cost;</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://github.com/OPY-bbt/2021/03/14/Core-Web-Vitals/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="山石岩">
<meta itemprop="description" content="">
<meta itemprop="image" content="https://avatars3.githubusercontent.com/u/16717283?s=460&v=4">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="前路漫漫 唯风作伴">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2021/03/14/Core-Web-Vitals/" itemprop="url">Core Web Vitals</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2021-03-14T22:37:05+08:00">
2021-03-14
</time>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2021/03/14/Core-Web-Vitals/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2021/03/14/Core-Web-Vitals/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>Google总结了健康网络的三个指标，旨在提高用户体验：</p>
<ul>
<li>Largest Contentful Paint (LCP): 最大内容绘制</li>
<li>First Input Delay (FID): 首次输入延迟</li>
<li>Cumulative Layout Shift (CLS): 累积布局转移<br>指标其实分别对应网站健康度的三个方面：加载、交互性、页面稳定性。<br>本文对这篇文章做总结，包含三个部分：指标定义，如何度量，如何优化。</li>
</ul>
<h3 id="LCP"><a href="#LCP" class="headerlink" title="LCP"></a>LCP</h3><p><code>是衡量页面加载性能的核心指标，表示视口中最大的文字或者图片块渲染的时间。</code></p>
<p>largest contentful elements 有以下几类：</p>
<ul>
<li>img 标签</li>
<li>SVG 中的 image</li>
<li>设置封面的 video</li>
<li>通过 background：url()加载背景的元素</li>
<li>包含了文本节点的块级元素</li>
</ul>
<p>需要注意的是，增加元素，删除元素会可能会改变 largest contentful element。<br>并且，加载没有完成的图片，字体没有加载完成的文字，也不能被认为是 contentful element，只有当加载完成后才是。<br>如果用户与页面有交互事件的发生（点击，滑动），浏览器就不会发布新的largest- contentful-paint 事件</p>
<h4 id="测量"><a href="#测量" class="headerlink" title="测量"></a>测量</h4><p>使用 PerformanceObserver API测量</p>
<p>new PerformanceObserver((entryList) => {})<br>.observe({type: ‘largest-contentful-paint’});<br>一般来说最后一个entry的startTime就是 largest-contentful-paint 时间,但也有例外的情况，主要是和background tab 相关。</p>
<p>Google已经提供了测量工具：<a href="https://github.com/GoogleChrome/web-vitals">https://github.com/GoogleChrome/web-vitals</a></p>
<p>也存在最大的元素并不是最重要的情况，这时候就需要自定义Timing工具 <a href="https://wicg.github.io/element-timing/" target="_blank" rel="noopener">https://wicg.github.io/element-timing/</a></p>
<h4 id="优化"><a href="#优化" class="headerlink" title="优化"></a>优化</h4><p>导致LCP很糟糕的原因主要有以下几种：</p>
<ul>
<li>服务器响应慢(没错，甩锅给后端是每个前端必备的能力)</li>
<li>JS 或者 CSS 阻塞</li>
<li>资源加载慢</li>
<li>客户端渲染慢</li>
</ul>
<p>对与服务器响应慢的情况，首先使用 window.performance.timing 来测量 TTFB，看是否因为服务器的问题。然后就是服务器优化的问题了，不展开。CDN，Cache等。</p>
<p>新增知识点get: 通过 <code><link rel="preconnect" href="https://example.com" /></code> 可以提前与服务器建立连接。或者 dns-prefetch 提前获得IP地址（不过这个因为缓存的原因，只有第一次请求的时候会有提高）</p>
<p>对于CSS阻塞渲染的情况，除了常见的减小体积，内联重要的css，还有一个是异步，用一个link标签就可以搞定：<br><code><link rel="stylesheet" href="/path/to/my.css" media="print" onload="this.media='all'; this.onload=null;"></code></p>
<p>在页面初始化的时候，仅加载需要用到的CSS样式，再异步请求剩余的CSS内容是比较好的处理方法，而且有已经有webpack插件来处理 <a href="https://github.com/GoogleChromeLabs/critters">https://github.com/GoogleChromeLabs/critters</a></p>
<h3 id="FID"><a href="#FID" class="headerlink" title="FID"></a>FID</h3><p><code>用户第一次与页面交互到执行监听事件所需的时间。</code></p>
<p>当主线程繁忙（解析或者执行JS文件的时候），浏览器不会立即响应用户操作。</p>
<h4 id="测量："><a href="#测量：" class="headerlink" title="测量："></a>测量：</h4><p>因为FID的测量需要用户点击，所以在实验环境中使用Total Blocking Time（TBT）</p>
<h4 id="优化："><a href="#优化：" class="headerlink" title="优化："></a>优化：</h4><ul>
<li>超过50ms的任务被认为是长任务。分割长任务为多个小的，异步执行任务是有效的方式。</li>
<li>使用 webworker</li>
</ul>
<h3 id="CLS"><a href="#CLS" class="headerlink" title="CLS"></a>CLS</h3><p><code>元素改变位置的得分总和</code></p>
<p>分数是影响分数和距离分数的乘积</p>
<p>layout shift score = impact fraction * distance fraction<br>impact fraction 代表前后两帧中，不稳定元素占视口的比例</p>
<p>distance fraction 代表所有不稳定元素中移动距离占视口的最大比例</p>
<h4 id="优化：-1"><a href="#优化：-1" class="headerlink" title="优化："></a>优化：</h4><ul>
<li>图片和视频需要加上尺寸属性</li>
<li>除非用户交互，否则不要在已有的元素上插入新的元素</li>
<li>使用 transform 动画</li>
</ul>
<h3 id="参考文档："><a href="#参考文档：" class="headerlink" title="参考文档："></a>参考文档：</h3><p><a href="https://web.dev/learn-web-vitals/" target="_blank" rel="noopener">https://web.dev/learn-web-vitals/</a><br><a href="https://web.dev/optimize-lcp/" target="_blank" rel="noopener">https://web.dev/optimize-lcp/</a><br><a href="https://wicg.github.io/element-timing/" target="_blank" rel="noopener">https://wicg.github.io/element-timing/</a><br><a href="https://github.com/filamentgroup/loadCSS/blob/master/README.md">https://github.com/filamentgroup/loadCSS/blob/master/README.md</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://github.com/OPY-bbt/2021/02/01/从测试看react源码-schedulerBrowser/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="山石岩">
<meta itemprop="description" content="">
<meta itemprop="image" content="https://avatars3.githubusercontent.com/u/16717283?s=460&v=4">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="前路漫漫 唯风作伴">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2021/02/01/从测试看react源码-schedulerBrowser/" itemprop="url">从测试看react源码_schedulerBrowser</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2021-02-01T22:00:00+08:00">
2021-02-01
</time>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2021/02/01/从测试看react源码-schedulerBrowser/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2021/02/01/从测试看react源码-schedulerBrowser/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p><code>主要测试 Scheduler 在浏览器中的运行。主要利用 MessageChannel API 进行异步执行 Task</code></p>
<h3 id="environment"><a href="#environment" class="headerlink" title="environment"></a>environment</h3><p>模拟浏览器 MessageChannel API，Mock了 port1 用于异步 onmessage，port2 用于 postmessage<br>在 port1的 onmessage 赋值了 performWorkUntilDeadline，此函数执行work直至当前 时间切片结束，默认时间切片时间为5ms，时间切片结束，将会把控制权交还给主线程，用于响应用户事件等。</p>
<h5 id="1-task-that-finishes-before-deadline"><a href="#1-task-that-finishes-before-deadline" class="headerlink" title="1. task that finishes before deadline"></a>1. task that finishes before deadline</h5><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">it(<span class="string">'task that finishes before deadline'</span>, () => {</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'Task'</span>);</span><br><span class="line"> });</span><br><span class="line"> runtime.assertLog([<span class="string">'Post Message'</span>]);</span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([<span class="string">'Message Event'</span>, <span class="string">'Task'</span>]);</span><br><span class="line">});</span><br></pre></td></tr></table></figure>
<h5 id="2-task-with-continuation"><a href="#2-task-with-continuation" class="headerlink" title="2. task with continuation"></a>2. task with continuation</h5><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line">it(<span class="string">'task with continuation'</span>, () => {</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'Task'</span>);</span><br><span class="line"> <span class="keyword">while</span> (!Scheduler.unstable_shouldYield()) {</span><br><span class="line"> runtime.advanceTime(<span class="number">1</span>);</span><br><span class="line"> }</span><br><span class="line"> runtime.log(<span class="string">`Yield at <span class="subst">${performance.now()}</span>ms`</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="function"><span class="params">()</span> =></span> {</span><br><span class="line"> runtime.log(<span class="string">'Continuation'</span>);</span><br><span class="line"> };</span><br><span class="line"> });</span><br><span class="line"> runtime.assertLog([<span class="string">'Post Message'</span>]);</span><br><span class="line"></span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([</span><br><span class="line"> <span class="string">'Message Event'</span>,</span><br><span class="line"> <span class="string">'Task'</span>,</span><br><span class="line"> <span class="string">'Yield at 5ms'</span>,</span><br><span class="line"> <span class="string">'Post Message'</span>,</span><br><span class="line"> ]);</span><br><span class="line"></span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([<span class="string">'Message Event'</span>, <span class="string">'Continuation'</span>]);</span><br><span class="line">});</span><br></pre></td></tr></table></figure>
<p>callback 返回子work，但是会在下一个 message event 事件中执行</p>
<h5 id="3-multiple-tasks"><a href="#3-multiple-tasks" class="headerlink" title="3. multiple tasks"></a>3. multiple tasks</h5><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">it(<span class="string">'multiple tasks'</span>, () => {</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'A'</span>);</span><br><span class="line"> });</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'B'</span>);</span><br><span class="line"> });</span><br><span class="line"> runtime.assertLog([<span class="string">'Post Message'</span>]);</span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([<span class="string">'Message Event'</span>, <span class="string">'A'</span>, <span class="string">'B'</span>]);</span><br><span class="line">});</span><br></pre></td></tr></table></figure>
<h5 id="4-multiple-tasks-with-a-yield-in-between"><a href="#4-multiple-tasks-with-a-yield-in-between" class="headerlink" title="4. multiple tasks with a yield in between"></a>4. multiple tasks with a yield in between</h5><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">it(<span class="string">'multiple tasks with a yield in between'</span>, () => {</span><br><span class="line"> <span class="comment">// 时间切片为5ms，当设置时间4999之后时，当前时间切片已经用完，所以yield之后，异步执行下一个task</span></span><br><span class="line"></span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'A'</span>);</span><br><span class="line"> runtime.advanceTime(<span class="number">4999</span>);</span><br><span class="line"> });</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'B'</span>);</span><br><span class="line"> });</span><br><span class="line"> runtime.assertLog([<span class="string">'Post Message'</span>]);</span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([</span><br><span class="line"> <span class="string">'Message Event'</span>,</span><br><span class="line"> <span class="string">'A'</span>,</span><br><span class="line"> <span class="comment">// Ran out of time. Post a continuation event.</span></span><br><span class="line"> <span class="string">'Post Message'</span>,</span><br><span class="line"> ]);</span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([<span class="string">'Message Event'</span>, <span class="string">'B'</span>]);</span><br><span class="line">});</span><br></pre></td></tr></table></figure>
<h5 id="5-throws-when-a-task-errors-then-continues-in-a-new-event"><a href="#5-throws-when-a-task-errors-then-continues-in-a-new-event" class="headerlink" title="5. throws when a task errors then continues in a new event"></a>5. throws when a task errors then continues in a new event</h5><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">it(<span class="string">'throws when a task errors then continues in a new event'</span>, () => {</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'Oops!'</span>);</span><br><span class="line"> <span class="keyword">throw</span> <span class="built_in">Error</span>(<span class="string">'Oops!'</span>);</span><br><span class="line"> });</span><br><span class="line"> scheduleCallback(NormalPriority, () => {</span><br><span class="line"> runtime.log(<span class="string">'Yay'</span>);</span><br><span class="line"> });</span><br><span class="line"> runtime.assertLog([<span class="string">'Post Message'</span>]);</span><br><span class="line"></span><br><span class="line"> expect(<span class="function"><span class="params">()</span> =></span> runtime.fireMessageEvent()).toThrow(<span class="string">'Oops!'</span>);</span><br><span class="line"> runtime.assertLog([<span class="string">'Message Event'</span>, <span class="string">'Oops!'</span>, <span class="string">'Post Message'</span>]);</span><br><span class="line"></span><br><span class="line"> runtime.fireMessageEvent();</span><br><span class="line"> runtime.assertLog([<span class="string">'Message Event'</span>, <span class="string">'Yay'</span>]);</span><br><span class="line">});</span><br></pre></td></tr></table></figure>
<p>如果 task 执行报错，后面的任务会在下一个 message event 中继续执行 因为在 workLoop 中在执行任务前会先将 task.callback 设置为null，就是取消任务 </p>
</div>