91 return dict([(i, 0) for i in self.orgs]) |
91 return dict([(i, 0) for i in self.orgs]) |
92 |
92 |
93 if self.algorithm == 1: |
93 if self.algorithm == 1: |
94 return self.preprocessingAllocation() |
94 return self.preprocessingAllocation() |
95 |
95 |
|
96 if self.algorithm == 2: |
|
97 return self.reliableAlgorithm() |
|
98 |
96 return self.iterativeAllocation() |
99 return self.iterativeAllocation() |
97 |
100 |
98 def buildSets(self): |
101 def buildSets(self): |
99 """Allocates slots with the specified constraints. |
102 """Allocates slots with the specified constraints. |
100 """ |
103 """ |
242 |
245 |
243 slots_left += slots - current |
246 slots_left += slots - current |
244 allocations[org] = slots |
247 allocations[org] = slots |
245 |
248 |
246 return allocations |
249 return allocations |
|
250 |
|
251 def reliableAlgorithm(self): |
|
252 """An algorithm that reliable calculates the slots assignments. |
|
253 """ |
|
254 |
|
255 adjusted_orgs = self.adjusted_orgs |
|
256 adjusted_slots = self.adjusted_slots |
|
257 locked_orgs = self.locked_orgs |
|
258 locked_slots = self.locked_slots |
|
259 unlocked_orgs = self.unlocked_orgs |
|
260 total_popularity = self.total_popularity |
|
261 |
|
262 available_slots = self.slots |
|
263 allocations = {} |
|
264 slack = {} |
|
265 |
|
266 # take out the easy ones |
|
267 for org in locked_orgs: |
|
268 popularity = self.popularity[org] |
|
269 slots = locked_slots[org] |
|
270 slots = float(slots) |
|
271 slots = self.rangeSlots(slots, org) |
|
272 |
|
273 total_popularity -= popularity |
|
274 available_slots -= slots |
|
275 allocations[org] = slots |
|
276 del self.popularity[org] |
|
277 |
|
278 total_popularity = sum(self.popularity.values()) |
|
279 |
|
280 pop_per_slot = float(available_slots)/float(total_popularity) |
|
281 |
|
282 slack = 0 |
|
283 wanted = {} |
|
284 |
|
285 # filter out all those that deserve more than their maximum |
|
286 for org in unlocked_orgs: |
|
287 popularity = self.popularity[org] |
|
288 raw_slots = float(popularity)*pop_per_slot |
|
289 slots = int(math.floor(raw_slots)) |
|
290 slots = self.rangeSlots(slots, org) |
|
291 max = self.max[org] |
|
292 |
|
293 if max > slots: |
|
294 wanted[org] = max - slots |
|
295 |
|
296 allocations[org] = slots |
|
297 |
|
298 available_slots = self.slots - sum(allocations.values()) |
|
299 |
|
300 # distribute the slack |
|
301 while available_slots > 0 and (sum(wanted.values()) > 0): |
|
302 for org, amount in wanted.iteritems(): |
|
303 available_slots = self.slots - sum(allocations.values()) |
|
304 if available_slots <= 0: |
|
305 break |
|
306 |
|
307 if wanted[org] <= 0: |
|
308 continue |
|
309 |
|
310 current = allocations[org] |
|
311 slots = self.rangeSlots(current + 1, org) |
|
312 extra = current - slots |
|
313 |
|
314 wanted[org] += extra |
|
315 allocations[org] = slots |
|
316 |
|
317 return allocations |