Определение минимума списка из n элементов - PullRequest
4 голосов
/ 03 июля 2010

У меня возникли проблемы при разработке алгоритма для определения минимума списка из n элементов. Дело не в том, чтобы найти минимум массива длины n, это просто:

min = A[0]
for i in range(1, len(A)):
    if min > A[i]: min = A[i]
print min

Но мой список содержит объекты:

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

И по той же классификации | тип "объекты У меня есть m элементов, и я хочу найти минимальный элемент той же" классификации | напечатайте ', сравнивая разницу между первым и последним.

Пример:

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])
list = [obj1, obj2, obj3, obj4, obj5, obj6, obj7]

Итак, мне нужен алгоритм для определения минимумов списка:

А | x -> Объект (['A', 'x', 6, 10])

B | z -> Объект (['B', 'z', 2, 15])

А | y -> Объект (['A', 'y', 5, 20])

Спасибо!

Ответы [ 3 ]

7 голосов
/ 03 июля 2010
filtered = [obj for obj in lst if obj.classification == 'A' and obj.type = 'x']
min(filtered, key=lambda x: x.last - x.first)

Примечание: не называйте вашу переменную list: она встроена в тени.

2 голосов
/ 03 июля 2010

Вот простой понятный динамический процедурный способ сделать это:

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).

1 голос
/ 03 июля 2010
import itertools 
group_func = lambda o: (o.classification, o.type)
map(lambda pair: (pair[0], min(pair[1], key=lambda o: o.last - o.first)),
    itertools.groupby(sorted(l, key=group_func), group_func))

group_func возвращает ключ кортежа, содержащий классификацию объекта, затем введите (например, ('A', 'x')). Сначала используется для сортировки списка l (sorted вызов). Затем мы вызываем groupby в отсортированном списке, используя group_func для группировки в подсписки. Каждый раз, когда ключ меняется, у нас появляется новый подсписок. В отличие от SQL, groupby требует, чтобы список был предварительно отсортирован по тому же ключу. map принимает вывод функции groupby. Для каждой группы map возвращает кортеж. Первый элемент - pair[0], который является ключом ('A', 'x'). Второй - это минимум группы (pair[1]), определяемый клавишей last - first.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...