Created
January 27, 2010 08:11
-
-
Save alg/287643 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
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 |
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' | |
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 |
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 '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 |
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 '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 |
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
# 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 |
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 '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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment