Come funziona la funzione di riduzione?

Question

Per quanto ho capito, la funzione di riduzione prende una lista l e una funzione f. Quindi, chiama la funzione f sui primi due elementi dell'elenco e quindi chiama ripetutamente la funzione f con l'elemento dell'elenco successivo e il risultato precedente.

Così, ho definire le seguenti funzioni:

La seguente funzione calcola il fattoriale.

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) 

Ora, questo non dovrebbe darmi ((1! * 3!) * 1!) = 6? Ma, invece, dà 720. Perché 720? Sembra prendere anche il fattoriale di 6. Ma, ho bisogno di capire perché.

Qualcuno può spiegare perché questo accada e una soluzione?

Principalmente voglio calcolare il prodotto di fattoriali di tutte le voci nell'elenco. Il piano di backup è di eseguire un ciclo e calcolarlo. Ma preferirei usare ridurre.

Answer 1

Ok, ce l'ha:

ho bisogno di mappare i numeri per i loro fattoriali e poi chiamare a ridurre con operatore si moltiplicano.

Quindi, questo dovrebbe funzionare:

lst_fact = map(fact, lst) 
reduce(operator.mul, lst_fact) 

Answer 2

La funzione chiama fact() su entrambi gli argomenti. Stai calcolando ((1! * 3!)! * 1!). La soluzione è chiamare solo solo sul secondo argomento, e passare reduce() un valore iniziale di 1.

Answer 3

Dal Python reduce documentation,

ridurre (funzione, sequenza) restituisce un singolo valore ottenuto invocando la (binaria) sui primi due elementi della sequenza, quindi sul risultato e sull'elemento successivo, e così via.

Quindi, passando. Calcola reduce_func dei primi due elementi, reduce_func(1, 3) = 1! * 3! = 6. Quindi, calcola reduce_func del risultato e l'elemento successivo: reduce_func(6, 1) = 6! * 1! = 720.

Si è perso che, quando il risultato della prima chiamata reduce_func viene passato come input al secondo, viene fattorizzato prima della moltiplicazione.

Answer 4

Beh, prima di tutto, il tuo reduce_func non ha la struttura di una piega; non corrisponde alla descrizione di una piega (che è corretta).

La struttura di una piega è: def foldl(func, start, iter): return func(start, foldl(func, next(iter), iter)

Ora, la funzione fact non opera su due elementi - calcola solo fattoriale.

Quindi, in sintesi, non stai usando una piega, e con quella definizione di fattoriale, non è necessario.

Se si vuole giocare con fattoriale, controlla la y-Combinator: http://mvanier.livejournal.com/2897.html

Se volete conoscere le pieghe, guarda la mia risposta a questa domanda, che dimostra il suo utilizzo per calcolare le frazioni cumulativi : creating cumulative percentage from a dictionary of data

Answer 5

Il modo più semplice per capire ridurre() è quello di guardare al suo puro Python codice equivalente:

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 

Si può vedere che ha senso solo per il vostro reduce_func() per applicare il fattoriale per l'argomento più a destra:

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) 

Con quella piccola revisione, il codice produce come vi aspettavate :-)

Answer 6

Si potrebbe anche implementare fattoriale usando ridurre.

def factorial(n): 
    return(reduce(lambda x,y:x*y,range(n+1)[1:])) 

Answer 7

Le altre risposte sono fantastiche. Io semplicemente aggiungo un esempio illustrato che trovo abbastanza bene da capire reduce():

>>> reduce(lambda x,y: x+y, [47,11,42,13]) 
113 

sarà calcolata come segue:

(Source) (mirror)

Answer 8

Ridurre esegue la funzione nel parametro # 1 successivamente attraverso i valori forniti dall'iteratore nel parametro #

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)