best way to determine sequence ordering?

[nikie]

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.

>  >>> 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), which is definitely worse than O(n) for
searching the list twice. And, of course, it would yield different
results if 'A' or 'D' are in the list more than once.

> If you care about memory in addition to speed, you could do something like:
>
>  >>> L = ['C', 'A', 'D', 'B']
>  >>> items_to_compare = ['A', 'D']
>  >>> positions = dict(
> ...     (item, i)
> ...     for i, item in enumerate(L)
> ...     if item in items_to_compare
> ... )
>  >>> positions
> {'A': 1, 'D': 2}
>  >>> positions['A'] < positions['D']
> True

Did you measure that? Is this really faster than using index twice, for
big lists? The number of comparisons (when dealing with strings, that's
probably what'll take the time) should be about twice as high as for
the index-version of the OP (assuming the items only exactly once in
the list).