Determinig position of a element in a list

Graham Breed usenet at microtonal.co.uk
Tue Aug 26 00:56:43 CEST 2003


Przemo Drochomirecki wrote:
> Hello,
> i'm wondering if there is any tricky way for doing following thing:
>     A - list of distinct integers  (e.x. A = [1,3,7,11,14,15])
>     very fast function determinig position of number x in list A
>     or -1 if x doesnt belong to A
> Operator IN returns only false/true values
> i can implement function index (e.x. index(5,A) = -1, index(7,A) = 2), but
> maybe there's is simpler(builtin?) solution

Yes, there is a builtin solution

Python 2.2.2 (#2, Feb  5 2003, 10:40:08)
[GCC 3.2.1 (Mandrake Linux 9.1 3.2.1-5mdk)] on linux-i386
Type "help", "copyright", "credits" or "license" for more information.
 >>> [1,3,7,11,14,15].index(7)
2
 >>> [1,3,7,11,14,15].index(5)
Traceback (most recent call last):
   File "<stdin>", line 1, in ?
ValueError: list.index(x): x not in list
 >>>

All you have to do is handle the exception instead of testing for -1.  I 
wouldn't count it as "very fast" though because it has to do a linear 
search.  If you need to do this a lot with a list that doesn't change, 
it might be worth converting it to a dictionary

 >>> original = [1,3,5,6,11,14,15]
 >>> reverse_lookup = {}
 >>> for i in range(len(original)):
...   reverse_lookup[original[i]] = i
...
 >>> reverse_lookup.get(7, -1)
-1
 >>> reverse_lookup.get(5, -1)
2

but if the list's big enough that speed's a problem, the extra memory 
usage might be as well.  Alternatively, if (as in the example) the 
integers are in order, a binary search will be more efficient than a 
linear one.  Hopefully, you'll find you don't need it to be very fast at 
all.


                       Graham





More information about the Python-list mailing list