Create an account


Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[Tut] Python List Length – What’s the Runtime Complexity of len()?

#1
Python List Length – What’s the Runtime Complexity of len()?

The runtime complexity of the len() 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.

Python list objects keep track of their own length. When you call the function len(...) on a list object, here’s what happens (roughly):

  • The Python virtual machine looks up the len(...) function in a dictionary to find the associated implementation.
  • You pass a list object as an argument to the len() function so the Python virtual machine checks the __len__ method of the list object.
  • 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 length stores the current length of the list. The method then returns the value self.length.
  • Done.

Here’s a snippet of the C++ implementation of the list data structure:

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;
}

What’s the Runtime Complexity of Other Python List Methods?


Here’s the table based on the official Python wiki:


Operation Average Case Amortized Worst Case
copy() O(n) O(n)
append() O(1) O(1)
pop() O(1) O(1)
pop(i) O(k) O(k)
insert() O(n) O(n)
list[i] O(1) O(1)
list[i] = x O(1) O(1)
remove(x) O(n) O(n)
for i in list O(n) O(n)
list[i:j] O(k) O(k)
del list[i:j] O(n) O(n)
list[i:j] = y O(k+n) O(k+n)
extend() O(k) O(k)
sort() O(n log n) O(n log n)
[…] * 10 O(nk) O(nk)
x in lst O(n)
min(lst), max(lst) O(n)
len(lst) O(1) O(1)

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.

Where to Go From Here


If you keep struggling with those basic Python commands and you feel stuck in your learning progress, I’ve got something for you: Python One-Liners (Amazon Link).

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!

Get the book from Amazon!

OFFICIAL BOOK DESCRIPTION: 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.



https://www.sickgaming.net/blog/2020/04/...ty-of-len/
Reply



Possibly Related Threads…
Thread Author Replies Views Last Post
  [Tut] How to Install PIL/Pillow in Python? A Helpful Illustrated Guide xSicKxBot 0 5 Yesterday, 12:00 AM
Last Post: xSicKxBot
  [Tut] How to Read a File Line-By-Line and Store Into a List? xSicKxBot 0 5 10-24-2020, 06:12 PM
Last Post: xSicKxBot
  [Tut] How To Kill A Thread In Python? xSicKxBot 0 8 10-24-2020, 05:40 AM
Last Post: xSicKxBot
  [Tut] Python’s NameError: name ‘xxx’ is not defined — How to Fix This Stupid Bug? xSicKxBot 0 16 10-16-2020, 10:30 PM
Last Post: xSicKxBot
  [Tut] Python IndentationError: unexpected indent (How to Fix This Stupid Bug) xSicKxBot 0 20 10-10-2020, 08:24 PM
Last Post: xSicKxBot
  [Tut] Yield Keyword in Python – A Simple Illustrated Guide xSicKxBot 0 21 10-09-2020, 06:13 PM
Last Post: xSicKxBot
  [Tut] Python Reverse List with Slicing — An Illustrated Guide xSicKxBot 0 39 10-02-2020, 04:24 AM
Last Post: xSicKxBot
  [Tut] How to Remove Duplicates From a Python List While Preserving Order? xSicKxBot 0 37 10-01-2020, 02:21 AM
Last Post: xSicKxBot
  [Tut] How To Update A Key In A Dictionary In Python If The Key Doesn’t Exist? xSicKxBot 0 42 09-29-2020, 09:02 PM
Last Post: xSicKxBot
  [Tut] How to Get the Last Element of a Python List? xSicKxBot 0 43 09-28-2020, 02:36 AM
Last Post: xSicKxBot

Forum Jump:

Become a Patron!
[-]
Upcoming Events

[-]
Latest Threads
(Indie Deal) Tropico 6, Assassin's Creed...
Last Post: xSicKxBot
Today 04:41 PM
» Replies: 0
» Views: 3
gRPC performance improvements in .NET 5
Last Post: xSicKxBot
Today 04:40 PM
» Replies: 0
» Views: 2
News - Season of the Hunt
Last Post: xSicKxBot
Today 04:40 PM
» Replies: 0
» Views: 2
News - Rumour: Hyrule Warriors: Age Of C...
Last Post: xSicKxBot
Today 04:39 PM
» Replies: 0
» Views: 2
News - It’s Been Three Years Since We Fi...
Last Post: xSicKxBot
Today 04:39 PM
» Replies: 0
» Views: 2
Xbox Wire - This Week on Xbox: October 1...
Last Post: xSicKxBot
Today 04:39 PM
» Replies: 0
» Views: 2
News - Master your grasp of player psych...
Last Post: xSicKxBot
Today 04:38 PM
» Replies: 0
» Views: 2
News - PlayStation’s new (web) store, ge...
Last Post: xSicKxBot
Today 04:38 PM
» Replies: 0
» Views: 2
News - The Rapid Blaster Deco Is Firing ...
Last Post: Derrickcott
Today 09:53 AM
» Replies: 2
» Views: 806
Mobile - Crash Bandicoot: On the Run som...
Last Post: xSicKxBot
Today 09:46 AM
» Replies: 0
» Views: 2

[-]
Twitter

[-]
Sponsored
Get the Deal of the Week at RefurBees.com

Copyright © SickGaming.net 2012-2020