- Notifications
You must be signed in to change notification settings - Fork 54
/
Copy pathDataStructures.html
343 lines (320 loc) · 27.8 KB
/
DataStructures.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
<!DOCTYPE html>
<htmlclass="writer-html5" lang="en" >
<head>
<metacharset="utf-8" /><metacontent="Topic: Data Structures, Difficulty: Medium, Category: Section" name="description" />
<metacontent="Big-O, complexity, efficiency, algorithm, interview preparation, list, tuple, sequence" name="keywords" />
<metaname="viewport" content="width=device-width, initial-scale=1.0" />
<title>Data Structures (Part I): Introduction — 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="Data Structures (Part II): Dictionaries" href="DataStructures_II_Dictionaries.html" />
<linkrel="prev" title="Scope" href="Scope.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 current"><aclass="reference internal" href="../module_2.html">Module 2: The Essentials of Python</a><ulclass="current">
<liclass="toctree-l2"><aclass="reference internal" href="Basic_Objects.html">Basic Object Types</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="SequenceTypes.html">Sequence Types</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Variables_and_Assignment.html">Variables & Assignment</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Introduction.html">Introducing Control Flow</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="ConditionalStatements.html">Conditional Statements</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="ForLoops.html">For-Loops and While-Loops</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Iterables.html">Iterables</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Generators_and_Comprehensions.html">Generators & Comprehension Expressions</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Itertools.html">Python’s “Itertools”</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Functions.html">Basics of Functions</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="Scope.html">Scope</a></li>
<liclass="toctree-l2 current"><aclass="current reference internal" href="#">Data Structures (Part I): Introduction</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#Describing-Algorithm-Complexity">Describing Algorithm Complexity</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#Sequential-Data-Structures:-Lists-and-Tuples">Sequential Data Structures: Lists and Tuples</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#List/Tuple-Complexities">List/Tuple Complexities</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#List-Complexities">List Complexities</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="DataStructures_II_Dictionaries.html">Data Structures (Part II): Dictionaries</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="DataStructures_III_Sets_and_More.html">Data Structures (Part III): Sets & the Collections Module</a></li>
</ul>
</li>
<liclass="toctree-l1"><aclass="reference internal" href="../module_2_problems.html">Module 2: Problems</a></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.html">Module 2: The Essentials of Python</a> »</li>
<li>Data Structures (Part I): Introduction</li>
<liclass="wy-breadcrumbs-aside">
<ahref="../_sources/Module2_EssentialsOfPython/DataStructures.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="Data-Structures-(Part-I):-Introduction">
<h1>Data Structures (Part I): Introduction<aclass="headerlink" href="#Data-Structures-(Part-I):-Introduction" title="Permalink to this headline"></a></h1>
<p>Here we survey Python’s built-in data structures. You should already be familiar with its lists and tuples, two data structures that facilitate working with sequential data. Two other critical, built-in data structures to be introduced are:</p>
<ulclass="simple">
<li><p>dictionary: a mapping from “keys” to “values”</p></li>
<li><p>sets: an unordered collection of items that can be used to perform set-algebraic operations (e.g. union and intersection)</p></li>
</ul>
<p>These data structures are not merely convenient constructs with some nice pre-written functionality; they also provide an interface to some optimized core utilities that have been written in C (or whatever language your Python interpreter is written in). For example, let’s write a function that checks if an item is contained within an iterable:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">is_in</span><spanclass="p">(</span><spanclass="n">seq</span><spanclass="p">,</span><spanclass="n">target</span><spanclass="p">):</span>
<spanclass="sd">""" Returns True if `target` is contained in `seq`."""</span>
<spanclass="k">for</span><spanclass="n">item</span><spanclass="ow">in</span><spanclass="n">seq</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">item</span><spanclass="o">==</span><spanclass="n">target</span><spanclass="p">:</span>
<spanclass="k">return</span><spanclass="kc">True</span>
<spanclass="k">return</span><spanclass="kc">False</span>
</pre></div>
</div>
<p>This function mirrors the C-algorithm that Python uses “under the hood” for checking for membership in a list (assuming you are using the CPython interpreter, which you almost definitely are). Because their function is implemented “at a lower level”, and need not be interpreted, we expect it to be faster than ours:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="gp">>>> </span><spanclass="n">x</span><spanclass="o">=</span><spanclass="p">[</span><spanclass="mi">1</span><spanclass="p">,</span><spanclass="s2">"moo"</span><spanclass="p">,</span><spanclass="mi">3</span><spanclass="p">,</span><spanclass="kc">True</span><spanclass="p">,</span><spanclass="mi">5</span><spanclass="p">,</span><spanclass="kc">None</span><spanclass="p">,</span><spanclass="mi">7</span><spanclass="p">,</span><spanclass="mi">8</span><spanclass="p">]</span>
<spanclass="gp">>>> </span><spanclass="n">is_in</span><spanclass="p">(</span><spanclass="n">x</span><spanclass="p">,</span><spanclass="o">-</span><spanclass="mi">1</span><spanclass="p">)</span><spanclass="c1"># takes 980 nanoseconds on my machine</span>
<spanclass="go">False</span>
<spanclass="gp">>>> </span><spanclass="o">-</span><spanclass="mi">1</span><spanclass="ow">in</span><spanclass="n">x</span><spanclass="c1"># takes 320 nanoseconds on my machine</span>
<spanclass="go">False</span>
</pre></div>
</div>
<p>Here, Python’s built-in sequence-membership function is 3x faster than using our own function. Furthermore, it will be important to know the advantages provided by each of the data structures. For instance, testing for membership in a set is even faster than is checking for membership in a list:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="c1"># test for membership in a list</span>
<spanclass="o">>>></span><spanclass="o">-</span><spanclass="mi">1</span><spanclass="ow">in</span><spanclass="p">[</span><spanclass="mi">1</span><spanclass="p">,</span><spanclass="s2">"moo"</span><spanclass="p">,</span><spanclass="mi">3</span><spanclass="p">,</span><spanclass="kc">True</span><spanclass="p">,</span><spanclass="mi">5</span><spanclass="p">,</span><spanclass="kc">None</span><spanclass="p">,</span><spanclass="mi">7</span><spanclass="p">,</span><spanclass="mi">8</span><spanclass="p">]</span><spanclass="c1"># takes 295 nanoseconds on my machine</span>
<spanclass="kc">False</span>
<spanclass="c1"># test for membership in a set</span>
<spanclass="o">>>></span><spanclass="o">-</span><spanclass="mi">1</span><spanclass="ow">in</span><spanclass="p">{</span><spanclass="mi">1</span><spanclass="p">,</span><spanclass="s2">"moo"</span><spanclass="p">,</span><spanclass="mi">3</span><spanclass="p">,</span><spanclass="kc">True</span><spanclass="p">,</span><spanclass="mi">5</span><spanclass="p">,</span><spanclass="kc">None</span><spanclass="p">,</span><spanclass="mi">7</span><spanclass="p">,</span><spanclass="mi">8</span><spanclass="p">}</span><spanclass="c1"># takes 65 nanoseconds on my machine</span>
<spanclass="kc">False</span>
</pre></div>
</div>
<p>We get a 4.5x speedup in our membership test just by using a set instead of a list, because the use of a set permits Python to use an entirely different algorithm for checking for membership. On our end, we merely replaced square brackets with curly braces! Hopefully this is sufficient motivation for learning about Python’s data structures and the algorithms that they utilize “under the hood”.</p>
<divclass="admonition note">
<pclass="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong>:</p>
<p>Python’s data structures come with a wealth of built-in functionality. Furthermore, understanding where each data structure “shines” is critical for writing efficient Python code. It is not necessary to memorize this information, but you should know that it exists and should be referenced frequently.</p>
</div>
<divclass="section" id="Describing-Algorithm-Complexity">
<h2>Describing Algorithm Complexity<aclass="headerlink" href="#Describing-Algorithm-Complexity" title="Permalink to this headline"></a></h2>
<p>In order to meaningfully compare the relative efficiency of algorithms, it is useful to summarize how algorithms “scale” with problem size. Two sorting algorithms may be comparable when sorting tens of items, and yet they may have wildly different performances when sorting thousands of items.</p>
<p>“Big-O” notation allows us to denote how an algorithm’s run time scales against problem size. Specifically, it signifies the “worst-case scenario” performance of an algorithm.</p>
<p>Let’s take, for instance, the <codeclass="docutils literal notranslate"><spanclass="pre">is_in</span></code> function that we wrote at the beginning of this section. In it, we iterate over a collection to check if it contains a specific item. The worst-case scenario for this algorithm is when the item is not a member of the collection at all - we have to iterate over the entire collection before we can conclude that it does not possess our item. So if we increase the collection to be <spanclass="math notranslate nohighlight">\(n\)</span> times larger in size, it should take <spanclass="math notranslate nohighlight">\(n\)</span> times as long to
iterate over it to determine that the item is not a member of the collection (again, dealing with the worst-case scenario). Because the worst-case scenario run time of <codeclass="docutils literal notranslate"><spanclass="pre">is_in</span></code> scales linearly with the size of the collection, <spanclass="math notranslate nohighlight">\(n\)</span>, we denote it’s run time complexity, using big-O notation, as <spanclass="math notranslate nohighlight">\(\mathcal{O}(n)\)</span>.</p>
<p>Now suppose we did a truly terrible job writing a membership algorithm, and performed a nested iteration over our collection:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="k">def</span><spanclass="nf">is_in_slow</span><spanclass="p">(</span><spanclass="n">seq</span><spanclass="p">,</span><spanclass="n">target</span><spanclass="p">):</span>
<spanclass="sd">""" Returns True if `target` is contained in `seq`."""</span>
<spanclass="k">for</span><spanclass="n">item</span><spanclass="ow">in</span><spanclass="n">seq</span><spanclass="p">:</span>
<spanclass="c1"># for each item in seq, iterate over seq in its entirety!</span>
<spanclass="k">for</span><spanclass="n">item2</span><spanclass="ow">in</span><spanclass="n">seq</span><spanclass="p">:</span>
<spanclass="k">if</span><spanclass="n">item</span><spanclass="o">==</span><spanclass="n">target</span><spanclass="p">:</span>
<spanclass="k">return</span><spanclass="kc">True</span>
<spanclass="k">return</span><spanclass="kc">False</span>
</pre></div>
</div>
<p>For each item in <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code> we iterate over <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code> again, thus in the worst-case scenario we need to iterate over <spanclass="math notranslate nohighlight">\(n\)</span> items, <spanclass="math notranslate nohighlight">\(n\)</span> separate times - a total of <spanclass="math notranslate nohighlight">\(n^{2}\)</span> “steps” in our algorithm. Thus we would say that <codeclass="docutils literal notranslate"><spanclass="pre">is_in_slow</span></code> is a <spanclass="math notranslate nohighlight">\(\mathcal{O}(n^{2})\)</span> algorithm: whereas doubling size of <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code> would increase the run time of our <spanclass="math notranslate nohighlight">\(\mathcal{O}(n)\)</span> algorithm by a factor of 2 (linear scaling), it would increase the run time of this <spanclass="math notranslate nohighlight">\(\mathcal{O}(n^{2})\)</span> algorithm
by 4 (quadratic scaling).</p>
<p>Here is a more formal description of this notation:</p>
<divclass="alert alert-block alert-info"><p><strong>“Big-O” Notation</strong>: Suppose that <spanclass="math notranslate nohighlight">\(n\)</span> denotes the “size” of the input to an algorithm, and that the mathematical expression <spanclass="math notranslate nohighlight">\(f(n)\)</span> describes how many computational steps the algorithm must take in its <em>worst-case scenario</em>, given that input. Then the algorithm’s run time complexity can be denoted using the <strong>“Big-O”</strong> notation: <spanclass="math notranslate nohighlight">\(\mathcal{O}(f(n))\)</span>.</p>
</div><p>A few important notes:</p>
<ulclass="simple">
<li><p>We only care about the “highest-order” term in <spanclass="math notranslate nohighlight">\(f(n)\)</span>. That is, <spanclass="math notranslate nohighlight">\(\mathcal{O}(n + n^{2})\)</span> should just be written as <spanclass="math notranslate nohighlight">\(\mathcal{O}(n^{2})\)</span>.</p></li>
<li><p>We never care about constant factors in our scaling. That is, even if an algorithm iterates over a sequence twice, its big-O complexity should be written as <spanclass="math notranslate nohighlight">\(\mathcal{O}(n)\)</span>, rather than <spanclass="math notranslate nohighlight">\(\mathcal{O}(2n)\)</span>.</p></li>
<li><p>An algorithm whose run time <em>does not depend on the size of its input</em> is a <spanclass="math notranslate nohighlight">\(\mathcal{O}(1)\)</span> algorithm.</p>
<ul>
<li><p>Example: a function that returns the second element from a list.</p></li>
</ul>
</li>
<li><p>There are more nuanced methods for analyzing algorithm complexity than solely considering the worst-case scenario, which can be overly pessimistic. Know that “big-O” notation can be used to convey mean performance, <aclass="reference external" href="https://en.wikipedia.org/wiki/Amortized_analysis">amortized</a> performance, and other types of analysis. Here, we will simply stick to the worst-case analysis.</p></li>
</ul>
<divclass="admonition note">
<pclass="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong>:</p>
<p>We will be using the “big-O” notation, <spanclass="math notranslate nohighlight">\(\mathcal{O}(f(n))\)</span>, to summarize the performance of the algorithms used by Python’s data structures.</p>
</div>
</div>
<divclass="section" id="Sequential-Data-Structures:-Lists-and-Tuples">
<h2>Sequential Data Structures: Lists and Tuples<aclass="headerlink" href="#Sequential-Data-Structures:-Lists-and-Tuples" title="Permalink to this headline"></a></h2>
<p>The “Sequence Types” section already introduced lists and tuples. Recall that both provide the same interface for accessing and summarizing the contents of a heterogeneous sequence of objects. However, a list can be mutated - updated, removed from, and added to - whereas a tuple cannot be mutated. Thus a list is <em>mutable</em>, whereas a tuple is <em>immutable</em>. Here you will find a summary of the algorithmic complexities of many of the built-in functions that work on sequential data structures.</p>
<p>For a complete rundown of the functions available to Python’s list, go <aclass="reference external" href="https://docs.python.org/3/tutorial/datastructures.html#more-on-lists">here</a>.</p>
<divclass="section" id="List/Tuple-Complexities">
<h3>List/Tuple Complexities<aclass="headerlink" href="#List/Tuple-Complexities" title="Permalink to this headline"></a></h3>
<p>Let <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code> represent a <strong>list or tuple</strong> of length <spanclass="math notranslate nohighlight">\(n\)</span>; <spanclass="math notranslate nohighlight">\(i\)</span> and <spanclass="math notranslate nohighlight">\(j\)</span> are integers drawn randomly from the interval <spanclass="math notranslate nohighlight">\([0, n-1]\)</span>; <spanclass="math notranslate nohighlight">\(k\)</span> is the length of any subsequence involved in the operation. The following is a summary of the complexities associated with various common operations using lists and tuple (according to their implementations in CPython):</p>
<tableclass="docutils align-default">
<colgroup>
<colstyle="width: 26%" />
<colstyle="width: 13%" />
<colstyle="width: 61%" />
</colgroup>
<thead>
<trclass="row-odd"><thclass="head"><p>Operation</p></th>
<thclass="head"><p>Complexity</p></th>
<thclass="head"><p>Explanation</p></th>
</tr>
</thead>
<tbody>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">len(seq)</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Return the number of items in the sequence</p></td>
</tr>
<trclass="row-odd"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">seq[i]</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Retrieve any item from the sequence</p></td>
</tr>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">seq[i:j]</span></code></p></td>
<td><p>O(k)</p></td>
<td><p>Retrieve a length-k slice from the sequence</p></td>
</tr>
<trclass="row-odd"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">for</span><spanclass="pre">item</span><spanclass="pre">in</span><spanclass="pre">seq..</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Iterate over the sequence</p></td>
</tr>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">obj</span><spanclass="pre">in</span><spanclass="pre">seq</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Check if <codeclass="docutils literal notranslate"><spanclass="pre">obj</span></code> is a member of <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code></p></td>
</tr>
<trclass="row-odd"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">seq.count(obj)</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Count the number of occurrences of <codeclass="docutils literal notranslate"><spanclass="pre">obj</span></code> in <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code></p></td>
</tr>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">seq.index(obj)</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Return position-index of <codeclass="docutils literal notranslate"><spanclass="pre">obj</span></code> in <codeclass="docutils literal notranslate"><spanclass="pre">seq</span></code></p></td>
</tr>
</tbody>
</table>
</div>
<divclass="section" id="List-Complexities">
<h3>List Complexities<aclass="headerlink" href="#List-Complexities" title="Permalink to this headline"></a></h3>
<p>Here we consider some mutating operations, like <codeclass="docutils literal notranslate"><spanclass="pre">append</span></code>, that are available to lists and not tuples. It is important to note that lists are implemented such that:</p>
<ulclass="simple">
<li><p>operations that add-to or remove-from the <em>end</em> of the list are <spanclass="math notranslate nohighlight">\(\mathcal{O}(1)\)</span></p></li>
<li><p>operations that add-to or remove-from the <em>beginning</em> of the list are <spanclass="math notranslate nohighlight">\(\mathcal{O}(n)\)</span></p></li>
</ul>
<p>Let <codeclass="docutils literal notranslate"><spanclass="pre">my_list</span></code> represent a list of length <spanclass="math notranslate nohighlight">\(n\)</span>, and <codeclass="docutils literal notranslate"><spanclass="pre">i</span></code> is an integer drawn randomly from the interval <spanclass="math notranslate nohighlight">\([0, n-1]\)</span>. The following is a summary of the complexities associated with various operations using a list (according to its implementation in CPython):</p>
<tableclass="docutils align-default">
<colgroup>
<colstyle="width: 28%" />
<colstyle="width: 13%" />
<colstyle="width: 59%" />
</colgroup>
<thead>
<trclass="row-odd"><thclass="head"><p>Operation</p></th>
<thclass="head"><p>Complexity</p></th>
<thclass="head"><p>Explanation</p></th>
</tr>
</thead>
<tbody>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">my_list[i]</span><spanclass="pre">=</span><spanclass="pre">obj</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Set the ith entry of the list with a new object.</p></td>
</tr>
<trclass="row-odd"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">my_list.append(obj)</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Append a new object to the end of the list.</p></td>
</tr>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">my_list.pop()</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Remove the object from the <em>end</em> of the list.</p></td>
</tr>
<trclass="row-odd"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">my_list.pop(0)</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Remove the object from the <em>beginning</em> of the list.</p></td>
</tr>
<trclass="row-even"><td><p><codeclass="docutils literal notranslate"><spanclass="pre">my_list.sort()</span></code></p></td>
<td><p>O(nlog(n))</p></td>
<td><p>Return a sorted version of the list.</p></td>
</tr>
</tbody>
</table>
</div>
</div>
</div>
</div>
</div>
<footer><divclass="rst-footer-buttons" role="navigation" aria-label="Footer">
<ahref="Scope.html" class="btn btn-neutral float-left" title="Scope" accesskey="p" rel="prev"><spanclass="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<ahref="DataStructures_II_Dictionaries.html" class="btn btn-neutral float-right" title="Data Structures (Part II): Dictionaries" 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>
