To check if two unordered lists x and y are identical, compare the converted sets with set(x) == set(y). However, this loses all information about duplicated elements. To consider duplicates, compare the sorted lists with sorted(x) == sorted(y). Due to the efficient merge-sort-like implementation of the sorted() function, this is quite fast for almost-sorted lists.
Problem: Given are two lists x and y. You want to return True if both lists contain the same elements, and otherwise False. A variant of this problem is to ignore duplicates (which makes this problem far simpler).
Examples:
x = [1, 2, 3, 4, 5] y = [1, 2, 3] # compare(x, y) --> False x = [1, 2, 3, 4, 5] y = [1, 2, 3, 5, 4] # compare(x, y) --> True x = [1, 2, 3, 4, 5] y = [1, 2, 3, 4, 5] # compare(x, y) --> True
Let’s discuss the most Pythonic ways of solving this problem. Here’s a quick interactive code overview:
Exercise: Glance over all methods and run the code. What questions come to mind? Do you understand each method?
Read on to learn about each method in detail!
Method 1: Set Conversion
This method assumes that you ignore duplicates. So, the lists [1, 1, 1] and [1] are considered to be identical:
###################
# 1. Set Conversion
###################
def method_1(x, y):
return set(x) == set(y)
print(method_1([1, 2, 3], [1, 2]))
# False
print(method_1([1, 2], [2, 1]))
# TrueConverting the list to a set has linear runtime complexity. Comparing two sets for equality also has linear runtime complexity (due to the constant runtime complexity of set membership). So, overall, the runtime complexity of this method is linear in the number of elements in the larger list.
However, a set doesn’t contain any information about the number of times each element is represented. To consider this information, you’ll need a multiset data structure.
Method 2: Multiset with Collections Counter
In Python, there are some multiset packages that are capable of considering the number of times each element is represented in the original list. One of them is the collections.Counter class.
###################
# 2. Collections Counter
###################
import collections
def method_2(x, y):
return collections.Counter(x) == collections.Counter(y)
print(method_2([1, 1, 1], [1, 1]))
# False
print(method_2([1, 2, 3], [2, 1, 3]))
# TrueThis method is also efficient and it hides implementation details which leads to a higher degree of decoupling in your Python application. However, you may not like that it requires to import another dependency.
Method 3: Sorting
Sorting a list in Python uses a highly efficient algorithm based on mergesort. This means that if the list is “almost” sorted, the sorting routine is very fast. Only in the absolute worst case, the computational complexity is O(n log n) to sort a list.
As soon as both lists are sorted, you can go on and use the element-wise comparison operator x==y to check identity of two ordered lists x and y.
###################
# 3. Sorting
###################
def method_3(x, y):
return sorted(x) == sorted(y)
print(method_2([1, 1, 1], [1, 1]))
# False
print(method_2([1, 2, 3], [2, 1, 3]))
# TrueThanks for reading this article! If you want to learn something new every day, join my free Python email series for continuous improvement in Python and computer science.
Related Video
This video is related to the problem: checking if two ordered lists are identical.
Where to Go From Here?
Enough theory. Let’s get some practice!
Coders get paid six figures and more because they can solve problems more effectively using machine intelligence and automation.
To become more successful in coding, solve more real problems for real people. 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?
You build high-value coding skills by working on practical coding projects!
Do you want to stop learning with toy projects and focus on practical code projects that earn you money and solve real problems for people?
🚀 If your answer is YES!, consider becoming 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.
If you just want to learn about the freelancing opportunity, feel free to watch my free webinar “How to Build Your High-Income Skill Python” and learn how I grew my coding business online and how you can, too—from the comfort of your own home.