-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
944 lines (645 loc) · 200 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.3.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/Helmet.ico">
<link rel="icon" type="image/png" sizes="32x32" href="/images/Helmet.ico">
<link rel="icon" type="image/png" sizes="16x16" href="/images/Helmet.ico">
<link rel="mask-icon" href="/images/Helmet.ico" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"www.mixaler.com","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
</script>
<meta name="description" content="永不关机">
<meta property="og:type" content="website">
<meta property="og:title" content="MIXALER--blog">
<meta property="og:url" content="http://www.mixaler.com/index.html">
<meta property="og:site_name" content="MIXALER--blog">
<meta property="og:description" content="永不关机">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="MIXALER">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="http://www.mixaler.com/">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'zh-CN'
};
</script>
<title>MIXALER--blog</title>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container use-motion">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">MIXALER--blog</h1>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
</div>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="main-menu menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>
</li>
</ul>
</nav>
</div>
</header>
<div class="back-to-top">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content index posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/06/24/%E4%B8%BA%E5%95%A5%E8%A6%81%E5%AD%A6%E5%BA%95%E5%B1%82/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/06/24/%E4%B8%BA%E5%95%A5%E8%A6%81%E5%AD%A6%E5%BA%95%E5%B1%82/" class="post-title-link" itemprop="url">为啥要学习底层</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-06-24 15:52:21 / 修改时间：15:48:42" itemprop="dateCreated datePublished" datetime="2021-06-24T15:52:21+08:00">2021-06-24</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>698</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>1 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>今天学习 socket 编程的时候，我在尝试着弄清楚 socket api 的各种参数的含义，然后尝试着写一个可以在服务端和客户端自由发送消息的程序。我突然想到这样一件事情。我以前吹牛逼说我可以一天时间用 python 做个什么什么炫酷的功能。但是我现在却在用 c 语言完成这样简单的事情。这就在程序功能上有很大的落差。由此产生了一个思考，学习这种底层的东西，比如汇编语言，编译原理，c 语言到底有没有意义。是否应该重复造轮子。</p>
<p>我的答案是，有必要。但前提是对程序员很有必要。或许可以说是对 ”高级“ 程序员有必要。如果只是拿编程语言干活的话，那么学习底层的效率就太低了。python，java 这种语言在开发效率上远超 c 语言。学习成本也要低得多。但是这种就像是开着一台挖掘机干活的驾驶员一样，你熟练地驾驶挖掘机，能快速完成生产任务。但是挖掘机的内部原理你不知道，其实你也没有必要知道。你知道怎样使挖掘机动起来就行了。就像是 python java 的许多框架可以快速的被用来搭建起一个网站，然后用来实现一些目的。熟练的程序员可以快速地完成这个任务，但是这个框架的内部实现程序员不知道，其实也没有必要知道。但是用 c 语言不一样，c 语言写出来的东西除了操作系统和操作系统提供的一些 API，很少有非常成熟的，可以说是事情标准的框架可以拿来直接用，当然也不是没有，比如 nginx，sqlite 等。但是就算是使用这类框架，复杂程度也比 java 和 python 那一套高得多。所以用 c 开发的时候就必须要求你对原理足够熟悉，否则就没法完成任务。总的来讲就像是写 c 的程序员在用车床造出挖掘机，写 python，java 的程序员用挖掘机来完成具体的任务。</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/06/24/%E6%96%BD%E5%AF%86%E7%89%B9%E6%AD%A3%E4%BA%A4%E5%8C%96%E6%96%B9%E6%B3%95/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/06/24/%E6%96%BD%E5%AF%86%E7%89%B9%E6%AD%A3%E4%BA%A4%E5%8C%96%E6%96%B9%E6%B3%95/" class="post-title-link" itemprop="url">python 实现格拉姆-施密特正交化方法</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-06-24 15:52:21 / 修改时间：15:51:53" itemprop="dateCreated datePublished" datetime="2021-06-24T15:52:21+08:00">2021-06-24</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>3.5k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>3 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>线性代数中，经常需要求 n 个 n 维线性无关向量的 n 个等价正交向量。用到的是 Gram-Schmidt 正交化方法</p>
<p>方法如下：</p>
<p><img src="assets/20190909220153311.png" alt="img"></p>
<p><img src="assets/20190909220915145.png" alt="img"></p>
<p><img src="assets/20190909220947370.png" alt="img"></p>
<p><img src="assets/20190909221018905.png" alt="img"></p>
<p>正交规范化示例</p>
<p><img src="assets/20190909221050868.png" alt="img"></p>
<p><img src="assets/20190909221206493.png" alt="img"></p>
<p>资料来源： <a target="_blank" rel="noopener" href="https://blog.csdn.net/hpdlzu80100/article/details/100677372">https://blog.csdn.net/hpdlzu80100/article/details/100677372</a></p>
<p>下面就通过 python 来实现这一过程</p>
<ul>
<li> 如果输入的是 n 个 n 维线性无关的向量，输出的是 n 个正交的长为 1 的向量</li>
<li> 如果输入的 n 个 n 维向量线性相关，输出的是包含有零向量的 n 个向量，非零向量相互正交</li>
</ul>
<p>其实现如下</p>
<ul>
<li> 通过 numpy</li>
</ul>
<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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">my_gramSchmidt_np</span>(<span class="params">vectors</span>):</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">proj</span>(<span class="params">x, u</span>):</span></span><br><span class="line"> u = unit_vec(u)</span><br><span class="line"> <span class="keyword">return</span> np.dot(x, u) * u</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">unit_vec</span>(<span class="params">x</span>):</span></span><br><span class="line"> <span class="keyword">return</span> x / np.linalg.norm(x)</span><br><span class="line"> vectors = np.atleast_2d(vectors)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">len</span>(vectors) == <span class="number">0</span>:</span><br><span class="line"> <span class="keyword">return</span> []</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">len</span>(vectors) == <span class="number">1</span>:</span><br><span class="line"> <span class="keyword">return</span> unit_vec(vectors)</span><br><span class="line"></span><br><span class="line"> u = vectors[-<span class="number">1</span>]</span><br><span class="line"></span><br><span class="line"> basis = my_gramSchmidt_np(vectors[<span class="number">0</span>:-<span class="number">1</span>])</span><br><span class="line"></span><br><span class="line"> w = np.atleast_2d(u - np.<span class="built_in">sum</span>(proj(u, v) <span class="keyword">for</span> v <span class="keyword">in</span> basis))</span><br><span class="line"> basis = np.append(basis, unit_vec(w), axis=<span class="number">0</span>)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> basis</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">gram_schmidt_np</span>(<span class="params">V</span>):</span></span><br><span class="line"> <span class="comment"># YOUR CODE HERE</span></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">type</span>(V) <span class="keyword">is</span> <span class="keyword">not</span> np.ndarray:</span><br><span class="line"> <span class="keyword">raise</span> ValueError</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> <span class="keyword">if</span> V.shape[<span class="number">0</span>] != V.shape[<span class="number">1</span>]:</span><br><span class="line"> <span class="keyword">raise</span> ValueError</span><br><span class="line"></span><br><span class="line"> vectors = np.array(V)</span><br><span class="line"> vectors = np.transpose(vectors)</span><br><span class="line"> vectors = vectors.tolist()</span><br><span class="line"> vectors = my_gramSchmidt_np(vectors)</span><br><span class="line"> dim = np.linalg.matrix_rank(vectors)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> dim == vectors.shape[<span class="number">0</span>]:</span><br><span class="line"> <span class="keyword">return</span> vectors</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> vectors = np.transpose(vectors)</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> vectors:</span><br><span class="line"> <span class="keyword">for</span> pos, j <span class="keyword">in</span> <span class="built_in">enumerate</span>(i):</span><br><span class="line"> <span class="keyword">if</span> pos >= dim:</span><br><span class="line"> i[pos] = <span class="number">0</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> vectors</span><br></pre></td></tr></table></figure>
<ul>
<li> 通过 sympy</li>
</ul>
<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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">my_gramSchmidt_sp</span>(<span class="params">*vectors</span>):</span></span><br><span class="line"> normalize = <span class="literal">True</span></span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">project</span>(<span class="params">a, b</span>):</span></span><br><span class="line"> <span class="keyword">return</span> b * (a.dot(b, hermitian=<span class="literal">True</span>) / b.dot(b, hermitian=<span class="literal">True</span>))</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">perp_to_subspace</span>(<span class="params">vec, basis</span>):</span></span><br><span class="line"></span><br><span class="line"> components = [project(vec, b) <span class="keyword">for</span> b <span class="keyword">in</span> basis]</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">len</span>(basis) == <span class="number">0</span>:</span><br><span class="line"> <span class="keyword">return</span> vec</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> vec - reduce(<span class="keyword">lambda</span> a, b: a + b, components)</span><br><span class="line"></span><br><span class="line"> ret = []</span><br><span class="line"> vectors = <span class="built_in">list</span>(vectors)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">while</span> <span class="built_in">len</span>(vectors) > <span class="number">0</span> <span class="keyword">and</span> vectors[<span class="number">0</span>].is_zero_matrix:</span><br><span class="line"> <span class="keyword">del</span> vectors[<span class="number">0</span>]</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> vec <span class="keyword">in</span> vectors:</span><br><span class="line"> perp = perp_to_subspace(vec, ret)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> <span class="keyword">not</span> perp.is_zero_matrix:</span><br><span class="line"> ret.append(Matrix(perp))</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> normalize:</span><br><span class="line"> ret = [vec / vec.norm() <span class="keyword">for</span> vec <span class="keyword">in</span> ret]</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> ret</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">gram_schmidt_sp</span>(<span class="params">V</span>):</span></span><br><span class="line"> <span class="comment"># YOUR CODE HERE</span></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">type</span>(V) <span class="keyword">is</span> <span class="keyword">not</span> sympy.MutableDenseMatrix:</span><br><span class="line"> <span class="keyword">raise</span> ValueError</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">len</span>(V.tolist()) != <span class="built_in">len</span>(V.tolist()[<span class="number">0</span>]):</span><br><span class="line"> <span class="keyword">raise</span> ValueError</span><br><span class="line"> V = np.array(V)</span><br><span class="line"> V = np.transpose(V)</span><br><span class="line"> V = Matrix(V)</span><br><span class="line"> vlist = V.tolist()</span><br><span class="line"> tmp_list = []</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> vlist:</span><br><span class="line"> tmp_list.append(Matrix(i))</span><br><span class="line"> result = my_gramSchmidt_sp(*tmp_list)</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">len</span>(result) == <span class="built_in">len</span>(tmp_list):</span><br><span class="line"> ma_list = []</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> result:</span><br><span class="line"> tmp_list = []</span><br><span class="line"> <span class="keyword">for</span> j <span class="keyword">in</span> i:</span><br><span class="line"> tmp_list.append(j)</span><br><span class="line"> tmp = tmp_list</span><br><span class="line"> ma_list.append(tmp)</span><br><span class="line"></span><br><span class="line"> result = Matrix(ma_list)</span><br><span class="line"> <span class="keyword">return</span> result</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> ma_list = []</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> result:</span><br><span class="line"> tmp_list = []</span><br><span class="line"> <span class="keyword">for</span> j <span class="keyword">in</span> i:</span><br><span class="line"> tmp_list.append(j)</span><br><span class="line"> tmp = tmp_list</span><br><span class="line"> ma_list.append(tmp)</span><br><span class="line"> result = Matrix(ma_list)</span><br><span class="line"> result = Matrix(result).H</span><br><span class="line"> result = result.row_join(Matrix([[<span class="number">0</span>], [<span class="number">0</span>]]))</span><br><span class="line"> <span class="keyword">return</span> result</span><br></pre></td></tr></table></figure>
<p>下面是测试代码</p>
<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></pre></td><td class="code"><pre><span class="line"><span class="comment"># Check that it works for a specific matrix V of linearly independent vectors.</span></span><br><span class="line">V = np.array([[<span class="number">1</span>, <span class="number">2</span>], [<span class="number">3</span>, <span class="number">4</span>]])</span><br><span class="line">W = np.array([[<span class="number">0.31622777</span>, <span class="number">0.9486833</span>], [<span class="number">0.9486833</span>, -<span class="number">0.31622777</span>]])</span><br><span class="line">W1 = gram_schmidt_np(V)</span><br><span class="line">difference = np.linalg.norm(W1 - W)</span><br><span class="line">assert_almost_equal(difference, <span class="number">0</span>, delta=<span class="number">1e-8</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># Check that it works for a case when vectors are linearly dependent</span></span><br><span class="line">V = np.array([[<span class="number">1</span>, <span class="number">2</span>], [<span class="number">2</span>, <span class="number">4</span>]])</span><br><span class="line">W = gram_schmidt_np(V)</span><br><span class="line"></span><br><span class="line">W1 = np.array([[<span class="number">0.4472136</span>, <span class="number">0.</span>], [<span class="number">0.89442719</span>, <span class="number">0.</span>]])</span><br><span class="line">difference = np.linalg.norm(W1 - W)</span><br><span class="line">assert_almost_equal(difference, <span class="number">0</span>, delta=<span class="number">1e-8</span>)</span><br><span class="line"></span><br><span class="line">assert_raises(ValueError, gram_schmidt_np, <span class="number">1</span>)</span><br><span class="line">assert_raises(ValueError, gram_schmidt_np, np.array([[<span class="number">1</span>, <span class="number">2</span>], [<span class="number">3</span>, <span class="number">4</span>], [<span class="number">5</span>, <span class="number">6</span>]]))</span><br><span class="line"></span><br><span class="line">V = sympy.Matrix([[<span class="number">1</span>, <span class="number">2</span>], [<span class="number">3</span>, <span class="number">4</span>]])</span><br><span class="line">W = sympy.Matrix([[sympy.sqrt(<span class="number">10</span>) / <span class="number">10</span>, <span class="number">3</span> * sympy.sqrt(<span class="number">10</span>) / <span class="number">10</span>], [<span class="number">3</span> * sympy.sqrt(<span class="number">10</span>) / <span class="number">10</span>, -sympy.sqrt(<span class="number">10</span>) / <span class="number">10</span>]])</span><br><span class="line">W1 = gram_schmidt_sp(V)</span><br><span class="line"></span><br><span class="line"><span class="comment"># W1.row_join()</span></span><br><span class="line">assert_equal(W - W1, sympy.zeros(<span class="number">2</span>, <span class="number">2</span>))</span><br><span class="line"></span><br><span class="line">V = sympy.Matrix([[<span class="number">1</span>, <span class="number">2</span>], [<span class="number">2</span>, <span class="number">4</span>]])</span><br><span class="line">W = sympy.Matrix([[sympy.sqrt(<span class="number">5</span>) / <span class="number">5</span>, <span class="number">0</span>], [<span class="number">2</span> * sympy.sqrt(<span class="number">5</span>) / <span class="number">5</span>, <span class="number">0</span>]])</span><br><span class="line">W1 = gram_schmidt_sp(V)</span><br><span class="line"></span><br><span class="line">assert_equal(W - W1, sympy.zeros(<span class="number">2</span>, <span class="number">2</span>))</span><br><span class="line"></span><br><span class="line">assert_raises(ValueError, gram_schmidt_sp, <span class="number">1</span>)</span><br><span class="line">assert_raises(ValueError, gram_schmidt_sp, sympy.Matrix([[<span class="number">1</span>, <span class="number">2</span>], [<span class="number">3</span>, <span class="number">4</span>], [<span class="number">5</span>, <span class="number">6</span>]]))</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/06/24/%E5%85%B3%E4%BA%8E%E5%86%99%E6%96%87%E6%A1%A3%E7%9A%84%E4%B8%80%E4%BA%9B%E6%83%B3%E6%B3%95/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/06/24/%E5%85%B3%E4%BA%8E%E5%86%99%E6%96%87%E6%A1%A3%E7%9A%84%E4%B8%80%E4%BA%9B%E6%83%B3%E6%B3%95/" class="post-title-link" itemprop="url">关于写文档的一些想法</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-06-24 15:52:21 / 修改时间：15:46:35" itemprop="dateCreated datePublished" datetime="2021-06-24T15:52:21+08:00">2021-06-24</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>248</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>1 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>要写出一篇好的文档，需要注意的部分还是很多的。和记录自己的灵感和思路不同的是，文档要保证具有条理性，便于阅读，且内容相对完成，自成体系。要求还是挺多的。那为啥要写文档，而不是像笔记本那样，随时记录，不需要排版，不需要逻辑清晰，随时都可以写，从而省去了大量的用于完善形式的时间。我以前也是这样想的，没有写文档的想法，就是单纯的记笔记。</p>
<p>一些要求： 每篇文档后面都要写上参考资料，附上链接，一是便于自己找到资料来源，重新阅读，二是尊重原作者，当然自己的博客被人转载分享或者引用为参考资料，我也会很开心的。</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/06/24/%E5%A4%9A%E7%BA%BF%E7%A8%8B%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/06/24/%E5%A4%9A%E7%BA%BF%E7%A8%8B%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95/" class="post-title-link" itemprop="url">多线程编程入门之多线程矩阵乘法</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-06-24 15:52:21 / 修改时间：15:44:34" itemprop="dateCreated datePublished" datetime="2021-06-24T15:52:21+08:00">2021-06-24</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>16k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>15 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="多线程编程入门之多线程矩阵乘法"><a href="#多线程编程入门之多线程矩阵乘法" class="headerlink" title="多线程编程入门之多线程矩阵乘法"></a>多线程编程入门之多线程矩阵乘法</h1><p>一个 2 阶矩阵相乘的例子</p>
<p><img src="assets/image-20210624153844783.png" alt="image-20210624153844783"></p>
<p>显然，$$c_{11}$$ 通过 [$$a_{11}$$, $$a_{12}$$] 与 $$ [b_{11}, b_{21}]^T $$ 相乘得到，做了两次乘法，一次加法。同理，得到矩阵 C 的其他元素也需要相同数量的乘法和加法。那么，设矩阵的阶数为 n，得到矩阵乘法的时间复杂度为 $$ O(n^3) $$。假如有 $ n^2 $ 个处理器并行工作，那么只需要做 n 次乘法运算即可完成矩阵乘法，时间复杂度降为 O(n)。</p>
<p>现在的计算机都是多核 cpu，每个核都可以看作一个独立的处理器。因此，将计算线程映射到每个核上可以显著提高整个算法的速度。现在的问题是如何用一个独立的线程实现向量相乘，从而实现矩阵乘法的并行运算。事实上，操作系统可以自动地将一个线程放到一个核上去执行，具体怎样实现的就不在本教程的范围内啦。当然，你可以创建数量超过处理器核心数量的线程，然后交给操作系统去安排如何调度执行这些线程。</p>
<p>本教程用 c 语言来实现多线程 $$ n<em>n $$ 矩阵乘法，并测量其运行性能。从 2</em>2 矩阵和 4 个线程开始，测量当增加 n 的值，从而增加线程数时，运行时的规模是怎样的。为了避免随机误差，同一个多线程乘法运行多次取平均值。</p>
<ul>
<li><p> 理论上，采用 $ n^2 $ 个线程时，可以达到 O(n) 的性能。但是，实现这一目标的可能性很小。这是为什么呢，下面通过实验来解释背后的原因</p>
</li>
<li><p> 另一个需要考虑的问题是，性能如何随 n 和用于计算向量积的静态分配线程的数量而变化</p>
</li>
<li><p> 是否有可能通过重用较小的线程池（小于 $$ n^2 $$）来实现近似相同的性能，其中每个线程执行两个或多个向量乘法的序列，通过实验来解释一下其中的原因。</p>
</li>
<li><p> 机器的物理核心数量对性能有影响吗，缓存大小呢</p>
</li>
</ul>
<p>在这个实验中，我们只考虑静态线程分配模型，其中在执行矩阵乘法之前创建一个足够大的<strong>线程池</strong>。这个方法比较容易实现。记录的时间只是矩阵乘法的持续时间。不包括创建/销毁线程的时间。解决方案只考虑执行矩阵乘法所花费的时间，而不是线程创建和销毁与操作系统相关的开销。</p>
<p>由于这是多线程编程，根据程序的组织方式，可能会遇到 race hazards，也就是说，一个线程偶尔会在另一个线程之前完成它的工作，结果有时会从不完整的结果中计算出答案。因此需要仔细考虑是否需要使用适当的同步机制。(显然，race hazards 是并发编程中的一个主要问题，也是许多软件灾难的根源!)</p>
<p>用于存储矩阵的数据结构由您决定，但是任何比二维数组更复杂的东西，比如专门的矩阵类，都可能给带来新问题。类似地，通过引用而不是值传递函数参数也是合理的。</p>
<p>本实验不使用 OpenMP 之类的复杂的并发平台。</p>
<p>当然可以用分治的方式实现将矩阵乘法的时间复杂度在单处理器上降低到 $$ O(n^2.81) $$，但是本实验目的是多线程编程，不考虑这种优化方式</p>
<p>本实验不涉及更改操作系统的线程调度方式。依赖操作系统的默认线程调度方式</p>
<p>本实验通过 c 语言实现，并利用 Linux 系统的标准 API</p>
<p>如果能找出决定多线程加速的关键因素，以及所采用的方法/方法的适当性，将会得到分数。</p>
<h2 id="1-单个线程执行矩阵乘法的基本情况"><a href="#1-单个线程执行矩阵乘法的基本情况" class="headerlink" title="1 单个线程执行矩阵乘法的基本情况"></a>1 单个线程执行矩阵乘法的基本情况</h2><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><time.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdlib.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><memory.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MALLOC(n, type) \</span></span><br><span class="line"> ((type *)<span class="built_in">malloc</span>( (n) * <span class="keyword">sizeof</span>(type)))</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> FREE(p) \</span></span><br><span class="line"> <span class="keyword">if</span>(p!=<span class="literal">NULL</span>) \</span><br><span class="line"> { \</span><br><span class="line"> <span class="built_in">free</span>(p); \</span><br><span class="line"> p = <span class="literal">NULL</span>; \</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span> **a, <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; ++j)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d "</span>, a[i][j]);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</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">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span> *argv[])</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> setbuf(<span class="built_in">stdout</span>, <span class="literal">NULL</span>);</span><br><span class="line"> <span class="keyword">if</span> (argc != <span class="number">3</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"Usage: ./a.out matrix_size measurement_times\n"</span>);</span><br><span class="line"> <span class="built_in">exit</span>(<span class="number">0</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">double</span> total_time;</span><br><span class="line"> <span class="keyword">int</span> n_times = atoi(argv[<span class="number">1</span>]);</span><br><span class="line"> <span class="keyword">int</span> matrix_size = atoi(argv[<span class="number">2</span>]);</span><br><span class="line"> <span class="keyword">int</span> **a;</span><br><span class="line"> <span class="keyword">int</span> **b;</span><br><span class="line"> <span class="keyword">int</span> **c;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> size = <span class="number">2</span>; size <= matrix_size; ++size)</span><br><span class="line"> {</span><br><span class="line"> <span class="comment">/* Dynamic allocation for matrices */</span></span><br><span class="line"> a = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> b = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> c = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> a[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> b[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> c[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> }</span><br><span class="line"> srand(time(<span class="literal">NULL</span>)); <span class="comment">// 通过时间初始化随机种子</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> time = <span class="number">0</span>; time < n_times; ++time)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; j++)</span><br><span class="line"> {</span><br><span class="line"> a[i][j] = rand() % <span class="number">10</span>;</span><br><span class="line"> b[i][j] = rand() % <span class="number">10</span>;</span><br><span class="line"> c[i][j] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">clock_t</span> start = clock();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; j++)</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k < size; k++)</span><br><span class="line"> c[i][j] += a[i][k] * b[k][j];</span><br><span class="line"> <span class="keyword">clock_t</span> finish = clock();</span><br><span class="line"> total_time += (<span class="keyword">double</span>) (finish - start);</span><br><span class="line"> print((<span class="keyword">const</span> <span class="keyword">int</span> **) a, size);</span><br><span class="line"> print((<span class="keyword">const</span> <span class="keyword">int</span> **) b, size);</span><br><span class="line"> print((<span class="keyword">const</span> <span class="keyword">int</span> **) c, size);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> FREE(a[i]);</span><br><span class="line"> FREE(b[i]);</span><br><span class="line"> FREE(c[i]);</span><br><span class="line"> }</span><br><span class="line"> FREE(a);</span><br><span class="line"> FREE(b);</span><br><span class="line"> FREE(c);</span><br><span class="line"> FILE *fd;</span><br><span class="line"> fd = fopen(<span class="string">"./single_thread_log.txt"</span>, <span class="string">"a"</span>);</span><br><span class="line"> <span class="built_in">fprintf</span>(fd, <span class="string">"Matrix Size = %d -----Average Runtime of %d times = %.10f\n"</span>, size, n_times,</span><br><span class="line"> (<span class="keyword">double</span>) (total_time / n_times) / CLOCKS_PER_SEC);</span><br><span class="line"> fclose(fd);</span><br><span class="line"> total_time = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>单个线程执行矩阵乘法是通过一个三重循环来实现的。因为 cpu 计算不同大小的数字相乘所用的时间不同，所以实验中利用随机函数生成随机矩阵来保证实验能够模拟自然情况下的矩阵乘法。然后通过时间函数记录每个三重循环所用的时间，重复多次取平均值，来准确的获得每次执行矩阵乘法所需要的时间。为了便于同后续的多线程矩阵乘法做性能比较，本实验获取了矩阵阶数从 2 到 100 中每个矩阵阶数做乘法所需要的时间。</p>
<h2 id="2-矩阵乘法的多线程加速"><a href="#2-矩阵乘法的多线程加速" class="headerlink" title="2 矩阵乘法的多线程加速"></a>2 矩阵乘法的多线程加速</h2><p>由上面的单线程矩阵乘法知道，每次矩阵乘法计算过程包含一个三重循环过程，这将带来 O(n3) 的时间复杂度。考虑到矩阵乘法是一个重复操作过程，即将矩阵 A 的不同行与矩阵 B 的不同列相乘，且各个相乘结果之间不存在互相依赖关系，容易想到利用多线程计算来对矩阵乘法的计算过程进行加速。那么，如果用一个线程实现矩阵的一行乘以另一个矩阵的一列，那么 N 阶矩阵相乘需要 N*N 个线程才能完成任务。通常的多线程实现过程利用了 Linux 系统的标准库 pthread.h ，通过创建线程实现并将具体的任务传入线程来完成一个具体的任务。下面演示通过这种方式实现的多线程矩阵乘法。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><pthread.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><time.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdlib.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><memory.h></span></span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">matrix</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> **a;</span><br><span class="line"> <span class="keyword">int</span> **b;</span><br><span class="line"> <span class="keyword">int</span> **c;</span><br><span class="line">} NMatrix;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">param</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> NMatrix *p_matrix;</span><br><span class="line"> <span class="keyword">int</span> row;</span><br><span class="line"> <span class="keyword">int</span> col;</span><br><span class="line"> <span class="keyword">int</span> size;</span><br><span class="line">} Param;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">func</span><span class="params">(Param *param)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> row = param->row;</span><br><span class="line"> <span class="keyword">int</span> col = param->col;</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < param->size; ++i)</span><br><span class="line"> {</span><br><span class="line"> ans += param->p_matrix->a[row][i] * param->p_matrix->b[i][col];</span><br><span class="line"> }</span><br><span class="line"> param->p_matrix->c[row][col] = ans;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MALLOC(n, type) \</span></span><br><span class="line"> ((type *)<span class="built_in">malloc</span>( (n) * <span class="keyword">sizeof</span>(type)))</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> FREE(p) \</span></span><br><span class="line"> <span class="keyword">if</span>(p!=<span class="literal">NULL</span>) \</span><br><span class="line"> { \</span><br><span class="line"> <span class="built_in">free</span>(p); \</span><br><span class="line"> p = <span class="literal">NULL</span>; \</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span> **a, <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; ++j)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d "</span>, a[i][j]);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</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">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span> *argv[])</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> setbuf(<span class="built_in">stdout</span>, <span class="literal">NULL</span>);</span><br><span class="line"> <span class="keyword">if</span> (argc != <span class="number">3</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"Usage: ./a.out matrix_size measurement_times\n"</span>);</span><br><span class="line"> <span class="built_in">exit</span>(<span class="number">0</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">double</span> total_time;</span><br><span class="line"> <span class="keyword">int</span> matrix_size = atoi(argv[<span class="number">1</span>]);</span><br><span class="line"> <span class="keyword">int</span> n_times = atoi(argv[<span class="number">2</span>]);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> size = <span class="number">2</span>; size <= matrix_size; ++size)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">pthread_t</span> **threads = MALLOC(size, <span class="keyword">pthread_t</span> *);</span><br><span class="line"> NMatrix matrixs;</span><br><span class="line"> matrixs.a = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> matrixs.b = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> matrixs.c = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> Param **param = MALLOC(size, Param *);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> threads[i] = MALLOC(size, <span class="keyword">pthread_t</span>);</span><br><span class="line"> matrixs.a[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> matrixs.b[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> matrixs.c[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> param[i] = MALLOC(size, Param);</span><br><span class="line"> }</span><br><span class="line"> srand(time(<span class="literal">NULL</span>)); <span class="comment">// 通过时间初始化随机种子</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> time = <span class="number">0</span>; time < n_times; ++time)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; j++)</span><br><span class="line"> {</span><br><span class="line"> matrixs.a[i][j] = rand() % <span class="number">10</span>;</span><br><span class="line"> matrixs.b[i][j] = rand() % <span class="number">10</span>;</span><br><span class="line"> matrixs.c[i][j] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">clock_t</span> start = clock();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; ++j)</span><br><span class="line"> {</span><br><span class="line"> param[i][j].row = i;</span><br><span class="line"> param[i][j].col = j;</span><br><span class="line"> param[i][j].size = size;</span><br><span class="line"> param[i][j].p_matrix = &matrixs;</span><br><span class="line"> pthread_create(&threads[i][j], <span class="literal">NULL</span>, (<span class="keyword">void</span> *) func, &param[i][j]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; ++j)</span><br><span class="line"> {</span><br><span class="line"> pthread_join(threads[i][j], <span class="literal">NULL</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">clock_t</span> finish = clock();</span><br><span class="line"> total_time += (<span class="keyword">double</span>) (finish - start);</span><br><span class="line"><span class="comment">// print((const int **)matrixs.a, size);</span></span><br><span class="line"><span class="comment">// print((const int **)matrixs.b, size);</span></span><br><span class="line"><span class="comment">// print((const int **)matrixs.c, size);</span></span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> FREE(matrixs.a[i]);</span><br><span class="line"> FREE(matrixs.b[i]);</span><br><span class="line"> FREE(matrixs.c[i]);</span><br><span class="line"> FREE(param[i]);</span><br><span class="line"> FREE(threads[i]);</span><br><span class="line"> }</span><br><span class="line"> FREE(matrixs.a);</span><br><span class="line"> FREE(matrixs.b);</span><br><span class="line"> FREE(matrixs.c);</span><br><span class="line"> FREE(param);</span><br><span class="line"> FREE(threads);</span><br><span class="line"></span><br><span class="line"> FILE *fd;</span><br><span class="line"> fd = fopen(<span class="string">"./parallel_log.txt"</span>, <span class="string">"a"</span>);</span><br><span class="line"> <span class="built_in">fprintf</span>(fd, <span class="string">"Matrix Size = %d -----Average Runtime of %d times = %.10f\n"</span>, size, n_times,</span><br><span class="line"> (<span class="keyword">double</span>) (total_time / n_times) / CLOCKS_PER_SEC);</span><br><span class="line"> fclose(fd);</span><br><span class="line"> total_time = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>理论上讲，用 N* N 个线程来执行矩阵乘法的时间复杂度应该降低到 O(N)，但是运行结果显示多线程执行矩阵乘法所用时间远超单线程执行矩阵乘法所用时间。导致这样的结果的原因有两个。第一个是计算用时的时候，不可避免地要将创建线程的时间计统计在内，而创建线程的耗时相比于简单的进行一行乘以一列的乘加运算，无疑是耗时高得多的。第二个原因是当矩阵阶数增加时，所需要的线程数量将是矩阵阶数平方倍的增加，所以会产生大量的线程。而每个线程都需要操作系统来调度执行，因为线程数量已经远远超过 cpu 核心的数量。所以需要操作系统来安排该由 cpu 的哪个核心执行哪个线程，并且线程需要排队等待 cpu 的调度。当线程数量远大于 cpu 核心数量的时候，调度花费的时间就远远高于执行矩阵行列的乘加运算的用时了。</p>
<h2 id="3-将矩阵乘法分布在少于-N-N个线程上的实现和演示"><a href="#3-将矩阵乘法分布在少于-N-N个线程上的实现和演示" class="headerlink" title="3 将矩阵乘法分布在少于 N*N个线程上的实现和演示"></a>3 将矩阵乘法分布在少于 N*N个线程上的实现和演示</h2><p>考虑到上面提到的过多的线程来执行矩阵乘法的缺点，同时也要利用 cpu 多核心并行运算的优点。自然而然地就想到，不建立过多的线程，从而避免线程调度耗费的时间。所以将核心数量控制在cpu 核心数量相同的数量级。那么，就出现了一个问题，如何将矩阵乘法的任务平均分配给这些线程呢。例如一个100阶的矩阵相乘，就需要 100 * 100 次的行列相乘。将其分配到8个线程上（因为我的 Linux 系统运行在一个 8 核心的 cpu 上）。也就是每个线程执行 1250 次行列乘加运算。那么该如何分配具体的行列相乘并相加的任务到具体的线程呢？8个线程的执行100阶矩阵乘法时可以确保每个线程分到的任务数量是相等的。那么 99 阶矩阵乘法需要的行列乘加运算次数为 99 * 99 次，8 个线程执行会导致有个线程少执行若干个行列乘加运算。当线程数量不固定，矩阵大小不固定的时候，这样的方式会给代码编写带来很大的困难。这时，一个简单的想法是，我创建一定数量的线程，并固定在那里，形成一个队列，然后把矩阵乘法看作一定数量的子任务的集合，显然每个子任务就是一个行列相乘并相加。然后我就把这些子任务分配给线程执行，线程执行完了之后也不销毁，等待下一个任务的到来，直到所有的任务执行完毕后再销毁。这就是线程池的概念。下面就是通过线程池实现矩阵乘法的展示：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdlib.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><unistd.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"pool.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">matrix</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> **a;</span><br><span class="line"> <span class="keyword">int</span> **b;</span><br><span class="line"> <span class="keyword">int</span> **c;</span><br><span class="line">} NMatrix;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">param</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> NMatrix *p_matrix;</span><br><span class="line"> <span class="keyword">int</span> row;</span><br><span class="line"> <span class="keyword">int</span> col;</span><br><span class="line"> <span class="keyword">int</span> size;</span><br><span class="line">} Param;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">func</span><span class="params">(Param *param)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> row = param->row;</span><br><span class="line"> <span class="keyword">int</span> col = param->col;</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < param->size; ++i)</span><br><span class="line"> {</span><br><span class="line"> ans += param->p_matrix->a[row][i] * param->p_matrix->b[i][col];</span><br><span class="line"> }</span><br><span class="line"> param->p_matrix->c[row][col] = ans;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MALLOC(n, type) \</span></span><br><span class="line"> ((type *)<span class="built_in">malloc</span>( (n) * <span class="keyword">sizeof</span>(type)))</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> FREE(p) \</span></span><br><span class="line"> <span class="keyword">if</span>(p!=<span class="literal">NULL</span>) \</span><br><span class="line"> { \</span><br><span class="line"> <span class="built_in">free</span>(p); \</span><br><span class="line"> p = <span class="literal">NULL</span>; \</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span> **a, <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; ++j)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d "</span>, a[i][j]);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</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">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span> *argv[])</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> setbuf(<span class="built_in">stdout</span>, <span class="literal">NULL</span>);</span><br><span class="line"> <span class="keyword">if</span> (argc != <span class="number">4</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"Usage: ./a.out max_thread_nums matrix_size measurement_times \n"</span>);</span><br><span class="line"> <span class="built_in">exit</span>(<span class="number">0</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">double</span> total_time;</span><br><span class="line"> <span class="keyword">int</span> max_threads = atoi(argv[<span class="number">1</span>]);</span><br><span class="line"> <span class="keyword">int</span> matrix_size = atoi(argv[<span class="number">2</span>]);</span><br><span class="line"> <span class="keyword">int</span> n_times = atoi(argv[<span class="number">3</span>]);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> size = <span class="number">2</span>; size <= matrix_size; ++size)</span><br><span class="line"> {</span><br><span class="line"> srand(time(<span class="literal">NULL</span>)); <span class="comment">// 通过时间初始化随机种子</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> n_thread = <span class="number">1</span>; n_thread < max_threads && n_thread <= size * size; ++n_thread)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">threadpool_t</span> pool;</span><br><span class="line"> threadpool_init(&pool, n_thread);</span><br><span class="line"> NMatrix matrixs;</span><br><span class="line"> matrixs.a = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> matrixs.b = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> matrixs.c = MALLOC(size, <span class="keyword">int</span> *);</span><br><span class="line"> Param **param = MALLOC(size, Param *);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> matrixs.a[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> matrixs.b[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> matrixs.c[i] = MALLOC(size, <span class="keyword">int</span>);</span><br><span class="line"> param[i] = MALLOC(size, Param);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> time = <span class="number">0</span>; time < n_times; ++time)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; j++)</span><br><span class="line"> {</span><br><span class="line"> matrixs.a[i][j] = rand() % <span class="number">10</span>;</span><br><span class="line"> matrixs.b[i][j] = rand() % <span class="number">10</span>;</span><br><span class="line"> matrixs.c[i][j] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">clock_t</span> start = clock();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; ++i)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < size; ++j)</span><br><span class="line"> {</span><br><span class="line"> param[i][j].row = i;</span><br><span class="line"> param[i][j].col = j;</span><br><span class="line"> param[i][j].size = size;</span><br><span class="line"> param[i][j].p_matrix = &matrixs;</span><br><span class="line"> threadpool_add_task(&pool, (<span class="keyword">void</span> *) func, &param[i][j]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">clock_t</span> finish = clock();</span><br><span class="line"> total_time += (<span class="keyword">double</span>) (finish - start);</span><br><span class="line"> }</span><br><span class="line"> threadpool_destroy(&pool);</span><br><span class="line"> print((<span class="keyword">const</span> <span class="keyword">int</span> **) matrixs.a, size);</span><br><span class="line"> print((<span class="keyword">const</span> <span class="keyword">int</span> **) matrixs.b, size);</span><br><span class="line"> print((<span class="keyword">const</span> <span class="keyword">int</span> **) matrixs.c, size);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < size; i++)</span><br><span class="line"> {</span><br><span class="line"> FREE(matrixs.a[i]);</span><br><span class="line"> FREE(matrixs.b[i]);</span><br><span class="line"> FREE(matrixs.c[i]);</span><br><span class="line"> FREE(param[i]);</span><br><span class="line"> }</span><br><span class="line"> FREE(matrixs.a);</span><br><span class="line"> FREE(matrixs.b);</span><br><span class="line"> FREE(matrixs.c);</span><br><span class="line"> FREE(param);</span><br><span class="line"> FILE *fd;</span><br><span class="line"> fd = fopen(<span class="string">"./pool_log.txt"</span>, <span class="string">"a"</span>);</span><br><span class="line"> <span class="built_in">fprintf</span>(fd, <span class="string">"Matrix Size = %d -----Average Runtime of %d times = %.10f\n"</span>, size, n_times,</span><br><span class="line"> (<span class="keyword">double</span>) (total_time / n_times) / CLOCKS_PER_SEC);</span><br><span class="line"> fclose(fd);</span><br><span class="line"> total_time = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>下面是实现线程池的头文件</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdlib.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><unistd.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><errno.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><time.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><pthread.h></span></span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">task</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">void</span> *(*run)(<span class="keyword">void</span> *arg);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">void</span> *arg;</span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">task</span> *<span class="title">next</span>;</span></span><br><span class="line">} <span class="keyword">task_t</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">condition</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">pthread_mutex_t</span> pmutex;</span><br><span class="line"> <span class="keyword">pthread_cond_t</span> pcond;</span><br><span class="line">} <span class="keyword">condition_t</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">threadpool</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">condition_t</span> ready;</span><br><span class="line"> <span class="keyword">task_t</span> *first;</span><br><span class="line"> <span class="keyword">task_t</span> *last;</span><br><span class="line"> <span class="keyword">int</span> counter;</span><br><span class="line"> <span class="keyword">int</span> idle;</span><br><span class="line"> <span class="keyword">int</span> max_threads;</span><br><span class="line"> <span class="keyword">int</span> quit;</span><br><span class="line">} <span class="keyword">threadpool_t</span>;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_init</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_lock</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_unlock</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_wait</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_timewait</span><span class="params">(<span class="keyword">condition_t</span> *cond, <span class="keyword">const</span> struct timespec *abstime)</span></span>;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_signal</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_broadcast</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_destory</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> *<span class="title">thread_routine</span><span class="params">(<span class="keyword">void</span> *arg)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">threadpool_init</span><span class="params">(<span class="keyword">threadpool_t</span> *pool, <span class="keyword">int</span> threads)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">threadpool_add_task</span><span class="params">(<span class="keyword">threadpool_t</span> *pool, <span class="keyword">void</span> *(*run)(<span class="keyword">void</span> *arg), <span class="keyword">void</span> *arg)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">threadpool_destroy</span><span class="params">(<span class="keyword">threadpool_t</span> *pool)</span></span>;</span><br></pre></td></tr></table></figure>
<p>pool.c</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"pool.h"</span></span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_init</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> status;</span><br><span class="line"> <span class="keyword">if</span> ((status = pthread_mutex_init(&cond->pmutex, <span class="literal">NULL</span>)))<span class="comment">//返回0代表初始化成功</span></span><br><span class="line"> <span class="keyword">return</span> status;</span><br><span class="line"> <span class="keyword">if</span> ((status = pthread_cond_init(&cond->pcond, <span class="literal">NULL</span>)))</span><br><span class="line"> <span class="keyword">return</span> status;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_lock</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> pthread_mutex_lock(&cond->pmutex);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_unlock</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> pthread_mutex_unlock(&cond->pmutex);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_wait</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> pthread_cond_wait(&cond->pcond, &cond->pmutex);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_timewait</span><span class="params">(<span class="keyword">condition_t</span> *cond, <span class="keyword">const</span> struct timespec *abstime)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> pthread_cond_timedwait(&cond->pcond, &cond->pmutex, abstime);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_signal</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> pthread_cond_signal(&cond->pcond);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_broadcast</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> pthread_cond_broadcast(&cond->pcond);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">condition_destory</span><span class="params">(<span class="keyword">condition_t</span> *cond)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> status;</span><br><span class="line"> <span class="keyword">if</span> ((status = pthread_mutex_destroy(&cond->pmutex)))</span><br><span class="line"> <span class="keyword">return</span> status;</span><br><span class="line"> <span class="keyword">if</span> ((status = pthread_cond_destroy(&cond->pcond)))</span><br><span class="line"> <span class="keyword">return</span> status;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</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">void</span> *<span class="title">thread_routine</span><span class="params">(<span class="keyword">void</span> *arg)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">timespec</span> <span class="title">abstime</span>;</span></span><br><span class="line"> <span class="keyword">int</span> timeout;</span><br><span class="line"> <span class="keyword">threadpool_t</span> *pool = (<span class="keyword">threadpool_t</span> *) arg;</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"> timeout = <span class="number">0</span>;</span><br><span class="line"> condition_lock(&pool->ready);</span><br><span class="line"> pool->idle++;</span><br><span class="line"> <span class="keyword">while</span> (pool->first == <span class="literal">NULL</span> && !pool->quit)</span><br><span class="line"> {</span><br><span class="line"> clock_gettime(CLOCK_REALTIME, &abstime);</span><br><span class="line"> abstime.tv_sec += <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">int</span> status = condition_timewait(&pool->ready, &abstime);</span><br><span class="line"> <span class="keyword">if</span> (status == ETIMEDOUT)</span><br><span class="line"> {</span><br><span class="line"> timeout = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"> pool->idle--;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (pool->first != <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">task_t</span> *t = pool->first;</span><br><span class="line"> pool->first = t->next;</span><br><span class="line"> condition_unlock(&pool->ready);</span><br><span class="line"> t->run(t->arg);</span><br><span class="line"> <span class="built_in">free</span>(t);</span><br><span class="line"> condition_lock(&pool->ready);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (pool->quit && pool->first == <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> pool->counter--;</span><br><span class="line"> <span class="keyword">if</span> (pool->counter == <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> condition_signal(&pool->ready);</span><br><span class="line"> }</span><br><span class="line"> condition_unlock(&pool->ready);</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (timeout && pool->first == <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> pool->counter--;</span><br><span class="line"> condition_unlock(&pool->ready);</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> condition_unlock(&pool->ready);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">threadpool_init</span><span class="params">(<span class="keyword">threadpool_t</span> *pool, <span class="keyword">int</span> threads)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> condition_init(&pool->ready);</span><br><span class="line"> pool->first = <span class="literal">NULL</span>;</span><br><span class="line"> pool->last = <span class="literal">NULL</span>;</span><br><span class="line"> pool->counter = <span class="number">0</span>;</span><br><span class="line"> pool->idle = <span class="number">0</span>;</span><br><span class="line"> pool->max_threads = threads;</span><br><span class="line"> pool->quit = <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">threadpool_add_task</span><span class="params">(<span class="keyword">threadpool_t</span> *pool, <span class="keyword">void</span> *(*run)(<span class="keyword">void</span> *arg), <span class="keyword">void</span> *arg)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">task_t</span> *new_task = (<span class="keyword">task_t</span> *) <span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(<span class="keyword">task_t</span>));</span><br><span class="line"> new_task->run = run;</span><br><span class="line"> new_task->arg = arg;</span><br><span class="line"> new_task->next = <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line"> condition_lock(&pool->ready);</span><br><span class="line"> <span class="keyword">if</span> (pool->first == <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> pool->first = new_task;</span><br><span class="line"> } <span class="keyword">else</span></span><br><span class="line"> pool->last->next = new_task;</span><br><span class="line"> pool->last = new_task;</span><br><span class="line"> <span class="keyword">if</span> (pool->idle > <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> condition_signal(&pool->ready);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (pool->counter < pool->max_threads)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">pthread_t</span> tid;</span><br><span class="line"> pthread_create(&tid, <span class="literal">NULL</span>, thread_routine, pool);</span><br><span class="line"> pool->counter++;</span><br><span class="line"> }</span><br><span class="line"> condition_unlock(&pool->ready);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">threadpool_destroy</span><span class="params">(<span class="keyword">threadpool_t</span> *pool)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (pool->quit)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> condition_lock(&pool->ready);</span><br><span class="line"> pool->quit = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (pool->counter > <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (pool->idle > <span class="number">0</span>)</span><br><span class="line"> condition_broadcast(&pool->ready);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">while</span> (pool->counter > <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> condition_wait(&pool->ready);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> condition_unlock(&pool->ready);</span><br><span class="line"> condition_destory(&pool->ready);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>相比于上一种方法实现的多线程矩阵乘法，基于线程池实现的矩阵乘法运行速度大幅提升，但是依然比单线程实现的矩阵乘法速度慢。主要原因有两点，第一点是，线程池一次创建可以重复多次使用，省去了大量的线程创建和线程销毁的时间，每次只需要将任务放入线程池中即可。第二点原因是线程池中的线程数量更少，用于进程调度所花费的时间更少。但仍然比单线程矩阵乘法执行速度慢的原因是线程池运算过程中的大量同步操作花费了大量的时间。</p>
<h2 id="4-基于处理器特性的整体分析"><a href="#4-基于处理器特性的整体分析" class="headerlink" title="4 基于处理器特性的整体分析"></a>4 基于处理器特性的整体分析</h2><p>本实验平台为 Linux，cpu 核心数量为8 。因此理论上8线程的矩阵乘法是能达到最好性能。但是本实验的实验结果没能验证这一点。我觉得原因在于矩阵乘法的任务本身和实现矩阵乘法的系统有关。首先是矩阵乘法的任务本身，本次实验由于时间原因只是进行到了100阶的矩阵乘法，cpu是一个高速设备，执行100个数的相乘并相加是非常快速的。消耗的时间远远低于进程调度和创建销毁进程所消耗的时间。如果是更高阶的矩阵乘法的话，那么每次行列乘加的任务就会变得很大，那么任务本身的耗时就会超过线程创建，线程调度的耗时。在这种情况下多线程执行矩阵乘法就变得更有意义。除开 cpu 的因素外，本次实验所基于的操作系统也是一个重要的因素。我们使用的是操作系统提供的线程创建和调度的方法，通常来讲，操作系统提供的线程调度和创建销毁方式是具体很强的通用性的。矩阵乘法这种级别的任务显得有点过于简单和单一。如果直接用操作系统提供的线程操作则显得过于笨重。（这一段为个人直觉，未经实验）</p>
<h2 id="5-最总结论"><a href="#5-最总结论" class="headerlink" title="5 最总结论"></a>5 最总结论</h2><p>矩阵乘法在理论上可以用多线程的方式实现 N * N 倍的加速，但是现实情况下很难实现，而且依赖于具体的硬件平台和软件算法。</p>
<p>阶数较低的矩阵乘法非常不适合于并行计算，用单线程计算要快得多，因为 cpu 本身的计算速度非常快。</p>
<p>阶数较高的矩阵通过多线程加速的方式可以取得相比于单线程更好的性能，但是矩阵的本身要足够大，且使用的线程数量要小于等于 cpu 核心数量。</p>
<p>矩阵乘法虽然是一个简单的任务，但是具有非常重要的作用。多线程优化加速矩阵乘法是一个非常值得探讨和研究的课题。事实上，现在应用非常广发的计算机视觉任务就非常依赖于多线程矩阵乘法的实现。但是这项任务用到了一个不同于 cpu 的硬件，那就是 GPU。GPU不具备cpu那样好的通用编程性能，但是它拥有数量远超过 cpu的核心数量可以用于快速的实现矩阵乘法。同时其在线程调度和算法层面做了大量的优化，具体的优化方法有待后续学习。</p>
<p>参考资料：</p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/s-lisheng/p/11244873.html">https://www.cnblogs.com/s-lisheng/p/11244873.html</a></p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/zhangchaoyang/articles/1853822.html">https://www.cnblogs.com/zhangchaoyang/articles/1853822.html</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_42819452/article/details/102807147">https://blog.csdn.net/weixin_42819452/article/details/102807147</a></p>
<p><a target="_blank" rel="noopener" href="https://github.com/micwu/ThreadPool">https://github.com/micwu/ThreadPool</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/06/24/python%20kmeans%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/06/24/python%20kmeans%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95/" class="post-title-link" itemprop="url">python 实现 kmeans 聚类算法</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-06-24 15:52:21 / 修改时间：15:52:02" itemprop="dateCreated datePublished" datetime="2021-06-24T15:52:21+08:00">2021-06-24</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>3.7k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>3 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>基本思想：初始随机给定 k 个簇中心，按最邻近原则（欧式距离？？）把待分类样本（任意样本？）点分到各簇。然后按平均法计算各个簇的质心，从而确定新的簇心。一直迭代，指导簇心的移动距离小于某个给定的值。</p>
<p>特点：</p>
<ol>
<li> 类别的个数是人为给定的</li>
<li> 数据之间的相似度可以用欧式距离度量，如果不能用欧式距离度量，要先把数据转换到能用欧式距离度量</li>
</ol>
<p>下面演示以信用卡数据为例子的 kmeans 聚类算法实现的代码</p>
<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></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> time</span><br><span class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</span><br><span class="line"><span class="keyword">import</span> pandas <span class="keyword">as</span> pd</span><br><span class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</span><br><span class="line"><span class="keyword">from</span> sklearn.decomposition <span class="keyword">import</span> PCA</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">CustomKMeans</span>:</span></span><br><span class="line"></span><br><span class="line"> <span class="comment"># 初始化参数</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, k, stop_var=<span class="number">1e-03</span>, dist_type=<span class="string">'l2'</span>, max_iter=<span class="number">300</span></span>):</span></span><br><span class="line"> self.inertia_ = <span class="number">0</span> <span class="comment"># 样本点距离聚类中心的距离和</span></span><br><span class="line"> self.num_cluster = k</span><br><span class="line"> self.max_iter = max_iter</span><br><span class="line"> self.stop_var = stop_var</span><br><span class="line"> self.dist_type = dist_type</span><br><span class="line"> self.variance = <span class="number">10</span> * stop_var</span><br><span class="line"> self.dists = <span class="literal">None</span></span><br><span class="line"> self.labels = <span class="literal">None</span></span><br><span class="line"> self.centers = <span class="literal">None</span></span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">l1_distance</span>(<span class="params">self, sample</span>):</span></span><br><span class="line"> <span class="keyword">return</span> np.<span class="built_in">sum</span>(np.<span class="built_in">abs</span>(sample - self.centers), axis=<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">l2_distance</span>(<span class="params">self, sample</span>):</span></span><br><span class="line"> <span class="keyword">return</span> np.sqrt(np.<span class="built_in">sum</span>(np.square(sample - self.centers), axis=<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">update_dists</span>(<span class="params">self, samples</span>):</span></span><br><span class="line"> labels = np.empty(samples.shape[<span class="number">0</span>]) <span class="comment"># shape: [N, 1]</span></span><br><span class="line"> dists = np.empty((<span class="number">0</span>, self.num_cluster)) <span class="comment"># shape: [N, n_cluster]</span></span><br><span class="line"> <span class="keyword">for</span> i, sample <span class="keyword">in</span> <span class="built_in">enumerate</span>(samples):</span><br><span class="line"> <span class="keyword">if</span> self.dist_type == <span class="string">'l1'</span>:</span><br><span class="line"> dist = self.l1_distance(sample)</span><br><span class="line"> <span class="keyword">elif</span> self.dist_type == <span class="string">'l2'</span>:</span><br><span class="line"> dist = self.l2_distance(sample)</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> <span class="keyword">raise</span> ValueError(<span class="string">'..'</span>)</span><br><span class="line"> labels[i] = np.argmin(dist) <span class="comment"># 距离最小的center就是该样本对应的类</span></span><br><span class="line"> dists = np.vstack((dists, dist[np.newaxis, :])) <span class="comment"># 将该样本对应的各个center距离加入到dists中</span></span><br><span class="line"> <span class="keyword">if</span> self.dists <span class="keyword">is</span> <span class="keyword">not</span> <span class="literal">None</span>:</span><br><span class="line"> self.variance = np.<span class="built_in">sum</span>(np.<span class="built_in">abs</span>(self.dists - dists))</span><br><span class="line"> self.dists = dists <span class="comment"># 更新</span></span><br><span class="line"> self.labels = labels <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">update_centers</span>(<span class="params">self, samples</span>):</span></span><br><span class="line"> centers = np.empty((<span class="number">0</span>, samples.shape[<span class="number">1</span>]))</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(self.num_cluster):</span><br><span class="line"> mask = (self.labels == i)</span><br><span class="line"> center_samples = samples[mask]</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">len</span>(center_samples) != <span class="number">0</span>:</span><br><span class="line"> center = np.mean(center_samples, axis=<span class="number">0</span>)</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> center = self.centers[i]</span><br><span class="line"> centers = np.vstack((centers, center[np.newaxis, :]))</span><br><span class="line"> self.centers = centers</span><br><span class="line"></span><br><span class="line"> <span class="comment"># 找到 k 个聚类中心点，然后标记每个数据属于哪个类</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">fit</span>(<span class="params">self, data, plot_steps=<span class="literal">False</span></span>):</span></span><br><span class="line"> <span class="comment"># 主成分分析，降维到二维</span></span><br><span class="line"> self.pca = PCA(<span class="number">2</span>).fit(data)</span><br><span class="line"> self.data = pd.DataFrame(data)</span><br><span class="line"> self.data_pca = pd.DataFrame(self.pca.transform(data))</span><br><span class="line"> self.data_pca.columns = [<span class="string">'PCA1'</span>, <span class="string">'PCA2'</span>]</span><br><span class="line"></span><br><span class="line"> self.iteration = <span class="number">1</span></span><br><span class="line"> n = data.shape[<span class="number">0</span>]</span><br><span class="line"></span><br><span class="line"> <span class="comment"># 降维后，在 n 个数据中，随机选取 k 个聚类中心</span></span><br><span class="line"> samples = self.data_pca.values <span class="comment"># 待聚类样本</span></span><br><span class="line"> init_row = np.random.randint(<span class="number">0</span>, self.data_pca.values.shape[<span class="number">0</span>], self.num_cluster)</span><br><span class="line"> self.centers = samples[init_row]</span><br><span class="line"> <span class="keyword">for</span> cur_iter <span class="keyword">in</span> <span class="built_in">range</span>(self.max_iter):</span><br><span class="line"> self.update_dists(samples) <span class="comment"># 更新样本到各个 centers 的距离, 同时更新每个样本点对应的center类</span></span><br><span class="line"> self.update_centers(samples) <span class="comment"># 更新各个 centers</span></span><br><span class="line"> <span class="keyword">if</span> self.variance < self.stop_var: <span class="comment"># 如果 centers 更新停止, 则提前退出</span></span><br><span class="line"> print(<span class="string">"cur_iter:"</span>, cur_iter)</span><br><span class="line"> <span class="keyword">break</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> plot_steps:</span><br><span class="line"> self.plot_state()</span><br><span class="line"> self.iteration += <span class="number">1</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(self.dists.shape[<span class="number">0</span>]):</span><br><span class="line"> self.inertia_ += self.dists[i].<span class="built_in">min</span>()</span><br><span class="line"> <span class="keyword">return</span> self</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">plot_state</span>(<span class="params">self</span>):</span></span><br><span class="line"></span><br><span class="line"> plt.figure(figsize=(<span class="number">8</span>, <span class="number">8</span>))</span><br><span class="line"> plt.scatter(self.data_pca[<span class="string">'PCA1'</span>], self.data_pca[<span class="string">'PCA2'</span>], c=self.labels)</span><br><span class="line"> plt.title(<span class="string">"Clusters and Centroids After step {}"</span>.<span class="built_in">format</span>(self.iteration))</span><br><span class="line"> plt.show()</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">"__main__"</span>:</span><br><span class="line"> plt.style.use(<span class="string">'ggplot'</span>)</span><br><span class="line"> <span class="comment"># 测试数据为 8950 个信用卡账户信息，每个账户有 17 个数据，通过 kmeans 聚类算法将这些账户分类</span></span><br><span class="line"> data = pd.read_csv(<span class="string">"creditcards.csv"</span>)</span><br><span class="line"> print(<span class="string">f"<span class="subst">{data.shape[<span class="number">0</span>]}</span> rows, <span class="subst">{data.shape[<span class="number">1</span>]}</span> columns"</span>)</span><br><span class="line"> print(data.head(<span class="number">10</span>))</span><br><span class="line"></span><br><span class="line"> K = <span class="number">5</span> <span class="comment"># 默认分为 5 类</span></span><br><span class="line"> tic = time.perf_counter()</span><br><span class="line"> custom_labels = CustomKMeans(K).fit(data, plot_steps=<span class="literal">True</span>)</span><br><span class="line"> toc = time.perf_counter()</span><br><span class="line"> print(<span class="string">f"Clustered <span class="subst">{data.shape[<span class="number">0</span>]}</span> datapoints in <span class="subst">{toc - tic:<span class="number">0.4</span>f}</span> seconds"</span>)</span><br><span class="line"></span><br><span class="line"> <span class="comment"># 可视化 分类数量从 2 到 20 时，所有样本点到聚类中心的总距离的变化情况</span></span><br><span class="line"> sum_of_distances = []</span><br><span class="line"> max_k = <span class="number">20</span></span><br><span class="line"> <span class="keyword">for</span> k <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">2</span>, max_k):</span><br><span class="line"> kmean = CustomKMeans(k).fit(data)</span><br><span class="line"> sum_of_distances.append(kmean.inertia_)</span><br><span class="line"></span><br><span class="line"> fig = plt.figure(figsize=(<span class="number">9</span>, <span class="number">6</span>))</span><br><span class="line"> plt.plot(<span class="built_in">range</span>(<span class="number">2</span>, max_k), sum_of_distances, <span class="string">'--x'</span>)</span><br><span class="line"> plt.title(<span class="string">"Cost vs # Clusters"</span>)</span><br><span class="line"> plt.xlabel(<span class="string">"# Clusters"</span>)</span><br><span class="line"> plt.ylabel(<span class="string">'Cost'</span>)</span><br><span class="line"> plt.show()</span><br></pre></td></tr></table></figure>
<p>运行结果图</p>
<p><img src="assets/image-20210617194403618.png" alt="image-20210617194403618"></p>
<p><a target="_blank" rel="noopener" href="https://github.com/MIXALER/python_projects/tree/master/kmeans">源代码链接</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/06/24/c++%E7%A8%8B%E5%BA%8F%E7%9A%84%E5%86%85%E5%AD%98%E6%A8%A1%E5%9E%8B/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/06/24/c++%E7%A8%8B%E5%BA%8F%E7%9A%84%E5%86%85%E5%AD%98%E6%A8%A1%E5%9E%8B/" class="post-title-link" itemprop="url">c/c++ 内存分区模型</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-06-24 15:52:21 / 修改时间：15:34:36" itemprop="dateCreated datePublished" datetime="2021-06-24T15:52:21+08:00">2021-06-24</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>3.2k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>3 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="c-c-内存分区模型"><a href="#c-c-内存分区模型" class="headerlink" title="c/c++内存分区模型"></a>c/c++内存分区模型</h2><p>《程序员的自我修养》一书深入的探讨了程序编译，链接，装载和运行过程中的细节，本文简单的记录一下程序运行过程中内存存放的数据区域。</p>
<p>以前一直听说程序运行中的全局变量，局部变量，静态变量，堆区，栈区，一直没有搞明白他们的关系是什么。现在来简单的梳理一下。我是初学者，不对的地方请指正。</p>
<p>首先分为四个大的区域：</p>
<h3 id="代码区"><a href="#代码区" class="headerlink" title="代码区"></a>代码区</h3><p>程序编译后，生成可执行程序，未执行该程序前分为两个区域</p>
<p>代码区：</p>
<p>存放cpu执行的机器指令</p>
<p>代码区共享的</p>
<p>只读</p>
<p>存放函数体的<strong>二进制</strong>代码，由操作系统进行管理</p>
<h3 id="全局区"><a href="#全局区" class="headerlink" title="全局区"></a>全局区</h3><p>存放全局变量和静态变量以及常量（const)</p>
<p>全局变量和静态变量存放在全局区</p>
<p>全局区还包含了常量区，字符串常量和其他常量（const）也存放于此。</p>
<p>该区域的数据在程序结束后由操作系统释放</p>
<h3 id="栈区"><a href="#栈区" class="headerlink" title="栈区"></a>栈区</h3><p>由编译器自动分配和释放，因此不要返回局部变量的地址，栈区开辟的数据由编译器自动释放。</p>
<p>函数的形参</p>
<p>声明在函数中的局部变量</p>
<p>用register声明的局部变量或函数形参。</p>
<h3 id="堆区"><a href="#堆区" class="headerlink" title="堆区"></a>堆区</h3><p>由程序员分配和释放，若程序员不释放（就是垃圾），程序结束时由操作系统回收。</p>
<p>c++中主要利用new再堆区开辟内存，释放用delete，c中用malloc和free。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> val;</span><br><span class="line"> Node* next;</span><br><span class="line"> Node(<span class="keyword">int</span> val, Node* next) : val(val), next(next) {}</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="comment">//全局变量，定义在函数体之外的变量</span></span><br><span class="line"><span class="keyword">int</span> global_a = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> global_b = <span class="number">0</span>;</span><br><span class="line"><span class="comment">// 全局变量加上静态存储期声明</span></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">int</span> static_global_a = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">static</span> <span class="keyword">int</span> static_global_b = <span class="number">0</span>;</span><br><span class="line"><span class="comment">//全局常量</span></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> kGlobalIntA = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> kGlobalIntB = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">// 局部变量，定义在函数体中</span></span><br><span class="line"> <span class="keyword">int</span> local_a = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">int</span> local_b = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// 局部变量加上静态存储期声明</span></span><br><span class="line"> <span class="keyword">static</span> <span class="keyword">int</span> static_local_a = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">static</span> <span class="keyword">int</span> static_local_b = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// 局部常量</span></span><br><span class="line"> <span class="keyword">const</span> <span class="keyword">int</span> kLocalA = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">const</span> <span class="keyword">int</span> kLocalB = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">string</span> kStrA = <span class="string">"see memory distribution A"</span>;</span><br><span class="line"> <span class="built_in">string</span> kStrB = <span class="string">"see memory distribution B"</span>;</span><br><span class="line"> <span class="comment">// new分配堆上的空间</span></span><br><span class="line"> Node* p_Node_local_a = <span class="keyword">new</span> Node(<span class="number">8</span>, <span class="literal">nullptr</span>);</span><br><span class="line"> Node* p_Node_local_b = <span class="keyword">new</span> Node(<span class="number">10</span>, <span class="literal">nullptr</span>);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"全局变量global_a的地址是： "</span> << &global_a << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"全局变量global_b的地址是： "</span> << &global_b << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"静态全局变量static_global_a的地址是： "</span> << &static_global_a << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"静态全局变量static_global_b的地址是： "</span> << &static_global_b << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"静态局部变量static_local_a的地址是： "</span> << &static_local_a << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"静态局部变量static_local_b的地址是： "</span> << &static_local_b << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"全局常量kGlobalIntA的地址是： "</span> << &kGlobalIntA << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"全局常量kGlobalIntB的地址是： "</span> << &kGlobalIntB << <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部变量local_a的地址是： "</span> << &local_a << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部变量local_b的地址是： "</span> << &local_b << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部常量kLocalA的地址是： "</span> << &kLocalA << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部常量kLocalB的地址是： "</span> << &kLocalB << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部字符串常量kStrA的地址是： "</span> << &kStrA << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部字符串常量kStrB的地址是： "</span> << &kStrB << <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部变量p_Node_local_a的地址是： "</span> << &p_Node_local_a << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"局部变量p_Node_local_b的地址是： "</span> << &p_Node_local_b << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"p_Node_local_a所指向的地址是： "</span> << p_Node_local_a << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"p_Node_local_a所指向的结构体成员变量val的地址是： "</span> << &p_Node_local_a->val << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"p_Node_local_a所指向的结构体成员变量next的地址是： "</span> << &p_Node_local_a->next << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"p_Node_local_b所指向的地址是： "</span> << p_Node_local_b << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"p_Node_local_b所指向的结构体成员变量val的地址是： "</span> << &p_Node_local_b->val << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"p_Node_local_b所指向的结构体成员变量next的地址是： "</span> << &p_Node_local_b->next << <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">delete</span> p_Node_local_a;</span><br><span class="line"> <span class="keyword">delete</span> p_Node_local_b;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>运行结果如下<br><img src="assets/memory_distribution.png" alt="运行结果"></p>
<p><strong>不同区域存放的数据，赋予不同的生命周期，编程更加灵活</strong>。</p>
<p>可视化一个递归调用栈</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="http://www.mixaler.com/2021/02/13/%E4%B8%80%E4%B8%AA%E9%AB%98%E6%80%A7%E8%83%BD%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E5%93%88%E5%B8%8C%E8%A1%A8/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="MIXALER">
<meta itemprop="description" content="永不关机">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="MIXALER--blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/02/13/%E4%B8%80%E4%B8%AA%E9%AB%98%E6%80%A7%E8%83%BD%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E5%93%88%E5%B8%8C%E8%A1%A8/" class="post-title-link" itemprop="url">一个高性能的线程安全的哈希表</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-02-13 17:50:45" itemprop="dateCreated datePublished" datetime="2021-02-13T17:50:45+08:00">2021-02-13</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-06-12 14:15:41" itemprop="dateModified" datetime="2021-06-12T14:15:41+08:00">2021-06-12</time>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>6.7k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>6 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="1-为什么需要哈希表"><a href="#1-为什么需要哈希表" class="headerlink" title="1 为什么需要哈希表"></a>1 为什么需要哈希表</h2><p>我们用计算机中来存储处理数据。要处理数据，首先要将数据存储在计算机中。那么问题来了，数据在计算机中是如何存储的，为了更加方便的处理数据，我们该选用何种方式存储数据？</p>
<p>根据计算机的结构，我们可以用两种方式来存储数据。即连续的数据存储和非连续的数据存储。</p>
<p>在一个连续空间中存储数据需要设定空间的大小。在现代编程语言中不需要我们手动计算空间大小，我们只需要告知编译器数据类型和该类型数据存储的数量即可。编译器会自动地计算除数据类型所需要的空间并乘以数量得到所需总空间的大小。在 c 语言中，这种存储方式被称为数组。以数组的方式存储数据一个明显的好处是定位很快。因为可以通过下标的方式来得到存放地址从而访问数据。时间复杂度为 O(1)。除此之外还有空间利用率高的优点。因为没有存放除数据以外的辅助信息。</p>
<p>但是上述方式也存在明显的缺点。那就是事先必须规定数据的存放数量。这在很多时候是无法获知的。如果分配的存储数量远远大于需要处理的数据数量，就存在空间浪费，如果分配的空间不够，则无法完成数据的处理。除此之外，数据的删除和插入也相对麻烦。删除和插入任意一个数据需要将后面的数据依次向前和向后移动一个位置，删除和插入的时间复杂度为 O(n)。</p>
<p>我们就想到了动态地分配空间来处理数据。这样的方式可以在计算机中查找空闲的内存块用于存放数据。即在计算机的不连续的空间中存储数据。显然，这种方式需要在存放数据的同时存放一些辅助信息，用于指示下一个数据的位置，否则就找不到数据的存放位置，也就无法处理数据了。这样的方式就有很多种设计单个数据的结构的方式。比较常见的就是链表。链表的一个节点中有数据部分和指向下一个节点的指针。我们可以通过指针一块一块的访问数据。链表这种结构就可以让我们随意的增加数据，不用担心事先分配的内存空间不够。而且链表的删除和插入就变得简单了，只需要改变指针的指向，时间复杂度为 O(1)。</p>
<p>但是链表上查找数据时就变得很费时间了。不同于数组可以直接访问空间中任意一个数据。链表只能通过指针一个一个的遍历到该数据的位置才能访问。所以链表的查找时间复杂度为 O(n)。</p>
<p>那么如何才能做到，既能够动态的管理空间，存储任意长度的数据，又使得数据的查找，插入，删除尽可能的快呢。该如何设计这样的数据结构呢？首先，肯定要在数据中保留其他数据的位置信息确保我们能够根据该位置信息遍历到所有的数据。其次，要能够快速的找到我们想要数据的位置。很明显的思路是通过二分查找的方式来查找数据。其实二分查找只是一个查找思路，就相当于快速的定位所需数据在某个部分，再在这个部分里面利用同样的方式去查找。定位这个数据的在哪个部分一定是常数时间内完成的。这就是排序二叉树，平衡二叉树，红黑树，b 树，b+ 树等经典数据结构的的设计思路。当然在这些数据结构之上还有一些变种，在某些场景下有更好的性能。此处不再赘述。比二分查找更为极端的思路是通过计算得到数据位置。这种计算方式叫做哈希。通过这种方式生成的数据结构的就是哈希表。理想的情况是，我们想要查找某个数据，我们通过该数据的特征来计算数据的存放位置，然后直接在该位置去查看该数据。计算该数据的位置所需时间是固定的，时间复杂度为 O(1)。这就是哈希表的设计思路和为啥我们需要哈希表。</p>
<h2 id="2-哈希表的实现原理"><a href="#2-哈希表的实现原理" class="headerlink" title="2 哈希表的实现原理"></a>2 哈希表的实现原理</h2><p>哈希表理论上能提供接近 O(1) 时间复杂度的查询性能。是因为我们通过数据的特征直接算出了数据的存放位置。但是数据的类型很多，比如字符串，整数，小数，矩阵等。不同的数据计算其特征到数据位置的方式不同，每种数据类型都有特定的方式，讲起来很麻烦。我们直接用一个 key-value 模型对其进行抽象。可以认为每个数据都由 value 部分和 key 部分组成。value 部分可以相同，key 一定不相同。我们可以通过 key 来计算数据存储位置。然后找到对应位置的 value。那么，如何由 key 到数据位置的这个计算方式也就是哈希函数如何设计呢。我们的理想情况是，不同的 key 计算出来的数据位置不一样。但是 key 的空间是无限大的，然而我们的数据存放位置是有限的。一个无限大的空间映射到有限的空间必定产生冲突。虽然 key 的空间是无限大的，但是我们需要存储的数据量其实是有限的。也就是说，只要这个映射方式足够的均匀，key 经过映射以后产生冲突的可能性还是很小的。所以设计这个映射函数也就是哈希函数成了问题的关键。除此之外，冲突产生后解决冲突的方式也是哈希表的设计种需要考虑的问题。</p>
<h2 id="3-哈希表的实现方式"><a href="#3-哈希表的实现方式" class="headerlink" title="3 哈希表的实现方式"></a>3 哈希表的实现方式</h2><p>首先是哈希函数。常见的哈希函数直接寻址法，数字分析法，平方取中法，折叠法，除留取余法。这是比较简单的实现。比较好的实现有经典的 MD4，MD5，SHA-1 等。</p>
<p>然后是冲突处理，有开放寻址法，再散列法，链地址法，建立一个公共溢出区，哈希桶等方式。</p>
<h2 id="4-基于哈希桶和除留取余法实现的哈希表示例"><a href="#4-基于哈希桶和除留取余法实现的哈希表示例" class="headerlink" title="4 基于哈希桶和除留取余法实现的哈希表示例"></a>4 基于哈希桶和除留取余法实现的哈希表示例</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><limits></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><vector></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> hashval = <span class="number">2</span>;</span><br><span class="line"><span class="keyword">int</span> R = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> N = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">float</span> threshold = <span class="number">0.75</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> num_entries = <span class="number">256</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">bucket</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> entries[num_entries];</span><br><span class="line"> bucket *overflow;</span><br><span class="line">} Bucket;</span><br><span class="line"></span><br><span class="line"><span class="built_in">vector</span><Bucket *> hashtable;</span><br><span class="line"></span><br><span class="line"><span class="function">Bucket *<span class="title">create_bucket</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Bucket *temp = (Bucket *) <span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(Bucket));</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < num_entries; i++)</span><br><span class="line"> temp->entries[i] = INT32_MIN;</span><br><span class="line"> temp->overflow = <span class="literal">NULL</span>;</span><br><span class="line"> N++;</span><br><span class="line"> <span class="keyword">return</span> temp;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">nearest_power</span><span class="params">(<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> p = <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">while</span> (p <= n)</span><br><span class="line"> p *= <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">if</span> (p > n)</span><br><span class="line"> p /= <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">return</span> p;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"Bucket "</span> << i << <span class="string">": "</span>;</span><br><span class="line"> Bucket *curr = hashtable[i];</span><br><span class="line"> <span class="keyword">while</span> (curr)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < num_entries; j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (hashtable[i]->entries[j] != INT32_MIN)</span><br><span class="line"> <span class="built_in">cout</span> << hashtable[i]->entries[j] << <span class="string">" "</span>;</span><br><span class="line"> }</span><br><span class="line"> curr = curr->overflow;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << <span class="built_in">endl</span>;</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">int</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> x = val % hashval;</span><br><span class="line"> <span class="keyword">if</span> (x < <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> x += hashval;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (x >= hashtable.size())</span><br><span class="line"> {</span><br><span class="line"> x -= hashval / <span class="number">2</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> x;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> bucket_num = search(val);</span><br><span class="line"> Bucket *curr = hashtable[bucket_num];</span><br><span class="line"> <span class="keyword">while</span> (curr)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < num_entries; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (curr->entries[i] == val)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> curr = curr->overflow;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert_val</span><span class="params">(<span class="keyword">int</span> bucket_num, <span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Bucket *curr = hashtable[bucket_num];</span><br><span class="line"> <span class="keyword">int</span> ins = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span> (curr)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < num_entries; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (curr->entries[i] == INT32_MIN)</span><br><span class="line"> {</span><br><span class="line"> curr->entries[i] = val;</span><br><span class="line"> ins = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (ins == <span class="number">1</span>)</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">if</span> (curr->overflow == <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> Bucket *temp = create_bucket();</span><br><span class="line"> curr->overflow = temp;</span><br><span class="line"> }</span><br><span class="line"> curr = curr->overflow;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">del</span><span class="params">(<span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> bucket_num = search(val);</span><br><span class="line"> Bucket *curr = hashtable[bucket_num];</span><br><span class="line"> <span class="keyword">while</span> (curr)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < num_entries; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (curr->entries[i] == val)</span><br><span class="line"> {</span><br><span class="line"> curr->entries[i] = INT32_MIN;</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> curr = curr->overflow;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">split_bucket</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> insert_at = hashtable.size();</span><br><span class="line"> hashtable.push_back(create_bucket());</span><br><span class="line"> <span class="keyword">int</span> split_bucket_num = insert_at - nearest_power(insert_at);</span><br><span class="line"> hashval = (hashtable.size() > hashval) ? <span class="number">2</span> * hashval : hashval;</span><br><span class="line"></span><br><span class="line"> Bucket *curr = hashtable[split_bucket_num];</span><br><span class="line"> <span class="keyword">while</span> (curr)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < num_entries; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> x = curr->entries[i] % hashval;</span><br><span class="line"> <span class="keyword">if</span> (x < <span class="number">0</span>)</span><br><span class="line"> x += hashval;</span><br><span class="line"> <span class="keyword">if</span> (x == insert_at)</span><br><span class="line"> {</span><br><span class="line"> insert_val(insert_at, curr->entries[i]);</span><br><span class="line"> curr->entries[i] = INT32_MIN;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> curr = curr->overflow;</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">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> bucket_num = search(val);</span><br><span class="line"> Bucket *curr = hashtable[bucket_num];</span><br><span class="line"> <span class="keyword">while</span> (curr)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < num_entries; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (curr->entries[i] == val)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"表中已经存在该 key 值，重复插入！"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> curr = curr->overflow;</span><br><span class="line"> }</span><br><span class="line"> insert_val(bucket_num, val);</span><br><span class="line"> R++;</span><br><span class="line"> <span class="keyword">float</span> fr = (<span class="keyword">float</span>) R / (<span class="keyword">float</span>) (N * num_entries);</span><br><span class="line"> <span class="keyword">if</span> (fr >= threshold)</span><br><span class="line"> split_bucket();</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">printMenu</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">cout</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"1:插入数据;"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"2:查询数据;"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"3:删除数据;"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"4:打印哈希表;"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"0:退出"</span> << <span class="built_in">endl</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < <span class="number">2</span>; i++)</span><br><span class="line"> {</span><br><span class="line"> Bucket *temp = create_bucket();</span><br><span class="line"> hashtable.push_back(temp);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"初始化哈希表，表长度为 "</span> << hashval << <span class="string">" 默认桶大小为 "</span> << num_entries << <span class="string">" 默认分裂阈值为 "</span> << threshold << <span class="built_in">endl</span>;</span><br><span class="line"> printMenu();</span><br><span class="line"> <span class="keyword">int</span> cmd;</span><br><span class="line"> <span class="keyword">int</span> key;</span><br><span class="line"> <span class="keyword">bool</span> res;</span><br><span class="line"> <span class="keyword">while</span> (<span class="built_in">cin</span> >> cmd)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">switch</span> (cmd)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"请输入 key 值: "</span>;</span><br><span class="line"> <span class="built_in">cin</span> >> key;</span><br><span class="line"> insert(key);</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"请输入待查询的 key 值："</span>;</span><br><span class="line"> <span class="built_in">cin</span> >> key;</span><br><span class="line"> res = count(key);</span><br><span class="line"> <span class="keyword">if</span> (res)</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"在哈希表中"</span>;</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"不在哈希表中"</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">case</span> <span class="number">3</span>:</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"请输入待删除的 key 值："</span>;</span><br><span class="line"> <span class="built_in">cin</span> >> key;</span><br><span class="line"> res = del(key);</span><br><span class="line"> <span class="keyword">if</span> (res)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"删除值： "</span> << key << <span class="string">"成功！"</span>;</span><br><span class="line"> } <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"错误！ 值："</span> << key << <span class="string">"不在哈希表中！"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">case</span> <span class="number">4</span>:</span><br><span class="line"> print();</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">case</span> <span class="number">0</span>:</span><br><span class="line"> print();</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">default</span>:</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"invalid command!"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> printMenu();</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="5-线程安全的哈希表"><a href="#5-线程安全的哈希表" class="headerlink" title="5 线程安全的哈希表"></a>5 线程安全的哈希表</h2><p><a target="_blank" rel="noopener" href="https://github.com/efficient/libcuckoo">https://github.com/efficient/libcuckoo</a> 示例 ，待完成</p>
<h2 id="6-stl-哈希表实现原理"><a href="#6-stl-哈希表实现原理" class="headerlink" title="6 stl 哈希表实现原理"></a>6 stl 哈希表实现原理</h2>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<script>
window.addEventListener('tabs:register', () => {
let { activeClass } = CONFIG.comments;
if (CONFIG.comments.storage) {
activeClass = localStorage.getItem('comments_active') || activeClass;
}
if (activeClass) {
let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
if (activeTab) {
activeTab.click();
}
}
});
if (CONFIG.comments.storage) {
window.addEventListener('tabs:click', event => {
if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
let commentClass = event.target.classList[1];
localStorage.setItem('comments_active', commentClass);
});
}
</script>
</div>
<div class="toggle sidebar-toggle">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
<aside class="sidebar">
<div class="sidebar-inner">
<ul class="sidebar-nav motion-element">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">MIXALER</p>
<div class="site-description" itemprop="description">永不关机</div>
</div>
<div class="site-state-wrap motion-element">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">7</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
</nav>
</div>
</div>
</div>
</aside>
<div id="sidebar-dimmer"></div>
</div>
</main>
<footer class="footer">
<div class="footer-inner">
<div class="copyright">
©
<span itemprop="copyrightYear">2021</span>
<span class="with-love">
<i class="fa fa-heart"></i>
</span>
<span class="author" itemprop="copyrightHolder">MIXALER</span>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-chart-area"></i>
</span>
<span class="post-meta-item-text">站点总字数：</span>
<span title="站点总字数">34k</span>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-coffee"></i>
</span>
<span class="post-meta-item-text">站点阅读时长 ≈</span>
<span title="站点阅读时长">31 分钟</span>
</div>
<div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
</div>
</div>
</footer>
</div>
<script src="/lib/anime.min.js"></script>
<script src="/lib/velocity/velocity.min.js"></script>
<script src="/lib/velocity/velocity.ui.min.js"></script>
<script src="/js/utils.js"></script>
<script src="/js/motion.js"></script>
<script src="/js/schemes/pisces.js"></script>
<script src="/js/next-boot.js"></script>
</body>
</html>