Created
February 7, 2010 13:31
-
-
Save jqr/297449 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
# http://rubylearning.com/blog/2010/01/26/rpcfn-fair-distribution-6/ | |
module Enumerable | |
def sum | |
inject(0) { |acc, v| acc + v } | |
end | |
end | |
class FairDistribution | |
attr_accessor :jobs, :worker_count, :distribution | |
def initialize(jobs, worker_count) | |
self.jobs = jobs | |
self.worker_count = worker_count | |
self.distribution = (1..worker_count).map { [] } | |
distribute | |
end | |
def distribute | |
todo = jobs.dup.sort | |
i = 0 | |
while largest = todo.pop | |
log "round #{i += 1 } (remaining #{todo.inspect})" | |
shortest_worker = distribution.sort { |a, b| a.sum <=> b.sum }.first | |
shortest_worker << largest | |
print_distribution | |
end | |
loop do | |
log "settling round #{i += 1 }" | |
distribution.each { |w| w.sort! } | |
sorted_distribution = distribution.sort { |a, b| a.sum <=> b.sum } | |
sorted_distribution = sorted_distribution.map { |w| w.dup } | |
largest = sorted_distribution.first.shift | |
smallest = sorted_distribution.last.pop | |
sorted_distribution.first << smallest | |
sorted_distribution.last << largest | |
if sorted_distribution.map { |w| w.sum }.max > time_required | |
log "settling round produced slower distribution" | |
break | |
end | |
self.distribution = sorted_distribution | |
print_distribution | |
end | |
log | |
print_distribution | |
end | |
def print_distribution | |
log distribution.map { |w| " %3s = #{w.inspect}" % w.sum.to_s }.join("\n") | |
end | |
def time_required | |
distribution.map { |w| w.sum }.max | |
end | |
def log(*args) | |
# puts *args | |
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 | |
# 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