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

[Frederic Rentsch]

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