[Tutor] Sorting against another list

[Remco Gerlich]

On  0, Sharriff Aina <NHYTRO@compuserve.com> wrote:
> I have a list that is created dynamically, how do I sort this list so that
> it matches amother "mater template" list?
> 
> example:
> [ 'aa', 'qq', 'ttt', 'hh']  # master list
> 
> my dynamic list cotains all or only a few of the elements in the master
> list:
> 
> ['ttt', 'hh', 'aa'] ### i would like to sort it to produce ['aa''ttt',
> 'hh']  accoriding to the sequense in the master list
> 
> or [ 'hh', 'qq' 'ttt'] ### would like ['qq', 'ttt', 'hh']
>  
> I would like to sort these example list so that they at least follow the
> order of the master list.

Hmm. Ok, we have two lists: 'master' and 'dynamic'.

You can give an argument to .sort(), an alternative way to compare two
items. You want to compare them using the order of the master list. The
easiest way to spell that is this:

def compare_using_master_list(a, b):
   # Compare the indices of the two items in the master list
   return cmp(master.index(a), master.index(b))

dynamic.sort(compare_using_master_list)

If any of the elements of dynamic doesn't occur in master, it gives an
exception, that seems like the right behavior to me.

If your lists are small (say, at most a few tens of items), this will work
fine. If they're bigger, the problem is that "master.index()" has to search
half the master list, on average, each time it's called. We can do better by
computing the indices first and caching them in a dictionary:

cachedict = {}
for i in range(len(master)):
   cachedict[master[i]] = i
   
def compare_using_master_cache(a, b):
   # Compare the cached index values of a and b
   return cmp(cachedict[a], cachedict[b])
   
dynamic.sort(compare_using_master_cache)

This should be faster with all but the most trivial lists (but I didn't test
it).

-- 
Remco Gerlich