Created
February 15, 2010 23:55
-
-
Save aurelienbottazini/305120 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
=begin | |
Original problem url: http://rubylearning.com/blog/2010/01/26/rpcfn-fair-distribution-6/ | |
The goal of this class is to schedule printing jobs between printing machines (presses) | |
Jobs should be distributed "in such a manner that (a) all t-shirts are printed in the least amount of time, | |
and (b) the distribution of work across machines is as fair as possible (i.e. the standard deviation | |
of the time each machine spends working is minimized)." | |
Usage: | |
jobs = [5,5,4,4,3,3,3] | |
number_of_presses = 3 | |
fd = FairDistribution.new(jobs, number_of_presses) | |
fd.time_required | |
fd.distribution | |
Note: | |
Class ensure that jobs is an array containing only positive numeric | |
Class ensure that number_of_presses is valid (positive and an integer) | |
tested with ruby 1.8.6-p388, 1.8.7-p249 and 1.9.1-p378 | |
=end | |
class FairDistribution | |
attr_accessor :distribution, :time_required | |
def initialize jobs, number_of_presses | |
if number_of_presses.integer? == false || number_of_presses < 1 | |
raise ArgumentError, "The number of presses needs to be an integer greater or equal to 1" | |
end | |
if jobs.is_a?(Array) == false | |
raise ArgumentError, "jobs should be an array containing positive numeric" | |
end | |
jobs.each do |job| | |
if job.is_a?(Numeric) == false || job < 0 | |
raise ArgumentError, "All Jobs should be positive numeric" | |
end | |
end | |
@number_of_presses = number_of_presses | |
# starting with the highest time possible (sum of all jobs) | |
@time_required = jobs.inject(0.0) { |sum, n| sum + n } | |
# will hold signatures of tested distributions (so that we don't | |
# try to compute equivalent distribution) | |
@signatures = Hash.new | |
# initializing an empty distribution with the correct number of presses | |
@distribution = [] | |
number_of_presses.times { @distribution << Array.new } | |
# sets @time_required and @distribution | |
distribute_jobs [[]], jobs.dup | |
end | |
private | |
# Recusive procedure | |
# It should be called initially with a list of jobs and an empty | |
# distribution containing one empty press ( = [[]]). | |
# It will try to find the optimal distribution and store it in | |
# @distribution. It will also store the time required by this | |
# optimal distribution in @time_required. | |
def distribute_jobs distrib, jobs | |
# we can stop, we have reached the maximum number of press | |
if distrib.size == @number_of_presses | |
# copy the remaining jobs in last press and empty jobs array | |
while !jobs.empty? | |
distrib.last << jobs.pop | |
end | |
# we don't have any solution yet, copy this one | |
if FairDistribution.is_distribution_empty?(@distribution) | |
@distribution = distrib | |
# let's check if this distribution is better than our previous | |
# best and make it the new solution if it is | |
elsif FairDistribution.time_required(distrib) <= @time_required && | |
FairDistribution.standard_deviation(distrib) < FairDistribution.standard_deviation(@distribution) | |
@distribution = distrib | |
@time_required = FairDistribution.time_required(@distribution) | |
end | |
return | |
end | |
# create a signature for this distribution so that we don't test | |
# equivalent distributions. | |
# ex: [[5, 4], [5, 4], [3, 3, 3]] and [[4, 5], [5, 4], [3, 3, 3]] | |
# are equivalent and only one of them needs to be tested. | |
signature = String.new | |
distrib.each_with_index {|e, index| distrib[index] = e.sort } | |
distrib.sort {|a,b| a.inject(0.0) { |sum, n| sum + n } <=> b.inject(0.0) { |sum, n| sum + n } }.each do |press| | |
press.each { |job| signature << "#{job};" } | |
signature << "|" | |
end | |
# have we tried yet this distribution? | |
if @signatures.key?(signature) == false | |
# we have exceeded the @time_required of our current best | |
# distribution, we don't need to test this distribution | |
if FairDistribution.time_required(distrib) <= @time_required | |
# mark this distribution has tried | |
@signatures[signature] = 1 | |
jobs.each_with_index do |job, index| | |
# we create two new distributions | |
# First one : we add one job in last press | |
# Second one: we add one job in last press and we add one | |
# more press | |
distrib_copy = FairDistribution.dup_distrib(distrib) | |
distrib_copy.last << job | |
distrib_copy2 = FairDistribution.dup_distrib(distrib_copy) | |
distrib_copy2 << Array.new | |
# copying remaining jobs list and removing the job we added | |
# in the two new distributions | |
jobs_copy = jobs.dup | |
jobs_copy.slice!(index) | |
distribute_jobs distrib_copy, jobs_copy | |
distribute_jobs distrib_copy2, jobs_copy.dup | |
end | |
end | |
end | |
end | |
def self.dup_distrib distrib | |
new_distrib = Array.new | |
distrib.each do |d| | |
new_distrib << d.dup | |
end | |
return new_distrib | |
end | |
def self.standard_deviation distrib | |
sums = Array.new | |
distrib.each do |d| | |
sums << d.inject(0.0) { |sum, n| sum + n } | |
end | |
mean = sums.inject(0.0) { |sum, n| sum + n } / distrib.size | |
variance = sums.inject(0.0) {|sum, n| sum + (n - mean) * (n - mean) } / distrib.size | |
return Math.sqrt(variance) | |
end | |
def self.time_required distrib | |
time_required = 0.0 | |
if distrib != nil | |
distrib.each do |d| | |
d_time_required = d.inject(0) { |sum, n| sum + n } | |
if d_time_required > time_required | |
time_required = d_time_required | |
end | |
end | |
end | |
return time_required | |
end | |
# empty meaning distribution containing no press or presses | |
# but without any jobs | |
def self.is_distribution_empty? distrib | |
is_empty = true | |
distrib.each do |d| | |
if d.size > 0 | |
is_empty = false | |
break | |
end | |
end | |
return is_empty | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'test/unit' | |
require 'fair_distribution' | |
#FairDistribution = LowMemoryFairDistribution | |
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 | |
def test_basic6 | |
jobs = [5,5,4,4,3,3,3,1,1,1] | |
number_of_presses = 3 | |
exp_max = 10 | |
fd = FairDistribution.new(jobs, number_of_presses) | |
assert_equal exp_max, fd.time_required | |
end | |
def test_basic7 | |
jobs = [10,10,1,1,1,1,1,1] | |
number_of_presses = 3 | |
exp_max = 10 | |
exp_distribution = [ | |
[10], | |
[10], | |
[1,1,1,1,1,1], | |
] | |
fd = FairDistribution.new(jobs, number_of_presses) | |
assert_equal exp_max, fd.time_required | |
end | |
def test_empty_jobs | |
jobs = [] | |
number_of_presses = 2 | |
fd = FairDistribution.new(jobs, number_of_presses) | |
assert_equal 0.0 , fd.time_required | |
assert_distributions_are_equivalent [[],[]], fd.distribution | |
number_of_presses = 1 | |
fd = FairDistribution.new(jobs, number_of_presses) | |
assert_distributions_are_equivalent [[]], fd.distribution | |
end | |
def test_zero_press | |
jobs = [1,2,3,4,5,6] | |
number_of_presses = 0 | |
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses) } | |
end | |
def test_float_number_of_press | |
jobs = [3,4,5,6,7,8] | |
number_of_presses = 2.3 | |
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses) } | |
end | |
def test_bad_jobs | |
jobs = ["dscscds", 1, 2.3] | |
number_of_presses = 3 | |
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses)} | |
jobs = [5, 2, -3] | |
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses)} | |
jobs = "wrong" | |
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses)} | |
end | |
# Testing Implementation | |
# def test_arrays_have_same_elements | |
# assert arrays_have_same_elements?([1,2,3], [3,1,2]) | |
# assert !arrays_have_same_elements?([], [1,2,3]) | |
# assert !arrays_have_same_elements?([1,2,3], [1,2,3,4]) | |
# assert !arrays_have_same_elements?([1,2,3,4], [1,2,3]) | |
# assert !arrays_have_same_elements?([1,1], [1]) | |
# assert !arrays_have_same_elements?([1], [1,1]) | |
# end | |
# | |
# def test_distributions_are_equivalent | |
# assert distributions_are_equivalent?([[1, 2], [2, 3]], [[3, 2], [2, 1]]) | |
# assert !distributions_are_equivalent?([[1, 3], [2, 2]], [[3, 2], [2, 1]]) | |
# assert !distributions_are_equivalent?([[1, 2], [3, 2]], [[3, 2], [3, 2]]) | |
# assert !distributions_are_equivalent?([[1, 2], [1, 2]], [[3, 2], [2, 1]]) | |
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment