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]))
# True
Converting 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]))
# True
This 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]))
# True
Thanks 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!
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.
Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.
https://www.sickgaming.net/blog/2020/06/...identical/