Comment réduire la fonction de travail?
Pour autant que je sache, la fonction reduce prend une liste l et une fonction f. Ensuite, il appelle la fonction f sur les deux premiers éléments de la liste, puis appelle à plusieurs reprises la fonction f avec l'élément de liste suivant et le résultat précédent.
Donc, je définis les fonctions suivantes:
La fonction suivante calcule la factorielle.
def fact(n):
if n == 0 or n == 1:
return 1
return fact(n-1) * n
def reduce_func(x,y):
return fact(x) * fact(y)
lst = [1, 3, 1]
print reduce(reduce_func, lst)
Maintenant, cela ne devrait-il pas me donner ((1! * 3!) * 1!) = 6? Mais, au lieu de cela, il donne 720. Pourquoi 720? Il semble prendre la factorielle de 6 aussi. Mais, j'ai besoin de comprendre pourquoi.
Quelqu'un peut-il expliquer pourquoi cela se produit et une solution de rechange?
Je veux essentiellement calculer le produit des factorielles de toutes les entrées de la liste. Le plan de sauvegarde consiste à exécuter une boucle et à la calculer. Mais, je préférerais utiliser reduce.
8 réponses
Les autres réponses sont géniales. Je vais simplement ajouter un exemple illustré que je trouve assez bon à comprendre reduce():
>>> reduce(lambda x,y: x+y, [47,11,42,13])
113
Sera calculé comme suit:
La façon la plus simple de comprendre reduce () est de regarder son code équivalent Python pur:
def myreduce(func, iterable, start=None):
it = iter(iterable)
if start is None:
try:
start = next(it)
except StopIteration:
raise TypeError('reduce() of empty sequence with no initial value')
accum_value = start
for x in iterable:
accum_value = func(accum_value, x)
return accum_value
Vous pouvez voir qu'il est logique que votre reduce_func() applique la factorielle à l'argument le plus à droite:
def fact(n):
if n == 0 or n == 1:
return 1
return fact(n-1) * n
def reduce_func(x,y):
return x * fact(y)
lst = [1, 3, 1]
print reduce(reduce_func, lst)
Avec cette petite révision, le code produit 6 comme vous vous y attendiez: -)
Vos appels de fonction fact() sur les deux arguments. Vous calculez ((1! * 3!)! * 1!). La solution consiste à ne l'appeler que sur le deuxième argument et à passer reduce() une valeur initiale de 1.
À partir de la documentation Python reduce ,
Reduce (function, sequence) renvoie une seule valeur construite en appelant la fonction (binaire) sur les deux premiers éléments de la séquence, puis sur le résultat et l'élément suivant, et ainsi de suite.
Donc, passer à travers. Il calcule {[1] } des deux premiers éléments, reduce_func(1, 3) = 1! * 3! = 6. Ensuite, il calcule reduce_func du résultat et de l'élément suivant: reduce_func(6, 1) = 6! * 1! = 720.
Vous avez manqué cela, lorsque le résultat du premier appel reduce_func est passé comme entrée à la seconde, elle est factorialisée avant la multiplication.
Ok, compris:
Je dois d'abord mapper les nombres à leurs factorielles, puis appeler reduce avec l'opérateur multiply.
Donc, cela fonctionnerait:
lst_fact = map(fact, lst)
reduce(operator.mul, lst_fact)
Eh Bien, tout d'abord, votre reduce_func n'a pas la structure d'une fois; il ne correspond pas à votre description d'un pli (qui est correcte).
La structure d'un pli est: def foldl(func, start, iter): return func(start, foldl(func, next(iter), iter)
Maintenant, votre Fonction fact ne fonctionne pas sur deux éléments - elle calcule simplement factorielle.
Donc, en somme, vous n'utilisez pas de pli, et avec cette définition de factorielle, vous n'en avez pas besoin.
Si vous voulez jouer avec factoriel, consultez le Y-combinator: http://mvanier.livejournal.com/2897.html
Si vous voulez en savoir plus sur les plis, regardez ma réponse à cette question, qui démontre son utilisation pour calculer les fractions cumulatives: créer un pourcentage cumulatif à partir d'un dictionnaire de données
Vous pouvez également implémenter factoriel en utilisant reduce.
def factorial(n):
return(reduce(lambda x,y:x*y,range(n+1)[1:]))
Réduire exécute la fonction en paramètre#1 successivement par les valeurs fournies par l'itérateur dans le paramètre#2
print '-------------- Example: Reduce(x + y) --------------'
def add(x,y): return x+y
x = 5
y = 10
import functools
tot = functools.reduce(add, range(5, 10))
print 'reduce('+str(x)+','+str(y)+')=' ,tot
def myreduce(a,b):
tot = 0
for i in range(a,b):
tot = tot+i
print i,tot
print 'myreduce('+str(a)+','+str(b)+')=' ,tot
myreduce(x,y)
print '-------------- Example: Reduce(x * y) --------------'
def add(x,y): return x*y
x = 5
y = 10
import functools
tot = functools.reduce(add, range(5, 10))
print 'reduce('+str(x)+','+str(y)+')=' ,tot
def myreduce(a,b):
tot = 1
for i in range(a,b):
tot = tot * i
print i,tot
print 'myreduce('+str(a)+','+str(b)+')=' ,tot
myreduce(x,y)