+- Sick Gaming (https://www.sickgaming.net)
+-- Forum: Programming (https://www.sickgaming.net/forum-76.html)
+--- Forum: Python (https://www.sickgaming.net/forum-83.html)
+--- Thread: [Tut] Python List Length – What’s the Runtime Complexity of len()? (/thread-94433.html)
[Tut] Python List Length – What’s the Runtime Complexity of len()? - xSicKxBot - 04-07-2020
Python List Length – What’s the Runtime Complexity of len()?
<div><p><strong>The runtime complexity of the <code>len()</code> function on your Python list is O(1). It takes constant runtime no matter how many elements are in the list. Why? Because the list object maintains an integer counter that increases and decreases as you add and remove list elements. Looking up the value of this counter takes constant time.</strong></p>
<p>Python list objects keep track of their own length. When you call the function <code>len(...)</code> on a list object, here’s what happens (roughly):</p>
<ul>
<li>The Python virtual machine looks up the <code>len(...)</code> function in a dictionary to find the associated implementation.</li>
<li>You pass a list object as an argument to the <code>len()</code> function so the Python virtual machine checks the <code>__len__</code> method of the list object. </li>
<li>The method is implemented in C++ and it’s just a counter that’s increased each time you add an element to the list and decreased if you remove an element from the list. For example, say, the variable <code>length</code> stores the current length of the list. The method then returns the value <code>self.length</code>.</li>
<li>Done.</li>
</ul>
<p>Here’s a snippet of the <a rel="noreferrer noopener" href="https://github.com/python/cpython/blob/master/Objects/listobject.c" target="_blank">C++ implementation</a> of the list data structure:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="cpp" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{ PyObject **items; size_t new_allocated, num_allocated_bytes; Py_ssize_t allocated = self->allocated; // some implementation details Py_SET_SIZE(self, newsize); self->allocated = new_allocated; return 0;
}</pre>
<h2>What’s the Runtime Complexity of Other Python List Methods?</h2>
<p>Here’s the table based on the <a rel="noreferrer noopener" href="https://wiki.python.org/moin/TimeComplexity" target="_blank">official Python wiki</a>: </p>
<figure class="wp-block-table is-style-stripes">
<table>
<tbody>
<tr>
<td><strong>Operation</strong></td>
<td><strong>Average Case</strong></td>
<td><strong><a href="http://en.wikipedia.org/wiki/Amortized_analysis" target="_blank" rel="noreferrer noopener">Amortized Worst Case</a></strong></td>
</tr>
<tr>
<td><a rel="noreferrer noopener" href="https://blog.finxter.com/python-list-copy/" target="_blank">copy()</a></td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-append/" target="_blank" rel="noreferrer noopener">append()</a></td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-pop/" target="_blank" rel="noreferrer noopener">pop()</a></td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-pop/" target="_blank" rel="noreferrer noopener">pop(i)</a></td>
<td>O(k)</td>
<td>O(k)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-insert-method/">insert()</a></td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td><a rel="noreferrer noopener" href="https://blog.finxter.com/python-lists/" target="_blank">l</a><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">i</a><a rel="noreferrer noopener" href="https://blog.finxter.com/python-lists/" target="_blank">st[i]</a></td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr>
<td><a rel="noreferrer noopener" href="https://blog.finxter.com/python-lists/" target="_blank">list[i] = x</a></td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-remove/" target="_blank" rel="noreferrer noopener">remove(x)</a></td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">for i in list</a></td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/introduction-to-slicing-in-python/" target="_blank" rel="noreferrer noopener">list[i:j]</a></td>
<td>O(k)</td>
<td>O(k)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-methods/" target="_blank" rel="noreferrer noopener">del list[i:j]</a></td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-slice-assignment/" target="_blank" rel="noreferrer noopener">list[i:j] = y</a></td>
<td>O(k+n)</td>
<td>O(k+n)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-extend/" target="_blank" rel="noreferrer noopener">extend()</a></td>
<td>O(k)</td>
<td>O(k)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-sort/" target="_blank" rel="noreferrer noopener">sort()</a></td>
<td>O(n log n)</td>
<td>O(n log n)</td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/what-is-asterisk-in-python/" target="_blank" rel="noreferrer noopener">[…] * 10</a></td>
<td>O(nk)</td>
<td>O(nk)</td>
</tr>
<tr>
<td><code><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">x in lst</a></code></td>
<td>O(n)</td>
<td></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/how-to-get-the-key-with-the-maximum-value-in-a-dictionary/" target="_blank" rel="noreferrer noopener">min(lst), max(lst)</a></td>
<td>O(n)</td>
<td></td>
</tr>
<tr>
<td>len(lst)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
</tbody>
</table>
</figure>
<p>The Python list is implemented using a C++ array. This means that it’s generally slow to modify elements at the beginning of each list because all elements have to be shifted to the right. If you add an element to the end of a list, it’s usually fast. However, resizing an array can become slow from time to time if more memory has to be allocated for the array.</p>
<h2>Where to Go From Here</h2>
<p>If you keep struggling with those basic Python commands and you feel stuck in your learning progress, I’ve got something for you: <a rel="noreferrer noopener" href="https://www.amazon.com/gp/product/B07ZY7XMX8" target="_blank">Python One-Liners</a> (Amazon Link). </p>
<p>In the book, I’ll give you a thorough overview of critical computer science topics such as machine learning, regular expression, data science, NumPy, and Python basics—all in a single line of Python code!</p>
<p><a rel="noreferrer noopener" href="https://www.amazon.com/gp/product/B07ZY7XMX8" target="_blank">Get the book from Amazon!</a></p>
<p><strong>OFFICIAL BOOK DESCRIPTION:</strong> <em>Python One-Liners will show readers how to perform useful tasks with one line of Python code. Following a brief Python refresher, the book covers essential advanced topics like slicing, list comprehension, broadcasting, lambda functions, algorithms, regular expressions, neural networks, logistic regression and more. Each of the 50 book sections introduces a problem to solve, walks the reader through the skills necessary to solve that problem, then provides a concise one-liner Python solution with a detailed explanation.</em></p></p>
</div>
https://www.sickgaming.net/blog/2020/04/07/python-list-length-whats-the-runtime-complexity-of-len/