6
I was having a lot of difficulty executing code efficiently and found that the problem was on a line that used the operator in
. Then I created a new function that searches for a match in the list of elements in binary form. I did an analysis of the performance of my function and the operator in
and I noticed, to my surprise, that my function was much faster. Here’s my code:
import bisect
import matplotlib.pyplot as plt
import time
import random
import numpy as np
import seaborn as sns
sns.set_style("whitegrid")
def belongs2(elements, value):
index = bisect.bisect_left(elements, value)
if index < len(elements) and elements[index] == value:
return True
else:
return False
def belongs2time(elements, value):
start_time=time.time()
index = bisect.bisect_left(elements, value)
if index < len(elements) and elements[index] == value:
True
else:
False
return time.time() - start_time
def in_time(elements, value):
start_time=time.time()
value in elements
return time.time() - start_time
# ### Timing belongs
number=random.choice(range(1000))
lengths=np.arange(100,100000,100)
time_belongs=[]
for lenght_list in lengths:
numbers=[random.choice(range(1000)) for i in range(lenght_list)]
numbers.sort()
time_belongs.append(belongs2time(numbers, number))
# ### Timing in
number=random.choice(range(1000))
lengths=np.arange(100,100000,100)
time_in=[]
for lenght_list in lengths:
numbers=[random.choice(range(1000)) for i in range(lenght_list)]
numbers.sort()
time_in.append(in_time(numbers, number))
fig, ax= plt.subplots()
ax.plot(lengths, time_belongs, label='belongs')
ax.plot(lengths, time_in, label='in')
ax.spines['right'].set_visible(False)
ax.spines['top'].set_visible(False)
plt.legend(loc='upper center', bbox_to_anchor=(0.5,-0.15),
ncol=2, fontsize=14)
plt.yscale('log')
plt.show()
I’m not used to doing this kind of "performance analysis" (actually, it’s the first time I’ve done it), so I may have made a mistake here and you’re coming to the wrong conclusion. But if you’re right, why the operator in
is so slow? I expected a more efficient implementation of a method so ubiquitous to python. Is there any other method built-in
more efficient than the in
for this type of operation?
Very interesting. Thank you for the detailed answer. I knew the concept of binary search, but how do you know that the
in
is linear? I did the test just because I didn’t know how toin
did the search. I had a way of knowing that it was ante-hand linear?– Lucas
Sorry, now that I saw that there was this information on the page you linked
– Lucas
@Lucas Another alternative is see the source code :-)
– hkotsubo