public
Created

  • Download Gist
fair_distribution.rb
Ruby
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
require 'utils'
require 'swap'
 
# A very simple algorithm based on incremental balancing of job queues.
# Initially, the first queue has all the jobs that are gradually distributed
# across available queues. The algorithm doesn't take much memory since it
# does not involve the recursive traversing of the options tree and
# doesn't store lots of intermediate data.
class FairDistribution
def initialize(jobs, num_of_queues)
@queues = [ jobs.sort.reverse ]
(num_of_queues - 1).times { @queues << [] }
 
# Balance the queues until they are perfectly balanced
while !balance_all_queues do; end
end
# Time required for all queues processing
def time_required
@queues.map { |q| q.sum }.max
end
# The actual distribution of jobs across the queues
def distribution
@queues
end
private
# Runs through all queues and balances them against each other.
# Makes one pass only and returns FALSE if there was nothing changed
# during the pass.
def balance_all_queues
updated = false
@queues.each_with_index do |q1, qi1|
(qi1+1 ... @queues.size).each do |qi2|
res = balance_queues(q1, @queues[qi2])
updated ||= res
end
end
return !updated
end
# Balances the two queues between themselves by finding the best possible
# swap of jobs between them. If there's nothing to be improved, returns FALSE.
def balance_queues(q1, q2)
delta = q1.sum - q2.sum
return false if delta == 0
best_swap = nil
best_swap_delta = delta.abs
q1.each_combination do |c1|
best_swap, best_swap_delta = choose_better_swap(c1, [], delta, best_swap, best_swap_delta)
q2.each_combination do |c2|
best_swap, best_swap_delta = choose_better_swap(c1, c2, delta, best_swap, best_swap_delta)
end
end
best_swap.apply(q1, q2) unless best_swap.nil?
return !best_swap.nil?
end
# Sees if the swap we have at hand is better than our current best
# swap and replaces the latest if it is.
def choose_better_swap(c1, c2, delta, best_swap, best_swap_delta)
unless c1 == c2
s = Swap.new(c1, c2, delta)
best_swap, best_swap_delta = s, s.delta if s.delta < best_swap_delta
end
return best_swap, best_swap_delta
end
end
fair_distribution_acceptance.rb
Ruby
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
require 'test/unit'
require 'fair_distribution'
 
class FairQueueTest < Test::Unit::TestCase
 
def test_basic1
jobs = [10, 15, 20, 24, 30, 45, 75]
number_of_presses = 2
exp_max = 110
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
 
# A Solution
# [75, 20, 15],
# [45, 30, 24, 10,]
end
def test_basic2
jobs = [1.0, 4.75, 2.83, 1.1, 5.8, 3.5, 4.4]
number_of_presses = 4
exp_max = 6.33
exp_distribution = [
[1.0, 4.75],
[2.83, 3.5],
[1.1, 4.4],
[5.8]
]
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
assert_distributions_are_equivalent exp_distribution, fd.distribution
end
def test_basic3
jobs = [0.23, 0.47, 0.73, 1.5, 3.0, 3.2, 1.75, 2.3, 0.11, 0.27, 1.09]
number_of_presses = 4
exp_max = 3.73
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
# A Solution
# [3.2, 0.47],
# [3.0, 0.73],
# [2.3, 1.09, 0.23],
# [1.75, 1.5, 0.27, 0.11]
end #if ARGV[0] == "full" # only use this TC if 'full' is added as an argument.
def test_basic4
jobs = [5,5,4,4,3,3,3]
number_of_presses = 3
exp_max = 9
exp_distribution = [
[5,4],
[5,4],
[3,3,3],
]
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
assert_distributions_are_equivalent exp_distribution, fd.distribution
end
 
def test_basic5
fd = FairDistribution.new([0.23, 0.47, 0.73, 1.5, 3.0, 3.2], 4)
assert_equal 3.2, fd.time_required
assert_distributions_are_equivalent [[3.0], [3.2], [0.23, 0.47, 0.73], [1.5]], fd.distribution
end
private
 
def assert_distributions_are_equivalent(dist1, dist2, msg=nil)
failure_message = "Distributions not equivalent: #{msg}: #{dist1.inspect} not equivalent to #{dist2.inspect}"
assert(distributions_are_equivalent?(dist1, dist2), failure_message)
end
 
def distributions_are_equivalent?(dist1, dist2)
return false if dist1.size != dist2.size
my_dist1 = dist1.dup
my_dist2 = dist2.dup
my_dist1.reject! {|queue1|
dist2.detect {|queue2| arrays_have_same_elements?(queue1, queue2)}
}
my_dist2.reject! {|queue2|
dist1.detect {|queue1| arrays_have_same_elements?(queue1, queue2)}
}
my_dist1.empty? && my_dist2.empty?
end
def arrays_have_same_elements?(arr1, arr2)
arr1.size == arr2.size && (arr1 - arr2).empty?
end
end
swap.rb
Ruby
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
require 'utils'
 
# Single swap operation. It knows what move from one queue to another and
# what will be the delta between those queues after the operation.
class Swap
 
attr_reader :delta
 
def initialize(from_q1, from_q2, current_delta)
@from_q1 = from_q1
@from_q2 = from_q2
@delta = (current_delta + 2 * (from_q2.sum - from_q1.sum)).abs
end
# Applies the swap
def apply(q1, q2)
@from_q1.each do |j|
q2 << q1.delete_at(q1.index(j))
end
 
@from_q2.each do |j|
q1 << q2.delete_at(q2.index(j))
end
end
end
swap_test.rb
Ruby
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
require 'test/unit'
require 'swap'
 
class SwapTest < Test::Unit::TestCase
def test_swap_returns_correct_positive_delta
current_delta = 10 # q1.sum - q2.sum = 10
from_q1 = [ 1, 2 ] # 1 + 2 = 3
from_q2 = [ 3, 4 ] # 3 + 4 = 7
swap = Swap.new(from_q1, from_q2, current_delta)
assert_equal 10 - 2 * (3 - 7), swap.delta
# We multiply by 2 since we not only take [1, 2] from q1, but also add them to q2
# which makes the difference twice as big.
end
def test_swap_returns_correct_negative_delta
current_delta = 10 # q1.sum - q2.sum = 10
from_q1 = [ 3, 4 ] # 3 + 4 = 7
from_q2 = [ 1, 2 ] # 1 + 2 = 3
swap = Swap.new(from_q1, from_q2, current_delta)
assert_equal 10 - 2 * (7 - 3), swap.delta
end
def test_applying_changes_should_move_elements_between_queues
q1 = [ 1, 1, 2 ]
q2 = [ 3, 4 ]
swap = Swap.new([ 1, 2 ], [ 3 ], -3)
swap.apply(q1, q2)
assert_equal [ 1, 3 ], q1
assert_equal [ 4, 1, 2 ], q2
end
end
utils.rb
Ruby
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
# Simple additions to the generic array that are used to calculate the
# sum of items and iterate over the elements in a specific fashion.
class Array
 
# Returns the sum of all values in the array
def sum
self.inject(0.0) do |memo, value|
memo + (value.is_a?(Array) ? value.total : value)
end
end
# Iterates over all unique (based on their sum) combinations of elements.
# [1,2,3] -> [1], [1,2], [1,2,3], [2], [2, 3] (see [3] is omitted as being equial to [1,2])
def each_combination(i = 0, c = [], sums = [], &block)
(i ... self.size).each do |x|
combo = c + [ self[x] ]
sum = combo.sum
unless sums.include?(sum)
sums << sum
block.call combo
each_combination(x + 1, combo, sums, &block)
end
end
end
 
end
utils_test.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
require 'test/unit'
require 'utils'
 
class UtilsTest < Test::Unit::TestCase
def test_each_combination_should_invoke
c = []
[1, 2, 3].each_combination { |combo| c << combo }
assert_equal [[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]], c
end
 
def test_uniqueness_of_each_combination
c = []
[1, 2, 1].each_combination { |combo| c << combo }
assert_equal [[1], [1, 2], [1, 2, 1], [1, 1]], c
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.