I was solving a hackerrank challenge.(in Python 3)
At one point I needed to sort a list and work with it.
(2 <= len(array) <= 10^5)
The list is containing unique integers.
I used arr.sort(), but I was getting "Time limit exceeded" message
Then I found if I use set(arr), it runs fast and passes all test cases.
here's is my function for more clarification
def pairs(k, ar):
ar.sort()
c=0
for i in ar:
if i+k in ar:
c+=1
return c
This gets me "Time limit exceeded"
def pairs(k, ar):
ar=set(ar)
c=0
for i in ar:
if i+k in ar:
c+=1
return c
This one with set() runs faster. Why is this set() is faster than sort(). Don't they use same sorting algorithm?
setobjects are absolutely not sorted in Python, not even as an implementation detail in any of the major implementationsinoperator.setdoesn't use a sorting algorithm at all, and produces something completely different. That said, the reason that sorting the list gives you a much slower result than using a set is that sorting the list doesn't helpinwork at all; theinoperator has no way to know that the list has been sorted, and therefore every element is still checked every time.intobjects (mostly) hash to themselveslistcould gain some speed on containment checks (going fromO(n)toO(log n)) by using thebisectmodule functions. But sorting (O(n log n)) plus repeated binary search (O(log n)) is almost certainly going to be much slower than conversion toset(O(n)) plus repeatedsetlookup (average caseO(1)). But yeah,inon a sortedlistandinon an unsortedlisthave identical performance (only way they'd differ in practice is if the thing being searched for was likely to be bigger or smaller than most elements of thelist).==onsets compares them w/o regard to iteration order, so that would be true even if thesets in question had the same values but iterated in different orders. Try it with{-2, -1}and{-1, -2}. They iterate in different orders (because I chose two values that, as an implementation detail of CPython, have identical hashes, so the first seen occupies its desired bucket, while the second hops around to find an open one; other values do this too, they're just a little harder to find), but they're still equal to each other.setdoesn't sort, and has no useful ordering.