best way to determine sequence ordering?

[nikie]

I V wrote:

> On Fri, 28 Apr 2006 14:27:00 -0700, nikie wrote:
> > Steven Bethard wrote:
> >
> >>  >>> L = ['C', 'A', 'D', 'B']
> >>  >>> positions = dict((item, i) for i, item in enumerate(L))
>
> Do you need the generator expression here? dict(enumerate(L)) should be
> equivalent, no?

I think the generator is needed to swap the item and the index.
dict(enumerate(L)) would yield a dict like {0:'C', 1:'A'...}

> > 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.
>
> Although presumably the dict method might be quicker if you were comparing
> the positions a large number of times.

Only if you build the dict once, but called index each and every time,
which is comparing apples with oranges...

> Incidentally, does python have a built-in to do a binary search on a
> sorted list? Obviously it's not too tricky to write one, but it would be
> nice if there was one implemented in C.

I once read in an algorithm book that it took 10 years from the first
binary search publication until a correct version was published, so, it
actually is a bit tricky... Better stick to the bisect module. Don't
know if it's written in C, though.