Tôi biết câu hỏi này là cũ, nhưng đây là cách nó có thể được thực hiện hiệu quả.
Tất cả mã hiện tại bằng Python mà tôi chắc chắn sẽ đủ dễ dàng dịch sang C++.
- Có thể bạn sẽ muốn di chuyển từ việc sử dụng số nguyên cho vector đặc trưng để sử dụng mảng bit, vì số nguyên được sử dụng sẽ cần 500 bit (không phải là vấn đề trong Python)
- Hãy cập nhật lên C++ bất kỳ ai.
- Distribute to các nút phạm vi của họ kết hợp (
start số và length để xử lý), các thiết lập của items từ tổ hợp để được lựa chọn, và số lượng, k, các mặt hàng để lựa chọn.
- Khởi tạo từng nút bằng cách tìm kết hợp bắt đầu trực tiếp từ
start và items.
- Chạy từng nút bằng cách thực hiện công việc cho kết hợp đầu tiên sau đó lặp qua các kết hợp còn lại của nó và thực hiện công việc liên quan.
Thực hiện làm như bạn đề nghị tìm n-chọn-k và chia nó thành các dãy - trong trường hợp của bạn 500-Chọn-5 được, như bạn nói, 255.244.687.600 như vậy, cho node = 0-9 bạn phát hành:
(start=node*25524468760, length=25524468760, items=items, k=5)
thực hiện bạn có thể tìm thấy sự kết hợp bắt đầu trực tiếp (không lặp lại) bằng cách sử dụng hệ thống số tổ hợp và tìm ra đại diện nguyên của vector đặc trưng của sự kết hợp (được sử dụng cho các lần lặp trong) cùng một lúc:
def getCombination(index, items, k):
'''Returns (combination, characteristicVector)
combination - The single combination, of k elements of items, that would be at
the provided index if all possible combinations had each been sorted in
descending order (as defined by the order of items) and then placed in a
sorted list.
characteristicVector - an integer with chosen item's bits set.
'''
combination = []
characteristicVector = 0
n = len(items)
nCk = 1
for nMinusI, iPlus1 in zip(range(n, n - k, -1), range(1, k + 1)):
nCk *= nMinusI
nCk //= iPlus1
curIndex = nCk
for k in range(k, 0, -1):
nCk *= k
nCk //= n
while curIndex - nCk > index:
curIndex -= nCk
nCk *= (n - k)
nCk -= nCk % k
n -= 1
nCk //= n
n -= 1
combination .append(items[n])
characteristicVector += 1 << n
return combination, characteristicVector
Biểu diễn số nguyên của vectơ đặc trưng có k bit được đặt ở vị trí của các mục tạo nên tổ hợp.
Thực hiện bạn có thể sử dụng Hack Gosper để lặp với vector đặc trưng tiếp theo cho sự kết hợp trong hệ thống cùng một số (sự kết hợp tiếp theo sẽ xuất hiện trong một danh sách được sắp xếp đảo ngược được sắp xếp kết hợp tương đối so với items) và, cùng một lúc, hãy tạo kết hợp:
def nextCombination(items, characteristicVector):
'''Returns the next (combination, characteristicVector).
combination - The next combination of items that would appear after the
combination defined by the provided characteristic vector if all possible
combinations had each been sorted in descending order (as defined by the order
of items) and then placed in a sorted list.
characteristicVector - an integer with chosen item's bits set.
'''
u = characteristicVector & -characteristicVector
v = u + characteristicVector
if v <= 0:
raise OverflowError("Ran out of integers") # <- ready for C++
characteristicVector = v + (((v^characteristicVector) // u) >> 2)
combination = []
copiedVector = characteristicVector
index = len(items) - 1
while copiedVector > 0:
present, copiedVector = divmod(copiedVector, 1 << index)
if present:
combination.append(items[index])
index -= 1
return combination, characteristicVector
Lặp lại số này length-1 lần (vì bạn đã tìm thấy số đầu tiên trực tiếp).
Ví dụ:
Năm nút xử lý 7-chọn-3 chữ cái:
>>> items = ('A','B','C','D','E','F','G')
>>> k = 3
>>> nodes = 5
>>> n = len(items)
>>> for nmip1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)):
... n = n * nmip1 // i
...
>>> for node in range(nodes):
... length = n // nodes
... start = node * length
... print("Node {0} initialised".format(node))
... combination, cv = getCombination(start, items, k)
... doWork(combination)
... for i in range(length-1):
... combination, cv = nextCombination(items, cv)
... doWork(combination)
...
Node 0 initialised
Doing work with: C B A
Doing work with: D B A
Doing work with: D C A
Doing work with: D C B
Doing work with: E B A
Doing work with: E C A
Doing work with: E C B
Node 1 initialised
Doing work with: E D A
Doing work with: E D B
Doing work with: E D C
Doing work with: F B A
Doing work with: F C A
Doing work with: F C B
Doing work with: F D A
Node 2 initialised
Doing work with: F D B
Doing work with: F D C
Doing work with: F E A
Doing work with: F E B
Doing work with: F E C
Doing work with: F E D
Doing work with: G B A
Node 3 initialised
Doing work with: G C A
Doing work with: G C B
Doing work with: G D A
Doing work with: G D B
Doing work with: G D C
Doing work with: G E A
Doing work with: G E B
Node 4 initialised
Doing work with: G E C
Doing work with: G E D
Doing work with: G F A
Doing work with: G F B
Doing work with: G F C
Doing work with: G F D
Doing work with: G F E
>>>
Không có nhiều kinh nghiệm trong lĩnh vực này, nhưng nó có vẻ như một vấn đề mà google MapReduce có thể là áp dụng cho. –
MapReduce không liên quan ở đây, vì câu hỏi là về phần "Bản đồ" của thuật ngữ: Làm thế nào để ánh xạ hiệu quả một vấn đề không gian n-select-k vào các phần m mà không cần một nhà phân phối trung tâm. –
@Reyzooti: Do đó "không có nhiều kinh nghiệm". Thật vui khi được sửa chữa. –