# Iterating X times (where X > Y) over Y element dictionary - is there a nicer way of doing this?

I need to write a procedure, that will take a dictionary consisting of server names and their available slots and a number of slots required, and redispatch it over the servers, so that every server would accept only that many assignments as he has free slots; servers with higher number of free slots would be assigned in first place; whole procedure would be robust and not prone to any stupid math errors I might have done. So far I've came up with something like that:

import operator

slots_required = 8
hosts = {'server1': 3, 'server2': 7, 'server3': 1}
jobs = {}

if slots_required > sum(hosts.values()):
print " [!] Not enough resources! Exiting."
else:
print " [x] entering while loop"
while slots_required > 0:
print " [x] while loop on interation: %s" % slots_required
for host in sorted(hosts.iteritems(), key=operator.itemgetter(1), reverse=True):
# if for any reason slots_required number is 0 or less, break
if slots_required <= 0:
break
# if the host has no slots free we're not iterating over it and removing it
if host[1] == 0:
hosts.pop(host[0])
break
else:
print " [x] for loop, host: %s" % host[0]
jobs[slots_required] = host
slots_required -= 1
hosts[host[0]] = host[1] - 1
print " [x] slots_required value after decreasing: %s" % slots_required

print " [x] exited the for loop"
print " [x] Iteration down to ZERO! Exiting!"
print " [x] exiting while loop"

print jobs
print hosts
print slots_required


Feel free to play around and change server numbers, their free slots and slots required of course. The numbers I've added are only for example and testing purposes, and the print functions can be taken out as well, the only thing I am interested in at the end is the jobs dictionary with server names and their assignments (there will be jobID inserted next to server name in jobs dictionary instead of a number, as it is right now). Is there a better, nicer, safer and quicker way of doing that? I've feeling the code although working in my tests, is extremely ugly and could be more functional. Thanks!

-

You can solve this mathematically. Let's suppose there are m hosts and n jobs. Sort the hosts into ascending order by their slots, so that si is the number of slots for host number i, and we have s0 ≤ s1 ≤ … ≤ sm−1.

Now we can immediately figure out how many jobs host 0 gets. Case (i): if s0m ≥ n, then we can distribute jobs evenly across the hosts, so that every host gets either ceil(n / m) or floor(n / m) jobs. Because jobs are distributed to the hosts with higher capacity first, we can be sure that host 0 gets floor(n / m) jobs. Case (ii): if s0m < n, then we have to give each host at least s0 jobs (and some hosts more).

So host 0 gets min(floor(n / m), s0) jobs, and then we can subtract 1 from m and go on to host 1. Like this:

import operator

class CapacityError(Exception):
pass

def schedule(hosts, n):
"""
Generate a schedule for picking n slots from hosts (a
dictionary mapping hostname to capacity). Raise CapacityError if
no such schedule is possible.

>>> sorted(schedule({'A': 3, 'B': 7, 'C': 1}, 8))
[('A', 3), ('B', 4), ('C', 1)]
"""
if n > sum(hosts.itervalues()):
raise CapacityError()
m = len(hosts)
for host, slots in sorted(hosts.iteritems(), key=operator.itemgetter(1)):
j = min(n // m, slots)
n -= j
m -= 1
yield host, j
assert(n == m == 0)


### Update 1: generators

I've implemented this function in the form of a generator because that's the most flexible way in Python to produce a sequence of things (here, elements of a schedule). You can easily turn the result into a dictionary:

>>> dict(schedule({'A': 3, 'B': 7, 'C': 1}, 8))
{'A': 3, 'C': 1, 'B': 4}


or a list:

>>> list(schedule({'A': 3, 'B': 7, 'C': 1}, 8))
[('C', 1), ('A', 3), ('B', 4)]


or just process the items one at a time:

>>> for host, slots in schedule({'A': 3, 'B': 7, 'C': 1}, 8):
...     print("{}: {}".format(host, slots))
...
C: 1
A: 3
B: 4


(If you're not happy with using generators, you can easily change the implementation to return a dictionary instead. But it's worth learning to use them. See the Python Tutorial, or this question on Stack Overflow.)

### Update 2: job ids

You asked in comments how to assign individual jobs. Well, one idea would be to pass in a list of jobs to the scheduler, and get out a list of jobs for each host, like this:

from itertools import islice

def schedule2(hosts, jobs):
"""
Generate a schedule for assigning the list jobs to hosts (a
dictionary mapping hostname to capacity). Raise CapacityError if
no such schedule is possible.

>>> jobs = ['j{}'.format(i) for i in range(8)]
>>> dict(schedule2({'A': 3, 'B': 7, 'C': 1}, jobs))
{'A': ['j1', 'j2', 'j3'], 'C': ['j0'], 'B': ['j4', 'j5', 'j6', 'j7']}
"""
n = len(jobs)
if n > sum(hosts.itervalues()):
raise CapacityError()
m = len(hosts)
jobs = iter(jobs)
for host, slots in sorted(hosts.iteritems(), key=operator.itemgetter(1)):
j = min(n // m, slots)
n -= j
m -= 1
yield host, list(islice(jobs, j))
assert(n == m == 0)


### Update 3: more explanation

You asked in comments for more explanation. Well, I'm going to assume that you know all about Python iterables, iterators, and generators (see the Python tutorial and the answers to this question on Stack Overflow).

So the remaining difficult bit is why I write jobs = iter(jobs) and list(islice(jobs, j)). Remember that jobs is a sequence of jobs, and we want to split it up into lists of jobs assigned to each host. In the line

        j = min(n // m, slots)


we compute the number of jobs to assign to the current host, so what we need to do is to take the next j elements from the list jobs. One way to do that would be able to keep a counter k of how far we got through the list jobs, and then take a slice of the next j elements starting at k. Like this:

    k = 0
for host, slots in sorted(hosts.iteritems(), key=operator.itemgetter(1)):
j = min(n // m, slots)
n -= j
m -= 1
yield host, jobs[k:k+j]
k += j


There's nothing wrong with doing it like this, except that it's a bit of a pain keeping the counter k up to date. We don't really care about the value of k, we just want the next j elements from jobs, whatver they are. That's where itertools.islice comes in. The call islice(iterator, j) returns an iterator that takes j elements from iterator. Which is almost exactly what we need, except that it's an iterator, but we need a list. So we convert it to a list by calling the built-in function list.

Here's an example showing islice in action:

>>> from itertools import count, islice
>>> c = count(1) # an iterator that counts upwards from 1
>>> a = islice(c, 5) # an iterator that gets 5 elements from c
>>> list(a)
[1, 2, 3, 4, 5]
>>> list(islice(c, 3)) # get another 3 elements from c
[6, 7, 8]


The only remaining problem with using islice to split up jobs is that this relies upon jobs being an iterator (a list won't work). So we use the built-in function iter to ensure that jobs is an iterator.

You should try out all these functions in the interactive interpreter to get a feel for what they do and how they work.

You also asked about assert. An assertion is a statement that tests a value and raises an exception if it's not true. It declares a condition that must be true at this point in the program. This is useful for programmers who want to read and understand the code, and it also catches implementation errors if these lead to the condition being violated. See Wikipedia on assertions.

In this case, I want to declare that the program has generated an assignment for every host (that is, m == 0 since m starts at the number of hosts and counts down for each one) and that every job has been assigned to some host (that is, n == 0, since n starts at the number of jobs, and gets reduced by j when we assign j jobs to some host).

-
Wow, that's some nice math there, but I think it doesnt produce desired output: a dictionary of hosts with assigned slots. What I can see it does, is returning list of hosts and number of assigned slots - not exactly the same thing. Also, why it doesnt work when I use it like print ({'A': 3, 'B': 7, 'C': 1}, 8) ? –  SpankMe Jan 31 '13 at 19:37
schedule is a generator function. Generators are very flexible: if you want to turn the output into a dictionary, you can call dict(schedule(...)). If you want to turn the output into a list, you can call list(schedule(...)). If you want to print out the assignments, you can write for host, jobs in schedule(...): print(host, jobs). And so on. –  Gareth Rees Jan 31 '13 at 19:41
As a note, you could replace the manual counter m with a zip(..., range(len(hosts), 0, -1)). –  Lattyware Jan 31 '13 at 22:01
@GarethRees: Ok, now it's making bit more sense, however, given the fact its a generator, I cant squeeze inside a job_id generation to be assigned to a server. It seems, I'd have to create a dictionary using your generator and then iterate over that dictionary and assign a unique job_id to every key in that dictionary. Is that correct or is there a better way? –  SpankMe Feb 1 '13 at 11:30
See updated answer. –  Gareth Rees Feb 1 '13 at 11:54