LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#51 February 2 2011

Joe
Member

Re: Exercise - Team Balancing

Are you benchmarking on separate computers?

#52 February 3 2011

arithma
Member

Re: Exercise - Team Balancing

I guess we are. I am only interested in the notion of performance rather than concrete comparison. As in does it take milliseconds, tens, hundreds of milliseconds, seconds, minutes, hours, does not halt in the foreseeable future.

@MSD: This is the article I was referring to earlier. I hope you'd post the difference between the partitions rather than the percentages. I will post the partition tonight.

As I said before (I think) this algorithm I am using now needs my interference for different problem sizes because I need to manually tune some iterations to get reasonable results. I will post something soon. Do note however that I lost my obsession with this problem, thankfully.

Last edited by arithma (February 3 2011)

#53 February 3 2011

Joe
Member

Re: Exercise - Team Balancing

arithma wrote:

I guess we are. I am only interested in the notion of performance rather than concrete comparison. As in does it take milliseconds, tens, hundreds of milliseconds, seconds, minutes, hours, does not halt in the foreseeable future.

Then maybe it'd be nice if you could print your specs. Again, not for comparison (you run at the milliseconds level), but to give a general idea. After all there is a wide selection of processors available today, ranging from mobiles ARM or Intel Atom, to 4 core processors like the i7 or the Quad Core.

Knowing your processing power would help us get a better idea of your times.

#54 February 3 2011

MSD
Member

Re: Exercise - Team Balancing

Difference is 1840.
@arithma, could you post your results?

#55 February 3 2011

arithma
Member

Re: Exercise - Team Balancing

Sure, I'll post it at night.

#56 February 3 2011

arithma
Member

Re: Exercise - Team Balancing

Here we go. Got it down to 129.

``````8222133 237176 8696668 966519 9612253 1648267 10606561 1803468 10908201 2182364 11330586 3177323 12884937 3861007 13587405 4222232 14496970 4438936 15038036 6502405 16134598 6540726 16157036 7807041 16516868
54122 8330499 357562 8845574 1550413 10248995 1686585 10764907 1959387 11022305 2598634 12616905 3632802 13238860 4009062 13630745 4436305 14675376 5783323 15388684 6508508 16149803 7087411 16263071 8156271
129
1397*1000000/2337910 = 597microseconds``````

Note that the really small times are due to the fact that it's an assisted algorithm. I had to run it 9 times to get a decent result.

By the way, the 2337910 corresponds to my CPU frequency. You can get it by calling the Win32 API function: QueryPerformanceFrequency. All the other factors in a PC are not relevant since the problem size does not touch RAM.

Last edited by arithma (February 3 2011)

#57 February 3 2011

MSD
Member

Re: Exercise - Team Balancing

Are these the solution results? Is the first line the first team and the second line the second? I cannot see the 129 difference you mentioned.

#58 February 4 2011

arithma
Member

Re: Exercise - Team Balancing

@MSD: Good eye. I was outputting the wrong array. Here is the real thing with better results (difference of 5):

``````1686585, 1803468, 1959387, 2182364, 3177323, 3632802, 4222232, 4438936, 5783323, 6502405, 6508508, 7087411, 7807041, 8222133, 8696668, 8845574, 9612253, 10248995, 10764907, 12884937, 13630745, 14675376, 16134598, 16263071, 16516868,
54122, 237176, 357562, 966519, 1550413, 1648267, 2598634, 3861007, 4009062, 4436305, 6540726, 8156271, 8330499, 10606561, 10908201, 11022305, 11330586, 12616905, 13238860, 13587405, 14496970, 15038036, 15388684, 16149803, 16157036,
5
104391*1000000/2337919 = 44651microseconds``````

Last edited by arithma (February 4 2011)

#59 February 6 2011

arithma
Member

Re: Exercise - Team Balancing

Here's the code: http://pastebin.com/APUgUrYB
I placed some decent comments on the important sections of the code. The C++ code is unobfuscated (largely by removing the bigger iterator infested arithmetic formulas where I used the * operator for multiplication and dereferencing an iterator) now. You  can still skim and understand what's happening, I hope.

Getting 144421 for 10 numbers with the 574 seed. This could very well be a nonoptimal result and verifiable to be not using a combination generator (something like your first suggestion).

#60 July 5 2012

Joe
Member

Re: Exercise - Team Balancing

Here's a oneliner that solves the problem. It takes a list of scores/ranking as an input and returns a 2-tuple with balanced scores.

Also, it's not really a oneliner when you're using itertools.permutation()

``````def oneline(l):
tsz = len(l)/2 # the size of each team, half of the total array size

# Behold the mighty one liner
return sorted((((x[tsz:], x[:tsz]), abs(sum(x[:tsz]) - sum(x[tsz:])))
for x in prmt(l)),key=iget(1))[0][0]``````

#61 May 27 2017

Member

Re: Exercise - Team Balancing

``````var pool=[];
var team1=[];
var team2=[];
function randomRating(){
return Math.floor(Math.random() * 200) + 1;
}
function average(array){
var sum = 0;
for(var i = 0; i < array.length; i++){
sum+=array[i];
}
return sum/array.length;
}
while(pool.length<10){
pool.push(Number(randomRating()));
}
pool.sort(function(a, b){ return a-b });

for(var i = 0; i < pool.length; i++){
i%2==0?team1.push(pool[i]):team2.push(pool[i]);
}
console.log('Team1: '+team1);
console.log('Average rating: '+average(team1));
console.log('Average rating %: '+(average(team1)*100/(average(team1)+average(team2))));
console.log('Team2: '+team2);
console.log('Average rating: '+average(team2));
console.log('Average rating %: '+(average(team2)*100/(average(team1)+average(team2))));``````

This code fills a random pool and then splits it into two teams.
Sample output:

``````Team1: 55,112,152,171,187
Average rating: 135.4
Average rating %: 48.04826117814052
Team2: 91,118,155,173,195
Average rating: 146.4
Average rating %: 51.95173882185947``````

It's a bit slow on big pools, probably because of the push operations. I'll try to make it faster without looking at others'.

Last edited by Adnan (May 27 2017)