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?

What really annoys me about python lists (and tuples) is that their ‘append’ method returns ‘None’.  This effectively renders the append method useless when working with custom classes that offer a dict like interface via __getitem__ and __setitem__.

Take the following code for example.

class MyClass( object ):

    def __init__( self ):
        self.dict = {}

    def __getitem__( self, name ):
        return self.dict[name]

    def __setitem__( self, name, value ):
        self.dict[name] = value

myclass = MyClass()
myclass["list"] = ["foo"]
myclass["list"].append( "bar" )

You’d think that myclass[”list”] now contains [”foo”, “bar”]. It actually contains None (the append methods return value).