Create an account


Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[Tut] The Most Pythonic Way to Check if Two Unordered Lists Are Identical

#1
The Most Pythonic Way to Check if Two Unordered Lists Are Identical

<div><p class="has-luminous-vivid-amber-background-color has-background">To check if two unordered lists <code>x</code> and <code>y</code> are identical, compare the converted sets with <code>set(x) == set(y)</code>. However, this loses all information about duplicated elements. To consider duplicates, compare the sorted lists with <code>sorted(x) == sorted(y)</code>. Due to the efficient merge-sort-like implementation of the <code>sorted()</code> function, this is quite fast for almost-sorted lists.</p>
<figure class="wp-block-image size-large is-resized"><img src="https://blog.finxter.com/wp-content/uploads/2020/06/probform_ordered_identical_lists-1024x576.jpg" alt="" class="wp-image-10097" width="768" height="432" srcset="https://blog.finxter.com/wp-content/uploads/2020/06/probform_ordered_identical_lists-scaled.jpg 1024w, https://blog.finxter.com/wp-content/uplo...00x169.jpg 300w, https://blog.finxter.com/wp-content/uplo...68x432.jpg 768w" sizes="(max-width: 768px) 100vw, 768px" /></figure>
<p><strong>Problem</strong>: Given are two <a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener" title="The Ultimate Guide to Python Lists">lists </a><code>x</code> and <code>y</code>. You want to return <code>True</code> if both lists contain the same elements, and otherwise <code>False</code>. A variant of this problem is to ignore <a href="https://blog.finxter.com/how-to-remove-duplicates-from-a-python-list-of-lists/" target="_blank" rel="noreferrer noopener" title="How to Remove Duplicates From a Python List of Lists?">duplicates </a>(which makes this problem far simpler).</p>
<p><strong>Examples</strong>:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">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</pre>
<p>Let’s discuss the most Pythonic ways of solving this problem. Here’s a quick interactive code overview:</p>
<p> <iframe src="https://trinket.io/embed/python/326d676c69" width="100%" height="700" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe> </p>
<p><em><strong>Exercise</strong>: Glance over all methods and run the code. What questions come to mind? Do you understand each method?</em></p>
<p>Read on to learn about each method in detail!</p>
<h2>Method 1: Set Conversion</h2>
<p>This method assumes that you ignore duplicates. So, the lists <code>[1, 1, 1]</code> and <code>[1]</code> are considered to be identical:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">###################
# 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</pre>
<p>Converting the list to a set has linear runtime complexity. Comparing two sets for equality also has linear runtime complexity (due to the <a href="https://blog.finxter.com/complexity-of-python-operations/" title="Complexity of Python Operations" target="_blank" rel="noreferrer noopener">constant runtime complexity of set membership</a>). So, overall, the runtime complexity of this method is linear in the number of elements in the larger list.</p>
<p>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. </p>
<h2>Method 2: Multiset with Collections Counter</h2>
<p>In Python, there are some <a href="https://pythonhosted.org/multiset/" title="https://pythonhosted.org/multiset/" target="_blank" rel="noreferrer noopener">multiset </a>packages that are capable of considering the number of times each element is represented in the original list. One of them is the <code>collections.Counter</code> class. </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">###################
# 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</pre>
<p>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.</p>
<h2>Method 3: Sorting</h2>
<p>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 <a href="https://blog.finxter.com/runtime-complexity-of-python-list-methods-easy-table-lookup/" title="Runtime Complexity of Python List Methods [Easy Table Lookup]" target="_blank" rel="noreferrer noopener">computational complexity</a> is <em>O(n log n)</em> to sort a list.</p>
<p>As soon as both lists are sorted, you can go on and use the element-wise comparison operator <code>x==y</code> to <a href="https://blog.finxter.com/check-if-two-ordered-lists-are-identical/" target="_blank" rel="noreferrer noopener" title="The Most Pythonic Way to Check if Two Ordered Lists Are Identical">check identity of two ordered lists</a> <code>x</code> and <code>y</code>. </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">###################
# 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</pre>
<p>Thanks for reading this article! If you want to learn something new every day, <a href="https://blog.finxter.com/subscribe/" title="Subscribe" target="_blank" rel="noreferrer noopener">join my free Python email series</a> for continuous improvement in Python and computer science.</p>
<h2>Related Video</h2>
<p>This video is related to the problem: <a href="https://blog.finxter.com/check-if-two-ordered-lists-are-identical/" target="_blank" rel="noreferrer noopener" title="The Most Pythonic Way to Check if Two Ordered Lists Are Identical">checking if two <strong><em>ordered </em></strong>lists are identical</a>.</p>
<figure class="wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio">
<div class="wp-block-embed__wrapper">
<div class="ast-oembed-container"><iframe title="The Most Pythonic Way to Check if Two Ordered Lists Are Identical" width="1400" height="788" src="https://www.youtube.com/embed/RkLh-6ylaUg?feature=oembed" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe></div>
</div>
</figure>
<h2>Where to Go From Here?</h2>
<p>Enough theory, let’s get some practice!</p>
<p>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?</p>
<p><strong>Practice projects is how you sharpen your saw in coding!</strong></p>
<p>Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?</p>
<p>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.</p>
<p>Join my free webinar <a rel="noreferrer noopener" href="https://blog.finxter.com/webinar-freelancer/" target="_blank">“How to Build Your High-Income Skill Python”</a> and watch how I grew my coding business online and how you can, too—from the comfort of your own home.</p>
<p><a href="https://blog.finxter.com/webinar-freelancer/" target="_blank" rel="noreferrer noopener">Join the free webinar now!</a></p>
</div>


https://www.sickgaming.net/blog/2020/06/...identical/
Reply



Forum Jump:


Users browsing this thread:
2 Guest(s)

Forum software by © MyBB Theme © iAndrew 2016