best way to determine sequence ordering?

[Steven Bethard]

nikie wrote:
> Steven Bethard wrote:
> 
>> John Salerno wrote:
>>> If I want to make a list of four items, e.g. L = ['C', 'A', 'D', 'B'],
>>> and then figure out if a certain element precedes another element, what
>>> would be the best way to do that?
>>>
>>> Looking at the built-in list functions, I thought I could do something
>>> like:
>>>
>>> if L.index('A') < L.index('D'):
>>>     # do some stuff
>> This is probably a pretty reasonable approach as long as you're not too
>> worried about efficiency.  It scans the list twice though, so if you
>> start doing this with really big lists, it might be better to do
>> something like:
> 
> On average, it'll only have go through half the list twice, as it can
> break as soon as it finds the item it searches for. Don't think you can
> get any more efficient than that.

Sure you can:

     a_index = None
     d_index = None
     for i, item in enumerate(L):
         if item == 'A':
             a_index = i
         elif item == 'D':
             d_index = i
         if a_index is not None and d_index is not None:
             break

     if a_index < d_index:
         # do some stuff

That goes through exactly the minimum number of elements.  But it's 
probably slower than two .index() calls since .index() is coded in C. 
But timeit and see if you're interested.

> 
>>  >>> L = ['C', 'A', 'D', 'B']
>>  >>> positions = dict((item, i) for i, item in enumerate(L))
>>  >>> positions
>> {'A': 1, 'C': 0, 'B': 3, 'D': 2}
>>  >>> positions['A'] < positions['D']
>> True
> 
> Isn't this bound to be less efficient? I mean, inserting the items into
> a dict is probably O(n log n)

No, it's O(N).  Dicts are just hash tables.  Insertion is O(1).  So N 
insertions is O(N).

This route is also dramatically more efficient if you need to make M 
comparisons between items instead of just 1 comparison.  In that case, 
using the dict is O(N + M) instead of the O(N * M) of the .index() route.

STeVe