“Combiner" Class trong một công việc MapReduce

Question

Một Combiner chạy sau khi Mapper và trước khi giảm, nó sẽ nhận như là đầu vào tất cả dữ liệu phát ra bởi các trường hợp Mapper trên một nút cho trước. Sau đó phát ra ra vào Hộp số.

và cũng có thể, Nếu một hàm giảm là cả giao hoán và kết hợp, sau đó nó có thể được sử dụng như một Combiner.

Câu hỏi của tôi là những gì hiện cụm từ "giao hoán và kết hợp" có nghĩa là trong tình huống này ?

Answer 1

Giả sử bạn có một danh sách các số, 1 2 3 4 5 6.

Associative đây có nghĩa là bạn có thể mất hoạt động của bạn và áp dụng nó vào bất kỳ phân nhóm, sau đó áp dụng nó vào kết quả của những và nhận được cùng một câu trả lời:

(1) + (2 + 3) + (4 + 5 + 6) 
    == 
(1 + 2) + (3 + 4) + (5) + (6) 
    == 
... 

Hãy suy nghĩ về dấu ngoặc đơn ở đây khi thực hiện bộ kết hợp.

giao hoán có nghĩa là thứ tự không quan trọng, vì vậy:

1 + 2 + 3 + 4 + 5 + 6 
    == 
2 + 4 + 6 + 1 + 2 + 3 
    == 
... 

Ví dụ, bổ sung, phù hợp với khách sạn này, như đã thấy trước đó. "Tối đa" cũng phù hợp với thuộc tính này ở trên, vì tối đa của giá thầu CPC tối đa (a, b) == tối đa (b, a).

Trung bình là ví dụ không hoạt động: trung vị của trung vị không phải là trung vị thực sự.

---

Đừng quên một thuộc tính quan trọng khác của bộ kết hợp: loại đầu vào cho khóa/giá trị và loại đầu ra của khóa/giá trị cần giống nhau. Ví dụ, bạn không thể lấy một chuỗi: int và trả về một chuỗi: float.

Thông thường, bộ giảm tốc có thể xuất ra một số loại chuỗi thay vì giá trị số, điều này có thể khiến bạn không thể cắm bộ giảm tốc làm bộ kết hợp.

Answer 2

Đối với tính tương đối, giả sử trình giảm tốc của bạn có thể được biểu diễn bằng một hàm (trong thuật ngữ toán học) được gọi là f(). Sau đó giảm tốc của bạn là giao hoán nếu f (a, b) = f (b, a) Ví dụ:

• sum (A, B) cũng giống như sum (B, A)
• xor (A, B) cũng giống như xor (B, A)
• concat (A, B) là không giống như concat (B, A)

Đối associativity, khách sạn sẽ là f (f (a, b), c) = f (a, f (b, c)). Ví dụ:

• (A + B) + C cũng giống như A + (B + C)
• (A - B) - C là không giống như A - (B - C)

Vì vậy, trong bối cảnh Map/Reduce, trình giảm tốc của bạn phải tôn trọng 2 thuộc tính này. Ví dụ, nếu bộ giảm tốc của bạn chỉ làm một tổng() hoặc max(), nó tôn trọng cả hai thuộc tính, nhưng một cái gì đó như mean() hoặc median() thì không, và do đó bạn không thể sử dụng nó như một bộ kết hợp.

Cá nhân tôi thấy tổ hợp như mini-gia giảm mà chạy trong bộ nhớ sau khi giai đoạn bản đồ như một tối ưu hóa để giảm lưu lượng mạng, và giao hoán/associativity thực sự có ý nghĩa nếu bạn nhìn thấy một bản đồ/Giảm theo cách này: