Tính kết hợp & giao hoán

Phép toán kết hợp thỏa $(a\odot b)\odot c=a\odot (b\odot c)$, cho phép đổi cách nhóm. Giao hoán thỏa $a\odot b=b\odot a$, cho phép đổi thứ tự. Hai tính chất khác nhau. Trong số thực tính bằng máy, sai số làm phép cộng không luôn kết hợp chính xác.

Lĩnh vực: Tính toán phân tán

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Nghĩa ở lĩnh vực khácNguồn kết hợp · Cơ học, nhiệt, điện từ và lượng tử

Bài giảng dùng khái niệm này

• MapReduce & xử lý dữ liệu lớnGiải thuật dữ liệu

Giải thích kỹ thuật

Gom cục bộ cần giữ đủ thông tin. Tính kết hợp cho phép đổi cách nhóm, còn tính giao hoán cho phép đổi thứ tự. Nối chuỗi kết hợp nhưng không giao hoán. Khi tính trên máy, làm tròn số thực có thể phá kết hợp chính xác của phép cộng.

Muốn tính trung bình , gửi cặp (tổng,số lượng), cộng hai thành phần rồi chia ở cuối. Trung bình các trung bình không giữ đủ thông tin nếu kích thước nhóm khác nhau.

Ví dụ

Cộng số nguyên kết hợp và giao hoán. Nối chuỗi kết hợp nhưng không giao hoán: "Ab" khác "ba".

Khi nào cần dùng?

Hiểu khi nào có thể gom cục bộ kết quả và thiết kế Combine.

Câu hỏi ôn lại

Lấy trung bình hai trung bình có luôn cho trung bình chung không?

Xem đáp án

Không. Cần tính cả số phần tử của mỗi nhóm để lấy trung bình có trọng số.

Thuật ngữ liên quan

• Tính toán phân tán
• Hàm trong lập trình
• Kỳ vọng