Do you want to convert a Python set to a list? Use the list(...) constructor and pass the set object as an argument. For example, to convert a set of strings friends into a list, use the code expression list(friends).
Here’s an example code snippet that converts the set to a list using the list(...) constructor:
# Create the set of strings
friends = {'Alice', 'Ann', 'Bob'} # Convert the set to a list
l = list(friends) # Print both
print(friends)
print(l) '''
{'Ann', 'Alice', 'Bob'}
['Alice', 'Ann', 'Bob'] '''
Try it in our interactive Python shell:
Exercise: Add more elements to the set. Does the list always have the same order as the set?
Python Set to List Order
A set is defined as an unordered collection of unique elements. The keyword is “unordered” here. Python does not guarantee any particular order of the elements in the resulting list. If you convert a set to a list, the elements can have an arbitrary order.
Python Set to List Keep Order
But what if you want to preserve the order when converting a set to a list (and, maybe, back)?
Create a dictionary from the elements in the list to remove all duplicates and convert the dictionary back to a list. This preserves the order of the original list elements.
Convert the list to a dictionary with dict.fromkeys(lst).
Convert the dictionary into a list with list(dict).
Each list element becomes a new key to the dictionary. For example, the list [1, 2, 3] becomes the dictionary {1:None, 2:None, 3:None}. All elements that occur multiple times will be assigned to the same key. Thus, the dictionary contains only unique keys—there cannot be multiple equal keys.
As dictionary values, you take dummy values (per default).
Then, you convert the dictionary back to a list, throwing away the dummy values.
Example: Convert set {0, 9, 8, 3} to the sorted list [0, 3, 8, 9].
Solution: Use the sorted(...) method that creates a new list from any iterable you pass as an argument.
Code: Let’s have a look at the source code that solves the problem!
s = {0, 9, 8, 3}
l = sorted(s)
print(l)
# [0, 3, 8, 9]
Exercise: Can you modify the code so that the elements are sorted in descending order?
Python Set to List Unpacking
An alternative method to convert a set to a list is unpacking with the asterisk operator *. You can simply unpack all elements in set s into an empty list by using the asterisk as a prefix within an empty list like this [*s]. It’s a fast and Pythonic way of converting a set to a list. And it has the advantage that you can also convert multiple sets into a single list like this: [*s1, *s2, ..., *sn].
Exercise: Play with the following code unpacking a fourth set into a new list l4.
Python Set to List Complexity
The time complexity of converting a set to a list is linear in the number of list elements. So, if the set has n elements, the asymptotic complexity is O(n). The reason is that you need to iterate over each element in the set which is O(n), and append this element to the list which is O(1). Together the complexity is O(n) * O(1) = O(n * 1) = O(n).
Here’s the pseudo-code implementation of the set to list conversion method:
def set_to_list(s): l = [] # Repeat n times --> O(n) for x in s: # Append element to list --> O(1) l.append(x) return s friends = {'Alice', 'Bob', 'Ann', 'Liz', 'Alice'}
l = set_to_list(friends)
print(l)
# {'Alice', 'Liz', 'Ann', 'Bob'}
Need help understanding this code snippet? Try visualizing it in your browser—just click “Next” to see what the code does in memory:
Python Add Set to List
Problem: Given a list l and a set s. Add all elements in s to list l.
Example: Given is list ['Alice', 'Bob', 'Ann'] and set {42, 21}. You want to get the resulting list ['Alice', 'Bob', 'Ann', 42, 21].
Solution: Use the list.extend(iterable) method to add all elements in the iterable to the list.
Code: The following code accomplishes this.
l = ['Alice', 'Bob', 'Ann']
s = {42, 21}
l.extend(s)
print(l)
# ['Alice', 'Bob', 'Ann', 42, 21]
Sometimes you can see the following seemingly strange behavior (e.g., here):
s = set([1, 2, 3])
l = list(s)
The output may give you the following cryptic error message:
TypeError: 'set' object is not callable
The reason is—in all likelihood—that you overwrote the name set in your namespace. This happens if you assign a value to a variable called ‘set’. Python will assume that set is a variable—and tells you that you cannot call variables.
Here’s code that will cause this issue:
set = {1, 2}
lst = [1, 2, 3]
s = set(lst) '''
Traceback (most recent call last): File "C:\Users\xcent\Desktop\code.py", line 3, in <module> s = set(lst)
TypeError: 'set' object is not callable '''
You can fix it by using another variable name so that the built-in function set() is not overshadowed:
s0 = {1, 2}
lst = [1, 2, 3]
s = set(lst)
Now, no such error is thrown because the set name correctly points to the Python built-in constructor function.
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
Do you have a list but you want to convert it to a Python set? No problem! Use the set(...) constructor and pass the list object as an argument. For example, if you have a list of strings friends, you can convert it to a set using the call set(friends).
Exercise: Add another string 'Alice' to the list friends and see the resulting set. How many elements do the list and the set have?
Python List to Set Time Complexity
The time complexity of converting a list to a set is linear in the number of list elements. So, if the set has n elements, the asymptotic complexity is O(n). The reason is that you need to iterate over each element in the list which is O(n), and add this element to the set which is O(1). Together the complexity is O(n) * O(1) = O(n * 1) = O(n).
Here’s the pseudo-code implementation of the list to set conversion method:
def list_to_set(l): s = set() # Repeat n times --> O(n) for x in l: # Add element to set --> O(1) s.add(x) return s friends = ['Alice', 'Bob', 'Ann', 'Liz', 'Alice']
s = list_to_set(friends)
print(s)
# {'Ann', 'Alice', 'Bob', 'Liz'}
Need help understanding this code snippet? Try visualizing it in your browser—just click “Next” to see what the code does in memory:
Collection: A set is a collection of elements like a list or a tuple. The collection consists of either primitive elements (e.g. integers, floats, strings), or complex elements (e.g. objects, tuples). However, in a set all data elements must be hashable because it heavily relies on the hash function to implement the specification.
Unordered: Unlike lists, sets are unordered because there is no fixed order of the elements. In other words, regardless of the order you put stuff in the set, you can never be sure in which order the set stores these elements.
Unique: All elements in the set are unique. Each pair of values (x,y) in the set produces a different pair of hash values (hash(x)!=hash(y)). Hence, each pair of elements x and y in the set are different.
Thus, you can remove all duplicates from a list x by converting it into a set and back into a list using the command list(set(x)). However, the ordering information may be lost in the process (as a set is, by definition, unordered).
This way, the resulting list doesn’t have any duplicates—but it also has lost the order of elements: strings 'Liz' and 'Ann' switched their order after conversion. This may be different on your computer!
Python List to Set to List: list(set(x))
By converting a list x to a set and back to a list with the nested constructor expression list(set(x)), you achieve two things:
You remove all duplicates from the original list x.
You lose all ordering information. The resulting list may (or may not) have a complete new ordering of the remaining elements.
There’s no way out: the set data structure is more efficient than the list data structure only because it’s less powerful.
It’s like compressing an image: by removing information from the original image, the new image needs less resources on your computer at the cost of having a lower quality. If you convert the lossy-compressed image (or the set for that matter) back into the original data structure, it doesn’t look the same anymore.
This highlights an important trade-off in programming: always choose the right data structure for the particular problem at hand.
Python List to Set Preserve Order
But what if you want to preserve the order when converting a list to a set (and, maybe, back)? (You’d only do this to remove duplicates).
Efficient Method: A shorter and more concise way is to create a dictionary out of the elements in the list to remove all duplicates and convert the dictionary back to a list. This preserves the order of the original list elements.
Convert the list to a dictionary with dict.fromkeys(lst).
Convert the dictionary into a list with list(dict).
Each list element becomes a new key to the dictionary. For example, the list [1, 2, 3] becomes the dictionary {1:None, 2:None, 3:None}. All elements that occur multiple times will be assigned to the same key. Thus, the dictionary contains only unique keys—there cannot be multiple equal keys.
As dictionary values, you take dummy values (per default).
Then, you convert the dictionary back to a list, throwing away the dummy values.
The result is an error message unhashable type: 'list'.
'''
Traceback (most recent call last): File "C:\Users\xcent\Desktop\code.py", line 6, in <module> s = set(users)
TypeError: unhashable type: 'list' '''
Why are lists unhashable?
Because they are mutable: you can change a list by appending or removing elements. If you change the list data type, the hash value changes (it is calculated based on the content of the list). This directly violates the definition that a “hash value […] never changes during its lifetime” (see here).
Key takeaway: mutable data types are not hashable. Therefore, you cannot use them in sets.
So, how to solve it? Simply convert the inner lists into an immutable collection type such as a tuple:
Now, the result is a set of tuple elements. As tuples are immutable, the hash value will never change and you can create a set out of them.
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
Problem: Given a dictionary and a filter condition. How to filter a dictionary by …
… key so that only those (key, value) pairs in the dictionary remain where the key satisfies the condition?
… value so that only those (key, value) pairs remain where the value satisfies the condition?
In this tutorial, you’ll learn four methods and how they compare against each other. It’s loosely based on this tutorial but extends it by many additional examples and code explanations.
If you’re too busy to read this tutorial, here’s the spoiler:
Method 4 — Dictionary comprehension {k:v for (k,v) in dict.items() if condition} is the most Pythonic and fastest way to filter a dictionary in Python.
However, by reading this short 8-minute tutorial, you’re going to learn a lot about the nuances of writing Pythonic code. So keep reading!
Method 1: Simple Iteration to Filter Dictionary
You should always start with the simplest method to solve a problem (see Occam’s razor) because premature optimization is the root of all evil!
So let’s have a look at the straightforward loop iteration method to filter a dictionary.
You want to keep those (key, value) pairs where key meets a certain condition (such as key%2 == 1).
newDict = dict() # Iterate over all (k,v) pairs in names
for key, value in names.items(): # Is condition satisfied? if key%2 == 1: newDict[key] = value
Only the (key, value) pairs where the key is an odd integer remain in the filtered dictionary newDict.
But what if you want to filter the dictionary by a condition on the values?
Filter Python Dictionary By Value (Simple Loop)
To filter by value, you only need to replace one line in the previous code snippet: instead of writing if key%2 == 1: ..., you use the value to determine whether to add a certain (key, value) pair: if len(value)<5: ....
newDict = dict() # Iterate over all (k,v) pairs in names
for key, value in names.items(): # Is condition satisfied? if len(value)<5: newDict[key] = value print(newDict)
# {2: 'Bob', 3: 'Carl', 4: 'Ann', 5: 'Liz'}
Only the dictionary (key, value) pairs remain in the filtered dictionary newDict where the length of the name string value is less than five characters.
Try It Yourself in Our Interactive Cod Shell (Click “run”):
Now, you know the basic method of filtering a dictionary in Python (by key and by value). But can we do better? What if you need to filter many dictionaries by many different filtering conditions? Do we have to rewrite the same code again and again?
The answer is no! Read on to learn about a more generic way to make filtering a dictionary as easy as calling a function passing the dictionary and the filter function.
Method 2: Generic Function to Filter Dictionary
How can you use different filtering functions on different dictionaries without writing the same code again and again? The answer is simple: create your own generic filtering function!
Your goal is to create a function filter_dict(dictionary, filter_func) that takes a dictionary to be filtered and a filter_func to determine for each (key, value) pair whether it should be included in the filtered dictionary.
def filter_dict(d, f): ''' Filters dictionary d by function f. ''' newDict = dict() # Iterate over all (k,v) pairs in names for key, value in d.items(): # Is condition satisfied? if f(key, value): newDict[key] = value return newDict
The function takes two arguments: the dictionary d to be filtered and the function f that decides if an element should be included in the new dictionary.
You create an empty dictionary newDict and decide for all elements of the original dictionary d whether they should be included. To accomplish this, you iterate over each original (key, value) pair and pass it to the function f: key, value --> Boolean. The function f returns a Boolean value. If it evaluates to True, the (key, value) pair is added to the new dictionary. Otherwise, it’s skipped. The return value is the newly created dictionary newDict.
Here’s how you can use the filtering function to filter by key:
Filter Python Dictionary By Key Using Generic Function
If you want to accomplish the same thing as above—filtering by key to include only odd keys—you simply use the following one-liner call:
That was easy! The lambda function you pass returns k%2 == 1 which is the Boolean filtering value associated to each original element in the dictionary names.
Similarly, if you want to filter by key to include only even key, you’d do the following:
The filter(function, iterable) function takes a function as input that takes one argument (an element of an iterable) and returns a Boolean value whether this element should pass the filter. All elements that pass the filter are returned as a new iterable object (a filter object).
You can use the lambda function statement to create the function right where you pass it as an argument. The syntax of the lambda function is lambda x: expression and it means that you use x as an input argument and you return expression as a result (that can or cannot use x to decide about the return value). For more information, see my detailed blog article about the lambda function.
Filter Python Dictionary By Key Using filter() + Lambda Functions
Here’s how you can filter a dictionary by key using only a single line of code (without defining your custom filter function as in method 2):
You may recognize the same filter lambda function lambda x: x[0]%2 == 1 that returns True if the key is an odd integer. Note that this lambda function takes only a single input as this is how the filter() function works (it requires that you pass a function object that takes one argument and maps it to a Boolean value).
You operate on the iterable names.items() that gives you all (key, value) pairs (an element of the iterable is a (key, value) tuple).
After filtering, you convert the filter object back to a dictionary using the dict(...) constructor function.
Filter Python Dictionary By Value Using filter() + Lambda Functions
You can use the same basic idea—filter() + lambda + dict()—to filter a dictionary by value. For example, if you want to filter out all (key, value) pairs where the value has less than five characters, use the following one-liner:
Dictionary comprehension allows you to transform one dictionary into another one—by modifying each (key, value) pair as you like.
Filter Python Dictionary By Key Using Dictionary Comprehension
The general framework for dictionary comprehension is { expression context }.
expression defines how you would like to change each (key, value) pair.
context defines the (key, value) pairs, you’d like to include in the new dictionary.
Here’s a practical example that filters all (key, value) pairs with odd keys:
print({k:v for (k,v) in names.items() if k%2 == 1})
# {1: 'Alice', 3: 'Carl', 5: 'Liz'}
And here’s an example that filters all (key, value) pairs with even keys:
print({k:v for (k,v) in names.items() if k%2 == 0})
# {2: 'Bob', 4: 'Ann'}
Let’s look at dictionary filtering by value! Is it any different?
Filter Python Dictionary By Value Using Dictionary Comprehension
No! It’s exactly the same:
print({k:v for (k,v) in names.items() if len(v)<5})
# {2: 'Bob', 3: 'Carl', 4: 'Ann', 5: 'Liz'}
This powerful framework is not only fast and easy to understand, it’s also concise and consistent. The filtering criteria is the last part of the expression so that you can quickly grasp how it’s filtered:
print({k:v for (k,v) in names.items() if v.startswith('A')})
# {1: 'Alice', 4: 'Ann'}
Try It Yourself in Our Interactive Cod Shell (Click “run”):
Here are all four methods from the tutorial to simplify copy&pasting:
names = {1: 'Alice', 2: 'Bob', 3: 'Carl', 4: 'Ann', 5: 'Liz'} ''' Method 1: Simple For Loop ''' # FILTER BY KEY
newDict = dict() # Iterate over all (k,v) pairs in names
for key, value in names.items(): # Is condition satisfied? if key%2 == 1: newDict[key] = value print(newDict)
# {1: 'Alice', 3: 'Carl', 5: 'Liz'} # FILTER BY VALUE
newDict = dict() # Iterate over all (k,v) pairs in names
for key, value in names.items(): # Is condition satisfied? if len(value)<5: newDict[key] = value print(newDict)
# {2: 'Bob', 3: 'Carl', 4: 'Ann', 5: 'Liz'} ''' Method 2: Custom Function ''' def filter_dict(d, f): ''' Filters dictionary d by function f. ''' newDict = dict() # Iterate over all (k,v) pairs in names for key, value in d.items(): # Is condition satisfied? if f(key, value): newDict[key] = value return newDict # FILTER BY KEY
print(filter_dict(names, lambda k,v: k%2 == 1))
print(filter_dict(names, lambda k,v: k%2 == 0)) # FILTER BY VALUE
print(filter_dict(names, lambda k,v: len(v)<5))
print(filter_dict(names, lambda k,v: v.startswith('A'))) ''' Method 3: filter() ''' # FILTER BY KEY
print(dict(filter(lambda x: x[0]%2 == 1, names.items())))
print(dict(filter(lambda x: x[0]%2 == 0, names.items()))) # FITER BY VALUE
print(dict(filter(lambda x: len(x[1])<5, names.items())))
print(dict(filter(lambda x: x[1].startswith('A'), names.items()))) ''' Method 4: Dict Comprehension ''' # FITER BY KEY
print({k:v for (k,v) in names.items() if k%2 == 1})
print({k:v for (k,v) in names.items() if k%2 == 0}) # FITER BY VALUE
print({k:v for (k,v) in names.items() if len(v)<5})
print({k:v for (k,v) in names.items() if v.startswith('A')})
But how do all of those methods compare in terms of algorithmic complexity and runtime? Let’s see…
Algorithmic Analysis
Before we benchmark those methods against each other, let’s quickly discuss computational complexity.
All four methods have linear runtime complexity in the number of elements in the original dictionary to be filtered—assuming that the filtering condition itself has constant runtime complexity (it’s independent of the number of elements in the dictionary).
Method
Complexity
Method 1: Loop
O(n)
Method 2: Custom
O(n)
Method 3: filter()
O(n)
Method 4: Dictionary Comprehension
O(n)
But this doesn’t mean that all methods are equally efficient. The dictionary comprehension is usually fastest for these types of filtering operations because it doesn’t use an intermediate function filter(). And it’s also easiest to understand. Therefore, you should use dictionary comprehension in your own code to filter a dictionary by key or by value!
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
What’s the runtime complexity of various list methods?
The following table summarizes the runtime complexity of all list methods.
Assume that the length of the data type is defined as n (that is—len(data_type)). You can now categorize the asymptotic complexity of the different complexity functions as follows:
Here’s your free PDF cheat sheet showing you all Python list methods on one simple page. Click the image to download the high-resolution PDF file, print it, and post it to your office wall:
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
In this tutorial, you’ll learn the runtime complexity of different Python operations.
Then, you’ll learn how to calculate the complexity of your own function by combining the complexity classes of its constituents. This is called “static analysis”
The tutorial is loosely based on (source) but it extends it significantly with more practical examples, interactive snippets, and explanatory material.
Introducing Big-O
Definition: The complexity of an operation (or an algorithm for that matter) is the number of resources that are needed to run it (source). Resources can be time (runtime complexity) or space (memory complexity).
So, how can you measure the complexity of an algorithm? In most cases, the complexity of an algorithm is not static. It varies with the size of the input to the algorithm or the operation.
For example, the list method list.sort() has one input argument: the list object to be sorted. The runtime complexity is not constant, it increases with increasing size of the list. If there are more elements to be sorted, the runtime of the algorithm increases.
Complexity Function
Given input size n, you can describe the complexity of your algorithm with a function of the input n → f(n) that defines the number of “resource units” (e.g., time, memory) needed to finish it (worst-case or average-case).
Say, you’ve got three implementations to sort a list: implementation_1, implementation_2, implementation_3.
The figure shows the three complexity functions. The x axis measures the input size (in our example, it would be the list size). The y axis measures the complexity with respect to this input.
implementation_1 has a quadratic complexity function f(n) = n².
implementation_2 has a quadratic complexity function f(n) = 2n².
implementation_3 has a logarithmic complexity function f(n) = n log(n).
You can see the code we used to generate this plot here:
import matplotlib.pyplot as plt
import math implementation_1 = [n**2 for n in range(1, 100, 10)]
implementation_2 = [2*n**2 for n in range(1, 100, 10)]
implementation_3 = [n*math.log(n) for n in range(1, 100, 10)] plt.plot(implementation_1, '--.', label='implementation 1')
plt.plot(implementation_2, '-o', label='implementation 2')
plt.plot(implementation_3, '-x', label='implementation 3') plt.legend()
plt.xlabel('Input (ex: List Size)')
plt.ylabel('Complexity (ex: Runtime)')
plt.grid()
plt.show()
Of course, it’s good to waste as little resources as possible so the logarithmic complexity function is superior to the quadratic complexity functions.
Big-O Notation
For large inputs, the runtime behavior will be dominated by the part of the complexity function that grows fastest. For example, a quadratic runtime complexity function f(n) = 1000n² + 100000n + 999 will be much better than a cubic runtime complexity function g(n) = 0.1n³.
Why? Because sooner or later the function g(n) will produce much higher values than f(n) as the input size n increases.
In fact, you can argue that the only important part of a complexity function is the part that grows fastest with increasing input size.
This is exactly what’s the Big-O notation is all about:
The Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. (wiki)
Roughly speaking, you remove everything but the fastest-growing term from the complexity function. This allows you to quickly compare different algorithms against each other.
To show this, have a look at our two examples:
Complexity function f(n) = 1000n² + 100000n + 999 grows like O(n²).
Complexity function g(n) = 0.1n³ grows like O(n³).
By reducing the complexity function to its asymptotic growth, you can immediately see that the former is superior to the latter in terms of runtime complexity—without being distracted by all the constant factors in front of the constituents or the constituents with smaller asymptotic growth.
Examples Big-O of Complexity Functions
So, here are a few examples of complexity functions and their asymptotic growth in Big-O notation:
Complexity Function
Asymptotic Growth
f(n) = 10000
O(1)
f(n) = n + 1000000
O(n)
f(n) = 33n + log(n)
O(n log(n))
f(n) = 33n + 4n * log(n)
O(n log(n))
f(n) = n² + n
O(n²)
f(n) = 1000n² + 100000n + 999
O(n²)
f(n) = 0.000000001n³ + 4n² + 100000n + 999
O(n³)
f(n) = n * n³ + 33n
O(n³)
You can see that the asymptotic growth of a function (in Big-O notation) is dominated by the fastest-growing term in the function equation.
Python Complexity of Operations
Let’s explore the complexity of Python operations—classified by the data structure on which you perform those operations. A great coder will always use the data structure that suits their needs best.
In general, the list data structure supports more operations than the set data structure as it keeps information about the ordering of the elements—at the cost of higher computational complexity.
Python List Complexity
Assume that the length of the data type is defined as n (that is—n = len(data_type)). You can now categorize the asymptotic complexity of the different complexity functions as follows:
Tuples are similar as lists—with a few exceptions: you cannot modify a tuple because they are immutable.
Let’s consider another important data structure:
Python Set Complexity
Assume that the length of the data type is defined as n (that is—n = len(data_type)). If there are two sets in a single operation such as s1 == s2, the lengths are given by the variables n1 and n2. You can now categorize the asymptotic complexity of the different complexity functions as follows:
I highlighted the set operations that are more efficient than the corresponding list operations. The reason for those being O(1) rather than O(n) is that the list data structure also maintains the ordering of the elements—which incurs additional overhead.
Python Dictionary Complexity
Now, have a look at the time complexity of Python dictionary operations:
Most operations are O(1) because Python dictionaries share multiple properties of Python sets (such as fast membership operation).
Composing Complexity Classes
Now, you know the complexity of different operations. But how do you obtain the complexity of your algorithm?
The concept is simple: you break the big problem (knowing the complexity of the whole algorithm) into a series of smaller problems (knowing the complexity of individual operations).
Then, you recombine the individual operation’s complexities to obtain the solution to the big problem.
How? Let’s start with a small example: you first get a list from a dictionary of list values. Then you sort the list:
You see in Equation (1) what you could call the “chain rule of complexity analysis”: O(f(n)) + O(g(n)) = O(f(n) + g(n)).
You can see in Equation (3) that the Big-O notation focuses only on the largest growing term. In our case, O(n log n) grows faster than O(2n).
Here are two important examples of Big-O recombination:
O(f(n)) + O(f(n)) = O(f(n) + f(n)) = O(2f(n)) = O(f(n). In other words, Executing an operation a constant (fixed) number of times, doesn’t change the overall complexity of the algorithm.
O(f(n) + g(n)) = O(f(n)) if the complexity function f(n) grows faster than g(n). An example is O(n³ + 1000n³) = O(n³).
In programming, you can also have conditional execution:
if condition: f(n)
else: g(n)
You can recombine the complexity class of the overall code snippet as follows: O(max(f(n), g(n)). Roughly speaking, (if the condition can be true), the complexity of the conditional execution is the maximum of both blocks f(n) or g(n).
Example:
if lst: lst.sort()
else: lst = [1, 2, 3, 4]
The complexity is O(n log n) because it grows faster than O(n) — the complexity of the block in the else statement.
Another possibility is to repeatedly execute a certain function (e.g., in a for loop).
If you repeat function f(n)m times, the computational complexity is m * O(f(n)) = O(m f(n)). If m is a constant, the computational complexity simplifies to O(f(n)).
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
A wildly popular operation you’ll find in any (non-trivial) code base is to concatenate lists—but there are multiple methods to accomplish this. Master coders will always choose the right method for the right problem.
This tutorial shows you the difference between three methods to concatenate lists:
Concatenate two lists with the + operator. For example, the expression [1, 2, 3] + [4, 5] results in a new list [1, 2, 3, 4, 5]. More here.
Concatenate two lists with the += operator. This operation is inplace which means that you don’t create a new list and the result of the expression lst += [4, 5] is to add the elements on the right to the existing list object lst. More here.
Concatenate two lists with the extend() method of Python lists. Like +=, this method modifies an existing list in place. So the result of lst.extend([4, 5]) adds the elements 4 and 5 to the list lst. More here.
To summarize: the difference between the + method and the += and extend() methods is that the former creates a new list and the latter modify an existing list object in-place.
You can quickly compare those three methods in the following interactive code shell:
Puzzle: Can you already figure out the outputs of this code snippet?
Fear not if you can’t! I’ll explain you each detailed example next.
Method 1: Add (+)
The standard way of adding two lists is to use the + operator like this:
While the + operator is the most readable one (especially for beginner coders), it’s not the best choice in most scenarios. The reason is that it creates a new list each time you call it. This can become very slow and I’ve seen many practical code snippets where the list data structure used with the + operator is the bottleneck of the whole algorithm.
In the above code snippet, you create two list objects in memory—even though your goal is probably just to update the existing list ['Alice', 'Bob', 'Ann'].
This can be nicely demonstrated in the code visualization tool:
Just keep clicking “Next” until the second list appears in memory.
Method 2: INPLACE Add (+=)
The += operator is not well understood by the Python community. Many of my students (join us for free) believe the add operation lst += [3, 4] is just short for lst = lst + [3, 4]. This is wrong and I’ll demonstrate it in the following example:
Again, you can visualize the memory objects with the following interactive tool (click “Next”):
The takeaway is that the += operation performs INPLACE add. It changes an existing list object rather than creating a new one. This makes it more efficient in the majority of cases. Only if you absolutely need to create a new list, you should use the + operator. In all other cases, you should use the += operator or the extend() method.
Speaking of which…
Method 3: Extend()
Like the previous method +=, the list.extend(iterable) method adds a number of elements to the end of a list. The method operators in-place so no new list object is created.
Click “Next” and explore how the memory allocation “unfolds” as the execution proceeds.
Speed Comparison Benchmark
Having understood the differences of the three methods + vs += vs extend(), you may ask: what’s the fastest?
To help you understand why it’s important to choose the best method, I’ve performed a detailed speed benchmark on my Intel i7 (8th Gen) Notebook (8GB RAM) concatenating lists with increasing sizes using the three methods described previously.
Here’s the result:
The plot shows that with increasing list size, the runtime difference between the + method (Method 1), and the += and extend() methods (Methods 2 and 3) becomes increasingly evident. The former creates a new list for each concatenation operation—and this slows it down.
Result: Thus, both INPLACE methods += and extend() are more than 30% faster than the + method for list concatenation.
You can reproduce the result with the following code snippet:
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
Want to boost your Python skills to the next level as an intermediate coder? Want to know how to overcome being stuck at average coding level? Do you enjoy solving puzzles?
We’re excited to release a new fresh, and tough Finxter book with 99 never-seen Python puzzles. It’s the hardest one in our Coffee Break Python series.
IF YOU CAN DO IT THERE, YOU CAN DO IT EVERYWHERE!
If you want to download a 50-page sample of the book for FREE, you’re on the right spot:
Title: Coffee Break Python – Mastery Workout
Subtitle: 99 Tricky Python Puzzles to Push You to Programming Mastery
YouTube is a great way of learning Python. But those channels top all others. In this article, you’ll find a list of the top YouTube Channels — in reverse order!
Channel Description: This channel is focused on creating tutorials and walkthroughs for software developers, programmers, and engineers. We cover topics for all different skill levels, so whether you are a beginner or have many years of experience, this channel will have something for you.
We’ve already released a wide variety of videos on topics that include: Python, Git, Development Environments, Terminal Commands, SQL, Programming Terms, JavaScript, Computer Science Fundamentals, and plenty of other tips and tricks which will help you in your career.
Channel Description: You can find awesome programming lessons here! Also, expect programming tips and tricks that will take your coding skills to the next level.
Channel Description: On this channel you’ll get new Python videos and screencasts every week. They’re bite-sized and to the point so you can fit them in with your day and pick up new Python skills on the side:
Channel Description: Socratica makes high-quality educational videos on math and science. The videos are …. different. Check them out to see what I mean!
Channel Description: Python Programming tutorials, going further than just the basics. Learn about machine learning, finance, data analysis, robotics, web development, game development and more.
These are the best Python channels on YouTube. Check them out, there’s an infinite number of YT videos that will make you a better coder — for free!
The Finxter Channel
You may also check out the Finxter channel which is a small Python Business related channel. If you want to improve your Python business skills, this channel is for you!
Want to create your own webserver in a single line of Python code? No problem, just use this command in your shell:
$ python -m http.server 8000
The terminal will tell you:
Serving HTTP on 0.0.0.0 port 8000
To shut down your webserver, kill the Python program with CTRL+c.
This works if you’ve Python 3 installed on your system. To check your version, use the command python --version in your shell.
You can run this command in your Windows Powershell, Win Command Line, MacOS Terminal, or Linux Bash Script.
You can see in the screenshot that the server runs on your local host listening on port 8000 (the standard HTTP port to serve web requests).
Note: The IP address is NOT 0.0.0.0—this is an often-confused mistake by many readers. Instead, your webserver listens at your “local” IP address 127.0.0.1 on port 8000. Thus, only web requests issued on your computer will arrive at this port. The webserver is NOT visible to the outside world.
Python 2: To run the same simple webserver on Python 2, you need to use another command using SimpleHTTPServerinstead of http:
$ python -m SimpleHTTPServer 8000
Serving HTTP on 0.0.0.0 port 8000 ...
If you want to start your webserver from within your Python script, no problem:
import http.server
import socketserver PORT = 8000 Handler = http.server.SimpleHTTPRequestHandler with socketserver.TCPServer(("", PORT), Handler) as httpd: print("serving at port", PORT) httpd.serve_forever()
You can execute this in our online Python browser (yes, you’re creating a local webserver in the browser—how cool is that)!
This code comes from the official Python documentation—feel free to read more if you’re interested in setting up the server (most of the code is relatively self-explanatory).
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
Python’s Tilde ~n operator is the bitwise negation operator: it takes the number n as binary number and “flips” all bits 0 to 1 and 1 to 0 to obtain the complement binary number. For example, the tilde operation ~1 becomes 0 and ~0 becomes 1 and ~101 becomes 010.
Sometimes, you’ll see the tilde operator in a Pandas DataFrame for indexing. Here’s an example:
import pandas as pd # Create a DataFrame
df = pd.DataFrame([{'User': 'Alice', 'Age': 22}, {'User': 'Bob', 'Age': 24}])
print(df) ''' User Age
0 Alice 22
1 Bob 24 ''' # Use Tilde to access all lines where user doesn't contain 'A'
df = df[~df['User'].str.contains('A')]
print(df) ''' User Age
1 Bob 24 '''
To improve your practical understanding, feel free to run this code in your browser in our interactive Python shell:
The tilde operator negates the Boolean values in the DataFrame: True becomes False and False becomes True.
You can see this in action when printing the result of different operations:
This is the original DataFrame in the code:
print(df) ''' User Age
0 Alice 22
1 Bob 24 '''
Now apply the contains operation to find all user names that contain the character 'A'.
Now, we use this DataFrame to access only those rows with users that don’t contain the character 'A'.
df = df[~df['User'].str.contains('A')]
print(df) ''' User Age
1 Bob 24 '''
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
