-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
805 lines (578 loc) · 116 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
<!DOCTYPE HTML>
<html>
<head>
<meta charset="utf-8">
<title>Machine Learning, Algorithms and others</title>
<meta name="author" content="Fayou Zhang">
<link rel="alternate" href="/hexoblog/atom.xml" title="Machine Learning, Algorithms and others" type="application/atom+xml">
<link rel="stylesheet" href="/hexoblog/css/style.css" media="screen" type="text/css">
<!--[if lt IE 9]><script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script><![endif]-->
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.8/jquery.min.js"></script>
</head>
<body>
<header id="header" class="inner"><nav>
<ul>
<li><a href="/">Home</a></li>
<li><a href="/archives">Archives</a></li>
</ul>
</nav></header>
<div id="content" class="inner">
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/29/god/">god</a></h1>
<time datetime="2015-05-29T04:51:40.000Z">
<span class="day">29</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<p>诸神在广场上向人们兜售着他们的理念，希望得到民众追随。众人发问：在你们之中，有谁是一直爱护着人类，没有由着自己的性子，对人类施加暴行的，我们就选择他当我们的神。</p>
<p>艾瑞斯默默的走了。</p>
<p>宙斯也默默的走了。</p>
<p>耶和华也红着脸，从旁边退了出去。</p>
<p>马克思没好意思留下。</p>
<p>最后，广场上还剩下一位。</p>
<p>于是众人高呼：“RAmen”。</p>
<hr>
<p>1.RAmen,是飞天面条教祈祷结束时的，飞天面条是对宗教的新面孔—-智能设计的嘲讽。参考维基百科。</p>
<p>2.这段是看到圣经上的一个小故事（可能来自约翰福音）：当时犹太人处于罗马的统治下，犹太教的信徒（还是长老？）为了给耶稣出难题，抓住了一个行淫的女人。请教耶稣如何审判。按照罗马法律，是不可以私刑的。但是按照摩西律法，该女子是要被处以石刑。耶稣无论是按照那个律法，都必然违反另一个法律。耶稣当时好像是说，你们当中谁没有犯过错误的，尽管拿石头砸她。众人想了想，就都退去了。</p>
<p>我对这段的逻辑没法理解。尽管我不赞同石刑。但是，这和行刑的人有没有犯过错误有什么关系，难道以前犯过错误，就不能主持正义了吗。</p>
<p>PS. 我最初以为石刑是绿教的，原来犹太教就有了。</p>
<footer class="meta">
<div class="tags">
<a href="/hexoblog/tags/随笔/">随笔</a></div>
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/29/friend/">朋友</a></h1>
<time datetime="2015-05-29T04:14:58.000Z">
<span class="day">29</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<p>记得以前看过一个小故事，大意是自己遇到了困难，打电话找朋友借钱帮忙，结果自己以为的有能力帮忙的几位好友全部借口推脱，反而是自己以为的关系一般的几位朋友纷纷二话不说，慷慨解囊。当他把这件事和一个生意上的朋友说的时候，那个朋友也借机打了十几个电话求帮忙。结果同样出乎意料，本来以为是好友的没有帮忙，十几个人中答应帮忙的仅有一二，而且是自己认为关系一般的朋友。于是两人得出结论：现在知道哪些人是真正的朋友了。</p>
<p>这个故事试图向我们传达：真正的朋友，就是那种在你需要帮忙的时候，慷慨解囊的人。</p>
<p>但我却觉得，该故事同时传达了：那些能被你利用的才是真正的朋友，在不能被你利用时，应该果断放弃那些没有利用价值了的朋友。而且为了试探朋友，自己采取撒谎欺骗的手段是可取的。</p>
<p>当初看到好多朋友同学纷纷转发，一直想把自己的想法写出来。<br>我自己的观点是：我对朋友的要求很低，在我遇到困难的时候，我也会向朋友寻求帮助。对于那些帮我的人，无论是物质帮助还是精神鼓励，我都很感激。对于没有帮助我的人，我也不会有怨言，我唯一的要求是不要在我陷入困境时落井下石即可。对于帮助朋友，我可能会按照自己心里的亲疏关系给予不同的帮助。但是我不会对自己能帮上忙要情要义的。对于帮不上忙的，或者有能力帮助而选择不帮的，我现在也不会有什么愧疚了。不过我可以确定的是，我不会选择落井下石。</p>
<footer class="meta">
<div class="tags">
<a href="/hexoblog/tags/随笔/">随笔</a></div>
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/26/bokeh notes/"></a></h1>
<time datetime="2015-05-26T00:32:59.000Z">
<span class="day">26</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<h1 id="bokeh_笔记">bokeh 笔记</h1><blockquote>
<p>The basic steps to creating plots with the bokeh.plotting interface are:<br>1.Prepare some data (in this case plain python lists).<br>2.Tell Bokeh where to generate output (in this case using output_file(), with “lines.html” as the filename to save as).<br>3.Call figure() to create a plot with some overall options like title, tools and axes labels.<br>4.Add renderers (in this case, Figure.line) for our data, with visual customizations like colors, legends and widths to the plot.<br>5.Ask Bokeh to show() or save() the results.</p>
</blockquote>
<h2 id="the_bokeh-plotting_Interface">the bokeh.plotting Interface</h2><h3 id="生成数据">生成数据</h3><p>可以是 list, array? DataFrame(pandas)?</p>
<h3 id="指定输出">指定输出</h3><p>可以是一个 html 文件或者是 ipython notebook</p>
<h3 id="生成一个_figure">生成一个 figure</h3><p>这一步使用 figure 函数 生成一个图，在这一步可以设定图形的一些参数：</p>
<ul>
<li>title</li>
<li>plot_width,plot_height</li>
<li>x_axis_label,y_axis_label</li>
<li>x_range , y_range 可以是2个元素的列表或者元组:[1,10] or (1,10)</li>
<li>tools,可以从这里面随便选TOOLS=”resize,crosshair,pan,wheel_zoom,box_zoom,reset,box_select,lasso_select”</li>
<li>x_axis_type,y_axis_type</li>
<li>legend</li>
<li>toolbar_location: could be “above” “below” “left”,”right”</li>
</ul>
<h3 id="利用数据绘图">利用数据绘图</h3><p>在这一步才是利用数据绘图。<br>bokeh provides several functions to draw different shape of glyphs.</p>
<ul>
<li>‘annular_wedge’,</li>
<li>‘annulus’,</li>
<li>‘arc’,</li>
<li>‘asterisk’,</li>
<li>‘bezier’,</li>
<li>‘circle’,</li>
<li>‘circle_cross’,</li>
<li>‘circle_x’,</li>
<li>‘cross’,</li>
<li>‘diamond’,</li>
<li>‘diamond_cross’,</li>
<li>‘image’,</li>
<li>‘image_rgba’,</li>
<li>‘image_url’,</li>
<li>‘inverted_triangle’,</li>
<li>‘line’,</li>
<li>‘multi_line’,</li>
<li>‘oval’,</li>
<li>‘patch’,</li>
<li>‘patches’,</li>
<li>…</li>
</ul>
<p>more than I can image. each glyph has its own parameters. these functions return a <code>plot</code></p>
<h3 id="show_the_plot">show the plot</h3><p>Finally, <code>show</code> function shows the plot.</p>
<h2 id="bokeh-charts_Interface">bokeh.charts Interface</h2><p>In this Interface, there are several functions:<br><figure class="highlight actionscript"><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="string">'Area'</span>,</span><br><span class="line"><span class="string">'Bar'</span>,</span><br><span class="line"><span class="string">'BoxPlot'</span>,</span><br><span class="line"><span class="string">'ColumnDataSource'</span>,</span><br><span class="line"><span class="string">'DataAdapter'</span>,</span><br><span class="line"> <span class="string">'Donut'</span>,</span><br><span class="line"> <span class="string">'Dot'</span>,</span><br><span class="line"> <span class="string">'HBox'</span>,</span><br><span class="line"> <span class="string">'HeatMap'</span>,</span><br><span class="line"> <span class="string">'Histogram'</span>,</span><br><span class="line"> <span class="string">'Horizon'</span>,</span><br><span class="line"> <span class="string">'Line'</span>,</span><br><span class="line"> <span class="string">'Scatter'</span>,</span><br><span class="line"> <span class="string">'Step'</span>,</span><br><span class="line"> <span class="string">'TimeSeries'</span>,</span><br><span class="line"> <span class="string">'VBox'</span>,</span><br></pre></td></tr></table></figure></p>
<footer class="meta">
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/25/gbdt/">gbdt</a></h1>
<time datetime="2015-05-25T13:41:11.000Z">
<span class="day">25</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<h1 id="GBDT">GBDT</h1><p>关于机器学习，我目前看到的最好的中文书籍是《统计学习方法》，讲解的清晰易懂，而且有算法。看了之后都没有写东西的冲动了。</p>
<pre><code>关于 GBDT，在该书中是放在第八章提升方法提升树这一节。该章首先介绍了 adaboost，关键是每次调整样本的权重，预测对了权重就调低，错了就调高。如何实现这一点呢？用得是
</code></pre><p>$$<br>\alpha_m = \frac{1}{2}log \frac{1-e_m}{e_m}<br>$$<br>其中$e_m$是预测错误率。</p>
<p>然后介绍的是前向分步算法，是一个解决加法模型的算法。紧接着就证明了，如果损失函数取指数损失函数的话，那么能得出 adaboost，也就是说，adaboost 是前向分步算法的一个特列。</p>
<p>紧接着，在提升树算法中，如果采用平方误差损失的话，损失变成了</p>
<p>$$<br>L(y,f<em>{m-1}(x)+T(x;\Theta_m))=[y-f</em>{m-1}(x)-T(x;\Theta_m)]^2=[r-T(x;\Theta_m)]^2<br>$$</p>
<p>其中，r 是当前模型拟合的残差</p>
<p>所以，对于回归问题的提升树来说，只需拟合当前模型的残差即可。</p>
<p>我觉得这很有意思，以前是要修改样本的权重，到现在是要拟合残差，和样本权重好像没关系了</p>
<p>最后介绍的是梯度提升，说如果的是利用损失函数的负梯度在当前模型的值<br>$$<br>-\bigg[\frac{\partial L(y,\;f(x<em>{i}))}{\partial f(x</em>{i})}\bigg]<em>{f(x)=f</em>{m-1}(x)}<br>$$<br>来作为回归问题提升树算法中得残差近似值。</p>
<p>这里给出了 R 的<a href="http://xccds1977.blogspot.com/2015/05/boosting.html" target="_blank" rel="external">博客</a></p>
<p><a href="https://gist.githubusercontent.com/xccds/432b8752a2f9c14e3148/raw/gbm.R" target="_blank" rel="external">代码</a></p>
<figure class="highlight r"><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><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="comment"># Learn Gradient Boosting Model by coding</span></span><br><span class="line"></span><br><span class="line"><span class="comment"># good slide</span></span><br><span class="line"><span class="comment"># http://www.ccs.neu.edu/home/vip/teach/MLcourse/4_boosting/slides/gradient_boosting.pdf</span></span><br><span class="line"><span class="comment"># http://cran.r-project.org/web/packages/gbm/gbm.pdf</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#1 Gradient Boosting for Regression</span></span><br><span class="line"></span><br><span class="line"><span class="comment"># generate data</span></span><br><span class="line">generate_func = <span class="keyword">function</span>(n=<span class="number">1000</span>,size=<span class="number">0.5</span>){</span><br><span class="line"> <span class="comment"># n: how many data points</span></span><br><span class="line"> <span class="comment"># size: hold 50% of all data as train </span></span><br><span class="line"> set.seed(<span class="number">1</span>)</span><br><span class="line"> x = seq(<span class="number">0</span>,<span class="number">2</span>*pi,length=n) <span class="comment"># generate x</span></span><br><span class="line"> noise = rnorm(n,<span class="number">0</span>,<span class="number">0.3</span>)</span><br><span class="line"> y = sin(x) + noise <span class="comment"># generate y</span></span><br><span class="line"> select_index = sample(<span class="number">1</span>:n,size=size*n,replace = <span class="literal">F</span>)</span><br><span class="line"> <span class="comment"># split data into train and test</span></span><br><span class="line"> train_x = x[select_index]</span><br><span class="line"> train_y = y[select_index]</span><br><span class="line"> test_x = x[-select_index]</span><br><span class="line"> test_y = y[-select_index]</span><br><span class="line"> data = list(<span class="string">'train_x'</span>=train_x,</span><br><span class="line"> <span class="string">'train_y'</span>=train_y,</span><br><span class="line"> <span class="string">'test_x'</span>=test_x,</span><br><span class="line"> <span class="string">'test_y'</span>=test_y)</span><br><span class="line"> <span class="keyword">return</span>(data)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">data = generate_func()</span><br><span class="line">objects(data)</span><br><span class="line"></span><br><span class="line"><span class="comment"># train boosting regression tree</span></span><br><span class="line">GBR = <span class="keyword">function</span>(x,y,rate=<span class="number">1</span>,iter=<span class="number">100</span>){</span><br><span class="line"> <span class="comment"># iter is iterate number, higher is better, but be carefule overfit.</span></span><br><span class="line"> <span class="comment"># rate is learning speed, lower is better, but too slow will cause longer time. </span></span><br><span class="line"> <span class="keyword">library</span>(rpart)</span><br><span class="line"> max_depth=<span class="number">1</span> <span class="comment"># tree stump</span></span><br><span class="line"> mu = mean(y) <span class="comment"># start with an initial model</span></span><br><span class="line"> dy = y - mu <span class="comment"># residuals or error, These are the parts that existing model cannot do well.</span></span><br><span class="line"> learner = list() <span class="comment"># define a learners holder </span></span><br><span class="line"> <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1</span>:iter) {</span><br><span class="line"> <span class="comment"># use a weak model to improve</span></span><br><span class="line"> learner[[i]] = rpart(dy~x, <span class="comment"># error is target variable</span></span><br><span class="line"> control=rpart.control(maxdepth=max_depth,cp=<span class="number">0</span>)) <span class="comment"># cp=0 means to growth a tree with any cost</span></span><br><span class="line"> <span class="comment"># modify residuals for next iter</span></span><br><span class="line"> dy = dy - rate*predict(learner[[i]])</span><br><span class="line"> }</span><br><span class="line"> result = list(<span class="string">'learner'</span>=learner,</span><br><span class="line"> <span class="string">'rate'</span>=rate,</span><br><span class="line"> <span class="string">'iter'</span>=iter)</span><br><span class="line"> <span class="keyword">return</span>(result)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">model = GBR(data$train_x,data$train_y,iter=<span class="number">1000</span>)</span><br><span class="line">objects(model)</span><br><span class="line"></span><br><span class="line"><span class="comment"># predict function</span></span><br><span class="line">predict_GBR = <span class="keyword">function</span>(x,y,model){</span><br><span class="line"> predict_y = list() <span class="comment"># hold predict result</span></span><br><span class="line"> mu = mean(y) <span class="comment"># initial model</span></span><br><span class="line"> n = length(y)</span><br><span class="line"> iter = model$iter</span><br><span class="line"> rate = model$rate</span><br><span class="line"> predict_y[[<span class="number">1</span>]] = rep(mu,n)</span><br><span class="line"> learner = model$learner</span><br><span class="line"> <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">2</span>:iter) {</span><br><span class="line"> <span class="comment"># add pre-model prediction to predict y</span></span><br><span class="line"> predict_y[[i]] = predict_y[[i-<span class="number">1</span>]] + rate * predict(learner[[i-<span class="number">1</span>]],newdata=data.frame(x))</span><br><span class="line"> }</span><br><span class="line"> <span class="comment"># mean sqare error</span></span><br><span class="line"> mse = sapply(predict_y,<span class="keyword">function</span>(pre_y) round(mean((y-pre_y)^<span class="number">2</span>),<span class="number">3</span>))</span><br><span class="line"> result = list(<span class="string">'predict_y'</span>=predict_y,</span><br><span class="line"> <span class="string">'mse'</span>= mse)</span><br><span class="line"> <span class="keyword">return</span>(result)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment"># predict train data</span></span><br><span class="line">predict_train = predict_GBR(data$train_x,data$train_y,model=model)</span><br><span class="line">objects(predict_train)</span><br><span class="line"></span><br><span class="line"><span class="comment"># more trees get less error</span></span><br><span class="line">plot(predict_train$mse,type=<span class="string">'l'</span>)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment"># plot the effect of boosing tree</span></span><br><span class="line">plotfunc = <span class="keyword">function</span>(x,y,predict,num){</span><br><span class="line"> <span class="keyword">library</span>(ggplot2)</span><br><span class="line"> pre = predict$predict_y[[num]] </span><br><span class="line"> plotdf = data.frame(x=x,y=y,pre = pre)</span><br><span class="line"> mse = round(mean((y-pre)^<span class="number">2</span>),<span class="number">3</span>)</span><br><span class="line"> p = ggplot(plotdf,aes(x,y)) +</span><br><span class="line"> geom_point(alpha=<span class="number">0.5</span>)</span><br><span class="line"> p = p + geom_line(aes(x,pre)) + xlab(paste0(<span class="string">'mse='</span>,mse))</span><br><span class="line"> plot(p)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment"># use mean of y to predict data</span></span><br><span class="line">plotfunc(data$train_x,data$train_y,predict_train,num=<span class="number">1</span>)</span><br><span class="line"><span class="comment"># add another tree model</span></span><br><span class="line">plotfunc(data$train_x,data$train_y,predict_train,num=<span class="number">2</span>)</span><br><span class="line"><span class="comment"># add more tree getter more result</span></span><br><span class="line">plotfunc(data$train_x,data$train_y,predict_train,num=<span class="number">10</span>)</span><br><span class="line">plotfunc(data$train_x,data$train_y,predict_train,num=<span class="number">100</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># predict test data</span></span><br><span class="line">predict_test = predict_GBR(data$test_x,data$test_y,model=model)</span><br><span class="line">plot(predict_test$mse,type=<span class="string">'l'</span>)</span><br><span class="line"></span><br><span class="line">plotfunc(data$test_x,data$test_y,predict_test,<span class="number">10</span>)</span><br><span class="line">plotfunc(data$test_x,data$test_y,predict_test,<span class="number">100</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># compare different parametter</span></span><br><span class="line"><span class="comment"># create 2 models with different rate</span></span><br><span class="line">model_1 = GBR(data$train_x,data$train_y,rate=<span class="number">1</span>,iter=<span class="number">500</span>)</span><br><span class="line">model_2 = GBR(data$train_x,data$train_y,rate=<span class="number">0.1</span>,iter=<span class="number">500</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># use train and test data, we have 4 results</span></span><br><span class="line">predict_train_1 = predict_GBR(data$train_x,data$train_y,model=model_1)</span><br><span class="line">predict_train_2 = predict_GBR(data$train_x,data$train_y,model=model_2)</span><br><span class="line">predict_test_1 = predict_GBR(data$test_x,data$test_y,model=model_1)</span><br><span class="line">predict_test_2 = predict_GBR(data$test_x,data$test_y,model=model_2)</span><br><span class="line"></span><br><span class="line"><span class="comment"># take out mse of these 4 results</span></span><br><span class="line">train_error_1 = predict_train_1$mse</span><br><span class="line">train_error_2 = predict_train_2$mse</span><br><span class="line">test_error_1 = predict_test_1$mse</span><br><span class="line">test_error_2 = predict_test_2$mse</span><br><span class="line">iter = <span class="number">1</span>:model_1$iter</span><br><span class="line"></span><br><span class="line"><span class="comment"># compare these mse</span></span><br><span class="line">plotdf = data.frame(iter,train_error_1,test_error_1,train_error_2,test_error_2)</span><br><span class="line"></span><br><span class="line">p = ggplot(plotdf)+</span><br><span class="line"> geom_line(aes(x=iter,y=train_error_1),color=<span class="string">'blue'</span>)+</span><br><span class="line"> geom_line(aes(x=iter,y=test_error_1),color=<span class="string">'red'</span>) +</span><br><span class="line"> geom_line(aes(x=iter,y=train_error_2),linetype=<span class="number">2</span>,color=<span class="string">'blue'</span>)+</span><br><span class="line"> geom_line(aes(x=iter,y=test_error_2),linetype=<span class="number">2</span>,color=<span class="string">'red'</span>)</span><br><span class="line">print(p)</span><br><span class="line"></span><br><span class="line"><span class="comment"># test error is better model performance.</span></span><br><span class="line"><span class="comment"># less rate is better but need more iter</span></span><br><span class="line">which.min(train_error_1)</span><br><span class="line">which.min(train_error_2)</span><br><span class="line">which.min(test_error_1)</span><br><span class="line">which.min(test_error_2)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 2. Gradient Boosting for Classification</span></span><br><span class="line"></span><br><span class="line"><span class="comment"># read data</span></span><br><span class="line">data = subset(iris,Species!=<span class="string">'virginica'</span>,select = c(<span class="number">1</span>,<span class="number">2</span>,<span class="number">5</span>))</span><br><span class="line">data$y = ifelse(data$Species == <span class="string">'setosa'</span>,<span class="number">1</span>,-<span class="number">1</span>)</span><br><span class="line">data$Species = <span class="literal">NULL</span></span><br><span class="line">names(data)[<span class="number">1</span>:<span class="number">2</span>] = c(<span class="string">'x1'</span>,<span class="string">'x2'</span>)</span><br><span class="line">head(data)</span><br><span class="line">p = ggplot(data,aes(x1,x2,color=factor(y)))+</span><br><span class="line"> geom_point()</span><br><span class="line">print(p)</span><br><span class="line"></span><br><span class="line"><span class="comment"># train boosting tree for classification</span></span><br><span class="line">GBC = <span class="keyword">function</span>(data,rate=<span class="number">0.1</span>,iter=<span class="number">100</span>){</span><br><span class="line"> <span class="keyword">library</span>(rpart)</span><br><span class="line"> max_depth=<span class="number">1</span></span><br><span class="line"> learner = list()</span><br><span class="line"> mu = mean(data$y==<span class="number">1</span>)</span><br><span class="line"> <span class="comment"># start with an initial model</span></span><br><span class="line"> <span class="comment"># mu=p(y=1) -> f=w*x = log(mu/(1-mu)) </span></span><br><span class="line"> f = log(mu/(<span class="number">1</span>-mu)) </span><br><span class="line"> data$dy = data$y/(<span class="number">1</span>+exp(data$y*f)) <span class="comment"># dy is negtive gradient of log loss funtion</span></span><br><span class="line"> <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1</span>:iter) {</span><br><span class="line"> <span class="comment"># use a weak model to improve</span></span><br><span class="line"> learner[[i]] = rpart(dy~x1+x2,data=data,</span><br><span class="line"> control=rpart.control(maxdepth=max_depth,cp=<span class="number">0</span>))</span><br><span class="line"> <span class="comment"># improve model </span></span><br><span class="line"> f = f + rate *predict(learner[[i]])</span><br><span class="line"> <span class="comment"># modify dy</span></span><br><span class="line"> data$dy = data$y/(<span class="number">1</span>+exp(data$y*f))</span><br><span class="line"> }</span><br><span class="line"> result = list(<span class="string">'learner'</span>=learner,</span><br><span class="line"> <span class="string">'rate'</span>=rate,</span><br><span class="line"> <span class="string">'iter'</span>=iter)</span><br><span class="line"> <span class="keyword">return</span>(result)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">model = GBC(data,rate=<span class="number">0.1</span>,iter=<span class="number">1000</span>)</span><br><span class="line">objects(model)</span><br><span class="line"></span><br><span class="line"><span class="comment"># predict function</span></span><br><span class="line">predict_GBC = <span class="keyword">function</span>(data,model){</span><br><span class="line"> predict_y = list()</span><br><span class="line"> mu = mean(data$y==<span class="number">1</span>)</span><br><span class="line"> f = log(mu/(<span class="number">1</span>-mu)) </span><br><span class="line"> n = nrow(data)</span><br><span class="line"> iter = model$iter</span><br><span class="line"> rate = model$rate</span><br><span class="line"> predict_y[[<span class="number">1</span>]] = rep(f,n)</span><br><span class="line"> learner = model$learner</span><br><span class="line"> <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">2</span>:iter) {</span><br><span class="line"> predict_y[[i]] = predict_y[[i-<span class="number">1</span>]] + rate *predict(learner[[i-<span class="number">1</span>]],newdata=data)</span><br><span class="line"> }</span><br><span class="line"> mse = sapply(predict_y,<span class="keyword">function</span>(pre_y) sum(log(<span class="number">1</span>+exp(-data$y*pre_y)))) <span class="comment"># logistic loss function</span></span><br><span class="line"> result = list(<span class="string">'predict_y'</span>=predict_y,</span><br><span class="line"> <span class="string">'mse'</span>= mse)</span><br><span class="line"> <span class="keyword">return</span>(result)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment"># predict data</span></span><br><span class="line">predict_train = predict_GBC(data,model=model)</span><br><span class="line">objects(predict_train)</span><br><span class="line">plot(predict_train$mse,type=<span class="string">'l'</span>)</span><br><span class="line"></span><br><span class="line">final = predict_train$predict_y[[<span class="number">1000</span>]]</span><br><span class="line">y_p = <span class="number">1</span>/(<span class="number">1</span>+exp(-final))</span><br><span class="line">y_pred = ifelse(y_p><span class="number">0.5</span>,<span class="number">1</span>,-<span class="number">1</span>)</span><br><span class="line">table(data$y, y_pred)</span><br><span class="line"></span><br><span class="line"><span class="comment"># # plot</span></span><br><span class="line"></span><br><span class="line">plotfunc2 = <span class="keyword">function</span>(data,num,rate=<span class="number">0.1</span>){</span><br><span class="line"> <span class="keyword">library</span>(ggplot2)</span><br><span class="line"> model = GBC(data,rate=rate,iter=num)</span><br><span class="line"> predict_train = predict_GBC(data,model=model)</span><br><span class="line"> final = predict_train$predict_y[[num]]</span><br><span class="line"> y_p = <span class="number">1</span>/(<span class="number">1</span>+exp(-final))</span><br><span class="line"> data$y_pre = ifelse(y_p><span class="number">0.5</span>,<span class="number">1</span>,-<span class="number">1</span>)</span><br><span class="line"> tree_f = sapply(model$learner,<span class="keyword">function</span>(x){</span><br><span class="line"> temp = x$splits</span><br><span class="line"> <span class="keyword">return</span>(row.names(temp)[<span class="number">1</span>])</span><br><span class="line"> })</span><br><span class="line"> tree_v = sapply(model$learner,<span class="keyword">function</span>(x){</span><br><span class="line"> temp = x$splits</span><br><span class="line"> <span class="keyword">return</span>(temp[<span class="number">1</span>,<span class="string">'index'</span>])</span><br><span class="line"> })</span><br><span class="line"> x1value = tree_v[tree_f==<span class="string">'x1'</span>]</span><br><span class="line"> x2value = tree_v[tree_f==<span class="string">'x2'</span>]</span><br><span class="line"> p = ggplot(data,aes(x=x1,y=x2))</span><br><span class="line"> p = p + geom_point(aes(color=factor(y_pre)),size=<span class="number">5</span>) +</span><br><span class="line"> geom_point(aes(color=factor(y)),size=<span class="number">3</span>)+</span><br><span class="line"> geom_vline(xintercept = x1value,alpha=<span class="number">0.4</span>) +</span><br><span class="line"> geom_hline(yintercept = x2value,alpha=<span class="number">0.4</span>) + </span><br><span class="line"> scale_colour_brewer(type=<span class="string">"seq"</span>, palette=<span class="string">'Set1'</span>) +</span><br><span class="line"> theme_bw()</span><br><span class="line"> print(p)</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">plotfunc2(data,num=<span class="number">10</span>)</span><br><span class="line">plotfunc2(data,num=<span class="number">20</span>)</span><br><span class="line">plotfunc2(data,num=<span class="number">60</span>)</span><br><span class="line">plotfunc2(data,num=<span class="number">100</span>)</span><br><span class="line">plotfunc2(data,num=<span class="number">1000</span>)</span><br></pre></td></tr></table></figure>
<footer class="meta">
<div class="tags">
<a href="/hexoblog/tags/boosting/">boosting</a><a href="/hexoblog/tags/machine-learning/">machine learning</a></div>
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/14/machine-learning-work-flow/">machine-learning-work-flow</a></h1>
<time datetime="2015-05-14T10:57:33.000Z">
<span class="day">14</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<h2 id="数据预处理">数据预处理</h2><p>去掉零方差、多重共线性等<br>在 scikit-learn 中，可以使用 sklearn.feature_selection 模块中的相应函数：</p>
<h3 id="Removing_features_with_low_variance">Removing features with low variance</h3><p>VarianceThreshold </p>
<h3 id="Univariate_feature_selection">Univariate feature selection</h3><ul>
<li><strong>SelectKBest</strong> removes all but the k highest scoring features</li>
<li><strong>SelectPercentile</strong> removes all but a user-specified highest scoring percentage of features</li>
<li>using common univariate statistical tests for each feature: false positive rate <strong>SelectFpr</strong>, false discovery rate <strong>SelectFdr</strong>, or family wise error <strong>SelectFwe</strong>.</li>
<li><strong>GenericUnivariateSelect</strong> allows to perform univariate feature<br>selection with a configurable strategy. This allows to select the best univariate selection strategy with hyper-parameter search estimator.</li>
</ul>
<h3 id="Recursive_feature_elimination">Recursive feature elimination</h3><ul>
<li>RFE</li>
<li>RFECV</li>
</ul>
<h3 id="L1-based_feature_selection">L1-based feature selection</h3><ul>
<li>linear_model.Lasso </li>
<li>linear_model.LogisticRegression</li>
<li>svm.LinearSVC</li>
<li>RandomizedLasso</li>
<li>RandomizedLogisticRegression</li>
<li>lasso_stability_path</li>
</ul>
<h3 id="Tree-based_feature_selection">Tree-based feature selection</h3><ul>
<li>ExtraTreesClassifier in sklearn.ensemble</li>
</ul>
<footer class="meta">
<div class="tags">
<a href="/hexoblog/tags/machine-learning/">machine learning</a></div>
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/08/gradient-descent-with-line-search/">gradient-descent-with-line-search</a></h1>
<time datetime="2015-05-08T13:43:07.000Z">
<span class="day">8</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<footer class="meta">
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/05/03/sympy-tutorial/">sympy tutorial</a></h1>
<time datetime="2015-05-03T08:56:13.000Z">
<span class="day">3</span><span class="month">May</span>
</time>
</header>
<div class="entry-content">
<p>自从看了卡尔曼滤波的教程，看到里面用到了 sympy 来显示公式和进行公式推导，忍不住心里痒痒，就想学学该怎么用。</p>
<pre><code><span class="keyword">from</span> sympy <span class="keyword">import</span> *
<span class="keyword">from</span> sympy.interactive <span class="keyword">import</span> printing
printing.init_printing(use_latex=<span class="keyword">True</span>)
</code></pre><p>这里默认使用 ipython notebook，上面的语句会使用比较漂亮的方式来显示公式。</p>
<h2 id="本文主要记录:">本文主要记录:</h2><p>1.变量的定义</p>
<p>2.演算</p>
<ul>
<li>极限</li>
<li>微分</li>
<li>级数展开</li>
<li>求和</li>
<li>积分</li>
<li>复数</li>
<li>函数</li>
<li>微分方程</li>
<li>代数方程</li>
<li>矩阵</li>
</ul>
<h2 id="变量的定义">变量的定义</h2><p>变量的定义使用 symbols 函数，可以限制变量的类型，比如为整数或者为函数等。</p>
<pre><code>x, y, z, t = <span class="function"><span class="title">symbols</span><span class="params">(<span class="string">'x y z t'</span>)</span></span>
<span class="tag">i</span>,k, m, n = <span class="function"><span class="title">symbols</span><span class="params">(<span class="string">'i k m n'</span>, integer=True)</span></span>
f, g, h = <span class="function"><span class="title">symbols</span><span class="params">(<span class="string">'f g h'</span>, cls=Function)</span></span>
<span class="function"><span class="title">symbols</span><span class="params">(<span class="string">'x:10'</span>)</span></span>
</code></pre><p>$$\left ( x_0, \quad x_1, \quad x_2, \quad x_3, \quad x_4, \quad x_5, \quad x_6, \quad x_7, \quad x_8, \quad x_9\right )$$</p>
<h2 id="极限">极限</h2><pre><code>limit<span class="list">(<span class="keyword">sin</span><span class="list">(<span class="keyword">x</span>)</span>/x,x,<span class="number">0</span>)</span>
</code></pre><p>$$1$$</p>
<p><strong>大小写的区别是大写不运算，小写给出运算结果</strong></p>
<pre><code>Limit<span class="list">(<span class="list">(<span class="number">3</span> <span class="variable">* n *</span><span class="variable">* 2 + 2 *</span> n )</span>/ <span class="list">(<span class="keyword">n</span> <span class="variable">**</span> <span class="number">2</span> + <span class="number">5</span>)</span>,n,oo)</span>
</code></pre><p>$$\lim_{n \to \infty}\left(\frac{3 n^{2} + 2 n}{n^{2} + 5}\right)$$</p>
<pre><code>limit<span class="list">(<span class="list">(<span class="number">3</span> <span class="variable">* n *</span><span class="variable">* 2 + 2 *</span> n )</span>/ <span class="list">(<span class="keyword">n</span> <span class="variable">**</span> <span class="number">2</span> + <span class="number">5</span>)</span>,n,oo)</span>
</code></pre><p>$$3$$</p>
<h2 id="微分">微分</h2><pre><code>diff<span class="list">(<span class="keyword">sin</span><span class="list">(<span class="keyword">x</span>)</span>,x)</span>
</code></pre><p>$$\cos{\left (x \right )}$$</p>
<pre><code><span class="function"><span class="title">diff</span><span class="params">(sin(<span class="number">2</span>*x)</span></span>, x, <span class="number">2</span>)
</code></pre><p>$$- 4 \sin{\left (2 x \right )}$$</p>
<h2 id="积分">积分</h2><pre><code>Integral<span class="list">(<span class="keyword">sqrt</span><span class="list">(<span class="number">1</span>/x)</span>,x)</span>
</code></pre><p>$$\int \sqrt{\frac{1}{x}}\, dx$$</p>
<pre><code>integrate<span class="list">(<span class="keyword">sqrt</span><span class="list">(<span class="number">1</span>/x)</span>,x)</span>
</code></pre><p>$$2 x \sqrt{\frac{1}{x}}$$</p>
<pre><code>integrate<span class="list">(<span class="keyword">sqrt</span><span class="list">(<span class="number">1</span>/x)</span>,<span class="list">(<span class="keyword">x</span>,<span class="number">1</span>,<span class="number">2</span>)</span>)</span>
</code></pre><p>$$-2 + 2 \sqrt{2}$$</p>
<h2 id="多项式">多项式</h2><pre><code>expand<span class="list">(<span class="list">(<span class="keyword">x</span> + <span class="number">1</span>)</span><span class="variable">**</span><span class="number">2</span>)</span>
</code></pre><p>$$x^{2} + 2 x + 1$$</p>
<pre><code>factor(x<span class="keyword">*</span><span class="keyword">*</span>3 - x<span class="keyword">*</span><span class="keyword">*</span>2 + x - 1)
</code></pre><p>$$\left(x - 1\right) \left(x^{2} + 1\right)$$</p>
<h2 id="级数展开">级数展开</h2><p>使用.series(var, point, order):</p>
<pre><code>(<span class="number">1</span>/<span class="function"><span class="title">cos</span><span class="params">(x)</span></span>).<span class="function"><span class="title">series</span><span class="params">(x, <span class="number">0</span>, <span class="number">10</span>)</span></span>
</code></pre><p>$$1 + \frac{x^{2}}{2} + \frac{5 x^{4}}{24} + \frac{61 x^{6}}{720} + \frac{277 x^{8}}{8064} + \mathcal{O}\left(x^{10}\right)$$</p>
<pre><code><span class="function"><span class="title">integrate</span><span class="params">(exp(-x ** <span class="number">2</span>)</span></span>,x).<span class="function"><span class="title">series</span><span class="params">(x,<span class="number">0</span>,<span class="number">10</span>)</span></span>
</code></pre><p>$$x - \frac{x^{3}}{3} + \frac{x^{5}}{10} - \frac{x^{7}}{42} + \frac{x^{9}}{216} + \mathcal{O}\left(x^{10}\right)$$</p>
<h3 id="画出级数图形">画出级数图形</h3><pre><code>%matplotlib inline
<span class="keyword">import</span> numpy <span class="keyword">as</span> np
<span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt
<span class="function"><span class="keyword">def</span> <span class="title">plot_taylor_approximations</span><span class="params">(func, x0=None, orders=<span class="params">(<span class="number">2</span>, <span class="number">4</span>)</span>, xrange=<span class="params">(<span class="number">0</span>,<span class="number">1</span>)</span>, yrange=None, npts=<span class="number">200</span>)</span>:</span>
<span class="string">"""Plot the Taylor series approximations to a function at various orders.
Parameters
----------
func : a sympy function
x0 : float
Origin of the Taylor series expansion. If not given, x0=xrange[0].
orders : list
List of integers with the orders of Taylor series to show. Default is (2, 4).
xrange : 2-tuple or array.
Either an (xmin, xmax) tuple indicating the x range for the plot (default is (0, 1)),
or the actual array of values to use.
yrange : 2-tuple
(ymin, ymax) tuple indicating the y range for the plot. If not given,
the full range of values will be automatically used.
npts : int
Number of points to sample the x range with. Default is 200.
"""</span>
<span class="keyword">if</span> <span class="keyword">not</span> callable(func):
<span class="keyword">raise</span> ValueError(<span class="string">'func must be callable'</span>)
<span class="keyword">if</span> isinstance(xrange, (list, tuple)):
x = np.linspace(float(xrange[<span class="number">0</span>]), float(xrange[<span class="number">1</span>]), npts)
<span class="keyword">else</span>:
x = xrange
<span class="keyword">if</span> x0 <span class="keyword">is</span> <span class="keyword">None</span>: x0 = x[<span class="number">0</span>]
xs = Symbol(<span class="string">'x'</span>)
<span class="comment"># Make a numpy-callable form of the original function for plotting</span>
fx = func(xs)
f = lambdify(xs, fx, modules=[<span class="string">'numpy'</span>])
<span class="comment"># We could use latex(fx) instead of str(), but matploblib gets confused</span>
<span class="comment"># with some of the (valid) latex constructs sympy emits. So we play it safe.</span>
plt.plot(x, f(x), label=str(fx), lw=<span class="number">2</span>)
<span class="comment"># Build the Taylor approximations, plotting as we go</span>
apps = {}
<span class="keyword">for</span> order <span class="keyword">in</span> orders:
app = fx.series(xs, x0, n=order).removeO()
apps[order] = app
<span class="comment"># Must be careful here: if the approximation is a constant, we can't</span>
<span class="comment"># blindly use lambdify as it won't do the right thing. In that case, </span>
<span class="comment"># evaluate the number as a float and fill the y array with that value.</span>
<span class="keyword">if</span> isinstance(app, numbers.Number):
y = np.zeros_like(x)
y.fill(app.evalf())
<span class="keyword">else</span>:
fa = lambdify(xs, app, modules=[<span class="string">'numpy'</span>])
y = fa(x)
tex = latex(app).replace(<span class="string">'$'</span>, <span class="string">''</span>)
plt.plot(x, y, label=<span class="string">r'$n=%s:\, %s$'</span> % (order, tex) )
<span class="comment"># Plot refinements</span>
<span class="keyword">if</span> yrange <span class="keyword">is</span> <span class="keyword">not</span> <span class="keyword">None</span>:
plt.ylim(*yrange)
plt.grid()
plt.legend(loc=<span class="string">'best'</span>).get_frame().set_alpha(<span class="number">0.8</span>)
<span class="comment"># You can change the default figure size to be a bit larger if you want,</span>
<span class="comment"># uncomment the next line for that:</span>
<span class="comment">#plt.rc('figure', figsize=(10, 6))</span>
plt.rc(<span class="string">'figure'</span>, figsize=(<span class="number">15</span>, <span class="number">9</span>))
plot_taylor_approximations(sin, <span class="number">0</span>, [<span class="number">2</span>, <span class="number">4</span>, <span class="number">6</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">15</span>, <span class="number">20</span>], (<span class="number">0</span>, <span class="number">2</span>*pi), (-<span class="number">2</span>,<span class="number">2</span>))
</code></pre><img src="/hexoblog/2015/05/03/sympy-tutorial/sympy-tutorial_30_0.png">
<h2 id="求和">求和</h2><pre><code>Sum<span class="list">(<span class="keyword">i</span> <span class="variable">**</span> <span class="number">2</span>,<span class="list">(<span class="keyword">i</span>,<span class="number">1</span>,n)</span>)</span>
</code></pre><p>$$\sum_{i=1}^{n} i^{2}$$</p>
<pre><code><span class="function"><span class="title">Sum</span><span class="params">(i ** <span class="number">2</span>,(i,<span class="number">1</span>,n)</span></span>).<span class="function"><span class="title">doit</span><span class="params">()</span></span>
</code></pre><p>$$\frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6}$$</p>
<h2 id="复数">复数</h2><pre><code><span class="function"><span class="title">exp</span><span class="params">(I*x)</span></span>.<span class="function"><span class="title">expand</span><span class="params">()</span></span>
</code></pre><p>$$e^{i x}$$</p>
<pre><code><span class="function"><span class="title">exp</span><span class="params">(I*x)</span></span>.<span class="function"><span class="title">expand</span><span class="params">(complex = True)</span></span>
</code></pre><p>$$i e^{- \Im{x}} \sin{\left (\Re{x} \right )} + e^{- \Im{x}} \cos{\left (\Re{x} \right )}$$</p>
<h2 id="微分方程">微分方程</h2><pre><code><span class="function"><span class="title">f</span><span class="params">(x)</span></span>.<span class="function"><span class="title">diff</span><span class="params">(x, x)</span></span> + <span class="function"><span class="title">f</span><span class="params">(x)</span></span>
</code></pre><p>$$f{\left (x \right )} + \frac{d^{2}}{d x^{2}} f{\left (x \right )}$$</p>
<pre><code><span class="function"><span class="title">dsolve</span><span class="params">(f(x)</span></span>.<span class="function"><span class="title">diff</span><span class="params">(x, x)</span></span> + <span class="function"><span class="title">f</span><span class="params">(x)</span></span>, <span class="function"><span class="title">f</span><span class="params">(x)</span></span>)
</code></pre><p>$$<br>f(x) = C_1 \sin(x) + C_2 \cos(x)<br>$$</p>
<h2 id="矩阵">矩阵</h2><pre><code>A = Matrix([[x <span class="keyword">*</span><span class="keyword">*</span> 2,2<span class="keyword">*</span>x<span class="keyword">*</span>y], [2<span class="keyword">*</span>x<span class="keyword">*</span>y,y <span class="keyword">*</span><span class="keyword">*</span> 2]])
A
</code></pre><p>$$\left[\begin{matrix}x^{2} & 2 x y\\2 x y & y^{2}\end{matrix}\right]$$</p>
<pre><code>A <span class="keyword">*</span><span class="keyword">*</span> 2
</code></pre><p>$$\left[\begin{matrix}x^{4} + 4 x^{2} y^{2} & 2 x^{3} y + 2 x y^{3}\\2 x^{3} y + 2 x y^{3} & 4 x^{2} y^{2} + y^{4}\end{matrix}\right]$$</p>
<pre><code>variables = Matrix<span class="comment">([x,y])</span>
<span class="comment">(A ** 2)</span>.row<span class="comment">(0)</span>
</code></pre><p>$$\left[\begin{matrix}x^{4} + 4 x^{2} y^{2} & 2 x^{3} y + 2 x y^{3}\end{matrix}\right]$$</p>
<pre><code>(A <span class="keyword">*</span><span class="keyword">*</span> 2).row(0).jacobian(variables)
</code></pre><p>$$\left[\begin{matrix}4 x^{3} + 8 x y^{2} & 8 x^{2} y\\6 x^{2} y + 2 y^{3} & 2 x^{3} + 6 x y^{2}\end{matrix}\right]$$</p>
<pre><code>hessian<span class="list">(<span class="keyword">f</span><span class="list">(<span class="keyword">x</span>,y)</span>,<span class="list">(<span class="keyword">x</span>,y)</span>)</span>
</code></pre><p>$$\left[\begin{matrix}\frac{\partial^{2}}{\partial x^{2}} f{\left (x,y \right )} & \frac{\partial^{2}}{\partial x\partial y} f{\left (x,y \right )}\\<br>\frac{\partial^{2}}{\partial x\partial y} f{\left (x,y \right )} & \frac{\partial^{2}}{\partial y^{2}} f{\left (x,y \right )}\end{matrix}\right]$$</p>
<pre><code>diff<span class="list">(<span class="keyword">f</span><span class="list">(<span class="keyword">x</span>,y)</span>,x)</span>
</code></pre><p>$$\frac{\partial}{\partial x} f{\left (x,y \right )}$$</p>
<footer class="meta">
<div class="tags">
<a href="/hexoblog/tags/python/">python</a><a href="/hexoblog/tags/sympy/">sympy</a></div>
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/04/30/Fibonacci-heap/">Finonacci_heap</a></h1>
<time datetime="2015-04-30T11:15:17.000Z">
<span class="day">30</span><span class="month">Apr</span>
</time>
</header>
<div class="entry-content">
<figure class="highlight python"><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><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br><span class="line">308</span><br><span class="line">309</span><br><span class="line">310</span><br><span class="line">311</span><br><span class="line">312</span><br><span class="line">313</span><br><span class="line">314</span><br><span class="line">315</span><br><span class="line">316</span><br><span class="line">317</span><br><span class="line">318</span><br><span class="line">319</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="string">"""Fibonacci Heap</span><br><span class="line"></span><br><span class="line"> Fibonacci heaps are especially desirable when the number of</span><br><span class="line"> extract_min() and delete() operations is small relative to the</span><br><span class="line"> number of other operations performed.</span><br><span class="line">"""</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">from</span> util <span class="keyword">import</span> torange</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">FibonacciHeap</span>:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self)</span>:</span></span><br><span class="line"> self.min = <span class="keyword">None</span></span><br><span class="line"> self.n = <span class="number">0</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">FibonacciHeapNode</span>:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self, key)</span>:</span></span><br><span class="line"> self.key = key</span><br><span class="line"> self.refresh()</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">refresh</span><span class="params">(self)</span>:</span></span><br><span class="line"> self.degree = <span class="number">0</span></span><br><span class="line"> self.parent = <span class="keyword">None</span></span><br><span class="line"> self.child = <span class="keyword">None</span></span><br><span class="line"> self.left = self</span><br><span class="line"> self.right = self</span><br><span class="line"> self.mark = <span class="keyword">False</span></span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">make_heap</span><span class="params">()</span>:</span></span><br><span class="line"> <span class="keyword">return</span> FibonacciHeap()</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">make_node</span><span class="params">(k)</span>:</span></span><br><span class="line"> <span class="keyword">return</span> FibonacciHeapNode(k)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">minimum</span><span class="params">(H)</span>:</span></span><br><span class="line"> <span class="keyword">return</span> H.min</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">is_empty</span><span class="params">(H)</span>:</span></span><br><span class="line"> <span class="keyword">return</span> H.n == <span class="number">0</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">insert</span><span class="params">(H, x)</span>:</span></span><br><span class="line"> x.refresh()</span><br><span class="line"> <span class="keyword">if</span> H.min == <span class="keyword">None</span>:</span><br><span class="line"> H.min = x</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> w = H.min.left</span><br><span class="line"> y = H.min</span><br><span class="line"> x.left = w</span><br><span class="line"> x.right = y</span><br><span class="line"> w.right = x</span><br><span class="line"> y.left = x</span><br><span class="line"> <span class="keyword">if</span> x.key < H.min.key:</span><br><span class="line"> H.min = x</span><br><span class="line"> H.n = H.n + <span class="number">1</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">extract</span><span class="params">(H)</span>:</span></span><br><span class="line"> x = H.min</span><br><span class="line"> <span class="keyword">if</span> x != <span class="keyword">None</span>:</span><br><span class="line"> <span class="keyword">if</span> x.child != <span class="keyword">None</span>:</span><br><span class="line"> __add_list(x.child, x)</span><br><span class="line"> x.left.right = x.right</span><br><span class="line"> x.right.left = x.left</span><br><span class="line"> <span class="keyword">if</span> x == x.right:</span><br><span class="line"> H.min = <span class="keyword">None</span></span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> H.min = x.right</span><br><span class="line"> __consolidate(H)</span><br><span class="line"> H.n = H.n - <span class="number">1</span></span><br><span class="line"> x.refresh()</span><br><span class="line"> <span class="keyword">return</span> x</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">decrease_key</span><span class="params">(H, x, k)</span>:</span></span><br><span class="line"> <span class="keyword">assert</span>(k <= x.key)</span><br><span class="line"> <span class="keyword">if</span> k == x.key:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> x.key = k</span><br><span class="line"> y = x.parent</span><br><span class="line"> <span class="keyword">if</span> y != <span class="keyword">None</span> <span class="keyword">and</span> x.key < y.key:</span><br><span class="line"> __cut(H, x, y)</span><br><span class="line"> __cascading_cut(H, y)</span><br><span class="line"> <span class="keyword">if</span> x.key < H.min.key:</span><br><span class="line"> H.min = x</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__cut</span><span class="params">(H, x, y)</span>:</span></span><br><span class="line"> <span class="comment"># remove x from the child list of y, decrementing y.degree.</span></span><br><span class="line"> x.left.right = x.right</span><br><span class="line"> x.right.left = x.left</span><br><span class="line"> y.degree = y.degree - <span class="number">1</span></span><br><span class="line"> y.child = x.right</span><br><span class="line"> <span class="keyword">if</span> x == x.right:</span><br><span class="line"> y.child = <span class="keyword">None</span></span><br><span class="line"> <span class="comment"># add x to the root list of H</span></span><br><span class="line"> x.parent = <span class="keyword">None</span></span><br><span class="line"> x.mark = <span class="keyword">False</span></span><br><span class="line"> x.left = H.min.left</span><br><span class="line"> x.right = H.min</span><br><span class="line"> x.left.right = x</span><br><span class="line"> x.right.left = x</span><br><span class="line"> <span class="comment">#__add_list(x, H.min)</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__cascading_cut</span><span class="params">(H, y)</span>:</span></span><br><span class="line"> z = y.parent</span><br><span class="line"> <span class="keyword">if</span> z != <span class="keyword">None</span>:</span><br><span class="line"> <span class="keyword">if</span> y.mark == <span class="keyword">False</span>:</span><br><span class="line"> y.mark = <span class="keyword">True</span></span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> __cut(H, y, z)</span><br><span class="line"> __cascading_cut(H, z)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__add_list</span><span class="params">(y, x)</span>:</span></span><br><span class="line"> <span class="string">"""Add list y to x."""</span></span><br><span class="line"> <span class="keyword">if</span> y == <span class="keyword">None</span> <span class="keyword">or</span> x == <span class="keyword">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> z = y</span><br><span class="line"> <span class="keyword">while</span> z.right != y:</span><br><span class="line"> z.parent = x.parent</span><br><span class="line"> z = z.right</span><br><span class="line"> z.parent = x.parent</span><br><span class="line"> y.left = x.left</span><br><span class="line"> x.left.right = y</span><br><span class="line"> z.right = x</span><br><span class="line"> x.left = z</span><br><span class="line"></span><br><span class="line"> </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__union</span><span class="params">(H1, H2)</span>:</span></span><br><span class="line"> H = FibonacciHeap()</span><br><span class="line"> <span class="keyword">if</span> H1.min != <span class="keyword">None</span> <span class="keyword">and</span> H2.min == <span class="keyword">None</span>:</span><br><span class="line"> H.min = H1.min</span><br><span class="line"> H.n = H1.n</span><br><span class="line"> <span class="keyword">elif</span> H1.min == <span class="keyword">None</span> <span class="keyword">and</span> H2.min != <span class="keyword">None</span>:</span><br><span class="line"> H.min = H2.min</span><br><span class="line"> H.n = H2.n</span><br><span class="line"> <span class="keyword">elif</span> H1.min != <span class="keyword">None</span> <span class="keyword">and</span> H2.min != <span class="keyword">None</span>:</span><br><span class="line"> __add_list(H2.min, H1.min)</span><br><span class="line"> <span class="keyword">if</span> H1.min.key <= H2.min.key:</span><br><span class="line"> H.min = H1.min</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> H.min = H2.min</span><br><span class="line"> H.n = H1.n + H2.n</span><br><span class="line"> <span class="keyword">return</span> H</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__consolidate</span><span class="params">(H)</span>:</span></span><br><span class="line"> max_degree = __max_degree(H.n)</span><br><span class="line"> A = []</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> torange(<span class="number">0</span>, max_degree):</span><br><span class="line"> A.append(<span class="keyword">None</span>)</span><br><span class="line"> root_list = []</span><br><span class="line"> x = H.min</span><br><span class="line"> x.left.right = <span class="keyword">None</span></span><br><span class="line"> <span class="keyword">while</span> x != <span class="keyword">None</span>:</span><br><span class="line"> next_x = x.right</span><br><span class="line"> x.left = x</span><br><span class="line"> x.right = x</span><br><span class="line"> root_list.append(x)</span><br><span class="line"> x = next_x</span><br><span class="line"> <span class="keyword">for</span> x <span class="keyword">in</span> root_list:</span><br><span class="line"> <span class="comment">#__print_node_info(x)</span></span><br><span class="line"> d = x.degree</span><br><span class="line"> <span class="comment">#print "index=", d, "max_degree=", max_degree, "H.n=",H.n</span></span><br><span class="line"> <span class="keyword">while</span> A[d] != <span class="keyword">None</span>:</span><br><span class="line"> y = A[d]</span><br><span class="line"> <span class="keyword">if</span> y.key < x.key:</span><br><span class="line"> x,y = y,x</span><br><span class="line"> __link(y, x)</span><br><span class="line"> A[d] = <span class="keyword">None</span></span><br><span class="line"> d = d + <span class="number">1</span></span><br><span class="line"> A[d] = x</span><br><span class="line"> H.min = <span class="keyword">None</span></span><br><span class="line"> <span class="keyword">for</span> x <span class="keyword">in</span> A:</span><br><span class="line"> <span class="keyword">if</span> x != <span class="keyword">None</span>:</span><br><span class="line"> x.left = x</span><br><span class="line"> x.right = x</span><br><span class="line"> x.parent = <span class="keyword">None</span></span><br><span class="line"> <span class="keyword">if</span> H.min == <span class="keyword">None</span>:</span><br><span class="line"> H.min = x</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> __add_list(x, H.min)</span><br><span class="line"> <span class="keyword">if</span> x.key < H.min.key:</span><br><span class="line"> H.min = x</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__print_node_info</span><span class="params">(x)</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">print</span> <span class="string">"""</span><br><span class="line"> --- node info ---</span><br><span class="line"> key = %.1f</span><br><span class="line"> """</span> % (x.key)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__max_degree</span><span class="params">(n)</span>:</span></span><br><span class="line"> <span class="string">"""floor(lg(n))"""</span></span><br><span class="line"> lg = <span class="number">0</span></span><br><span class="line"> <span class="keyword">while</span> n/<span class="number">2</span> > <span class="number">0</span>:</span><br><span class="line"> lg = lg + <span class="number">1</span></span><br><span class="line"> n = n / <span class="number">2</span></span><br><span class="line"> <span class="keyword">return</span> lg</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">__link</span><span class="params">(y, x)</span>:</span></span><br><span class="line"> y.left.right = y.right</span><br><span class="line"> y.right.left = y.left</span><br><span class="line"> y.parent = x</span><br><span class="line"> <span class="keyword">if</span> x.child != <span class="keyword">None</span>:</span><br><span class="line"> x.child.left.right = y</span><br><span class="line"> y.left = x.child.left</span><br><span class="line"> y.right = x.child</span><br><span class="line"> x.child.left = y</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> x.child = y</span><br><span class="line"> y.left = y</span><br><span class="line"> y.right = y</span><br><span class="line"> x.degree = x.degree + <span class="number">1</span></span><br><span class="line"> y.mark = <span class="keyword">False</span></span><br><span class="line"></span><br><span class="line"><span class="comment">######################################################################</span></span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">print_heap</span><span class="params">(s, indent=<span class="string">'#'</span>, char=<span class="string">'#'</span>)</span>:</span></span><br><span class="line"> x = s</span><br><span class="line"> first_iteration = <span class="keyword">True</span></span><br><span class="line"> <span class="keyword">while</span> x != <span class="keyword">None</span> <span class="keyword">and</span> (first_iteration <span class="keyword">or</span> x != s):</span><br><span class="line"> first_iteration = <span class="keyword">False</span></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"%s %s [%d]"</span> %(indent, x.key, x.degree)</span><br><span class="line"> <span class="keyword">if</span> x.child != <span class="keyword">None</span>:</span><br><span class="line"> print_heap(x.child, indent+char, char)</span><br><span class="line"> x = x.right</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">show_heap</span><span class="params">(H)</span>:</span></span><br><span class="line"> print_heap(H.min, <span class="string">'o'</span>, <span class="string">'->'</span>)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">test</span><span class="params">()</span>:</span></span><br><span class="line"> <span class="comment">#data = [31,40,50,37,45,60,65,73,23,76]</span></span><br><span class="line"> <span class="comment">#data = [10,20,30,40,50,60,70,80,90]</span></span><br><span class="line"> data = [<span class="number">30</span>,<span class="number">10</span>,<span class="number">90</span>,<span class="number">80</span>,<span class="number">60</span>,<span class="number">70</span>,<span class="number">20</span>,<span class="number">50</span>,<span class="number">40</span>]</span><br><span class="line"> <span class="comment">#data = [3,3,2,1,8,3,7]</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"Input data:"</span>, data</span><br><span class="line"></span><br><span class="line"> <span class="comment">############################################################</span></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"""</span><br><span class="line"> We print out the state of the heap as each data item is wrapped in</span><br><span class="line"> a node and inserted into the heap. Depth of the tree is indicated</span><br><span class="line"> by the indentation. The first number is the key, and the number</span><br><span class="line"> in square brackets the degree of the node.</span><br><span class="line"> """</span></span><br><span class="line"></span><br><span class="line"> min = <span class="keyword">None</span></span><br><span class="line"> max = <span class="keyword">None</span></span><br><span class="line"> nodes = []</span><br><span class="line"> H = make_heap()</span><br><span class="line"> <span class="keyword">for</span> d <span class="keyword">in</span> data:</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"---------------------------------------- insert (%2d) ---"</span>%(d)</span><br><span class="line"> n = make_node(d)</span><br><span class="line"> <span class="keyword">if</span> min == <span class="keyword">None</span> <span class="keyword">or</span> n.key < min.key:</span><br><span class="line"> min = n</span><br><span class="line"> <span class="keyword">if</span> max == <span class="keyword">None</span> <span class="keyword">or</span> n.key > max.key:</span><br><span class="line"> max = n</span><br><span class="line"> nodes.append(n)</span><br><span class="line"> insert(H, n)</span><br><span class="line"> print_heap(H.min, <span class="string">'o'</span>, <span class="string">'->'</span>)</span><br><span class="line"></span><br><span class="line"> <span class="comment">############################################################</span></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"""</span><br><span class="line"> Test if the D() function (__max_degree()) works. Print out</span><br><span class="line"> D(0..9).</span><br><span class="line"> """</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> xrange(<span class="number">10</span>):</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"D(%d)=%d"</span> % (i, __max_degree(i))</span><br><span class="line"></span><br><span class="line"> <span class="comment">############################################################</span></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"""</span><br><span class="line"> Extract half of the data. Do we get them in the right order?</span><br><span class="line"> """</span></span><br><span class="line"></span><br><span class="line"> print_heap(H.min, <span class="string">'o'</span>, <span class="string">'->'</span>)</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> xrange(len(data)/<span class="number">2</span>):</span><br><span class="line"> n = extract(H)</span><br><span class="line"> <span class="keyword">if</span> n != <span class="keyword">None</span>:</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"---------------------------------------- extracted (%2d) ---"</span>%(n.key)</span><br><span class="line"> print_heap(H.min, <span class="string">'o'</span>, <span class="string">'->'</span>)</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"---------------------------------------- extracted (None) ---"</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">############################################################</span></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"""</span><br><span class="line"> To test decrease key, we print out the state of the heap, decrease</span><br><span class="line"> node %d to %d, and print out the heap again.</span><br><span class="line"> """</span> % (max.key, min.key)</span><br><span class="line"></span><br><span class="line"> print_heap(H.min, <span class="string">'before o'</span>, <span class="string">'->'</span>)</span><br><span class="line"> decrease_key(H, max, min.key)</span><br><span class="line"> <span class="keyword">print</span></span><br><span class="line"> print_heap(H.min, <span class="string">'after o'</span>, <span class="string">'->'</span>)</span><br><span class="line"></span><br><span class="line"> <span class="comment">############################################################</span></span><br><span class="line"> factor = <span class="number">2</span></span><br><span class="line"> repetitions = <span class="number">10</span></span><br><span class="line"> <span class="keyword">print</span> <span class="string">"""</span><br><span class="line"> Rigorous insert and extract test. We extract one node, multiply</span><br><span class="line"> it by %.1f, insert it back in, and repeat this %d times.</span><br><span class="line"> """</span> % (factor, repetitions)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> xrange(repetitions):</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"------------------------------------------------------------"</span></span><br><span class="line"> n = extract(H)</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"Extracted %.1f"</span> % (n.key)</span><br><span class="line"> n.key = n.key * factor</span><br><span class="line"> insert(H, n)</span><br><span class="line"> <span class="keyword">print</span> <span class="string">"Inserted %.1f"</span> % (n.key)</span><br><span class="line"> print_heap(H.min, <span class="string">'o'</span>, <span class="string">'->'</span>)</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><br><span class="line"><span class="comment">######################################################################</span></span><br><span class="line"><span class="comment">######################################################################</span></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>: test()</span><br><span class="line"></span><br><span class="line"><span class="comment"># LocalWords: doublely</span></span><br></pre></td></tr></table></figure>
<footer class="meta">
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/04/30/floyd-warshall/">floyd_warshall</a></h1>
<time datetime="2015-04-30T02:58:59.000Z">
<span class="day">30</span><span class="month">Apr</span>
</time>
</header>
<div class="entry-content">
<p>wiki 伪代码</p>
<h2 id="algorithm">algorithm</h2><pre><code>1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3 dist[<span class="link_label">v</span>][<span class="link_reference">v</span>] ← 0
4 for each edge (u,v)
5 dist[<span class="link_label">u</span>][<span class="link_reference">v</span>] ← w(u,v) // the weight of the edge (u,v)
6 for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[<span class="link_label">i</span>][<span class="link_reference">j</span>] > dist[<span class="link_label">i</span>][<span class="link_reference">k</span>] + dist[<span class="link_label">k</span>][<span class="link_reference">j</span>]
10 dist[<span class="link_label">i</span>][<span class="link_reference">j</span>] ← dist[<span class="link_label">i</span>][<span class="link_reference">k</span>] + dist[<span class="link_label">k</span>][<span class="link_reference">j</span>]
11 end if
</code></pre><h2 id="Path_reconstruction">Path reconstruction</h2><pre><code>let dist be a |V| × |V| <span class="keyword">array</span> <span class="keyword">of</span> minimum distances initialized <span class="keyword">to</span> ∞ (infinity)
let <span class="keyword">next</span> be a |V| × |V| <span class="keyword">array</span> <span class="keyword">of</span> vertex indices initialized <span class="keyword">to</span> <span class="keyword">null</span>
<span class="keyword">procedure</span> FloydWarshallWithPathReconstruction ()
<span class="keyword">for</span> each edge (u,v)
dist[u][v] ← w(u,v) // the weight <span class="keyword">of</span> the edge (u,v)
<span class="keyword">next</span>[u][v] ← v
<span class="keyword">for</span> k from <span class="number">1</span> <span class="keyword">to</span> |V| // standard Floyd-Warshall implementation
<span class="keyword">for</span> i from <span class="number">1</span> <span class="keyword">to</span> |V|
<span class="keyword">for</span> j from <span class="number">1</span> <span class="keyword">to</span> |V|
<span class="keyword">if</span> dist[i][k] + dist[k][j] < dist[i][j] <span class="keyword">then</span>
dist[i][j] ← dist[i][k] + dist[k][j]
<span class="keyword">next</span>[i][j] ← <span class="keyword">next</span>[i][k]
<span class="keyword">procedure</span> Path(u, v)
<span class="keyword">if</span> <span class="keyword">next</span>[u][v] = <span class="keyword">null</span> <span class="keyword">then</span>
<span class="keyword">return</span> []
path = [u]
<span class="keyword">while</span> u ≠ v
u ← <span class="keyword">next</span>[u][v]
path.append(u)
<span class="keyword">return</span> path
</code></pre>
<footer class="meta">
</footer>
</div>
</article>
<article class="post">
<div class="gallery">
<div class="photoset">
<img src="">
</div>
<div class="control">
<div class="prev"></div>
<div class="next"></div>
</div>
</div>
<header>
<h1 class="title"><a href="/hexoblog/2015/04/30/binarysearchtree/">binarysearchtree</a></h1>
<time datetime="2015-04-30T02:50:16.000Z">
<span class="day">30</span><span class="month">Apr</span>
</time>
</header>
<div class="entry-content">
<!-- the code is from https://gist.github.com/thinkphp/1450738 -->
<figure class="highlight python"><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><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">'''</span><br><span class="line"> by Adrian Statescu <[email protected]></span><br><span class="line"> Twitter: @thinkphp</span><br><span class="line"> G+ : http://gplus.to/thinkphp</span><br><span class="line"> MIT Style License</span><br><span class="line">'''</span></span><br><span class="line"><span class="string">'''</span><br><span class="line"> Binary Search Tree</span><br><span class="line"> ------------------</span><br><span class="line"></span><br><span class="line"> Trees can come in many different shapes, and they can vary in the number of children allowed per node or in the way</span><br><span class="line"> they organize data values within the nodes. One of the most commonly used trees in computer science is the binary tree.</span><br><span class="line"> A binary tree is a tree in which each node can have at most two children. On child is identified as the left child and</span><br><span class="line"> the other as the right child. The topmost node of the tree is known as the root node.It provides the single acccess point</span><br><span class="line"> into the structure. The root node is the only node in the tree that does not have an incoming edge (an edge directed towart it)</span><br><span class="line"> By definition every non=empty tree must have contain a root node.</span><br><span class="line"> </span><br><span class="line">'''</span></span><br><span class="line"> </span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self,info)</span>:</span> <span class="comment">#constructor of class</span></span><br><span class="line"> </span><br><span class="line"> self.info = info <span class="comment">#information for node</span></span><br><span class="line"> self.left = <span class="keyword">None</span> <span class="comment">#left leef</span></span><br><span class="line"> self.right = <span class="keyword">None</span> <span class="comment">#right leef</span></span><br><span class="line"> self.level = <span class="keyword">None</span> <span class="comment">#level none defined</span></span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__str__</span><span class="params">(self)</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">return</span> str(self.info) <span class="comment">#return as string</span></span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">searchtree</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self)</span>:</span> <span class="comment">#constructor of class</span></span><br><span class="line"> </span><br><span class="line"> self.root = <span class="keyword">None</span></span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">create</span><span class="params">(self,val)</span>:</span> <span class="comment">#create binary search tree nodes</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> self.root == <span class="keyword">None</span>:</span><br><span class="line"> </span><br><span class="line"> self.root = Node(val)</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> </span><br><span class="line"> current = self.root</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">while</span> <span class="number">1</span>:</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> val < current.info:</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> current.left:</span><br><span class="line"> current = current.left</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> current.left = Node(val)</span><br><span class="line"> <span class="keyword">break</span>; </span><br><span class="line"> </span><br><span class="line"> <span class="keyword">elif</span> val > current.info:</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> current.right:</span><br><span class="line"> current = current.right</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> current.right = Node(val)</span><br><span class="line"> <span class="keyword">break</span>; </span><br><span class="line"> </span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> <span class="keyword">break</span> </span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">bft</span><span class="params">(self)</span>:</span> <span class="comment">#Breadth-First Traversal</span></span><br><span class="line"> </span><br><span class="line"> self.root.level = <span class="number">0</span> </span><br><span class="line"> queue = [self.root]</span><br><span class="line"> out = []</span><br><span class="line"> current_level = self.root.level</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">while</span> len(queue) > <span class="number">0</span>:</span><br><span class="line"> </span><br><span class="line"> current_node = queue.pop(<span class="number">0</span>)</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> current_node.level > current_level:</span><br><span class="line"> current_level += <span class="number">1</span></span><br><span class="line"> out.append(<span class="string">"\n"</span>)</span><br><span class="line"> </span><br><span class="line"> out.append(str(current_node.info) + <span class="string">" "</span>)</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> current_node.left:</span><br><span class="line"> </span><br><span class="line"> current_node.left.level = current_level + <span class="number">1</span></span><br><span class="line"> queue.append(current_node.left)</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> current_node.right:</span><br><span class="line"> </span><br><span class="line"> current_node.right.level = current_level + <span class="number">1</span></span><br><span class="line"> queue.append(current_node.right)</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"> <span class="keyword">print</span> <span class="string">""</span>.join(out) </span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">inorder</span><span class="params">(self,node)</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> node <span class="keyword">is</span> <span class="keyword">not</span> <span class="keyword">None</span>:</span><br><span class="line"> </span><br><span class="line"> self.inorder(node.left)</span><br><span class="line"> <span class="keyword">print</span> node.info</span><br><span class="line"> self.inorder(node.right)</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">preorder</span><span class="params">(self,node)</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> node <span class="keyword">is</span> <span class="keyword">not</span> <span class="keyword">None</span>:</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">print</span> node.info</span><br><span class="line"> self.preorder(node.left)</span><br><span class="line"> self.preorder(node.right)</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">postorder</span><span class="params">(self,node)</span>:</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> node <span class="keyword">is</span> <span class="keyword">not</span> <span class="keyword">None</span>:</span><br><span class="line"> </span><br><span class="line"> self.postorder(node.left)</span><br><span class="line"> self.postorder(node.right)</span><br><span class="line"> <span class="keyword">print</span> node.info</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line">tree = searchtree() </span><br><span class="line">arr = [<span class="number">8</span>,<span class="number">3</span>,<span class="number">1</span>,<span class="number">6</span>,<span class="number">4</span>,<span class="number">7</span>,<span class="number">10</span>,<span class="number">14</span>,<span class="number">13</span>]</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> arr:</span><br><span class="line"> tree.create(i)</span><br><span class="line"><span class="keyword">print</span> <span class="string">'Breadth-First Traversal'</span></span><br><span class="line">tree.bft()</span><br><span class="line"><span class="keyword">print</span> <span class="string">'Inorder Traversal'</span></span><br><span class="line">tree.inorder(tree.root) </span><br><span class="line"><span class="keyword">print</span> <span class="string">'Preorder Traversal'</span></span><br><span class="line">tree.preorder(tree.root) </span><br><span class="line"><span class="keyword">print</span> <span class="string">'Postorder Traversal'</span></span><br><span class="line">tree.postorder(tree.root)</span><br></pre></td></tr></table></figure>
<footer class="meta">
</footer>
</div>
</article>
<nav id="pagenavi">
<a href="/hexoblog/page/2/" class="alignright next">下一頁</a>
<div class="clearfix"></div>
</nav></div>
<footer id="footer" class="inner"><div class="social alignright">
<a class="rss" href="/hexoblog/atom.xml" title="RSS">RSS</a>
</div>
<p>
© 2015 Fayou Zhang
</p>
<div class="clearfix"></div></footer>
<script src="/hexoblog/js/jquery.imagesloaded.min.js"></script>
<script src="/hexoblog/js/gallery.js"></script>
<link rel="stylesheet" href="/hexoblog/fancybox/jquery.fancybox.css" media="screen" type="text/css">
<script src="/hexoblog/fancybox/jquery.fancybox.pack.js"></script>
<script type="text/javascript">
(function($){
$('.fancybox').fancybox();
})(jQuery);
</script>
<div id="phasebeam">
<canvas></canvas>
<canvas></canvas>
<canvas></canvas>
</div>
<script src="/hexoblog/js/phasebeam.js"></script>
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
processEscapes: true
}
});
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
}
});
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Queue(function() {
var all = MathJax.Hub.getAllJax(), i;
for(i=0; i < all.length; i += 1) {
all[i].SourceElement().parentNode.className += ' has-jax';
}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ["$","$"], ["\\(","\\)"] ],
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
processEscapes: true
}
});
MathJax.Hub.Queue(function() {
var all = MathJax.Hub.getAllJax();
for (var i = 0; i < all.length; ++i)
all[i].SourceElement().parentNode.className += ' has-jax';
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
</body>
</html>