Chức năng giảm hoạt động như thế nào?

Question

Theo như tôi hiểu, hàm reduce lấy một danh sách l và một hàm f. Sau đó, nó gọi hàm f trên hai phần tử đầu tiên của danh sách và sau đó liên tục gọi hàm f với phần tử danh sách tiếp theo và kết quả trước đó.

Vì vậy, tôi xác định các chức năng sau:

Hàm sau đây tính giai thừa.

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) 

Bây giờ, điều này có nên cho tôi ((1! * 3!) * 1!) = 6 không? Nhưng thay vào đó, nó cung cấp cho 720. Tại sao lại là 720? Dường như có giai thừa của 6. Nhưng, tôi cần hiểu tại sao.

Ai đó có thể giải thích lý do tại sao điều này xảy ra và xung quanh công việc?

Tôi về cơ bản muốn tính sản phẩm giai thừa của tất cả các mục nhập trong danh sách. Kế hoạch sao lưu là chạy vòng lặp và tính toán nó. Nhưng, tôi thích sử dụng giảm.

Answer 1

Ok, đã nhận được:

Tôi cần ánh xạ số tới giai thừa của họ trước rồi gọi giảm bằng toán tử nhân.

Vì vậy, điều này sẽ làm việc:

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

Answer 2

Chức năng của bạn gọi fact() trên cả hai đối số. Bạn đang tính toán ((1! * 3!)! * 1!). Cách giải quyết là để chỉ gọi nó về chỉ số thứ hai, và vượt qua reduce() một giá trị ban đầu của 1.

Answer 3

Từ Python reduce documentation,

giảm (chức năng, trình tự) trả về một giá trị duy nhất được xây dựng bằng cách gọi (nhị phân) chức năng trên hai mục đầu tiên của chuỗi, sau đó trên kết quả và các mục tiếp theo, và như vậy.

Vì vậy, hãy xem qua. Nó tính toán reduce_func của hai phần tử đầu tiên, reduce_func(1, 3) = 1! * 3! = 6. Sau đó, nó tính toán reduce_func kết quả và mục tiếp theo: reduce_func(6, 1) = 6! * 1! = 720.

Bạn đã bỏ lỡ điều đó, khi kết quả của cuộc gọi reduce_func đầu tiên được chuyển làm đầu vào cho lần thứ hai, nó được sắp xếp trước khi nhân lên.

Answer 4

Vâng, trước hết, bạn reduce_func không có cấu trúc của một lần; nó không phù hợp với mô tả của bạn về một lần (đó là chính xác).

Cấu trúc của một lần là: def foldl(func, start, iter): return func(start, foldl(func, next(iter), iter)

Bây giờ, chức năng fact của bạn không hoạt động trên hai yếu tố - nó chỉ tính toán thừa.

Vì vậy, tổng hợp, bạn không sử dụng nếp gấp và với định nghĩa giai thừa đó, bạn không cần phải làm như vậy.

Nếu bạn muốn chơi xung quanh với giai thừa, hãy kiểm tra y-Combinator: http://mvanier.livejournal.com/2897.html

Nếu bạn muốn tìm hiểu về nếp gấp, nhìn vào câu trả lời của tôi cho câu hỏi này, trong đó chứng tỏ việc sử dụng nó để tính toán phân số tích lũy : creating cumulative percentage from a dictionary of data

Answer 5

cách dễ nhất để hiểu giảm() là nhìn vào tinh khiết mã tương đương Python của nó:

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 

Bạn có thể thấy rằng nó chỉ có ý nghĩa cho reduce_func của bạn() để áp dụng giai thừa cho lập luận ngoài cùng bên phải:

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) 

Với phiên bản nhỏ, mã sản xuất như bạn mong đợi :-)

Answer 6

Bạn cũng có thể thực hiện giai thừa sử dụng giảm.

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

Answer 7

Các câu trả lời khác rất tuyệt. Tôi chỉ đơn giản là sẽ thêm một ví dụ minh họa mà tôi tìm thấy khá tốt để hiểu reduce():

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

sẽ được tính như sau:

(Source) (mirror)

Answer 8

Giảm thực thi hàm trong tham số # 1 liên tiếp thông qua các giá trị được cung cấp bởi trình lặp trong tham số # 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)