469,631 Members | 1,218 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,631 developers. It's quick & easy.

best way to determine sequence ordering?

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

But I didn't know if maybe there was a preferred method for this type of
operation, or perhaps a better function to use to figure out the
ordering. Or even if I wanted to write my own utility function to make
it look cleaner than above, I'd still need to use something like above
in my function, so I wanted to know what might be the 'cleanest' looking
solution.

Thanks.
Apr 28 '06 #1
21 1458
gry
index is about the best you can do with the structure you're using.
If you made the "items" instances of a class, then you could define a
__cmp__ member, which would let you do:

a=Item('A')
b=Item('B')
if a<b: something

The Item class could use any of various means to maintain order
information. If there are not too many values, it could have a
dictionary storing an integer for the order:

class Item(object):
def __init__(self, value):
self.val=value
self.order = dict(c=0, a=1, d=2, b=3)
def __cmp__(self, other):
return cmp(self.order[self.val], self.order[other.val])

If you don't care about performance, or you find it clearer, just use:
self.order = ['C', 'A', 'D', 'B']
and
def __cmp__(self, other):
return cmp(self.order.index(self.value),
self.order.index(other.value))
-- George Young

Apr 28 '06 #2
gr*@ll.mit.edu wrote:
index is about the best you can do with the structure you're using.
If you made the "items" instances of a class, then you could define a
__cmp__ member, which would let you do:

a=Item('A')
b=Item('B')
if a<b: something

The Item class could use any of various means to maintain order
information. If there are not too many values, it could have a
dictionary storing an integer for the order:

class Item(object):
def __init__(self, value):
self.val=value
self.order = dict(c=0, a=1, d=2, b=3)
def __cmp__(self, other):
return cmp(self.order[self.val], self.order[other.val])

If you don't care about performance, or you find it clearer, just use:
self.order = ['C', 'A', 'D', 'B']
and
def __cmp__(self, other):
return cmp(self.order.index(self.value),
self.order.index(other.value))
-- George Young


Thanks. As I progressed with my little project, I was beginning to
wonder about making a class, so your suggestions might be helpful if I
convert it to that.
Apr 28 '06 #3
gr*@ll.mit.edu wrote:
class Item(object):
def __init__(self, value):
self.val=value
self.order = dict(c=0, a=1, d=2, b=3)
def __cmp__(self, other):
return cmp(self.order[self.val], self.order[other.val])


An object that keeps track of the order it's stored in an external container
seems bass-ackwards to me (if you'll pardon the expression). How do you
update the order? Why does every object need to carry around a global
ordering? What happens if you need two separate orderings like a,b,c,d and
a,c,d,b? And it isn't clear at all what the < operator is comparing in
your example:

a=Item('A')
b=Item('B')
if a < b: something

I'd put the ordering logic in the container instead. Something like this:

class mylist(list):
def before (me, a, b):
return me.index(a) < me.index(b)

l = mylist (['C', 'A', 'D', 'B'])
if l.before('A', 'D'):
something

This seems clearer and more flexible. You'll still have to handle
exceptions when a or b aren't in the list.
Apr 28 '06 #4
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:
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

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

STeVe
Apr 28 '06 #5
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).

Apr 28 '06 #6
I V
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?
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.

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.
Apr 28 '06 #7
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.

Apr 28 '06 #8
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
Apr 29 '06 #9
I V
On Fri, 28 Apr 2006 16:39:33 -0700, nikie wrote:
I V wrote:
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'...}


Oh, of course, I wasn't paying attention.
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.


Thanks for pointing out the bisect module - that's exactly what I was
looking for.
Apr 29 '06 #10
I V wrote:
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.


See the bisect module.

Kent
Apr 29 '06 #11
Steven Bethard wrote:
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.


On my PC, calling index twice is 5 times faster.

But let's just pretend for a moment Python code was compiled and
optimized as well as C code. Then, this function would still not be
faster than calling index twice. You seem to be under the impression
that "looping through a list" takes a lot of time and "comparing items"
takes none. The reverse is the case: Looping through a list means the
processor has to do something like "increment an index" once for every
item in the list (for optimized C code! Looping through a generator
like the one returned by enumerate in interpreted code is a lot more
complex). Comparing two items on the other hand involves (as lists
aren't statically typed) looking up a cmp-method dynamically, calling
it dynamically, and, of course, a string comparison, which again
involves two pointer lookups for every character that has to be
compared. So, if you want to know how fast your function will be,
you'll have to count the number of comparisons. (Of course, we're
ignoring the fact that smaller functions tend to run quicker due to
cache-, branch-prediction and optimization-effects) If you call your
function with the list ['C', 'A', 'D', 'B'], it will compare the first
item 'C' to 'A' and 'D', than the second, 'A' to 'A' and the third 'D'
to 'A' and 'D', so it'll have to do 5 comparisons, correct? If you call
index to find the first occurence of the item 'A' in the same list, it
will have to do 2 comparisons (it can break as soon as it finds the
iten), and 3 comparisons are needed for finding the item 'D', so it'll
do 5 comparisons, too. Plus, you have a small overhead for comparing
"a_index" and "d_index" to none (which is faster than a
sting-comparison, but still takes time, probably more time than
incrementing an index for looping through a list). Things get even
worse if 'A' and 'D' aren't "neighbors" in the list, because than all
the items bewteen 'A' and 'D' will have to be compared to 'A' and 'D'
in the version above, but only to 'D' if you call index twice. So, the
function above isn't only less readable, it's also slower on the
average case.

You might however be able to tweak the performance of the index-version
a little bit if you call it only on small chunks of the array at a
time, using the index()-versions that take a start- and stop index, so
the whole list only has to be moved from the memory to the cache once.
But I'm not sure the performance is memory-bound at all (always hard to
tell in an interpreted language).
>>> 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).


I've measured that with the timeit module. The time it takes to build a
dict with N entries doesn't seem to be proportional to N, (t-c)/n keeps
increasing. Try this:

import timeit, math

def time(N):
return timeit.Timer("dict([('%%010i'%%i,i) for i in range(%i)])" %
N).timeit(number=5)

c = time(1000)*2-time(2000)

for i in range(1000,1000000,1000):
t = time(i)
print "%5i -> %f (t/n = %f)" % (i,t, (t-c)/i*1000)
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.


Assuming (as I have said already) that you build the dict once, but
call index again and again for every comparison, which is of course
comparing apples with oranges.

Apr 29 '06 #12
nikie wrote:
Steven Bethard wrote:
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.


On my PC, calling index twice is 5 times faster.

But let's just pretend for a moment Python code was compiled and
optimized as well as C code.


Ok, lets get comparable functions by writing them both in Python:

----- temp.py -----
def index(L, item):
for i, x in enumerate(L):
if x == item:
return i
return -1
def a_d_index(L):
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
return a_index, d_index
-------------------

$ python -m timeit -s "import temp; L = ['C', 'A', 'D', 'B']" "a =
temp.index(L, 'A'); d = temp.index(L, 'D'); a < d"
100000 loops, best of 3: 5.73 usec per loop

$ python -m timeit -s "import temp; L = ['C', 'A', 'D', 'B']" "a, d =
temp.a_d_index(L); a < d"
100000 loops, best of 3: 3.75 usec per loop

The a_d_index() function is definitely faster.

I understand your point about comparison time, but in this case we're
just comparing one element strings, so it's not so horrible. Sure, if
you used strings that are more complicated to compare (or worse yet, you
used your own custom objects with __cmp__ methods) you could provoke the
kind of behavior you're looking for.

But in this particular case, there really is some substantial overhead
to Python's iterator protocol, and you can't just ignore that.

Of course the moral of the story (as is the moral of all such threads)
is that if you're really interested in speeding things up you need to
start timing things.

STeVe
Apr 29 '06 #13
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 actually performs pretty well since list.index is implemented in
C.

The obvious (to me) implementation of:
def before(lst, a, b):
for x in lst:
if x == a:
return True
if x == b:
return False

runs about 10-50 times faster than the double index method if I use
psyco. Without psyco, it ends up being faster for the cases where a or
b appears early on in the list, and the other appears towards the end.

Apr 30 '06 #14
Steven Bethard wrote:
nikie wrote:
Steven Bethard wrote:
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.


On my PC, calling index twice is 5 times faster.

But let's just pretend for a moment Python code was compiled and
optimized as well as C code.


Ok, lets get comparable functions by writing them both in Python:


That's changing the subject, and you know that. The OP asked whether
using "L.index('A') < L.index('D')" was a good (pythonic, efficient)
idea. It is. Maybe it wouldn't be efficient if "List.index" was
implemented in python (because, as I have already said in my previous
post, looping through an enumerate-object in python is more complex
than a simple C-loop), but it is actually implemented in C. Even if you
wrote a C function that tried to do all the comparisons in one sweep
through the list, I'm willing to bet it won't be faster than the OP's
suggestion on the average (at least for moderate-sized lists,
otherwise, processing the list in blocks, using the cache more
efficiently might be a good idea).

That's what this thread was all about. Now, I don't really see what you
are trying to say: Are you still trying to convince the OP that he
should write a Python function like one of those you suggested, for
performance reasons? If not, I must have misunderstood your last posts,
and apologize for repeating the obvious ;-)

Apr 30 '06 #15
nikie wrote:
That's what this thread was all about. Now, I don't really see what you
are trying to say: Are you still trying to convince the OP that he
should write a Python function like one of those you suggested, for
performance reasons?


Sure, if it really matters. Code it in C, and you can do better than
..index(). But I don't think it really matters. ;-)

STeVe
Apr 30 '06 #16
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


Just to clarify, because there seems to be some confusion. I would
absolutely go with this approach unless you have profiled and found it
to be a bottleneck. It's clear, concise, and quite fast.

STeVe
Apr 30 '06 #17
Steven Bethard wrote:
Ok, lets get comparable functions by writing them both in Python:


First of all, your functions aren't quite comparable. The first index takes
the value to locate as a variable, while the second has both values
hard-coded as literals. Changing the second one to index2(L, a, b) makes a
slight but not significant difference in the timings.

Secondly, the lists you tested with are artificially short. As you increase
the size of the list, the difference lessens to unimportance:

$ python -m timeit -s "import temp; L = ['x'] * 500 + ['C', 'A', 'D', 'B']"
"a, d = temp.index2(L,'A','D'); a < d"
1000 loops, best of 3: 227 usec per loop

$ python -m timeit -s "import temp; L = ['x'] * 500 + ['C', 'A', 'D', 'B']"
"a = temp.index1(L, 'A'); d = temp.index1(L, 'D'); a < d"
1000 loops, best of 3: 236 usec per loop

Third, the target values are very close together in those lists. If there's
a large difference in their positions, then the "two-in-one-pass" algorithm
becomes much slower:

$ python -m timeit -s "import temp; L = ['C','A'] + ['x'] * 500 + ['D',
'B']" "a = temp.index1(L, 'A'); d = temp.index1(L, 'D'); a < d"
10000 loops, best of 3: 120 usec per loop

$ python -m timeit -s "import temp; L = ['C','A'] + ['x'] * 500 + ['D',
'B']" "a, d = temp.index2(L,'A','D'); a < d"
1000 loops, best of 3: 267 usec per loop

Remember kids:
1. Numbers can show anything
2. Know your data set
3. Premature optimizations are evil
Apr 30 '06 #18
Edward Elliott wrote:
Remember kids:
1. Numbers can show anything
2. Know your data set
3. Premature optimizations are evil


Amen. =)

STeVe
Apr 30 '06 #19
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


Ok, since, as happens some times, the discussion here has gotten
extremely sidetracked from the original question, as a public service ;)
I thought I'd give a brief summary of the options discussed and when
they might be useful:

* The original::

if L.index('A') < L.index('D'):
# do some stuff

If you're doing exactly one comparison, this is probably your best
bet in most cases as .index() is coded in C. It's clear, concise and
correct.

* Justin Azoff's before()::

def before(lst, a, b):
for x in lst:
if x == a:
return True
if x == b:
return False

if before(L, 'A', 'D'):
# do some stuff

You might gain a bit from this version if one of the elements you're
looking for appears early in the list. It only iterates through the
list once, but performs two comparisons each time, so you'll only gain
from it if you comparisons aren't too costly (e.g. you're comparing
single character strings).

* building a dict of indicies::

positions = dict((item, i) for i, item in enumerate(L))

if positions['A'] < positions['D']:
# do some stuff

You'll only get a gain from this version if you need to do several
comparisons instead of just one.
And most importantly, as Edward Elliot put it:

Remember kids:
1. Numbers can show anything
2. Know your data set
3. Premature optimizations are evil
HTH,

STeVe
Apr 30 '06 #20
> * building a dict of indicies::

positions = dict((item, i) for i, item in enumerate(L))

if positions['A'] < positions['D']:
# do some stuff

You'll only get a gain from this version if you need to do several
comparisons instead of just one.


Hi Steven,

your solution may not create the correct answer if an item occurs twice
in the list because the later occurrence overwrites the former during
dict creation:
L = ['C', 'A', 'D', 'B', 'A']
dict((item, i) for i, item in enumerate(L))

{'A': 4, 'C': 0, 'B': 3, 'D': 2}

This gives the impression that 'D' always precedes 'A' which is wrong.

Apr 30 '06 #21
Kay Schluehr wrote:
* building a dict of indicies::

positions = dict((item, i) for i, item in enumerate(L))

if positions['A'] < positions['D']:
# do some stuff

You'll only get a gain from this version if you need to do several
comparisons instead of just one.


Hi Steven,

your solution may not create the correct answer if an item occurs twice
in the list because the later occurrence overwrites the former during
dict creation:
L = ['C', 'A', 'D', 'B', 'A']
dict((item, i) for i, item in enumerate(L))

{'A': 4, 'C': 0, 'B': 3, 'D': 2}

This gives the impression that 'D' always precedes 'A' which is wrong.


Yeah, thanks for the update. I meant to include that too.

STeVe
Apr 30 '06 #22

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by Séb | last post: by
3 posts views Thread by Steve | last post: by
17 posts views Thread by glenn.robinson | last post: by
3 posts views Thread by evandroc | last post: by
2 posts views Thread by shumaker | last post: by
29 posts views Thread by gs | last post: by
7 posts views Thread by Steve | last post: by
7 posts views Thread by Dmitriy V'jukov | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.