Python annoyance 2: List searching is slow
One of the things that really slows Wine-Doors down is the code that figures out whether a package is installed/available or and upgrade, so I decided to investigate why.
In this example I created a list of 1000 numbers (0-999) and randomly choose a number from that list, which I then give to my 3 search functions, linear_search, binary_search and python_search. Each search function returns the number of iterations needed to find the item in the list (or None if its not in there, which would be worrying) and a function decorator prints the time it took.
Value we are searching for is '760' Performing linear search linear_search took 0.668 ms Found test value in 760 iterations Performing binary search binary_search took 0.085 ms Found test value in 26 iterations Performing python search python_search took 2.234 ms Found test value in 0 iterations
linear_search iterates through each item in the list one by one. binary_search (I call it binary_search, but its not really, it uses a custom algorithm) starts at the middle and heads in which ever direction makes the most sense, if it is heading in the right direction it speeds up, and if not it changes direction and slows down. python_search just uses the following code:
def python_search( list, value ):
if value in list:
return 0:
return None
python search failed miserably, and this is the recommend way to determine if a value is in a list so you’d think it would be the fastest. linear_search came second which really surprised me, as I was certain it would come last. But wow, binary_search really killed both of them.
Why doesn’t python use something like this internally to speed this kind of thing up?