HowTo Search in nested lists

Rich Krauter rmkrauter at yahoo.com
Fri Jan 30 19:50:53 CET 2004


I'm still learning too; this is how I would do it, but
there are probably better ways:

If you require the data structure to be lists, and the
lists are relatively small, this approach is probably
ok -  it returns a list of tuples of indices where the
value is found:

Suppose you were trying to find the location of the
value 5:
a = [1,2,3]
b = [4,5,6]
c = [7,8,9]
t = [a,b,c]
>>> [(x,y) for (x,n) in enumerate(t) for y in
range(len(n)) if n[y] == 5]
[(1,1)]

You can replace the 5 in the above expression with
whatever you want to search for.


If you need to do many look-ups, where you are asking
"Does this value occur at any position in my array?",
and the lists are very, very large, I would consider a
different way using dicts instead of lists; looping
through the lists every time you need to check if a
value is present is not very efficient.

Build up a dict out of the table, using tuples of
indices as keys 
d = {}
d[(0,0)] = 1
d[(1,0)] = 2 
# etc

# build up the "reverse" dict

dd = {}
for k,v in d.items():
     dd.setdefault(v,[]).append(k)


(You can just make dd{} directly from original table
using some other method, without the intermediate step
of making d{}; that step doesn't really provide any
benefit to you, other than allowing you to build up
dd{} using above snippet.)
  
Then you can look up a table value using tuples of
indices as keys to d{}.  Also, you can check for
membership and/or original index locations of a value
by using it as a key to dd{}. The look-up should be
much faster than the list comprehension method for
very large lists.

Rich

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free web site building tool. Try it!
http://webhosting.yahoo.com/ps/sb/




More information about the Python-list mailing list