-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathdistribute.py
123 lines (95 loc) · 4.14 KB
/
distribute.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
"""Contains the sorting algorithm for the distribution of the ratio lists of latency and load.
"""
def selection_sort(ratio_list, threshold=0.75):
"""Distributes the ratios in the list to ensure that no ratio exceeds the threshold value.
Methodology
-----------
1. If the current ratio 'r' exceeds the threshold value, then the difference between r and the threshold is calculated.
2. The difference is then added to the least ratio in the list.
3. r is then reduced by the difference.
4. The least ratio is increased by the difference.
5. The ratio list is updated with the new values.
6. The process is repeated for all the ratios in the list.
Time Complexity
---------------
O(n²): Outer loop runs n times, and the inner loop runs n times (finding the least ratio in the list).
Space Complexity
----------------
O(1): No extra space is used.
Args
----
- ratio_list: List of ratios to be distributed.
- threshold: The max value of the ratio that is allowed.
Returns
-------
- ratio_list: The list of ratios after distribution.
"""
# Deep copy of the list
ratio_list = ratio_list[:]
for i in range(len(ratio_list)):
ratio = ratio_list[i]
if ratio >= threshold: # Ratio exceeds threshold value, then exchange
difference = ratio - threshold
# Find the least ratio and its index
least_ratio = min(ratio_list)
least_ratio_index = ratio_list.index(least_ratio)
if least_ratio + difference <= 0.75: # Distributing Load only if Lower Bar after addition is < threshold
ratio -= difference
least_ratio += difference
else:
print("❌ Cannot Distribute ratios in this Region")
print("Continuing anyway...")
# Updating
ratio_list[i] = ratio
ratio_list[least_ratio_index] = least_ratio
return ratio_list
def linear_sort(ratio_list, threshold=0.75):
"""Distributes the ratios in the list to ensure that no ratio exceeds the threshold value.
Methodology
-----------
1. Create a 'buffer' variable that stores the excess ratio (exceeding threshold).
2. Iterate over the list of ratios
2.1 if ratio >= threshold, then add the excess (ratio - threshold) to the buffer, set the ratio to threshold.
3. Iterate over the list of ratios
3.1 if ratio < threshold, then add that much from the buffer to the ratio such that new_ratio < threshold.
4. If some amount is still left in buffer, then not possible to distribute the ratios.
4. Return the updated ratio list.
Args
----
- ratio_list: List of ratios to be distributed.
- threshold: The max value of the ratio that is allowed.
Returns
-------
"""
n = len(ratio_list)
buffer = 0
for i in range(n):
if ratio_list[i] >= threshold:
buffer += ratio_list[i] - threshold
ratio_list[i] = threshold
if buffer > 0:
for i in range(n):
if ratio_list[i] < threshold:
required = threshold - ratio_list[i]
if buffer >= required:
ratio_list[i] = threshold
buffer -= required
else:
ratio_list[i] += buffer
buffer = 0
if buffer > 0:
print("❌ Buffer is still not empty. Some ratios is still left to be distributed.")
print("Continuing anyway...")
return ratio_list
if __name__ == '__main__':
print("Testing the distribute module...")
ratio_list = [0.8, 0.9, 0.7, 0.6, 0.8, 0.4, 0.7,
0.2, 0.1, 0.3, 0.7, 0.6, 0.8, 0.9, 0.7, 0.6]
print(
f"Original Ratio List: {ratio_list}, sum of ratios: {sum(ratio_list):.2f}")
selection_sort_ratio_list = selection_sort(ratio_list)
print(
f"After Selection Sort: {selection_sort_ratio_list}, sum of ratios: {sum(selection_sort_ratio_list):.2f}")
linear_sort_ratio_list = linear_sort(ratio_list)
print(
f"After Linear Sort: {linear_sort_ratio_list}, sum of ratios: {sum(linear_sort_ratio_list):.2f}")