Python-сообщество

Есть итератор - it, который возвращает некие комбинации элементов списка.
Необходимо найти min(it, key=D) и max(it, key=D) для одного списка, но не хочется два раза проходится по всем комбинациям.
Есть вариант так отсортировать - sorted(it, key=D) и взять 1 и последний элементы. Но это не очень хорошо для большого количества комбинаций. Или искать минимум и максимум вручную.
Какие есть варианты красиво это решить? Академический интерес. Python 3.1.

Dimka665
Какие есть варианты красиво это решить? Академический интерес. Python 3.1.

Хорошая задачка

Функция возвращает кортеж из двух элементов: минимального и максимального из итератора с одним проходом без явного объявления промежуточных переменных

import functools

def minmax( it, key = lambda self: self ):
return functools.reduce( lambda pair, x: (x,x) if pair is None else ( +min(x, pair, key=key), max(x, pair, key=key) ), it, None )

print( minmax(range(100), key = lambda s: -s ) )
#вернет
#(99, 0)

Упс… там случайно знак + прокрался перед функцией min

По-моему вручную с промежуточными переменными будет гораздо более читабельно.

Приведите рабочий пример этой функции, чтобы можно было начать дискуссию :)

С удовольствием:

import functools
from time import time

def minmax1(iterable):
    minm = None
    maxm = None
    for item in iterable:
       if maxm is None or item > maxm:
          maxm = item
       if minm is None or item < minm:
          minm = item
    return minm, maxm

def minmax( it, key = lambda self: self ):
    return functools.reduce( lambda pair, x: (x,x) if pair is None else ( +min(x, pair[0], key=key), max(x, pair[1], key=key) ), it, None )

for fun in minmax, minmax1:
    start = time()
    print "result:", fun(xrange(2000000)), 'time spent:', time() - start

Отредактировано (Авг. 27, 2010 17:19:34)

Кстати, по производительности очень интересно себя показали двупроходный вариант и вариант с сортировкой:

def minmax2(iterable):
    return min(iterable), max(iterable)

def minmax3(iterable):
    isorted = sorted(iterable)
    return isorted[0], isorted[-1]

Отредактировано (Авг. 27, 2010 17:53:36)

import functools
from time import time

def minmax( it ):
def cmp( pair, x ):
if x < pair: return x, pair
if x > pair: return pair, x
return pair
return functools.reduce( cmp, it, 2*(it,) ) if it else None


def minmax1(iterable):
minm = None
maxm = None
for item in iterable:
if maxm is None or item > maxm:
maxm = item
if minm is None or item < minm:
minm = item
return minm, maxm

for fun in minmax, minmax1:
start = time()
print( “result for {0}: {1}, ‘time spent:{2}”.format( fun.__name__, fun(range(2000000)), time() - start ))

Я чуточку подправил свою функцию (убрал вызов встроенных функций min и max, ключ сравнения и для лямбды сделал явную функцию для читабельности).
Второе, я использую питон 3 (это тоже может влиять)
Я так же поменял порядок выполнения функций (сначала ваша, потом моя). Это влияет на скорость выполнения (не очень сильно) из-за кэширования данных интерпретатором.

Результат на моей машине:

result for minmax1: (0, 1999999), ’time spent:0.561000108719
result for minmax: (0, 1999999), 'time spent:0.771000146866

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

Для любителей лямбды: Читайте прекрасный рецепт по использованию лямбда в Питоне от Fredrik Lundh здесь: http://docs.python.org/howto/functional.html#small-functions-and-the-lambda-expression
Мой вольный перевод:
1. Напишите лямбда функцию
2. Напишите комментарий, объясняющий что за хренотень она делает.
3. Поизучайте комментарий какое-то время и подумайте об имени, которое бы показывало сущность коментария
4. Преобразуйте вашу лямбду в обычную функцию, используя это имя
5. Удалите комментарий

PS: О, вы поступили прям в соответствии с этим рецептом :)

Отредактировано (Авг. 27, 2010 18:12:42)