Найти - Пользователи
Полная версия: Клонирование итератора
Начало » Python для экспертов » Клонирование итератора
1 2 3 4
Dimka665
Есть итератор - it, который возвращает некие комбинации элементов списка.
Необходимо найти min(it, key=D) и max(it, key=D) для одного списка, но не хочется два раза проходится по всем комбинациям.
Есть вариант так отсортировать - sorted(it, key=D) и взять 1 и последний элементы. Но это не очень хорошо для большого количества комбинаций. Или искать минимум и максимум вручную.
Какие есть варианты красиво это решить? Академический интерес. Python 3.1.
PooH
Dimka665
Какие есть варианты красиво это решить? Академический интерес. Python 3.1.
Два аккумулятора minValue и maxValue, первый инициализируем заведомо большим, второй заведомо меньшим значением. На каждой итерации сравниваем и соответственно уменьшаем первый/увеличиваем второй. Время линейное, память константная. Это в теории. На практике на не слишком длинных последовательностях sorted на C может оказаться быстрее сравнений на питоне.
Isem
Хорошая задачка

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

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)
Isem
Упс… там случайно знак + прокрался перед функцией min
Ed
По-моему вручную с промежуточными переменными будет гораздо более читабельно.
Isem
Приведите рабочий пример этой функции, чтобы можно было начать дискуссию :)
Ed
С удовольствием:
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
Результат на моей машине:
result: (0, 1999999) time spent: 6.88936591148
result: (0, 1999999) time spent: 0.646008014679

Вердикт - нечитаемо и тормозно :)
Лямбда - зло.
Ed
Кстати, по производительности очень интересно себя показали двупроходный вариант и вариант с сортировкой:
def minmax2(iterable):
return min(iterable), max(iterable)

def minmax3(iterable):
isorted = sorted(iterable)
return isorted[0], isorted[-1]
Общий результат для итератора длиной 2000000 такой:
result: (0, 1999999) time spent: 6.82379508018 - minmax
result: (0, 1999999) time spent: 0.649875879288 - minmax1
result: (0, 1999999) time spent: 0.331388950348 - minmax2
result: (0, 1999999) time spent: 0.218975067139 - minmax3
Isem
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

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

PS: О, вы поступили прям в соответствии с этим рецептом :)
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB