Simple Problem but tough for me if i want it in linear time
Peter Otten
__peter__ at web.de
Sun Aug 15 09:14:33 EDT 2010
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
More information about the Python-list
mailing list