Algorithm / function that clusters are based on the weights of each node?
Let's say I have the following:
A 2
B 2
C 2
D 6
E 12
F 3
G 3
I want a function that takes # the groups I want and creates a cluster based on # / weight. So, for example, if the number of groups you want is 4, it might return something like:
(A, B, C), (D), (F, G), (E) A+B+C = 6 D = 6 F + G = 6 E = 12
Is there some algorithm / function that allows me to get this kind of result? Is there a perfect method?
source to share
It is like grouping jobs evenly according to their weights for distribution across n threads.
For small numbers of combinatorial combinations, there might be a way to go, however if you have thousands of jobs to be grouped and spread across hundreds of threads, most definitely combinatorics are not viable.
So my approach would be a much simpler but two-phase solution. The first phase returns an almost perfect result, and the second phase tries to bring it to perfection.
Due to my limited time, I am only currently implementing the first phase and will leave the second phase for the next few days. In the meantime, please study it and try to implement it yourself. yourself.
The idea behind the first phase is very simple.
- Sorting jobs in descending order (so the heavy jobs are loaded first and the lighter are used for balancing)
- Find the lightest piece.
- Insert the first task into the found fragment.
- Find the lightest piece.
- Insert the next task in the found fragment and continue from step 4.
This is how I implemented:
function chunkJobs(js,cc){ // jobs and chunk count as arguments
var init = [...Array(cc)].map(_ => ({"jobs": [], "weight": 0}));
return js.sort((a,b) => b.weight - a.weight)
.reduce(function (cs,j){
var c = cs.reduce((p,c) => p.weight < c.weight ? p : c);
c.jobs.push(j.id);
c.weight += j.weight;
return cs;
}, init);
}
var jobs = [{id: "A", weight: 2},
{id: "B", weight: 2},
{id: "C", weight: 2},
{id: "D", weight: 6},
{id: "F", weight: 3},
{id: "G", weight: 3}],
result = chunkJobs(jobs,3);
console.log(result)
So as you can see the exit
[ { jobs: [ 'G', 'B' ], weight: 5 },
{ jobs: [ 'F', 'A', 'C' ], weight: 7 },
{ jobs: [ 'D' ], weight: 6 } ]
As I mentioned earlier, while this may not be the ideal solution for a large number of ob problems, it will be very close to ideal. For example, let's change the data to have 97 tasks, each with a random weight selected from 0-20, and add 3 very heavy tasks to the mix.{"id": 98, "weight": 113},{"id": 99, "weight": 63},{"id": 100, "weight": 91}
function chunkJobs(js,cc){ // jobs and chunk count as arguments
var init = [...Array(cc)].map(_ => ({"jobs": [], "weight": 0}));
return js.sort((a,b) => b.weight - a.weight)
.reduce(function (cs,j){
var c = cs.reduce((p,c) => p.weight < c.weight ? p : c);
c.jobs.push(j.id);
c.weight += j.weight;
return cs;
}, init);
}
var jobs = [...Array(97)].map((_,i) => ({"id": i+1, "weight": ~~(Math.random()*20)})).concat({"id": 98, "weight": 113},{"id": 99, "weight": 63},{"id": 100, "weight": 91});
result = chunkJobs(jobs,16);
console.log(result);
Something like that
[ { jobs: [ 50, 91, 40, 33, 75, 41, 32 ], weight: 67 },
{ jobs: [ 70, 1, 20, 19, 30, 93, 97 ], weight: 67 },
{ jobs: [ 59, 8, 64, 29, 78, 13, 68 ], weight: 67 },
{ jobs: [ 17, 66, 65, 2, 73, 67, 14 ], weight: 67 },
{ jobs: [ 60, 43, 11, 84, 45, 35, 56 ], weight: 67 },
{ jobs: [ 90, 77, 21, 18, 9, 34, 37 ], weight: 67 },
{ jobs: [ 52, 5, 42, 69, 86, 72, 46 ], weight: 68 },
{ jobs: [ 95, 85, 54, 48, 38, 61, 88 ], weight: 68 },
{ jobs: [ 79, 82, 92, 31, 74, 25, 15 ], weight: 68 },
{ jobs: [ 87, 44, 58, 47, 51, 4 ], weight: 67 },
{ jobs: [ 26, 22, 49, 10, 39, 27, 7, 96, 71, 89, 55, 23 ], weight: 67 },
{ jobs: [ 6, 83, 28, 53, 63, 81, 36 ], weight: 68 },
{ jobs: [ 76, 62, 12, 24, 94, 80, 57 ], weight: 68 },
{ jobs: [ 99, 3, 16 ], weight: 69 },
{ jobs: [ 100 ], weight: 91 },
{ jobs: [ 98 ], weight: 113 } ]
But we will not be satisfied and will continue to capture the result in the second phase. As a hint for the second phase. I don't think we can do anything with threads resolved with one job (like the last two in the above example), but for the rest, it's a dynamic programming approach that is based on replacing jobs between threads according to differences in thread weights is perhaps one good way to start with.
source to share
As a first step, filter out any values greater than 6. But the problem is here.
Since you want the result of adding all the operands in a group to be 6, you cannot get an arbitrary number of groups from a small set with a limited number of operands. You can create various combinations of operands within a group, but this requires that adding all the operands within a group gives 6. The exception, as I see in your example, is from operands that are greater than or equal to 6, these operands form their own groups (e.g. E and D ).
As you have two 2, one 3 and only one 1, how many 7 can you get from these numbers in different combinations using unique operands within each group?
A = 2
B = 2
C = 3
D = 1
A = 2
B = 2
C = 3
D = 1
The above operands <7
Rearrange these operands:
A + B = 4
A + C = 3
A + D = 3
A + B + C = 7
A + B + D = 5
A + C + D = 6
B + C = 5
B + D = 3
B + C + D = 6
C + D = 4
The answer is just one group, when we add all our operands we get 7. This group has three operands A + B + C
.
This is the case in your desired algorithm. Although sometimes you can get an arbitrary number of groups, this is not guaranteed all the time, even if you use operands that were used in other groups, like in the example above, there is only exactly one group when we add all our operands that we get 7.
Furthermore, the addition is commutative (A + B = B + A ), so I have not included B + A
, C + B
, D + C
, ...
Therefore, you can only get one group, given the set above, that when we add all of its operands, we get 7. It's not only the uniqueness of the operands within a group that is problematic; it is also the nature of the limited set of values we have, which prevents us from getting an arbitrary number of groups.
source to share