Simple Problem but tough for me if i want it in linear time

Frederic Rentsch anthra.norell at bluewin.ch
Mon Aug 16 20:40:52 CEST 2010


On Sun, 2010-08-15 at 15:14 +0200, Peter Otten wrote:
> ChrisChia wrote:
> 
> > dataList = [a, b, c, ...]
> > where a, b, c are objects of a Class X.
> > In Class X, it contains self.name and self.number
> > 
> > If i wish to test whether a number (let's say 100) appears in one of
> > the object, and return that object,
> > is that only fast way of solving this problem without iterating
> > through every object to see the number value?
> > 
> > dataList.__contains__ can only check my object instance name...
> > anyone can solve this in linear complexity?
> 
> Well, iteration as in 
> 
> next(item for item in dataList if item.number == 100) 
> 
> is O(n) and list.__contains__() has no magic way to do better. If you need 
> O(1) lookup you can use a dict or collections.defaultdict that maps 
> item.number to a list (or set) of X instances:
> 
> lookup = {}
> for item in dataList:
>     lookup.setdefault(item.number, []).append(item)
> 
> print lookup[100]
> 
> 
> Peter
> 

How about 

>>> [obj for obj in dataList if obj.number == 100]

That should create a list of all objects whose .number is 100. No need
to cycle through a loop. If .number doesn't repeat get your object at
index 0. The approach may seem inefficient for the purpose of extracting
a single item, but the list needs to be gone through in any case and the
list comprehension is surely the most efficient way to do it. 

Frederic





More information about the Python-list mailing list