- Notifications
You must be signed in to change notification settings - Fork 54
/
Copy pathMergeMaxDicts.html
403 lines (375 loc) · 44 KB
/
MergeMaxDicts.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
<!DOCTYPE html>
<htmlclass="writer-html5" lang="en" >
<head>
<metacharset="utf-8" /><metacontent="Topic: Dictionary Merge Exercise, Difficulty: Easy, Category: Practice Problem" name="description" />
<metacontent="dictionary, merge, practice problem" name="keywords" />
<metaname="viewport" content="width=device-width, initial-scale=1.0" />
<title>Merging Two Dictionaries — Python Like You Mean It</title>
<linkrel="stylesheet" href="../../_static/pygments.css" type="text/css" />
<linkrel="stylesheet" href="../../_static/css/theme.css" type="text/css" />
<linkrel="stylesheet" href="../../_static/my_theme.css" type="text/css" />
<!--[if lt IE 9]>
<script src="../../_static/js/html5shiv.min.js"></script>
<![endif]-->
<scriptdata-url_root="../../" id="documentation_options" src="../../_static/documentation_options.js"></script>
<scriptsrc="../../_static/jquery.js"></script>
<scriptsrc="../../_static/underscore.js"></script>
<scriptsrc="../../_static/doctools.js"></script>
<scriptasync="async" src="https://www.googletagmanager.com/gtag/js?id=UA-115029372-1"></script>
<scriptsrc="../../_static/gtag.js"></script>
<scriptcrossorigin="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>
<scriptdefer="defer" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<scriptsrc="../../_static/js/theme.js"></script>
<linkrel="index" title="Index" href="../../genindex.html" />
<linkrel="search" title="Search" href="../../search.html" />
<linkrel="next" title="Within Margin Percentage" href="MarginPercentage.html" />
<linkrel="prev" title="Module 2: Problems" href="../../module_2_problems.html" />
</head>
<bodyclass="wy-body-for-nav">
<divclass="wy-grid-for-nav">
<navdata-toggle="wy-nav-shift" class="wy-nav-side">
<divclass="wy-side-scroll">
<divclass="wy-side-nav-search" >
<ahref="../../index.html" class="icon icon-home"> Python Like You Mean It
</a>
<divclass="version">
1.4
</div>
<divrole="search">
<formid="rtd-search-form" class="wy-form" action="../../search.html" method="get">
<inputtype="text" name="q" placeholder="Search docs" />
<inputtype="hidden" name="check_keywords" value="yes" />
<inputtype="hidden" name="area" value="default" />
</form>
</div>
</div><divclass="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<pclass="caption" role="heading"><spanclass="caption-text">Table of Contents:</span></p>
<ulclass="current">
<liclass="toctree-l1"><aclass="reference internal" href="../../intro.html">Python Like You Mean It</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="../../module_1.html">Module 1: Getting Started with Python</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="../../module_2.html">Module 2: The Essentials of Python</a></li>
<liclass="toctree-l1 current"><aclass="reference internal" href="../../module_2_problems.html">Module 2: Problems</a><ulclass="current">
<liclass="toctree-l2 current"><aclass="current reference internal" href="#">Merging Two Dictionaries</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#A-Simple,-Buggy-Solution">A Simple, Buggy Solution</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#A-Simple,-Correct-Solution">A Simple, Correct Solution</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#A-Minor-Optimization">A Minor Optimization</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#Extended-Problem:-Merging-Arbitrary-Numbers-of-Dictionaries">Extended Problem: Merging Arbitrary Numbers of Dictionaries</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#Generalized-Solution">Generalized Solution</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#Handling-Zero-Inputs">Handling Zero Inputs</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#Handling-One-Input">Handling One Input</a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#Extra-Challenges">Extra Challenges</a></li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="MarginPercentage.html">Within Margin Percentage</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="DifferenceFanout.html">Difference Fanout</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="EncodeAsString.html">Encode as String</a></li>
</ul>
</li>
<liclass="toctree-l1"><aclass="reference internal" href="../../module_3.html">Module 3: The Essentials of NumPy</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="../../module_3_problems.html">Module 3: Problems</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="../../module_4.html">Module 4: Object Oriented Programming</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="../../module_5.html">Module 5: Odds and Ends</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="../../changes.html">Changelog</a></li>
</ul>
</div>
</div>
</nav>
<sectiondata-toggle="wy-nav-shift" class="wy-nav-content-wrap"><navclass="wy-nav-top" aria-label="Mobile navigation menu" >
<idata-toggle="wy-nav-top" class="fa fa-bars"></i>
<ahref="../../index.html">Python Like You Mean It</a>
</nav>
<divclass="wy-nav-content">
<divclass="rst-content">
<divrole="navigation" aria-label="Page navigation">
<ulclass="wy-breadcrumbs">
<li><ahref="../../index.html" class="icon icon-home"></a> »</li>
<li><ahref="../../module_2_problems.html">Module 2: Problems</a> »</li>
<li>Merging Two Dictionaries</li>
<liclass="wy-breadcrumbs-aside">
<ahref="../../_sources/Module2_EssentialsOfPython/Problems/MergeMaxDicts.md.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<divrole="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<divitemprop="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>
<divclass="section" id="Merging-Two-Dictionaries">
<h1>Merging Two Dictionaries<aclass="headerlink" href="#Merging-Two-Dictionaries" title="Permalink to this headline"></a></h1>
<blockquote>
<div><p>Merge two <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/DataStructures_II_Dictionaries.html#Data-Structures-(Part-II):-Dictionaries">dictionaries</a> together such that the resulting dictionary always retain the <em>greater</em> value among mappings with common keys.</p>
</div></blockquote>
<p>Here’s an example:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="c1"># merging two dictionaries, retaining the greatest value among</span>
<spanclass="c1"># common keys</span>
<spanclass="o">>>></span><spanclass="n">dict1</span><spanclass="o">=</span><spanclass="p">{</span><spanclass="s1">'bananas'</span><spanclass="p">:</span><spanclass="mi">7</span><spanclass="p">,</span><spanclass="s1">'apples'</span><spanclass="p">:</span><spanclass="mi">3</span><spanclass="p">,</span><spanclass="s1">'pears'</span><spanclass="p">:</span><spanclass="mi">14</span><spanclass="p">}</span>
<spanclass="o">>>></span><spanclass="n">dict2</span><spanclass="o">=</span><spanclass="p">{</span><spanclass="s1">'bananas'</span><spanclass="p">:</span><spanclass="mi">3</span><spanclass="p">,</span><spanclass="s1">'apples'</span><spanclass="p">:</span><spanclass="mi">6</span><spanclass="p">,</span><spanclass="s1">'grapes'</span><spanclass="p">:</span><spanclass="mi">9</span><spanclass="p">}</span>
<spanclass="o">>>></span><spanclass="n">merge_max_mappings</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">,</span><spanclass="n">dict2</span><spanclass="p">)</span>
<spanclass="p">{</span><spanclass="s1">'bananas'</span><spanclass="p">:</span><spanclass="mi">7</span><spanclass="p">,</span><spanclass="s1">'apples'</span><spanclass="p">:</span><spanclass="mi">6</span><spanclass="p">,</span><spanclass="s1">'pears'</span><spanclass="p">:</span><spanclass="mi">14</span><spanclass="p">,</span><spanclass="s1">'grapes'</span><spanclass="p">:</span><spanclass="mi">9</span><spanclass="p">}</span>
</pre></div>
</div>
<p>Write a function that accepts two dictionaries and merges them in the fashion shown above. The <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/DataStructures_II_Dictionaries.html#What-Can-a-Dictionary-Store?">dictionaries’ keys need not be strings</a>, and the values should be any data type that can be ordered (e.g. can be compared using the inequality operators <codeclass="docutils literal notranslate"><spanclass="pre"><</span></code>, <codeclass="docutils literal notranslate"><spanclass="pre">></span></code>, etc.).</p>
<divclass="section" id="A-Simple,-Buggy-Solution">
<h2>A Simple, Buggy Solution<aclass="headerlink" href="#A-Simple,-Buggy-Solution" title="Permalink to this headline"></a></h2>
<p>Let’s begin by writing a straightforward but flawed solution to our problem. The following function will correctly merge its two input dictionaries and is generally well-written, however, something insidious is afoot… Can you identify the bad behavior that will result from this function?</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">buggy_merge_max_mappings</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">,</span><spanclass="n">dict2</span><spanclass="p">):</span>
<spanclass="c1"># create the output dictionary, which contains all</span>
<spanclass="c1"># the mappings from `dict1`</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="n">dict1</span>
<spanclass="c1"># populate `merged` with the mappings in dict2 if:</span>
<spanclass="c1"># - the key doesn't exist in `merged`</span>
<spanclass="c1"># - the value in dict2 is larger</span>
<spanclass="k">for</span><spanclass="n">key</span><spanclass="ow">in</span><spanclass="n">dict2</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="ow">or</span><spanclass="n">dict2</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]:</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">dict2</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span>
<spanclass="k">return</span><spanclass="n">merged</span>
</pre></div>
</div>
<p>Let’s first see what this function does right. Recall that <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/DataStructures_II_Dictionaries.html#Inspecting-a-Dictionary">iterating over a dictionary</a> will produce each of its keys one-by-one. Thus <codeclass="docutils literal notranslate"><spanclass="pre">for</span><spanclass="pre">key</span><spanclass="pre">in</span><spanclass="pre">dict2</span></code> loops over every key in <codeclass="docutils literal notranslate"><spanclass="pre">dict2</span></code>. We then set a key-value from <codeclass="docutils literal notranslate"><spanclass="pre">dict2</span></code> mapping in <codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code> if that key doesn’t exist in merged or if the value is larger than the one stored in existing mapping. Given that
<codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code> is initialized to have the same mappings as <codeclass="docutils literal notranslate"><spanclass="pre">dict1</span></code>, this is a correct algorithm for merging our two dictionaries based on max-value.</p>
<p>The problem with our function is that we inadvertently merge <codeclass="docutils literal notranslate"><spanclass="pre">dict2</span></code><em>into</em><codeclass="docutils literal notranslate"><spanclass="pre">dict1</span></code>, rather than merging the two dictionaries into a <em>new</em> dictionary. Recall that dictionaries are <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Variables_and_Assignment.html#Referencing-a-Mutable-Object-with-Multiple-Variables">mutable</a> objects and that the statement <codeclass="docutils literal notranslate"><spanclass="pre">merged</span><spanclass="pre">=</span><spanclass="pre">dict1</span></code> simply assigns a variable that references <codeclass="docutils literal notranslate"><spanclass="pre">dict1</span></code> rather than creating a new copy of the dictionary.
Thus calling this function will <em>mutate</em> (change) the state of <codeclass="docutils literal notranslate"><spanclass="pre">dict1</span></code>, as demonstrated here:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="gp">>>> </span><spanclass="n">exam_1</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">Alice</span><spanclass="o">=</span><spanclass="mi">99</span><spanclass="p">,</span><spanclass="n">Bob</span><spanclass="o">=</span><spanclass="mi">87</span><spanclass="p">,</span><spanclass="n">Cindy</span><spanclass="o">=</span><spanclass="mi">65</span><spanclass="p">)</span><spanclass="c1"># equivalent to {'Alice': 99, 'Bob': 87, 'Cindy': 65}</span>
<spanclass="gp">>>> </span><spanclass="n">exam_2</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">Alice</span><spanclass="o">=</span><spanclass="mi">77</span><spanclass="p">,</span><spanclass="n">Bob</span><spanclass="o">=</span><spanclass="mi">90</span><spanclass="p">,</span><spanclass="n">Cindy</span><spanclass="o">=</span><spanclass="mi">78</span><spanclass="p">)</span>
<spanclass="gp">>>> </span><spanclass="n">buggy_merge_max_mappings</span><spanclass="p">(</span><spanclass="n">exam_1</span><spanclass="p">,</span><spanclass="n">exam_2</span><spanclass="p">)</span>
<spanclass="go">{'Alice': 99, 'Bob': 90, 'Cindy': 78}</span>
</pre></div>
</div>
<p>See that the value of <codeclass="docutils literal notranslate"><spanclass="pre">exam_1</span></code> has changed, and that it matches the output of our function:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="gp">>>> </span><spanclass="n">exam_1</span>
<spanclass="go">{'Alice': 99, 'Bob': 90, 'Cindy': 78}</span>
</pre></div>
</div>
<p>To reiterate, this is because the statement <codeclass="docutils literal notranslate"><spanclass="pre">merged</span><spanclass="pre">=</span><spanclass="pre">dict1</span></code> found at the beginning of our function <em>merely creates a reference to</em><codeclass="docutils literal notranslate"><spanclass="pre">dict1</span></code>, not a copy of it. In the above example <codeclass="docutils literal notranslate"><spanclass="pre">exam_1</span></code> stored a class’ exam-1 scores for each student. After passing it to our function, it now stores the max score for each student across two exams!</p>
<p>While we are likely to have tested that our function properly merges dictionaries as we desire, we are less likely to test that it leaves its inputs unchanged. This is a valuable lesson to be l</p>
<divclass="admonition note">
<pclass="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong></p>
<ulclass="simple">
<li><p>Be mindful of <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Variables_and_Assignment.html#Mutable-&-Immutable-Types-of-Objects">object mutability</a> and take care never to unwittingly mutate an input variable or global scope variable within a function.</p></li>
<li><p>When testing a function, include a check that the function does not mutate its inputs.</p></li>
</ul>
</div>
</div>
<divclass="section" id="A-Simple,-Correct-Solution">
<h2>A Simple, Correct Solution<aclass="headerlink" href="#A-Simple,-Correct-Solution" title="Permalink to this headline"></a></h2>
<p>We can easily stomp the bug in the previous function; updating <codeclass="docutils literal notranslate"><spanclass="pre">merged</span><spanclass="pre">=</span><spanclass="pre">dict1</span></code> with either <codeclass="docutils literal notranslate"><spanclass="pre">merged</span><spanclass="pre">=</span><spanclass="pre">dict(dict1)</span></code> or <codeclass="docutils literal notranslate"><spanclass="pre">merged</span><spanclass="pre">=</span><spanclass="pre">dict1.copy()</span></code> will ensure that <codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code> references a <em>new</em> dictionary, which we are free to update:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">simple_merge_max_mappings</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">,</span><spanclass="n">dict2</span><spanclass="p">):</span>
<spanclass="sd">""" Merges two dictionaries based on the largest value in a given mapping.</span>
<spanclass="sd"> Parameters</span>
<spanclass="sd"> ----------</span>
<spanclass="sd"> dict1 : Dict[Any, Comparable]</span>
<spanclass="sd"> dict2 : Dict[Any, Comparable]</span>
<spanclass="sd"> Returns</span>
<spanclass="sd"> -------</span>
<spanclass="sd"> Dict[Any, Comparable]</span>
<spanclass="sd"> The merged dictionary</span>
<spanclass="sd"> """</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">)</span>
<spanclass="k">for</span><spanclass="n">key</span><spanclass="ow">in</span><spanclass="n">dict2</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="ow">or</span><spanclass="n">dict2</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]:</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">dict2</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span>
<spanclass="k">return</span><spanclass="n">merged</span>
</pre></div>
</div>
<p>Note the use of simple and descriptive variables (e.g. we use the variable name <codeclass="docutils literal notranslate"><spanclass="pre">key</span></code> when we iterate over the keys of a dictionary). This, along with a good docstring, makes our code easy to read, understand, and debug. Also note that our code is general: it makes no presumptions about the dictionaries’ keys - they need not be strings nor of any other particular type. Similarly, the only constraint on the dictionaries’ values is that they can be compared against one another. This is reflected
in the docstring of our function.</p>
<p>Consider the importance of the ordering of the conditional statement:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">if</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="ow">or</span><spanclass="n">dict2</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]:</span>
</pre></div>
</div>
<p>What is different if we flip the ordering of the terms? I.e.:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">if</span><spanclass="n">dict2</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="ow">or</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="p">:</span>
</pre></div>
</div>
<p>The problem with this flipped ordering is that the given key may not exist in <codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code> yet, thus <codeclass="docutils literal notranslate"><spanclass="pre">dict2[key]</span><spanclass="pre">></span><spanclass="pre">merged[key]</span></code> will raise a <codeclass="docutils literal notranslate"><spanclass="pre">KeyError</span></code>. Using the original ordering, such a case would cause <codeclass="docutils literal notranslate"><spanclass="pre">key</span><spanclass="pre">not</span><spanclass="pre">in</span><spanclass="pre">merged</span></code> to return <codeclass="docutils literal notranslate"><spanclass="pre">True</span></code>, and the overall expression will return <codeclass="docutils literal notranslate"><spanclass="pre">True</span></code> without evaluating the second part of the expression (convince yourself that <codeclass="docutils literal notranslate"><spanclass="pre">True</span><spanclass="pre">or</span><spanclass="pre"><whatever></span></code> will always return <codeclass="docutils literal notranslate"><spanclass="pre">True</span></code>).</p>
</div>
<divclass="section" id="A-Minor-Optimization">
<h2>A Minor Optimization<aclass="headerlink" href="#A-Minor-Optimization" title="Permalink to this headline"></a></h2>
<p>Supposing that your code makes heavy use of dictionary merging and that its performance is a bottleneck for the overall performance of your code, then there is a minor optimization that we can implement.</p>
<p>Consider a case of extreme imbalance in the sizes of our dictionaries; suppose <codeclass="docutils literal notranslate"><spanclass="pre">dict1</span></code> is contains one key while <codeclass="docutils literal notranslate"><spanclass="pre">dict2</span></code> contains 10,000. It would be preferable for our solution to manually iterate over the smaller of these two dictionaries. We can easily accommodate this in our function by choosing <codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code> to be the longer of the two dictionaries and iterating over the other dictionary:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">opt_merge_max_mappings</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">,</span><spanclass="n">dict2</span><spanclass="p">):</span>
<spanclass="sd">""" Merges two dictionaries based on the largest value in a given mapping.</span>
<spanclass="sd"> Parameters</span>
<spanclass="sd"> ----------</span>
<spanclass="sd"> dict1 : Dict[Any, Comparable]</span>
<spanclass="sd"> dict2 : Dict[Any, Comparable]</span>
<spanclass="sd"> Returns</span>
<spanclass="sd"> -------</span>
<spanclass="sd"> Dict[Any, Comparable]</span>
<spanclass="sd"> The merged dictionary</span>
<spanclass="sd"> """</span>
<spanclass="c1"># we will iterate over `other` to populate `merged`</span>
<spanclass="n">merged</span><spanclass="p">,</span><spanclass="n">other</span><spanclass="o">=</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">,</span><spanclass="n">dict2</span><spanclass="p">)</span><spanclass="k">if</span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">)</span><spanclass="o">></span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dict2</span><spanclass="p">)</span><spanclass="k">else</span><spanclass="p">(</span><spanclass="n">dict2</span><spanclass="p">,</span><spanclass="n">dict1</span><spanclass="p">)</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">merged</span><spanclass="p">)</span>
<spanclass="k">for</span><spanclass="n">key</span><spanclass="ow">in</span><spanclass="n">other</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="ow">or</span><spanclass="n">other</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]:</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">other</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span>
<spanclass="k">return</span><spanclass="n">merged</span>
</pre></div>
</div>
<p>Here, we make keen use of a <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/ConditionalStatements.html#Inline-if-else-statements">inline if-else statement</a> and <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Iterables.html#%E2%80%9CUnpacking%E2%80%9D-iterables">iterable unpacking</a>, which helps keep our code succinct despite the logic that we have added to it. See that</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="n">merged</span><spanclass="p">,</span><spanclass="n">other</span><spanclass="o">=</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">,</span><spanclass="n">dict2</span><spanclass="p">)</span><spanclass="k">if</span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">)</span><spanclass="o">></span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dict2</span><spanclass="p">)</span><spanclass="k">else</span><spanclass="p">(</span><spanclass="n">dict2</span><spanclass="p">,</span><spanclass="n">dict1</span><spanclass="p">)</span>
</pre></div>
</div>
<p>is equivalent to:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">if</span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dict1</span><spanclass="p">)</span><spanclass="o"><</span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dict2</span><spanclass="p">):</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="n">dict1</span>
<spanclass="n">other</span><spanclass="o">=</span><spanclass="n">dict2</span>
<spanclass="k">else</span><spanclass="p">:</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="n">dict2</span>
<spanclass="n">other</span><spanclass="o">=</span><spanclass="n">dict1</span>
</pre></div>
</div>
<p>We can use the <codeclass="docutils literal notranslate"><spanclass="pre">timeit</span></code><aclass="reference external" href="https://ipython.readthedocs.io/en/stable/interactive/magics.html">magic command</a> in either a Jupyter notebook or an IPython console to time our functions (Note: each <codeclass="docutils literal notranslate"><spanclass="pre">timeit</span></code> must be run in a separate notebook cell, and <codeclass="docutils literal notranslate"><spanclass="pre">%%timeit</span></code> must be the topmost command in the cell).</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="n">a</span><spanclass="o">=</span><spanclass="p">{}</span>
<spanclass="n">b</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="nb">zip</span><spanclass="p">(</span><spanclass="nb">range</span><spanclass="p">(</span><spanclass="mi">10000</span><spanclass="p">),</span><spanclass="nb">range</span><spanclass="p">(</span><spanclass="mi">10000</span><spanclass="p">)))</span><spanclass="c1"># {1 : 1, 2: 2, ..., 9999:9999}</span>
</pre></div>
</div>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span>%%timeit
simple_merge_max_mappings(a, b)
2.05 ms ± 90.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
</pre></div>
</div>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span>%%timeit
opt_merge_max_mappings(a, b)
455 µs ± 12.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
</pre></div>
</div>
<p>This is a relatively small speedup despite the rather stark example we cooked up.</p>
</div>
<divclass="section" id="Extended-Problem:-Merging-Arbitrary-Numbers-of-Dictionaries">
<h2>Extended Problem: Merging Arbitrary Numbers of Dictionaries<aclass="headerlink" href="#Extended-Problem:-Merging-Arbitrary-Numbers-of-Dictionaries" title="Permalink to this headline"></a></h2>
<p>There is no reason that our function should only be able to merge two dictionaries, it should be easy to accommodate an arbitrary number of inputs:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="gp">>>> </span><spanclass="n">a</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">a</span><spanclass="o">=</span><spanclass="mi">0</span><spanclass="p">,</span><spanclass="n">b</span><spanclass="o">=</span><spanclass="mi">100</span><spanclass="p">,</span><spanclass="n">c</span><spanclass="o">=</span><spanclass="mi">3</span><spanclass="p">)</span>
<spanclass="gp">>>> </span><spanclass="n">b</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">a</span><spanclass="o">=</span><spanclass="mi">10</span><spanclass="p">,</span><spanclass="n">b</span><spanclass="o">=</span><spanclass="mi">10</span><spanclass="p">)</span>
<spanclass="gp">>>> </span><spanclass="n">c</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">c</span><spanclass="o">=</span><spanclass="mi">50</span><spanclass="p">)</span>
<spanclass="gp">>>> </span><spanclass="n">d</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">(</span><spanclass="n">d</span><spanclass="o">=-</span><spanclass="mi">70</span><spanclass="p">)</span>
<spanclass="gp">>>> </span><spanclass="n">e</span><spanclass="o">=</span><spanclass="nb">dict</span><spanclass="p">()</span>
<spanclass="gp">>>> </span><spanclass="n">merge_max_mappings</span><spanclass="p">(</span><spanclass="n">a</span><spanclass="p">,</span><spanclass="n">b</span><spanclass="p">,</span><spanclass="n">c</span><spanclass="p">,</span><spanclass="n">d</span><spanclass="p">,</span><spanclass="n">e</span><spanclass="p">)</span>
<spanclass="go">{'a': 10, 'b': 100, 'c': 50, 'd': -70}</span>
</pre></div>
</div>
<p>Before you write your solution, consider the following: 1. How do you write a function signature so that it can handle an arbitrary number of input dictionaries? 2. How should your function handle zero inputs? How about one input?</p>
</div>
<divclass="section" id="Generalized-Solution">
<h2>Generalized Solution<aclass="headerlink" href="#Generalized-Solution" title="Permalink to this headline"></a></h2>
<p>Addressing point #1, we will want to use the <codeclass="docutils literal notranslate"><spanclass="pre">*args</span></code> syntax in our function signature so that <aclass="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Functions.html#Accommodating-an-Arbitrary-Number-of-Positional-Arguments">it can accommodate an arbitrary number of dictionaries</a>. Thus all of the dictionaries fed to our function will be packed into a tuple that can be accessed via <codeclass="docutils literal notranslate"><spanclass="pre">args</span></code> (or whatever variable name we use in our signature).</p>
<p>Regarding point #2, we can handle the case of receiving no inputs by simply returning an empty dictionary. We will also see that handling the case of a single input is more subtle than one might guess. This point will be discussed further once the solution is presented.</p>
<p>Our solution is to create an empty dictionary, <codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code>, and to simply iterate over each mapping of each input dictionary and perform our merging as we did above:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">merge_max_mappings</span><spanclass="p">(</span><spanclass="o">*</span><spanclass="n">dicts</span><spanclass="p">):</span>
<spanclass="sd">""" Merges an arbitrary number of dictionaries based on the</span>
<spanclass="sd"> maximum value in a given mapping.</span>
<spanclass="sd"> Parameters</span>
<spanclass="sd"> ----------</span>
<spanclass="sd"> dicts : Dict[Any, Comparable]</span>
<spanclass="sd"> Returns</span>
<spanclass="sd"> -------</span>
<spanclass="sd"> Dict[Any, Comparable]</span>
<spanclass="sd"> The merged dictionary</span>
<spanclass="sd"> """</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="p">{}</span>
<spanclass="k">for</span><spanclass="n">d</span><spanclass="ow">in</span><spanclass="n">dicts</span><spanclass="p">:</span><spanclass="c1"># `dicts` is a tuple storing the input dictionaries</span>
<spanclass="k">for</span><spanclass="n">key</span><spanclass="ow">in</span><spanclass="n">d</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="ow">or</span><spanclass="n">d</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]:</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">d</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span>
<spanclass="k">return</span><spanclass="n">merged</span>
</pre></div>
</div>
<divclass="section" id="Handling-Zero-Inputs">
<h3>Handling Zero Inputs<aclass="headerlink" href="#Handling-Zero-Inputs" title="Permalink to this headline"></a></h3>
<p>See that our function returns an empty dictionary if it is not passed any inputs, this is because <codeclass="docutils literal notranslate"><spanclass="pre">dicts</span></code> will be an empty tuple and thus our loop over it will immediately exit, returning an unpopulated <codeclass="docutils literal notranslate"><spanclass="pre">merged</span></code>:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="gp">>>> </span><spanclass="n">merge_max_mappings</span><spanclass="p">()</span>
<spanclass="go">{}</span>
</pre></div>
</div>
<p>While you may have thought to have returned <codeclass="docutils literal notranslate"><spanclass="pre">None</span></code> in the case of there being no dictionaries to merge, returning an empty dictionary is much better behavior as code downstream from our function will only need to accommodate one type of output. Additionally, our function’s docstring promises that it will return a dictionary and we should always abide by this contract.</p>
</div>
<divclass="section" id="Handling-One-Input">
<h3>Handling One Input<aclass="headerlink" href="#Handling-One-Input" title="Permalink to this headline"></a></h3>
<p>In the case that our function is passed a single dictionary, our function effectively makes a (shallow) copy of that dictionary and returns it. Suppose we tried to be clever and wrote our function to pass a single dictionary through; e.g.</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">bad_merge_max_mappings</span><spanclass="p">(</span><spanclass="o">*</span><spanclass="n">dicts</span><spanclass="p">):</span>
<spanclass="k">if</span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dicts</span><spanclass="p">)</span><spanclass="o">==</span><spanclass="mi">1</span><spanclass="p">:</span>
<spanclass="k">return</span><spanclass="n">dicts</span><spanclass="p">[</span><spanclass="mi">0</span><spanclass="p">]</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="p">{}</span>
<spanclass="k">for</span><spanclass="n">d</span><spanclass="ow">in</span><spanclass="n">dicts</span><spanclass="p">:</span>
<spanclass="k">for</span><spanclass="n">key</span><spanclass="ow">in</span><spanclass="n">d</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">key</span><spanclass="ow">not</span><spanclass="ow">in</span><spanclass="n">merged</span><spanclass="ow">or</span><spanclass="n">d</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]:</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">d</span><spanclass="p">[</span><spanclass="n">key</span><spanclass="p">]</span>
<spanclass="k">return</span><spanclass="n">merged</span>
</pre></div>
</div>
<p>What is wrong with this solution? The problem is similar to the one that we considered above; our function always returns a dictionary that is independent from its inputs, meaning that mutating the merged dictionary has no impact on any of the inputs dictionaries. This is no longer the case when we receive a single dictionary - here the “merged” dictionary is simply a reference to the input. Any subsequent mutation of the output dictionary will also mutate the input dictionary, and vice versa.
This unanticipated behavior could create very hard-to-find bugs in your code!</p>
<p>It is best to not try to handle specialized cases like this, when the general code behaves appropriately to begin with.</p>
</div>
</div>
<divclass="section" id="Extra-Challenges">
<h2>Extra Challenges<aclass="headerlink" href="#Extra-Challenges" title="Permalink to this headline"></a></h2>
<ulclass="simple">
<li><p>Write tests for your functions where the dictionary keys aren’t strings and the values aren’t numbers.</p></li>
<li><p>What if you wanted to merge values based on a criterion other than the maximum value? Try rewriting the function so that a comparison function can passed in as an argument. Remember that functions, once defined, are objects just like integers and strings - they can be passed as arguments into other functions.</p></li>
</ul>
<p>The following code is correct, but really bad:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">gross_merge_max_mappings</span><spanclass="p">(</span><spanclass="o">*</span><spanclass="n">dicts</span><spanclass="p">):</span>
<spanclass="sd">"""merges dicts"""</span>
<spanclass="n">merged</span><spanclass="o">=</span><spanclass="p">{}</span>
<spanclass="k">for</span><spanclass="n">i</span><spanclass="ow">in</span><spanclass="nb">range</span><spanclass="p">(</span><spanclass="nb">len</span><spanclass="p">(</span><spanclass="n">dicts</span><spanclass="p">)):</span>
<spanclass="k">for</span><spanclass="n">j</span><spanclass="ow">in</span><spanclass="n">dicts</span><spanclass="p">[</span><spanclass="n">i</span><spanclass="p">]:</span>
<spanclass="k">if</span><spanclass="ow">not</span><spanclass="p">(</span><spanclass="n">j</span><spanclass="ow">in</span><spanclass="nb">list</span><spanclass="p">(</span><spanclass="n">merged</span><spanclass="p">)):</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">j</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">dicts</span><spanclass="p">[</span><spanclass="n">i</span><spanclass="p">][</span><spanclass="n">j</span><spanclass="p">]</span>
<spanclass="k">elif</span><spanclass="n">dicts</span><spanclass="p">[</span><spanclass="n">i</span><spanclass="p">][</span><spanclass="n">j</span><spanclass="p">]</span><spanclass="o">></span><spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">j</span><spanclass="p">]:</span>
<spanclass="n">merged</span><spanclass="p">[</span><spanclass="n">j</span><spanclass="p">]</span><spanclass="o">=</span><spanclass="n">dicts</span><spanclass="p">[</span><spanclass="n">i</span><spanclass="p">][</span><spanclass="n">j</span><spanclass="p">]</span>
<spanclass="k">else</span><spanclass="p">:</span>
<spanclass="k">continue</span>
<spanclass="k">return</span><spanclass="n">merged</span>
</pre></div>
</div>
<p>Compare this code to the solution that we devised, and enumerate all of the stylistic mistakes that are made here. Appreciate how simple and readable our code is by comparison and make a promise to yourself that you will not write code like this.</p>
</div>
</div>
</div>
</div>
<footer><divclass="rst-footer-buttons" role="navigation" aria-label="Footer">
<ahref="../../module_2_problems.html" class="btn btn-neutral float-left" title="Module 2: Problems" accesskey="p" rel="prev"><spanclass="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<ahref="MarginPercentage.html" class="btn btn-neutral float-right" title="Within Margin Percentage" accesskey="n" rel="next">Next <spanclass="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<divrole="contentinfo">
<p>© Copyright 2021, Ryan Soklaski.</p>
</div>
Built with <ahref="https://www.sphinx-doc.org/">Sphinx</a> using a
<ahref="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <ahref="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function(){
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>
