Python: Обработка исключений при сортировке

Question

У меня есть список объектов, которые мне нужно отсортировать в соответствии с key function. Проблема в том, что некоторые элементы из моего списка могут «устаревать», а список сортируется. Когда ключевая функция вызывается на таком истекшем элементе, она выходит из строя с исключением.

В идеале, что бы мне хотелось, это способ сортировки моего списка с помощью ключевой функции, так что при возникновении ошибки при вызове ключевой функции для элемента этот элемент исключается из результата сортировки.

Моя проблема может быть восстановлена ​​с помощью следующего примера: Предположим, у меня есть два класса, Good и Bad:

class Good(object): 
    def __init__(self, x): 
     self.x = x 
    def __repr__(self): 
     return 'Good(%r)' % self.x 

class Bad(object): 
    @property 
    def x(self): 
     raise RuntimeError() 
    def __repr__(self): 
     return 'Bad' 

Я хочу, чтобы отсортировать экземпляры этих классов в соответствии с их x собственности. Например .:

>>> sorted([Good(5), Good(3), Good(7)], key=lambda obj: obj.x) 
[Good(3), Good(5), Good(7)] 

Теперь, когда есть в моем списке Bad, сортировка не удается:

>>> sorted([Good(5), Good(3), Bad()], key=lambda obj: obj.x) 
... RuntimeError 

Ищу волшебную функцию func, что сортирует список в соответствии с ключевой функцией, а просто игнорирует элементы, для которых функциональная клавиша возникает ошибка:

>>> func([Good(5), Good(3), Bad()], key=lambda obj: obj.x) 
[Good(3), Good(5)] 

самый Pythonic способ достижения этой цели?

Answer 1

Поскольку результат ключевой функции может меняться со временем, и большинство вариантов сортировки, вероятно, принимают детерминированную ключевую функцию, вероятно, лучше всего выполнять только одну ключевую функцию один раз на объект, чтобы обеспечить упорядоченное и аварийное окончательный список.

def func(seq, **kargs): 
    key = kargs["key"] 
    stored_values = {} 
    for item in seq: 
     try: 
      value = key(item) 
      stored_values[item] = value 
     except RuntimeError: 
      pass 
    return sorted(stored_values.iterkeys(), key=lambda item: stored_values[item]) 


print func([Good(5), Good(3), Bad()], key=lambda obj: obj.x) 

Результат:

[Good(3), Good(5)] 

Answer 2

Каждый алгоритм сортировки, который я знаю, не выбрасывает некоторые значения, потому что они устарели или что-то в этом роде. Задача алгоритма сортировки - сортировать список, сортировать его быстро, все остальное постороннее, конкретная задача.
Итак, я бы написал эту магическую функцию сам. Он выполнил бы сортировку в два этапа: сначала он будет фильтровать список, оставив только значения Good, а затем отсортировать полученный список.

Answer 3

Я сделал это один раз с объединением. Mergesort делает это относительно простым, чтобы исключить ненужные значения.

Проект, который я сделал, находится в http://stromberg.dnsalias.org/~dstromberg/equivalence-classes.html#python-3e. Не стесняйтесь совершать набеги на идеи или вынимать из нее код; это бесплатно, как в речи (GPLv2 или позже, по вашему выбору).

Сортировка этого кода должна почти делать то, что вы хотите, за исключением того, что сортирует список с дубликатами в список списков, где каждый подсписчик имеет равные значения. Эта часть может быть или не быть полезной для вас.

У меня есть более простой слияние (он не делает дубликаты ведра, но он не имеет дело с понижением значений не более длинного значения) на http://stromberg.dnsalias.org/svn/sorts/compare/trunk/. Файл является .m4, но не позволяйте этому обмануть вас - это действительно чистый питон или cython, автогенерируемый из того же .m4-файла.

Answer 4

Если элементы списка могут перейти от хорошего к плохому во время сортировки, то нет ничего, что вы можете сделать. В key s вычисляется только один раз перед сортировкой, поэтому любое изменение в ключе будет невидимым для функции сортировки:

>>> from random import randrange 
>>> values = [randrange(100) for i in range(10)] 
>>> values 
[54, 72, 91, 73, 55, 68, 21, 25, 18, 95] 
>>> def k(x): 
... print x 
... return x 
... 
>>> values.sort(key=k) 
54 
72 
91 
73 
55 
68 
21 
25 
18 
95 

(Если ключ оценивал много раз в течение рода, вы бы увидеть номера напечатанных многие раз).