author | Lennard de Rijk <ljvderijk@gmail.com> |
Mon, 01 Jun 2009 20:03:22 +0200 | |
changeset 2372 | f1cbafd21f75 |
parent 2366 | 1a954e80d444 |
permissions | -rw-r--r-- |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
1 |
#!/usr/bin/python2.5 |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
2 |
# |
1307
091a21cf3627
Update the copyright notice for 2009.
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1056
diff
changeset
|
3 |
# Copyright 2009 the Melange authors. |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
4 |
# |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
5 |
# Licensed under the Apache License, Version 2.0 (the "License"); |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
6 |
# you may not use this file except in compliance with the License. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
7 |
# You may obtain a copy of the License at |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
8 |
# |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
9 |
# http://www.apache.org/licenses/LICENSE-2.0 |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
10 |
# |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
11 |
# Unless required by applicable law or agreed to in writing, software |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
12 |
# distributed under the License is distributed on an "AS IS" BASIS, |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
13 |
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
14 |
# See the License for the specific language governing permissions and |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
15 |
# limitations under the License. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
16 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
17 |
"""Slot allocation logic. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
18 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
19 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
20 |
__authors__ = [ |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
21 |
'"Sverre Rabbelier" <sverre@rabbelier.nl>', |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
22 |
] |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
23 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
24 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
25 |
import math |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
26 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
27 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
28 |
class Error(Exception): |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
29 |
"""Error class for the Allocation module. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
30 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
31 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
32 |
pass |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
33 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
34 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
35 |
class Allocator(object): |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
36 |
"""A simple student slots allocator. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
37 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
38 |
The buildSets method is used to validate the allocation data as well as |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
39 |
construct the sets that the algorithm then uses to distribute the slots. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
40 |
By separating these steps it is possible to write a different allocation |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
41 |
algorithm but re-use the sets and validation logic. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
42 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
43 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
44 |
# I tried to write explicit code that does not require any |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
45 |
# additional comments (with the exception of the set notation for |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
46 |
# the convenience of any mathematicians that happen to read this |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
47 |
# piece of code ;). |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
48 |
|
2130
83f4fab7c556
Drop the 'adjustement' part of slots allocation
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2073
diff
changeset
|
49 |
def __init__(self, orgs, popularity, max, slots, |
2139
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
50 |
max_slots_per_org, min_slots_per_org, algorithm): |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
51 |
"""Initializes the allocator. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
52 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
53 |
Args: |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
54 |
orgs: a list of all the orgs that need to be allocated |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
55 |
popularity: the amount of applications per org |
2139
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
56 |
max: the amount of assigned mentors per org |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
57 |
slots: the total amount of available slots |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
58 |
max_slots_per_org: how many slots an org should get at most |
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
59 |
min_slots_per_org: how many slots an org should at least get |
2139
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
60 |
algorithm: the algorithm to use |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
61 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
62 |
|
1651
ce52003ca18f
Comment out unused variables and add used but not declared class variables to __init__ method in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1307
diff
changeset
|
63 |
self.locked_slots = {} |
ce52003ca18f
Comment out unused variables and add used but not declared class variables to __init__ method in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1307
diff
changeset
|
64 |
self.adjusted_slots = {} |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
65 |
self.adjusted_orgs = [] |
1651
ce52003ca18f
Comment out unused variables and add used but not declared class variables to __init__ method in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1307
diff
changeset
|
66 |
self.locked_orgs = [] |
2073
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
67 |
self.unlocked_orgs = [] |
1651
ce52003ca18f
Comment out unused variables and add used but not declared class variables to __init__ method in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1307
diff
changeset
|
68 |
self.unlocked_applications = [] |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
69 |
self.slots = slots |
2366
1a954e80d444
Style fixes and pylint: disable-msg comments in different modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
2188
diff
changeset
|
70 |
self.mentors = {} |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
71 |
self.max_slots_per_org = max_slots_per_org |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
72 |
self.min_slots_per_org = min_slots_per_org |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
73 |
self.orgs = set(orgs) |
2073
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
74 |
self.popularity = None |
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
75 |
self.total_popularity = None |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
76 |
self.initial_popularity = popularity |
2130
83f4fab7c556
Drop the 'adjustement' part of slots allocation
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2073
diff
changeset
|
77 |
self.max = max |
2139
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
78 |
self.algorithm = algorithm |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
79 |
|
2130
83f4fab7c556
Drop the 'adjustement' part of slots allocation
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2073
diff
changeset
|
80 |
def allocate(self, locked_slots): |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
81 |
"""Allocates the slots and returns the result. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
82 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
83 |
Args: |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
84 |
locked_slots: a dict with orgs and the number of slots they get |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
85 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
86 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
87 |
self.locked_slots = locked_slots |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
88 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
89 |
self.buildSets() |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
90 |
|
2130
83f4fab7c556
Drop the 'adjustement' part of slots allocation
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2073
diff
changeset
|
91 |
if not sum(self.popularity.values()) or not sum(self.max.values()): |
2137
3d5692ae414c
If nothing is assigned, return no assignments
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2130
diff
changeset
|
92 |
return dict([(i, 0) for i in self.orgs]) |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
93 |
|
2139
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
94 |
if self.algorithm == 1: |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
95 |
return self.preprocessingAllocation() |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
96 |
|
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
97 |
if self.algorithm == 2: |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
98 |
return self.reliableAlgorithm() |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
99 |
|
2139
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
100 |
return self.iterativeAllocation() |
43a02512ebf7
Change iterative to algorithm in slot allocator
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2137
diff
changeset
|
101 |
|
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
102 |
def buildSets(self): |
2073
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
103 |
"""Allocates slots with the specified constraints. |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
104 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
105 |
|
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
106 |
popularity = self.initial_popularity.copy() |
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
107 |
|
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
108 |
# set s |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
109 |
locked_slots = self.locked_slots |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
110 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
111 |
# set a and b |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
112 |
locked_orgs = set(locked_slots.keys()) |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
113 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
114 |
# set a' and b' |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
115 |
unlocked_orgs = self.orgs.difference(locked_orgs) |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
116 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
117 |
# a+o and b+o should be o |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
118 |
locked_orgs_or_orgs = self.orgs.union(locked_orgs) |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
119 |
|
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
120 |
total_popularity = sum(popularity.values()) |
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
121 |
|
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
122 |
# a+o should be o, testing length is enough though |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
123 |
if len(locked_orgs_or_orgs) != len(self.orgs): |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
124 |
raise Error("Unknown org as locked slot") |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
125 |
|
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
126 |
self.unlocked_orgs = unlocked_orgs |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
127 |
self.locked_orgs = locked_orgs |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
128 |
self.popularity = popularity |
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
129 |
self.total_popularity = total_popularity |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
130 |
|
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
131 |
def rangeSlots(self, slots, org): |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
132 |
"""Returns the amount of slots for the org within the required bounds. |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
133 |
""" |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
134 |
|
1737
9dc63101b107
Support non-float slots
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1721
diff
changeset
|
135 |
slots = int(math.floor(float(slots))) |
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
136 |
slots = min(slots, self.max_slots_per_org) |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
137 |
slots = max(slots, self.min_slots_per_org) |
2130
83f4fab7c556
Drop the 'adjustement' part of slots allocation
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2073
diff
changeset
|
138 |
slots = min(slots, self.max[org]) |
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
139 |
|
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
140 |
return slots |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
141 |
|
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
142 |
def iterativeAllocation(self): |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
143 |
"""A simple iterative algorithm. |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
144 |
""" |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
145 |
|
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
146 |
adjusted_orgs = self.adjusted_orgs |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
147 |
adjusted_slots = self.adjusted_slots |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
148 |
locked_orgs = self.locked_orgs |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
149 |
locked_slots = self.locked_slots |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
150 |
|
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
151 |
unallocated_popularity = self.total_popularity - len(locked_slots) |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
152 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
153 |
available_slots = self.slots |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
154 |
allocations = {} |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
155 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
156 |
for org in self.orgs: |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
157 |
popularity = self.popularity[org] |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
158 |
mentors = self.mentors[org] |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
159 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
160 |
if org in locked_orgs: |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
161 |
slots = locked_slots[org] |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
162 |
elif unallocated_popularity: |
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
163 |
weight = float(popularity) / float(unallocated_popularity) |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
164 |
slots = int(math.floor(weight*available_slots)) |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
165 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
166 |
if org in adjusted_orgs: |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
167 |
slots += adjusted_slots[org] |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
168 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
169 |
slots = min(slots, self.max_slots_per_org) |
1717
d4c4c8668871
Added assigned mentors and amount of minimum slots per org
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1651
diff
changeset
|
170 |
slots = min(slots, mentors) |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
171 |
slots = min(slots, available_slots) |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
172 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
173 |
allocations[org] = slots |
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
174 |
available_slots -= slots |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
175 |
unallocated_popularity -= popularity |
1056
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
176 |
|
d0c82bdc2de2
Added a simple slot allocation algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff
changeset
|
177 |
return allocations |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
178 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
179 |
def preprocessingAllocation(self): |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
180 |
"""An algorithm that pre-processes the input before running as normal. |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
181 |
""" |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
182 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
183 |
adjusted_orgs = self.adjusted_orgs |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
184 |
adjusted_slots = self.adjusted_slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
185 |
locked_orgs = self.locked_orgs |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
186 |
locked_slots = self.locked_slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
187 |
unlocked_orgs = self.unlocked_orgs |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
188 |
total_popularity = self.total_popularity |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
189 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
190 |
available_slots = self.slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
191 |
allocations = {} |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
192 |
slack = {} |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
193 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
194 |
for org in locked_orgs: |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
195 |
popularity = self.popularity[org] |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
196 |
slots = locked_slots[org] |
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
197 |
slots = self.rangeSlots(slots, org) |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
198 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
199 |
total_popularity -= popularity |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
200 |
available_slots -= slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
201 |
allocations[org] = slots |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
202 |
del self.popularity[org] |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
203 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
204 |
# adjust the orgs in need of adjusting |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
205 |
for org in adjusted_orgs: |
1748
f789ffe213a3
Play nice with non-float allocations
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1737
diff
changeset
|
206 |
slots = float(adjusted_slots[org]) |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
207 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
208 |
adjustment = (float(total_popularity)/float(available_slots))*slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
209 |
adjustment = int(math.ceil(adjustment)) |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
210 |
self.popularity[org] += adjustment |
1751
17c7a7a48dc7
Switch from actual applications to popularity
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1748
diff
changeset
|
211 |
total_popularity += adjustment |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
212 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
213 |
# adjust the popularity so that the invariants are always met |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
214 |
for org in unlocked_orgs: |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
215 |
popularity = self.popularity[org] |
2073
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
216 |
# mentors = self.mentors[org] |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
217 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
218 |
slots = (float(popularity)/float(total_popularity))*available_slots |
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
219 |
slots = self.rangeSlots(slots, org) |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
220 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
221 |
popularity = (float(total_popularity)/float(available_slots))*slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
222 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
223 |
self.popularity[org] = popularity |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
224 |
|
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
225 |
total_popularity = sum(self.popularity.values()) |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
226 |
|
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
227 |
# do the actual calculation |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
228 |
for org in unlocked_orgs: |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
229 |
popularity = self.popularity[org] |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
230 |
raw_slots = (float(popularity)/float(total_popularity))*available_slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
231 |
slots = int(math.floor(raw_slots)) |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
232 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
233 |
slack[org] = raw_slots - slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
234 |
allocations[org] = slots |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
235 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
236 |
slots_left = available_slots - sum(allocations.values()) |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
237 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
238 |
# add leftover slots, sorted by slack, decending |
2073
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
239 |
for org, slack in sorted(slack.iteritems(), |
6eb9b4652c80
Style fixes and removal of unused imports in soc.logic modules.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
1854
diff
changeset
|
240 |
key=lambda (k, v): v, reverse=True): |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
241 |
if slots_left < 1: |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
242 |
break |
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
243 |
|
1721
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
244 |
current = allocations[org] |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
245 |
slots = self.rangeSlots(current + 1, org) |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
246 |
|
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
247 |
slots_left += slots - current |
9acf4fe1b9bb
Adjust the total_popularity after ranging
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1718
diff
changeset
|
248 |
allocations[org] = slots |
1718
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
249 |
|
ca34f4a8c61b
Added an pre-processing algorithm
Sverre Rabbelier <srabbelier@gmail.com>
parents:
1717
diff
changeset
|
250 |
return allocations |
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
251 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
252 |
def reliableAlgorithm(self): |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
253 |
"""An algorithm that reliable calculates the slots assignments. |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
254 |
""" |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
255 |
|
2188
95b23c66257b
Comment out unused variables in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
2143
diff
changeset
|
256 |
# adjusted_orgs = self.adjusted_orgs |
95b23c66257b
Comment out unused variables in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
2143
diff
changeset
|
257 |
# adjusted_slots = self.adjusted_slots |
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
258 |
locked_orgs = self.locked_orgs |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
259 |
locked_slots = self.locked_slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
260 |
unlocked_orgs = self.unlocked_orgs |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
261 |
total_popularity = self.total_popularity |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
262 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
263 |
available_slots = self.slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
264 |
allocations = {} |
2188
95b23c66257b
Comment out unused variables in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
2143
diff
changeset
|
265 |
# slack = {} |
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
266 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
267 |
# take out the easy ones |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
268 |
for org in locked_orgs: |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
269 |
popularity = self.popularity[org] |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
270 |
slots = locked_slots[org] |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
271 |
slots = float(slots) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
272 |
slots = self.rangeSlots(slots, org) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
273 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
274 |
total_popularity -= popularity |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
275 |
available_slots -= slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
276 |
allocations[org] = slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
277 |
del self.popularity[org] |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
278 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
279 |
total_popularity = sum(self.popularity.values()) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
280 |
|
2143
67c1cb524b78
Fix bug exposed in previous commit
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2140
diff
changeset
|
281 |
# all orgs have been locked, nothing to do |
67c1cb524b78
Fix bug exposed in previous commit
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2140
diff
changeset
|
282 |
if total_popularity <= 0: |
67c1cb524b78
Fix bug exposed in previous commit
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2140
diff
changeset
|
283 |
return allocations |
67c1cb524b78
Fix bug exposed in previous commit
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2140
diff
changeset
|
284 |
|
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
285 |
pop_per_slot = float(available_slots)/float(total_popularity) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
286 |
|
2188
95b23c66257b
Comment out unused variables in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
2143
diff
changeset
|
287 |
# slack = 0 |
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
288 |
wanted = {} |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
289 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
290 |
# filter out all those that deserve more than their maximum |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
291 |
for org in unlocked_orgs: |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
292 |
popularity = self.popularity[org] |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
293 |
raw_slots = float(popularity)*pop_per_slot |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
294 |
slots = int(math.floor(raw_slots)) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
295 |
slots = self.rangeSlots(slots, org) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
296 |
max = self.max[org] |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
297 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
298 |
if max > slots: |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
299 |
wanted[org] = max - slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
300 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
301 |
allocations[org] = slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
302 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
303 |
available_slots = self.slots - sum(allocations.values()) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
304 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
305 |
# distribute the slack |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
306 |
while available_slots > 0 and (sum(wanted.values()) > 0): |
2188
95b23c66257b
Comment out unused variables in soc.logic.allocations module.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
2143
diff
changeset
|
307 |
for org, _ in wanted.iteritems(): |
2140
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
308 |
available_slots = self.slots - sum(allocations.values()) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
309 |
if available_slots <= 0: |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
310 |
break |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
311 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
312 |
if wanted[org] <= 0: |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
313 |
continue |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
314 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
315 |
current = allocations[org] |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
316 |
slots = self.rangeSlots(current + 1, org) |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
317 |
extra = current - slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
318 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
319 |
wanted[org] += extra |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
320 |
allocations[org] = slots |
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
321 |
|
32b0731f0bf5
Add a new allocation algorithm and use it
Sverre Rabbelier <srabbelier@gmail.com>
parents:
2139
diff
changeset
|
322 |
return allocations |