Вот простой понятный динамический процедурный способ сделать это:
class Object:
def __init__(self, somelist):
self.classification = somelist[0] # String
self.type = somelist[1] # String
self.first = somelist[2] # Integer
self.last = somelist[3] # Integer
def weight(self):
return self.last - self.first
def __str__(self):
return "Object(%r, %r, %r, %r)" % (self.classification, self.type, self.first, self.last)
__repr__ = __str__
obj1 = Object(['A', 'x', 4, 17])
obj2 = Object(['A', 'y', 5, 20])
obj3 = Object(['B', 'z', 10, 27])
obj4 = Object(['B', 'z', 2, 15])
obj5 = Object(['B', 'z', 20, 40])
obj6 = Object(['A', 'x', 6, 10])
obj7 = Object(['A', 'x', 2, 9])
olist = [obj1, obj2, obj3, obj4, obj5, obj6, obj7]
mindict = {}
for o in olist:
key = (o.classification, o.type)
if key in mindict:
if o.weight() >= mindict[key].weight():
continue
mindict[key] = o
from pprint import pprint
pprint(mindict)
и вот вывод:
{('A', 'x'): Object('A', 'x', 6, 10),
('A', 'y'): Object('A', 'y', 5, 20),
('B', 'z'): Object('B', 'z', 2, 15)}
Примечание: __str__
, __repr__
и pprint
просто для того, чтобы получить шикарную распечатку, это не обязательно.Также приведенный выше код работает без изменений на Python 2.2 до 2.7.
Время выполнения : O (N), где N - количество объектов в списке.Решения, которые сортируют объекты, в среднем O (N * log (N)).Другим решением является O (K * N), где K <= N - количество уникальных (классификация, тип) ключей, полученных из объектов. </p>
Используется дополнительная память : только O(К).Другие решения, кажется, O (N).