-
Notifications
You must be signed in to change notification settings - Fork 54
/
Copy pathDataStructures_II_Dictionaries.html
601 lines (560 loc) · 65.3 KB
/
DataStructures_II_Dictionaries.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
<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8" /><meta content="Topic: Introduction to Dictionaries, Difficulty: Medium, Category: Section" name="description" />
<meta content="dictionary, complexity, key, value, iteration, get item, hashing, lookup, interview preparation" name="keywords" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Data Structures (Part II): Dictionaries — Python Like You Mean It</title>
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="../_static/my_theme.css" type="text/css" />
<!--[if lt IE 9]>
<script src="../_static/js/html5shiv.min.js"></script>
<![endif]-->
<script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<script async="async" src="https://www.googletagmanager.com/gtag/js?id=UA-115029372-1"></script>
<script src="../_static/gtag.js"></script>
<script crossorigin="anonymous" integrity="sha256-Ae2Vz/4ePdIu6ZyI/5ZGsYnb+m0JlOmKPjt6XZ9JJkA=" src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.4/require.min.js"></script>
<script>window.MathJax = {"tex": {"inlineMath": [["$", "$"], ["\\(", "\\)"]], "processEscapes": true}, "options": {"ignoreHtmlClass": "tex2jax_ignore|mathjax_ignore|document", "processHtmlClass": "tex2jax_process|mathjax_process|math|output_area"}}</script>
<script defer="defer" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script src="../_static/js/theme.js"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="Data Structures (Part III): Sets & the Collections Module" href="DataStructures_III_Sets_and_More.html" />
<link rel="prev" title="Data Structures (Part I): Introduction" href="DataStructures.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="../index.html" class="icon icon-home"> Python Like You Mean It
</a>
<div class="version">
1.4
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<p class="caption" role="heading"><span class="caption-text">Table of Contents:</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../intro.html">Python Like You Mean It</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_1.html">Module 1: Getting Started with Python</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../module_2.html">Module 2: The Essentials of Python</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="Basic_Objects.html">Basic Object Types</a></li>
<li class="toctree-l2"><a class="reference internal" href="SequenceTypes.html">Sequence Types</a></li>
<li class="toctree-l2"><a class="reference internal" href="Variables_and_Assignment.html">Variables & Assignment</a></li>
<li class="toctree-l2"><a class="reference internal" href="Introduction.html">Introducing Control Flow</a></li>
<li class="toctree-l2"><a class="reference internal" href="ConditionalStatements.html">Conditional Statements</a></li>
<li class="toctree-l2"><a class="reference internal" href="ForLoops.html">For-Loops and While-Loops</a></li>
<li class="toctree-l2"><a class="reference internal" href="Iterables.html">Iterables</a></li>
<li class="toctree-l2"><a class="reference internal" href="Generators_and_Comprehensions.html">Generators & Comprehension Expressions</a></li>
<li class="toctree-l2"><a class="reference internal" href="Itertools.html">Python’s “Itertools”</a></li>
<li class="toctree-l2"><a class="reference internal" href="Functions.html">Basics of Functions</a></li>
<li class="toctree-l2"><a class="reference internal" href="Scope.html">Scope</a></li>
<li class="toctree-l2"><a class="reference internal" href="DataStructures.html">Data Structures (Part I): Introduction</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">Data Structures (Part II): Dictionaries</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#Dictionary-Basics">Dictionary Basics</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#Constructing-a-dictionary">Constructing a dictionary</a></li>
<li class="toctree-l4"><a class="reference internal" href="#Retrieving-a-value,-given-a-key">Retrieving a value, given a key</a></li>
<li class="toctree-l4"><a class="reference internal" href="#Adding-more-key-value-mappings">Adding more key-value mappings</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#What-Can-a-Dictionary-Store?">What Can a Dictionary Store?</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#Numerical-Precision-&-Dictionary-Keys">Numerical Precision & Dictionary Keys</a></li>
<li class="toctree-l4"><a class="reference internal" href="#Inspecting-a-Dictionary">Inspecting a Dictionary</a></li>
<li class="toctree-l4"><a class="reference internal" href="#Time-Complexities-of-the-Dictionary’s-Functions">Time Complexities of the Dictionary’s Functions</a></li>
<li class="toctree-l4"><a class="reference internal" href="#Are-Dictionaries-Ordered?-A-Word-of-Warning">Are Dictionaries Ordered? A Word of Warning</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#Links-to-Official-Documentation">Links to Official Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="#Reading-Comprehension-Solutions">Reading Comprehension Solutions</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="DataStructures_III_Sets_and_More.html">Data Structures (Part III): Sets & the Collections Module</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../module_2_problems.html">Module 2: Problems</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_3.html">Module 3: The Essentials of NumPy</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_3_problems.html">Module 3: Problems</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_4.html">Module 4: Object Oriented Programming</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_5.html">Module 5: Odds and Ends</a></li>
<li class="toctree-l1"><a class="reference internal" href="../changes.html">Changelog</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="../index.html">Python Like You Mean It</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="../index.html" class="icon icon-home"></a> »</li>
<li><a href="../module_2.html">Module 2: The Essentials of Python</a> »</li>
<li>Data Structures (Part II): Dictionaries</li>
<li class="wy-breadcrumbs-aside">
<a href="../_sources/Module2_EssentialsOfPython/DataStructures_II_Dictionaries.md.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<style>
/* CSS overrides for sphinx_rtd_theme */
/* 24px margin */
.nbinput.nblast.container,
.nboutput.nblast.container {
margin-bottom: 19px; /* padding has already 5px */
}
/* ... except between code cells! */
.nblast.container + .nbinput.container {
margin-top: -19px;
}
.admonition > p:before {
margin-right: 4px; /* make room for the exclamation icon */
}
/* Fix math alignment, see https://github.com/rtfd/sphinx_rtd_theme/pull/686 */
.math {
text-align: unset;
}
</style>
<div class="section" id="Data-Structures-(Part-II):-Dictionaries">
<h1>Data Structures (Part II): Dictionaries<a class="headerlink" href="#Data-Structures-(Part-II):-Dictionaries" title="Permalink to this headline"></a></h1>
<p>Python’s dictionary allows you to store key-value pairs, and then pass the dictionary a key to quickly retrieve its corresponding value. Specifically, you construct the dictionary by specifying one-way mappings from key-objects to value-objects. <strong>Each key must map to exactly one value</strong>, meaning that a key must be unique.</p>
<p>Let’s create the following mapping of grocery-to-price:</p>
<ul class="simple">
<li><p>“cheese” <span class="math notranslate nohighlight">\(\rightarrow\)</span> 2.53,</p></li>
<li><p>“milk” <span class="math notranslate nohighlight">\(\rightarrow\)</span> 3.40,</p></li>
<li><p>“frozen pizza” <span class="math notranslate nohighlight">\(\rightarrow\)</span> 8.01</p></li>
</ul>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># use a dictionary to map groceries to prices: item-name -> price</span>
<span class="o">>>></span> <span class="n">items_to_prices</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"cheese"</span><span class="p">:</span> <span class="mf">2.53</span><span class="p">,</span> <span class="s2">"milk"</span><span class="p">:</span> <span class="mf">3.40</span><span class="p">,</span> <span class="s2">"frozen pizza"</span><span class="p">:</span> <span class="mf">8.01</span><span class="p">}</span>
<span class="c1"># looking up the price of "frozen pizza"</span>
<span class="o">>>></span> <span class="n">items_to_prices</span><span class="p">[</span><span class="s2">"frozen pizza"</span><span class="p">]</span>
<span class="mf">8.01</span>
</pre></div>
</div>
<p>Python’s dictionary is a shining star among its data structures; it is compact, fast, versatile, and extremely useful. It can be used to create a wide variety of mappings.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># keep track of whether or not a 3D coordinate fell into some region in space</span>
<span class="c1"># map (x, y, z) coordinates to "is in a region": (x, y, z) -> True/False</span>
<span class="o">>>></span> <span class="n">point_to_region</span> <span class="o">=</span> <span class="p">{(</span><span class="mf">0.1</span><span class="p">,</span> <span class="mf">2.2</span><span class="p">,</span> <span class="mi">3</span><span class="p">):</span><span class="kc">False</span><span class="p">,</span> <span class="p">(</span><span class="o">-</span><span class="mf">10.</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mf">4.5</span><span class="p">):</span><span class="kc">True</span><span class="p">,</span> <span class="p">(</span><span class="mf">4.3</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">9.5</span><span class="p">):</span><span class="kc">False</span><span class="p">}</span>
<span class="o">>>></span> <span class="n">point_to_region</span><span class="p">[(</span><span class="o">-</span><span class="mf">10.</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mf">4.5</span><span class="p">)]</span>
<span class="kc">True</span>
<span class="c1"># map student-name to exam scores: name -> scores</span>
<span class="o">>>></span> <span class="n">name_to_scores</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"Ryan S"</span><span class="p">:</span> <span class="p">[</span><span class="mi">65</span><span class="p">,</span> <span class="mi">50</span><span class="p">,</span> <span class="mi">80</span><span class="p">],</span> <span class="s2">"Nick S"</span><span class="p">:</span> <span class="p">[</span><span class="mi">100</span><span class="p">,</span> <span class="mi">99</span><span class="p">,</span> <span class="mi">90</span><span class="p">]}</span>
<span class="o">>>></span> <span class="n">name_to_scores</span><span class="p">[</span><span class="s2">"Ryan S"</span><span class="p">]</span>
<span class="p">[</span><span class="mi">65</span><span class="p">,</span> <span class="mi">50</span><span class="p">,</span> <span class="mi">80</span><span class="p">]</span>
</pre></div>
</div>
<p>It is important to note outright that the time it takes for dictionary to take a key and retrieve a value <em>does not depend on the size of the dictionary.</em> That is the complexity for a dictionary look-up is <span class="math notranslate nohighlight">\(\mathcal{O}(1)\)</span>! It accomplishes this by making use of a technique known as <a class="reference external" href="https://en.wikipedia.org/wiki/Hash_function">hashing</a>.</p>
<p>These are all instances of the built-in <code class="docutils literal notranslate"><span class="pre">dict</span></code> type:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="nb">type</span><span class="p">(</span><span class="n">items_to_prices</span><span class="p">)</span>
<span class="go">dict</span>
</pre></div>
</div>
<p>We will be discussing the essentials of the dictionary. It is highly recommended that you refer to the official Python documentation for a <a class="reference external" href="https://docs.python.org/3/library/stdtypes.html#dict">complete rundown of all the functions available to the dictionary</a>.</p>
<div class="section" id="Dictionary-Basics">
<h2>Dictionary Basics<a class="headerlink" href="#Dictionary-Basics" title="Permalink to this headline"></a></h2>
<div class="section" id="Constructing-a-dictionary">
<h3>Constructing a dictionary<a class="headerlink" href="#Constructing-a-dictionary" title="Permalink to this headline"></a></h3>
<p>A nice syntax for creating a dictionary is to specify key-value pairs inside “curly braces”: <code class="docutils literal notranslate"><span class="pre">{key1:value1,</span> <span class="pre">key2:value2,</span> <span class="pre">...}</span></code>. As an example, let’s construct a dictionary that maps types of foods to “fruit” or “vegetable”. We’ll start by mapping “apple” to “fruit”, and “carrot” to “vegetable”</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># use `{key1:value1, key2:value2, ...} to create a dictionary that maps:</span>
<span class="c1"># "apple" -> "fruit"</span>
<span class="c1"># "carrot" -> "vegetable</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"apple"</span><span class="p">:</span><span class="s2">"fruit"</span><span class="p">,</span> <span class="s2">"carrot"</span><span class="p">:</span><span class="s2">"vegetable"</span><span class="p">}</span>
<span class="c1"># create an empty dictionary</span>
<span class="o">>>></span> <span class="p">{}</span>
<span class="p">{}</span>
</pre></div>
</div>
<p>You can also use <code class="docutils literal notranslate"><span class="pre">dict</span></code> as a constructor to create the dictionary. It can be fed an iterable of key-value pairs, each of which is packed in a sequence, such as a tuple.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># use `dict` to create a dictionary that maps:</span>
<span class="c1"># "apple" -> "fruit"</span>
<span class="c1"># "carrot" -> "vegetable</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">([(</span><span class="s2">"apple"</span><span class="p">,</span> <span class="s2">"fruit"</span><span class="p">),</span> <span class="p">(</span><span class="s2">"carrot"</span><span class="p">,</span> <span class="s2">"vegetable"</span><span class="p">)])</span>
<span class="c1"># use `dict` to create an empty dictionary:</span>
<span class="o">>>></span> <span class="nb">dict</span><span class="p">()</span>
<span class="p">{}</span>
</pre></div>
</div>
<p>Lastly, Python also supports a dictionary-comprehension syntax, which mirrors the generator/list comprehension syntax covered earlier in this module:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>{key:value for key, value in <iterable of key-value pairs> [if bool(<condition>)]}
</pre></div>
</div>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># use the 'dictionary comprehension' syntax to create a dictionary that maps:</span>
<span class="c1"># "apple" -> "fruit"</span>
<span class="c1"># "carrot" -> "vegetable</span>
<span class="o">>>></span> <span class="p">{</span><span class="n">k</span><span class="p">:</span><span class="n">v</span> <span class="k">for</span> <span class="n">k</span><span class="p">,</span><span class="n">v</span> <span class="ow">in</span> <span class="p">[(</span><span class="s2">"apple"</span><span class="p">,</span> <span class="s2">"fruit"</span><span class="p">),</span> <span class="p">(</span><span class="s2">"carrot"</span><span class="p">,</span> <span class="s2">"vegetable"</span><span class="p">)]}</span>
<span class="p">{</span><span class="s1">'apple'</span><span class="p">:</span> <span class="s1">'fruit'</span><span class="p">,</span> <span class="s1">'carrot'</span><span class="p">:</span> <span class="s1">'vegetable'</span><span class="p">}</span>
</pre></div>
</div>
</div>
<div class="section" id="Retrieving-a-value,-given-a-key">
<h3>Retrieving a value, given a key<a class="headerlink" href="#Retrieving-a-value,-given-a-key" title="Permalink to this headline"></a></h3>
<p>Now we can use this dictionary to “look up” if an item is a fruit or a veggie. Dictionaries support the same square-bracket “get-item” syntax as a list/tuple, but here a valid key is used as the index:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># get the value associated with the key "apple"</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span><span class="p">[</span><span class="s2">"apple"</span><span class="p">]</span>
<span class="s2">"fruit"</span>
</pre></div>
</div>
<p><code class="docutils literal notranslate"><span class="pre">KeyError</span></code> will be raised if you try to look-up a key that doesn’t exist:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># "grape" hasn't been specified as a key</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span><span class="p">[</span><span class="s2">"grape"</span><span class="p">]</span>
<span class="o">---------------------------------------------------------------------------</span>
<span class="ne">KeyError</span> <span class="n">Traceback</span> <span class="p">(</span><span class="n">most</span> <span class="n">recent</span> <span class="n">call</span> <span class="n">last</span><span class="p">)</span>
<span class="o"><</span><span class="n">ipython</span><span class="o">-</span><span class="nb">input</span><span class="o">-</span><span class="mi">30</span><span class="o">-</span><span class="mi">74</span><span class="n">c002a67890</span><span class="o">></span> <span class="ow">in</span> <span class="o"><</span><span class="n">module</span><span class="o">></span><span class="p">()</span>
<span class="o">----></span> <span class="mi">1</span> <span class="n">fruit_or_veggie</span><span class="p">[</span><span class="s2">"grape"</span><span class="p">]</span>
<span class="ne">KeyError</span><span class="p">:</span> <span class="s1">'grape'</span>
</pre></div>
</div>
</div>
<div class="section" id="Adding-more-key-value-mappings">
<h3>Adding more key-value mappings<a class="headerlink" href="#Adding-more-key-value-mappings" title="Permalink to this headline"></a></h3>
<p>Once created, a dictionary can have a new key-value pair be “set” using <code class="docutils literal notranslate"><span class="pre">my_dict[new_key]</span> <span class="pre">=</span> <span class="pre">new_value</span></code>:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># set the mapping "banana" -> "fruit"</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span><span class="p">[</span><span class="s2">"banana"</span><span class="p">]</span> <span class="o">=</span> <span class="s2">"fruit"</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span>
<span class="p">{</span><span class="s1">'apple'</span><span class="p">:</span> <span class="s1">'fruit'</span><span class="p">,</span> <span class="s1">'banana'</span><span class="p">:</span> <span class="s1">'fruit'</span><span class="p">,</span> <span class="s1">'carrot'</span><span class="p">:</span> <span class="s1">'vegetable'</span><span class="p">}</span>
</pre></div>
</div>
<p>If the key already exists, the mapping for that key will simply be updated.</p>
<p>The <code class="docutils literal notranslate"><span class="pre">update</span></code> function can be used to add multiple key-value pairs at once. This function can be passed another dictionary or an iterable of key-value sequences</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># adding multiple key-value pairs to the dictionary</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span><span class="o">.</span><span class="n">update</span><span class="p">([(</span><span class="s2">"grape"</span><span class="p">,</span> <span class="s2">"fruit"</span><span class="p">),</span> <span class="p">(</span><span class="s2">"onion"</span><span class="p">,</span> <span class="s2">"vegetable"</span><span class="p">)])</span>
<span class="o">>>></span> <span class="n">fruit_or_veggie</span>
<span class="p">{</span><span class="s1">'apple'</span><span class="p">:</span> <span class="s1">'fruit'</span><span class="p">,</span>
<span class="s1">'banana'</span><span class="p">:</span> <span class="s1">'fruit'</span><span class="p">,</span>
<span class="s1">'carrot'</span><span class="p">:</span> <span class="s1">'vegetable'</span><span class="p">,</span>
<span class="s1">'grape'</span><span class="p">:</span> <span class="s1">'fruit'</span><span class="p">,</span>
<span class="s1">'onion'</span><span class="p">:</span> <span class="s1">'vegetable'</span><span class="p">}</span>
</pre></div>
</div>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Reading Comprehension: Dictionary Basics</strong></p>
<p>Given the tuple of student names <code class="docutils literal notranslate"><span class="pre">("Ashley",</span> <span class="pre">"David",</span> <span class="pre">"Edward",</span> <span class="pre">"Zoe")</span></code>, and their corresponding exam grades <code class="docutils literal notranslate"><span class="pre">(0.92,</span> <span class="pre">0.72,</span> <span class="pre">0.88,</span> <span class="pre">0.77)</span></code>, create a dictionary that maps: name <span class="math notranslate nohighlight">\(\rightarrow\)</span> grade. Then, update Zoe’s grade to <code class="docutils literal notranslate"><span class="pre">.79</span></code>. Lastly, add a new student, Ryan, whose grade is 0.34.</p>
</div>
</div>
</div>
<div class="section" id="What-Can-a-Dictionary-Store?">
<h2>What Can a Dictionary Store?<a class="headerlink" href="#What-Can-a-Dictionary-Store?" title="Permalink to this headline"></a></h2>
<p>Although the preceding example only involves a mappings from strings to strings, <em>the keys and values of a dictionary can be heterogeneous in type</em>:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># demonstrates the wide variety of object types that can be used as</span>
<span class="c1"># keys and values in a dictionary</span>
<span class="o">>>></span> <span class="n">example_dict</span> <span class="o">=</span> <span class="p">{</span><span class="o">-</span><span class="mi">1</span><span class="p">:</span><span class="mi">10</span><span class="p">,</span> <span class="s2">"moo"</span><span class="p">:</span><span class="kc">True</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">):</span><span class="nb">print</span><span class="p">,</span> <span class="mf">3.4</span><span class="p">:</span><span class="s2">"cow"</span><span class="p">,</span> <span class="kc">False</span><span class="p">:[]}</span>
<span class="o">>>></span> <span class="n">example_dict</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
<span class="mi">10</span>
<span class="o">>>></span> <span class="n">example_dict</span><span class="p">[</span><span class="s2">"moo"</span><span class="p">]</span>
<span class="kc">True</span>
<span class="o">>>></span> <span class="n">example_dict</span><span class="p">[(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">)]</span>
<span class="o"><</span><span class="n">function</span> <span class="nb">print</span><span class="o">></span>
<span class="o">>>></span> <span class="n">example_dict</span><span class="p">[</span><span class="mf">3.4</span><span class="p">]</span>
<span class="s2">"cow"</span>
<span class="o">>>></span> <span class="n">example_dict</span><span class="p">[</span><span class="kc">False</span><span class="p">]</span>
<span class="p">[]</span>
</pre></div>
</div>
<p>To be specific, a dictionary’s contents are dictated by the following rules:</p>
<ul class="simple">
<li><p>A dictionary <em>key</em> must be an <em>immutable</em> object (more precisely, it must be <a class="reference external" href="https://docs.python.org/3/glossary.html#term-hashable">hashable</a>; don’t worry about this detail).</p></li>
<li><p>A dictionary <em>value</em> can be any object (even the dictionary itself! Try this, it’s cool!)</p></li>
</ul>
<div class="admonition warning">
<p class="admonition-title fa fa-exclamation-circle"><strong>Recall</strong>:</p>
<p>A mutable object can be changed after it is created. An immutable object cannot be changed.</p>
</div>
<p>Thus valid keys can be the following types:</p>
<ul class="simple">
<li><p>numbers (integers, floating-point numbers, complex numbers)</p></li>
<li><p>strings</p></li>
<li><p>tuples (if the tuple contains anything, it must be other immutable objects)</p></li>
<li><p>boolean values</p></li>
<li><p><a class="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/DataStructures_III_Sets_and_More.html#Set-operations">frozenset</a> objects</p></li>
</ul>
<p>Trying to use a mutable object as a key is problematic since that object could be changed <em>after</em> it was already used as a key. Thus the dictionary would have to “detect” this change and recreate its “lookup scheme” for the changed key. Values, on the other hand, can be mutable because the details of a given value-object have no impact on how the dictionary retrieves it.</p>
<p>In accordance with this discussion will get a <code class="docutils literal notranslate"><span class="pre">TypeError</span></code> if you try to use a list as a key, since lists are mutable:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># trying to use a list as a key</span>
<span class="c1"># this raises an error because lists are mutable</span>
<span class="o">>>></span> <span class="n">bad_dict</span> <span class="o">=</span> <span class="p">{[]:</span><span class="mi">1</span><span class="p">}</span>
<span class="o">---------------------------------------------------------------------------</span>
<span class="ne">TypeError</span> <span class="n">Traceback</span> <span class="p">(</span><span class="n">most</span> <span class="n">recent</span> <span class="n">call</span> <span class="n">last</span><span class="p">)</span>
<span class="o"><</span><span class="n">ipython</span><span class="o">-</span><span class="nb">input</span><span class="o">-</span><span class="mi">50</span><span class="o">-</span><span class="n">e7cf39509d06</span><span class="o">></span> <span class="ow">in</span> <span class="o"><</span><span class="n">module</span><span class="o">></span><span class="p">()</span>
<span class="o">----></span> <span class="mi">1</span> <span class="n">bad_dict</span> <span class="o">=</span> <span class="p">{[]:</span><span class="mi">1</span><span class="p">}</span>
<span class="ne">TypeError</span><span class="p">:</span> <span class="n">unhashable</span> <span class="nb">type</span><span class="p">:</span> <span class="s1">'list'</span>
</pre></div>
</div>
<div class="section" id="Numerical-Precision-&-Dictionary-Keys">
<h3>Numerical Precision & Dictionary Keys<a class="headerlink" href="#Numerical-Precision-&-Dictionary-Keys" title="Permalink to this headline"></a></h3>
<p>Care must be taken when using floating-point numbers as a key in a dictionary, <a class="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Basic_Objects.html#Understanding-Numerical-Precision">due to its limited numerical precision</a>. For the same reason that you ought not rely on two floats being equal, you should not assume that two floats will produce the same hash, when stored as a key:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># the folly of using a floating-point number as a key</span>
<span class="c1"># in a dictionary</span>
<span class="o">>>></span> <span class="n">x</span> <span class="o">=</span> <span class="p">{}</span>
<span class="o">>>></span> <span class="n">x</span><span class="p">[(</span><span class="mf">0.1</span> <span class="o">+</span> <span class="mf">0.1</span> <span class="o">+</span> <span class="mf">0.1</span><span class="p">)</span> <span class="o">-</span> <span class="mf">0.3</span><span class="p">]</span> <span class="o">=</span> <span class="s2">"apple"</span>
<span class="o">>>></span> <span class="n">x</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span>
<span class="ne">KeyError</span><span class="p">:</span> <span class="mi">0</span>
</pre></div>
</div>
<p>An acceptable way of accommodating the use of a float as a key, depending on the use case, is to first round the floating point number to normalize it to a lower precision:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># rounding a float before using it as a key</span>
<span class="o">>>></span> <span class="n">x</span> <span class="o">=</span> <span class="p">{}</span>
<span class="c1"># round the float to its 2nd decimal place</span>
<span class="o">>>></span> <span class="n">float_key</span> <span class="o">=</span> <span class="nb">round</span><span class="p">((</span><span class="mf">0.1</span> <span class="o">+</span> <span class="mf">0.1</span> <span class="o">+</span> <span class="mf">0.1</span><span class="p">)</span> <span class="o">-</span> <span class="mf">0.3</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
<span class="o">>>></span> <span class="n">x</span><span class="p">[</span><span class="n">float_key</span><span class="p">]</span> <span class="o">=</span> <span class="s2">"apple"</span>
<span class="o">>></span> <span class="n">x</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span>
<span class="s1">'apple'</span>
</pre></div>
</div>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong>:</p>
<p>A dictionary key must be an immutable object. A dictionary value can be any object.</p>
</div>
</div>
<div class="section" id="Inspecting-a-Dictionary">
<h3>Inspecting a Dictionary<a class="headerlink" href="#Inspecting-a-Dictionary" title="Permalink to this headline"></a></h3>
<p>The dictionary provides tooling for inspecting and iterating over its keys and values. We will use the following dictionary for our examples:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">example_dict</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"key1"</span><span class="p">:</span><span class="s2">"value1"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">:</span><span class="s2">"value2"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">:</span><span class="s2">"value3"</span><span class="p">}</span>
</pre></div>
</div>
<p><strong>Inspecting a dictionary’s keys</strong></p>
<p>The dictionary itself can be used to iterate over its keys:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># iterating over a dictionary produces its keys</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="p">]</span>
<span class="p">[</span><span class="s1">'key1'</span><span class="p">,</span> <span class="s1">'key2'</span><span class="p">,</span> <span class="s1">'key3'</span><span class="p">]</span>
</pre></div>
</div>
<p>You can also use the dictionary to test for membership among its keys:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># checking if an object is among a dictionary's keys</span>
<span class="o">>>></span> <span class="s2">"key3"</span> <span class="ow">in</span> <span class="n">example_dict</span>
<span class="kc">True</span>
<span class="c1"># you *cannot* use this to check for membership among its valus</span>
<span class="o">>>></span> <span class="s2">"value3"</span> <span class="ow">in</span> <span class="n">example_dict</span>
<span class="kc">False</span>
</pre></div>
</div>
<p><code class="docutils literal notranslate"><span class="pre">len</span></code> counts the number of keys in the dictionary:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="nb">len</span><span class="p">(</span><span class="n">example_dict</span><span class="p">)</span>
<span class="go">3</span>
</pre></div>
</div>
<p><code class="docutils literal notranslate"><span class="pre">example_dict.keys()</span></code> also returns an iterable over the dictionary’s keys, and thus can be used to exactly the same effect as the dictionary itself in these preceding examples.</p>
<p><strong>Inspecting a dictionary’s values</strong></p>
<p><code class="docutils literal notranslate"><span class="pre">example_dict.values()</span></code> can be iterated over to produce that dictionary’s values:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># iterating over a dictionary's values</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="o">.</span><span class="n">values</span><span class="p">()]</span>
<span class="p">[</span><span class="s1">'value1'</span><span class="p">,</span> <span class="s1">'value2'</span><span class="p">,</span> <span class="s1">'value3'</span><span class="p">]</span>
</pre></div>
</div>
<p>You can also use this to test for membership among the dictionary’s values:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># checking if an object is among a dictionary's values</span>
<span class="o">>>></span> <span class="s2">"value1"</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="o">.</span><span class="n">values</span><span class="p">()</span>
<span class="kc">True</span>
</pre></div>
</div>
<p><strong>Inspecting a dictionary’s key-value pairs</strong></p>
<p><code class="docutils literal notranslate"><span class="pre">example_dict.items()</span></code> can be iterated over to produce that dictionary’s key-value pairs (which are packed into tuples):</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># iterating over a dictionary produces its keys</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="o">.</span><span class="n">items</span><span class="p">()]</span>
<span class="p">[(</span><span class="s1">'key1'</span><span class="p">,</span> <span class="s1">'value1'</span><span class="p">),</span> <span class="p">(</span><span class="s1">'key2'</span><span class="p">,</span> <span class="s1">'value2'</span><span class="p">),</span> <span class="p">(</span><span class="s1">'key3'</span><span class="p">,</span> <span class="s1">'value3'</span><span class="p">)]</span>
</pre></div>
</div>
<p>You can also use this to test for membership among the dictionary’s key-value pairs:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># checking if a key-value pair exists in a dictionary</span>
<span class="o">>>></span> <span class="p">(</span><span class="s1">'key1'</span><span class="p">,</span> <span class="s1">'value1'</span><span class="p">)</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="o">.</span><span class="n">items</span><span class="p">()</span>
<span class="kc">True</span>
</pre></div>
</div>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Reading Comprehension: Inverting a Dictionary</strong></p>
<p>Write a function that inverts a dictionary. For example, if you were given <code class="docutils literal notranslate"><span class="pre">x</span> <span class="pre">=</span> <span class="pre">{'k1':</span> <span class="pre">'v1',</span> <span class="pre">'k2':</span> <span class="pre">'v2',</span> <span class="pre">'k3':</span> <span class="pre">'v3'}</span></code>, you would produce the dictionary <code class="docutils literal notranslate"><span class="pre">inverted_x</span> <span class="pre">=</span> <span class="pre">{'v1':</span> <span class="pre">'k1',</span> <span class="pre">'v2':</span> <span class="pre">'k2',</span> <span class="pre">'v3':</span> <span class="pre">'k3'}</span></code>.</p>
</div>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Reading Comprehension: Inspecting a Dictionary</strong></p>
<p>Assume we are working with a dictionary whose values are all <em>unique</em> numbers. Write a function that returns the <em>key</em> that maps to the <em>largest</em> value in the dictionary.</p>
<p>Next, generalize your solution for a dictionary whose values are not necessarily unique. Return a tuple of all of the keys that map to that max value.</p>
</div>
</div>
<div class="section" id="Time-Complexities-of-the-Dictionary’s-Functions">
<h3>Time Complexities of the Dictionary’s Functions<a class="headerlink" href="#Time-Complexities-of-the-Dictionary’s-Functions" title="Permalink to this headline"></a></h3>
<p>In addition to being flexible and versatile, the dictionary’s functions manage to be quite efficient as well. The following is a summary of the time complexities associated with various common operations using a dictionary (according to its implementation in CPython) - note all the <span class="math notranslate nohighlight">\(\mathcal{O}(1)\)</span> operations!</p>
<p>Let <code class="docutils literal notranslate"><span class="pre">example_dict</span></code> represent a dictionary with <span class="math notranslate nohighlight">\(n\)</span> key-value pair mappings.</p>
<p>The following are <span class="math notranslate nohighlight">\(\mathcal{O}(1)\)</span> operations:</p>
<ul class="simple">
<li><p>Return the number of keys in the dictionary: <code class="docutils literal notranslate"><span class="pre">len(example_dict)</span></code></p></li>
<li><p>Check if the key is in the dictionary, and return the value if it is: <code class="docutils literal notranslate"><span class="pre">example_dict[key]</span></code></p></li>
<li><p>Set a key-value mapping: <code class="docutils literal notranslate"><span class="pre">example_dict[key]</span> <span class="pre">=</span> <span class="pre">value</span></code></p></li>
<li><p>Check if an object is among the dictionary’s keys: <code class="docutils literal notranslate"><span class="pre">obj</span> <span class="pre">in</span> <span class="pre">example_dict</span></code></p></li>
<li><p>Check if a pair of objects are among the dictionary’s key-value pairs: <code class="docutils literal notranslate"><span class="pre">(obj1,</span> <span class="pre">obj2)</span> <span class="pre">in</span> <span class="pre">example_dict.items()</span></code></p></li>
</ul>
<p>The following are <span class="math notranslate nohighlight">\(\mathcal{O}(n)\)</span> operations:</p>
<ul class="simple">
<li><p>Check if an object is among the dictionary’s values: <code class="docutils literal notranslate"><span class="pre">obj</span> <span class="pre">in</span> <span class="pre">example_dict.values()</span></code></p></li>
<li><p>Iterate over the dictionary’s keys/values/key-value pairs</p></li>
</ul>
</div>
<div class="section" id="Are-Dictionaries-Ordered?-A-Word-of-Warning">
<h3>Are Dictionaries Ordered? A Word of Warning<a class="headerlink" href="#Are-Dictionaries-Ordered?-A-Word-of-Warning" title="Permalink to this headline"></a></h3>
<p>Unlike Python’s sequences, the dictionary has no inherent ordering… that is, until Python 3.6 came out.</p>
<p>Prior to Python 3.6, a dictionary had no ordering associated with it. If you iterated over a dictionary’s keys, values, or key-value pairs, you had no guarantee about the <em>order</em> in which these items would be produced. <code class="docutils literal notranslate"><span class="pre">[i</span> <span class="pre">for</span> <span class="pre">i</span> <span class="pre">in</span> <span class="pre">example_dict]</span></code> could produce a list of keys with different ordering each time the code was run; you were only guaranteed that the list would contain all of the dictionary’s keys:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># in Python 3.5 and earlier, dictionaries were unordered</span>
<span class="o">>>></span> <span class="n">example_dict</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"key1"</span><span class="p">:</span><span class="s2">"value1"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">:</span><span class="s2">"value2"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">:</span><span class="s2">"value3"</span><span class="p">}</span>
<span class="c1"># this can produce lists with different orders</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="p">]</span>
<span class="p">[</span><span class="s2">"key1"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">]</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="p">]</span>
<span class="p">[</span><span class="s2">"key2"</span><span class="p">,</span> <span class="s2">"key1"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">]</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="p">]</span>
<span class="p">[</span><span class="s2">"key1"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">]</span>
<span class="o">...</span>
</pre></div>
</div>
<p>The dictionary was <a class="reference external" href="https://docs.python.org/3/whatsnew/3.6.html#new-dict-implementation">reimplemented in Python 3.6</a> so that it will consume roughly 25% less memory than before (which is a big deal!). The catch is that this new implementation entails that the dictionary’s various iterables (e.g. <code class="docutils literal notranslate"><span class="pre">dict.keys()</span></code>, <code class="docutils literal notranslate"><span class="pre">dict.values()</span></code>, <code class="docutils literal notranslate"><span class="pre">dict.items()</span></code>) will always yield their items according to the order in which they were added to the dictionary.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># in Python 3.6 and beyond dictionaries are ordered according to the order in</span>
<span class="c1"># which key-value pairs were added to the dictionary by the user</span>
<span class="o">>>></span> <span class="n">example_dict</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"key1"</span><span class="p">:</span><span class="s2">"value1"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">:</span><span class="s2">"value2"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">:</span><span class="s2">"value3"</span><span class="p">}</span>
<span class="c1"># this will always produce the same ordering of keys</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">example_dict</span><span class="p">]</span>
<span class="p">[</span><span class="s2">"key1"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">]</span>
</pre></div>
</div>
<p>This is great, right? Wrong! If you write code in Python 3.6 that relies on the fact that dictionaries are ordered, your algorithm will almost certainly produce the wrong results if you run it using Python 3.5 or earlier! Worst of all, it very unlikely that this will raise any error in your code so the bug will persist silently - this is very tough to catch!</p>
<p><strong>Unless you make explicit that your code is incompatible with versions of Python prior to Python 3.6, write your code as if the dictionary is unordered!</strong></p>
<p>If you do want to use an ordered dictionary, make use of <code class="docutils literal notranslate"><span class="pre">collections.OrderedDict</span></code>, which behaves like just like the standard dictionary but is guaranteed to maintain ordering regardless of what version of Python you are using.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">OrderedDict</span>
<span class="o">>>></span> <span class="n">ordered</span> <span class="o">=</span> <span class="n">OrderedDict</span><span class="p">([(</span><span class="s1">'key1'</span><span class="p">,</span> <span class="s1">'value1'</span><span class="p">),</span> <span class="p">(</span><span class="s1">'key2'</span><span class="p">,</span> <span class="s1">'value2'</span><span class="p">),</span> <span class="p">(</span><span class="s1">'key3'</span><span class="p">,</span> <span class="s1">'value3'</span><span class="p">)])</span>
<span class="c1"># this will always produce the same result, regardless of what</span>
<span class="c1"># version of Python is being used</span>
<span class="o">>>></span> <span class="p">[</span><span class="n">i</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">ordered</span><span class="p">]</span>
<span class="p">[</span><span class="s2">"key1"</span><span class="p">,</span> <span class="s2">"key2"</span><span class="p">,</span> <span class="s2">"key3"</span><span class="p">]</span>
</pre></div>
</div>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong>:</p>
<p>No matter what version of Python you are using, write your code as if the Python dictionary is unordered. If you do want to use an ordered dictionary, your code should make use of <code class="docutils literal notranslate"><span class="pre">collections.OrderedDict</span></code>.</p>
</div>
</div>
</div>
<div class="section" id="Links-to-Official-Documentation">
<h2>Links to Official Documentation<a class="headerlink" href="#Links-to-Official-Documentation" title="Permalink to this headline"></a></h2>
<ul class="simple">
<li><p><a class="reference external" href="https://docs.python.org/3/library/stdtypes.html#mapping-types-dict">Dictionaries</a></p>
<ul>
<li><p><a class="reference external" href="https://docs.python.org/3/tutorial/datastructures.html#dictionaries">Dictionaries tutorial</a></p></li>
</ul>
</li>
<li><p><a class="reference external" href="https://docs.python.org/3/glossary.html#term-hashable">Definition of ‘hashable’</a></p></li>
<li><p><a class="reference external" href="https://docs.python.org/3/library/stdtypes.html#dictionary-view-objects">Dictionary view objects</a></p></li>
</ul>
</div>
<div class="section" id="Reading-Comprehension-Solutions">
<h2>Reading Comprehension Solutions<a class="headerlink" href="#Reading-Comprehension-Solutions" title="Permalink to this headline"></a></h2>
<p><strong>Dictionary Basics: Solutions</strong></p>
<p>Given the tuple of student names <code class="docutils literal notranslate"><span class="pre">(Ashley,</span> <span class="pre">David,</span> <span class="pre">Edward,</span> <span class="pre">Zoe)</span></code>, and their corresponding exam grades <code class="docutils literal notranslate"><span class="pre">(0.92,</span> <span class="pre">0.72,</span> <span class="pre">0.88,</span> <span class="pre">0.77)</span></code>, create a dictionary that maps: name <span class="math notranslate nohighlight">\(\rightarrow\)</span> grade.</p>
<p>Then, update Zoe’s grade to <code class="docutils literal notranslate"><span class="pre">.79</span></code>. Lastly, add a new student, Ryan, whose grade is 0.34.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">names</span> <span class="o">=</span> <span class="p">(</span><span class="s2">"Ashley"</span><span class="p">,</span> <span class="s2">"David"</span><span class="p">,</span> <span class="s2">"Edward"</span><span class="p">,</span> <span class="s2">"Zoe"</span><span class="p">)</span>
<span class="n">scores</span> <span class="o">=</span> <span class="p">(</span><span class="mf">0.92</span><span class="p">,</span> <span class="mf">0.72</span><span class="p">,</span> <span class="mf">0.88</span><span class="p">,</span> <span class="mf">0.77</span><span class="p">)</span>
</pre></div>
</div>
<p>Here is a basic, but verbose solution. It is too long and its logic is complicated by the use of <code class="docutils literal notranslate"><span class="pre">index</span></code>.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># basic solution for creating `grades`</span>
<span class="n">grades</span> <span class="o">=</span> <span class="p">{}</span>
<span class="k">for</span> <span class="n">index</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">names</span><span class="p">)):</span>
<span class="n">name</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">index</span><span class="p">]</span>
<span class="n">value</span> <span class="o">=</span> <span class="n">scores</span><span class="p">[</span><span class="n">index</span><span class="p">]</span>
<span class="n">grades</span><span class="p">[</span><span class="n">name</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>
</pre></div>
</div>
<p>You should make use of the function <a class="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Itertools.html#zip">zip</a> to pair the names and scores together in an iterable, and create the dictionary using a comprehension expression.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># much better solution for creating `grades`</span>
<span class="n">grades</span> <span class="o">=</span> <span class="p">{</span><span class="n">student</span><span class="p">:</span><span class="n">value</span> <span class="k">for</span> <span class="n">student</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">names</span><span class="p">,</span> <span class="n">scores</span><span class="p">)}</span>
<span class="c1"># updating Zoe's grade</span>
<span class="n">grades</span><span class="p">[</span><span class="s2">"Zoe"</span><span class="p">]</span> <span class="o">=</span> <span class="mf">0.79</span>
<span class="c1"># adding Ryan's grade</span>
<span class="n">grades</span><span class="p">[</span><span class="s2">"Ryan"</span><span class="p">]</span> <span class="o">=</span> <span class="mf">0.34</span>
</pre></div>
</div>
<p><strong>Inverting a Dictionary: Solution</strong></p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># simple solution: using a for-loop</span>
<span class="n">x</span> <span class="o">=</span> <span class="p">{</span><span class="s1">'k1'</span><span class="p">:</span> <span class="s1">'v1'</span><span class="p">,</span> <span class="s1">'k2'</span><span class="p">:</span> <span class="s1">'v2'</span><span class="p">,</span> <span class="s1">'k3'</span><span class="p">:</span> <span class="s1">'v3'</span><span class="p">}</span>
<span class="n">inverted_x</span> <span class="o">=</span> <span class="p">{}</span>
<span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">x</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
<span class="n">inverted_x</span><span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="o">=</span> <span class="n">key</span>
</pre></div>
</div>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># better solution: using a dictionary-comprehension</span>
<span class="n">inverted_x</span> <span class="o">=</span> <span class="p">{</span><span class="n">value</span><span class="p">:</span><span class="n">key</span> <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">x</span><span class="o">.</span><span class="n">items</span><span class="p">()}</span>
</pre></div>
</div>
<p><strong>Inspecting a Dictionary: Solution</strong></p>
<p>Assume we are working with a dictionary whose values are all <em>unique</em> numbers. Write a function that returns the key that maps to the <em>largest</em> value in the dictionary.</p>
<p>The solution that you should be able to arrive at is:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># solution</span>
<span class="k">def</span> <span class="nf">max_key</span><span class="p">(</span><span class="n">x</span><span class="p">):</span>
<span class="n">max_val</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">x</span><span class="o">.</span><span class="n">values</span><span class="p">())</span>
<span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">x</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
<span class="k">if</span> <span class="n">value</span> <span class="o">==</span> <span class="n">max_val</span><span class="p">:</span>
<span class="k">return</span> <span class="n">key</span>
</pre></div>
</div>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">max_key</span><span class="p">({</span><span class="s1">'a'</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">:</span> <span class="mi">2</span><span class="p">,</span> <span class="s1">'c'</span><span class="p">:</span> <span class="mi">200</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">:</span> <span class="mi">0</span><span class="p">})</span>
<span class="go">'c'</span>
</pre></div>
</div>
<p>The downside of this is that it iterates over <code class="docutils literal notranslate"><span class="pre">x</span></code> twice: once via <code class="docutils literal notranslate"><span class="pre">max</span></code> and once via the for-loop. The optimal solution for this only involves a single iteration, however it requires advanced concepts that are beyond the scope of the material presented here. We include the ideal solution for posterity:</p>
<p>You can provide the <code class="docutils literal notranslate"><span class="pre">max</span></code> function with “key” argument, which accepts the function that should be used to evaluate the “value” for each iteration, which is used to discern the max element. Here, we pass it the built-in dictionary-function <a class="reference external" href="https://docs.python.org/3/library/stdtypes.html#dict.get">get</a>, which takes in a dictionary’s key as an argument, and returns the corresponding value from the mapping. Thus <code class="docutils literal notranslate"><span class="pre">max</span></code> will iterate over each key of <code class="docutils literal notranslate"><span class="pre">x</span></code>, and discern the maximum value by
comparing the value returned by each <code class="docutils literal notranslate"><span class="pre">x.get(key)</span></code> (which is effectively the same as <code class="docutils literal notranslate"><span class="pre">x[key]</span></code>).</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># optimal solution (for the sake of completeness)</span>
<span class="k">def</span> <span class="nf">max_key_optimal</span><span class="p">(</span><span class="n">x</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">max</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="n">x</span><span class="o">.</span><span class="n">get</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">max_key_optimal</span><span class="p">({</span><span class="s1">'a'</span><span class="p">:</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">:</span> <span class="mi">30</span><span class="p">,</span> <span class="s1">'c'</span><span class="p">:</span> <span class="mi">10</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">:</span> <span class="mi">500</span><span class="p">})</span>
<span class="go">'d'</span>
</pre></div>
</div>
<p>You can read more about this <code class="docutils literal notranslate"><span class="pre">key</span></code> parameter <a class="reference external" href="https://docs.python.org/3/howto/sorting.html#key-functions">here</a>.</p>
<p>Next, generalize your solution for a dictionary whose values are not necessarily unique. Return a tuple of the keys that map to that max value.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">get_maxes</span><span class="p">(</span><span class="n">dictionary</span><span class="p">):</span>
<span class="n">max_val</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">dictionary</span><span class="o">.</span><span class="n">values</span><span class="p">())</span>
<span class="k">return</span> <span class="nb">tuple</span><span class="p">(</span><span class="n">k</span> <span class="k">for</span> <span class="n">k</span><span class="p">,</span><span class="n">v</span> <span class="ow">in</span> <span class="n">dictionary</span><span class="o">.</span><span class="n">items</span><span class="p">()</span> <span class="k">if</span> <span class="n">v</span> <span class="o">==</span> <span class="n">max_val</span><span class="p">)</span>
<span class="o">>>></span> <span class="n">get_maxes</span><span class="p">(</span><span class="nb">dict</span><span class="p">(</span><span class="n">a</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">b</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">c</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">d</span><span class="o">=</span><span class="mi">1</span><span class="p">))</span>
<span class="p">(</span><span class="s1">'b'</span><span class="p">,</span> <span class="s1">'c'</span><span class="p">)</span>
</pre></div>
</div>
</div>
</div>
</div>
</div>
<footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer">
<a href="DataStructures.html" class="btn btn-neutral float-left" title="Data Structures (Part I): Introduction" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<a href="DataStructures_III_Sets_and_More.html" class="btn btn-neutral float-right" title="Data Structures (Part III): Sets & the Collections Module" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<div role="contentinfo">
<p>© Copyright 2021, Ryan Soklaski.</p>
</div>
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a
<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>