-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathdictvslist.html
137 lines (128 loc) · 10.7 KB
/
dictvslist.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
<!DOCTYPE html>
<html lang="vi">
<head>
<title>Tin tức Python PyMI.vn</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<meta charset="utf-8" />
<link href="https://n.pymi.vn/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Tin tức Python PyMI.vn Full Atom Feed" />
<!-- twitter card metadata -->
<meta name="twitter:site" content="">
<meta name="twitter:title" content="Tìm kiếm trong dict nhanh gấp list hàng ngàn lần">
<meta name="twitter:description" content="Dictionary tối ưu cho việc tìm kiếm">
<!-- OG Tags -->
<meta property="og:url" content="./dictvslist.html"/>
<meta property="og:title" content="Tìm kiếm trong dict nhanh gấp list hàng ngàn lần | Tin tức Python PyMI.vn" />
<meta property="og:description" content="Dictionary tối ưu cho việc tìm kiếm" />
<!-- favicon -->
<!-- moment.js for date formatting -->
<script src="./theme/js/moment.js"></script>
<!-- css -->
<link rel="stylesheet" type="text/css" href="./theme/css/main.css" />
<script>
/*! grunt-grunticon Stylesheet Loader - v2.1.2 | https://github.com/filamentgroup/grunticon | (c) 2015 Scott Jehl, Filament Group, Inc. | MIT license. */
(function(e){function t(t,n,r,o){"use strict";function a(){for(var e,n=0;u.length>n;n++)u[n].href&&u[n].href.indexOf(t)>-1&&(e=!0);e?i.media=r||"all":setTimeout(a)}var i=e.document.createElement("link"),l=n||e.document.getElementsByTagName("script")[0],u=e.document.styleSheets;return i.rel="stylesheet",i.href=t,i.media="only x",i.onload=o||null,l.parentNode.insertBefore(i,l),a(),i}var n=function(r,o){"use strict";if(r&&3===r.length){var a=e.navigator,i=e.Image,l=!(!document.createElementNS||!document.createElementNS("http://www.w3.org/2000/svg","svg").createSVGRect||!document.implementation.hasFeature("http://www.w3.org/TR/SVG11/feature#Image","1.1")||e.opera&&-1===a.userAgent.indexOf("Chrome")||-1!==a.userAgent.indexOf("Series40")),u=new i;u.onerror=function(){n.method="png",n.href=r[2],t(r[2])},u.onload=function(){var e=1===u.width&&1===u.height,a=r[e&&l?0:e?1:2];n.method=e&&l?"svg":e?"datapng":"png",n.href=a,t(a,null,null,o)},u.src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///ywAAAAAAQABAAACAUwAOw==",document.documentElement.className+=" grunticon"}};n.loadCSS=t,e.grunticon=n})(this);(function(e,t){"use strict";var n=t.document,r="grunticon:",o=function(e){if(n.attachEvent?"complete"===n.readyState:"loading"!==n.readyState)e();else{var t=!1;n.addEventListener("readystatechange",function(){t||(t=!0,e())},!1)}},a=function(e){return t.document.querySelector('link[href$="'+e+'"]')},c=function(e){var t,n,o,a,c,i,u={};if(t=e.sheet,!t)return u;n=t.cssRules?t.cssRules:t.rules;for(var l=0;n.length>l;l++)o=n[l].cssText,a=r+n[l].selectorText,c=o.split(");")[0].match(/US\-ASCII\,([^"']+)/),c&&c[1]&&(i=decodeURIComponent(c[1]),u[a]=i);return u},i=function(e){var t,o,a;o="data-grunticon-embed";for(var c in e)if(a=c.slice(r.length),t=n.querySelectorAll(a+"["+o+"]"),t.length)for(var i=0;t.length>i;i++)t[i].innerHTML=e[c],t[i].style.backgroundImage="none",t[i].removeAttribute(o);return t},u=function(t){"svg"===e.method&&o(function(){i(c(a(e.href))),"function"==typeof t&&t()})};e.embedIcons=i,e.getCSS=a,e.getIcons=c,e.ready=o,e.svgLoadedCallback=u,e.embedSVG=u})(grunticon,this);
grunticon(["./theme/css/icons.data.svg.css", "./theme/css/icons.data.png.css", "./theme/css/icons.fallback.css"]);
</script>
<noscript><link href="./theme/css/icons.fallback.css" rel="stylesheet"></noscript>
<!-- menu toggle javascript -->
<script type="text/javascript">
document.addEventListener("DOMContentLoaded", initMenu);
function initMenu(){
var menu = document.getElementById("menu");
var menulink = document.getElementById("menu-link");
menulink.addEventListener("click", function toggleMenu(){
window.event.preventDefault();
menulink.classList.toggle('active');
menu.classList.toggle('active');
});
};
</script>
<meta name="description" content="Dictionary tối ưu cho việc tìm kiếm" />
<meta name="tags" content="dict" />
<meta name="tags" content="list" />
<meta name="tags" content="timeit" />
<meta name="tags" content="speed" />
<meta name="tags" content="bigO" />
</head>
<body>
<div role="banner" id="masthead">
<header>
<h1><a href="/">Pymiers's Blog</a></h1>
<a href="#menu" id="menu-link">more stuff</a>
<nav id="menu">
<ul>
<li><a href="./category/features.html">features</a></li>
<li class="active"><a href="./category/news.html">news</a></li>
<li><a href="./category/pymivn.html">pymi.vn</a></li>
</ul>
</nav>
</header>
</div>
<div class="page" role="main">
<div class="article" role="article">
<article>
<footer>
<a name="top"></a>
<p>
<time datetime=" 2021-11-06 00:00:00+07:00">
<script>document.write(moment('2021-11-06 00:00:00+07:00').format('LL'));</script>
</time>
</p>
</footer>
<header>
<h2>
Tìm kiếm trong dict nhanh gấp list hàng ngàn lần
</h2>
<center>
<h4>
by Pymier0
</h4>
</center>
</header>
<div class="content">
<p>Python rất dễ dùng, để tìm kiếm chỉ cần gõ: <code>i in X</code>
dù X là list, dict, set, str, tuple đều chạy.</p>
<p>Code giống nhau, nhưng cách chạy thì khác nhau. Viết <code>i in List</code> so với
<code>i in Dict</code> hoặc <code>i in Set</code> có tốc độ khác nhau rất nhiều.</p>
<p><img alt="img" src="https://images.unsplash.com/photo-1624724585603-967eb2073e03?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwyMzI1MzN8MHwxfHJhbmRvbXx8fHx8fHx8fDE2MzYxNzA5Nzk&ixlib=rb-1.2.1&q=80&w=600"></p>
<p><code>i in List</code>: list là 1 array/list, để tìm 1 giá trị, Python sẽ kiểm tra lần
lượt từng giá trị từ đầu tới cuối cho đến khi tìm thấy. Tức trường hợp xấu nhất,
khi không thấy, Python phải kiểm tra hết <code>len(List)</code> phần tử. Số lần kiểm tra
tỷ lệ thuận với số phần tử, gọi là có độ phức tạp thuật toán về thời gian <code>O(n)</code>.</p>
<p>Dùng timeit để đo:</p>
<div class="highlight"><pre><span></span><code><span class="err">$</span> <span class="n">python3</span> <span class="o">-</span><span class="n">m</span> <span class="n">timeit</span> <span class="o">--</span><span class="n">setup</span> <span class="s1">'n=10_000; L=list(range(n))'</span> <span class="s1">'n in L'</span>
<span class="mi">5000</span> <span class="n">loops</span><span class="p">,</span> <span class="n">best</span> <span class="n">of</span> <span class="mi">5</span><span class="p">:</span> <span class="mf">55.2</span> <span class="n">usec</span> <span class="n">per</span> <span class="n">loop</span>
<span class="err">$</span> <span class="n">python3</span> <span class="o">-</span><span class="n">m</span> <span class="n">timeit</span> <span class="o">--</span><span class="n">setup</span> <span class="s1">'n=100_000; L=list(range(n))'</span> <span class="s1">'n in L'</span>
<span class="mi">500</span> <span class="n">loops</span><span class="p">,</span> <span class="n">best</span> <span class="n">of</span> <span class="mi">5</span><span class="p">:</span> <span class="mi">569</span> <span class="n">usec</span> <span class="n">per</span> <span class="n">loop</span>
</code></pre></div>
<p>Thấy khi list có 100_000 phần tử, trường hợp xấu nhất sẽ chậm hơn 10 lần so với
list có 10_000 phần tử.</p>
<p>Kiểu dict được tối ưu cho việc tìm kiếm (nên đặt tên là dictionary), việc tìm
kiếm diễn ra “tức thì”, không quan tâm dict lớn đến đâu. Việc tìm kiếm với tốc
độ cố định này gọi là thuật toán có độ phức tạp hằng số (constant), hay <code>O(1)</code>:</p>
<div class="highlight"><pre><span></span><code><span class="err">$</span> <span class="n">python3</span> <span class="o">-</span><span class="n">m</span> <span class="n">timeit</span> <span class="o">--</span><span class="n">setup</span> <span class="s1">'n = 10_000; D = {i: i**2 for i in range(n)}'</span> <span class="s1">'n in D'</span>
<span class="mi">20000000</span> <span class="n">loops</span><span class="p">,</span> <span class="n">best</span> <span class="n">of</span> <span class="mi">5</span><span class="p">:</span> <span class="mf">17.7</span> <span class="n">nsec</span> <span class="n">per</span> <span class="n">loop</span>
<span class="err">$</span> <span class="n">python3</span> <span class="o">-</span><span class="n">m</span> <span class="n">timeit</span> <span class="o">--</span><span class="n">setup</span> <span class="s1">'n = 100_000; D = {i: i**2 for i in range(n)}'</span> <span class="s1">'n in D'</span>
<span class="mi">20000000</span> <span class="n">loops</span><span class="p">,</span> <span class="n">best</span> <span class="n">of</span> <span class="mi">5</span><span class="p">:</span> <span class="mf">18.3</span> <span class="n">nsec</span> <span class="n">per</span> <span class="n">loop</span>
</code></pre></div>
<p>Trường hợp đầu tiên với 10_000, tìm trong dict nhanh hơn trong list 3000 lần,
trường hợp thứ 2 là 30_000 lần.</p>
<p>Khi cần tìm kiếm, nhớ dùng dict (và set).</p>
<p>Đăng ký ngay tại <a href="https://pymi.vn">PyMI.vn</a> để học Python tại Hà Nội <span class="caps">TP</span> <span class="caps">HCM</span> (Sài Gòn),
trở thành lập trình viên #python chuyên nghiệp ngay sau khóa học.</p>
</div>
<div class="back-to-top">
<a href="#top">back to top</a>
</div>
</article>
</div>
<!-- end article -->
<footer>
<div class="icons">
<a href="https://github.com/pymivn" target="_blank"><div class="icon-github icon"></div></a>
</div>
<p>© <script>document.write(moment().format('YYYY'));</script> Pymiers</p>
</footer>
</div>
</body>
</html>