ruby - 计算超市排队时间
ruby - calculating time in supermarket queue
假设超市的自助收银台排起了长队。我正在尝试编写一个函数来计算所有客户结账所需的总时间！
输入：
customers：代表队列的正整数数组。每个整数代表一个客户，它的值是他们结账所需的时间。
n：正整数，结账次数。
输出：
函数应该return一个整数，需要的总时间。示例：
queue_time([5,3,4], 1)
# should return 12
# because when n=1, the total time is just the sum of the times
queue_time([10,2,3,3], 2)
# should return 10
# because here n=2 and the 2nd, 3rd, and 4th people in the
# queue finish before the 1st person has finished.
queue_time([2,3,10], 2)
# should return 12
只有一个队列服务于多个收银机，并且
队列的顺序永远不会改变。
队列中最前面的人（array/list 中的第一个元素）一有空就去收银台。
我试过了，但它不能正常工作，我不确定如何让下一个人进入
直到它打开。
def queue_time(customers, n)
if customers == []
n=0
else
x= customers.reduce(:+) / n
if x < customers.max
customers.max
else
x
end
end
end
例如，测试
customers = [751, 304, 2, 629, 36, 674, 1]
n = 2
expected: 1461, instead got: 1198
。谢谢:-)
def queue_time(time_required, n)
remaining_time_by_line = Array.new(n) { 0 }
curr_time = 0
time_required.each do |t|
wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
curr_time += wait_time
remaining_time_by_line.map! { |rt| rt - wait_time }
remaining_time_by_line[line_assigned] = t
end
curr_time + remaining_time_by_line.max
end
queue_time([5,3,4], 1)
#=> 12
queue_time([10,2,3,3], 2)
#=> 10
queue_time([2,3,10], 2)
#=> 12
queue_time([2,3,4,1,2,5], 3)
#=> 8
queue_time([751, 304, 2, 629, 36, 674, 1], 2)
#=> 1461
在用 puts 语句加盐后执行该方法，我可以最轻松地解释计算。
def queue_time(time_required, n)
remaining_time_by_line = Array.new(n) { 0 }
curr_time = 0
time_required.each do |t|
wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
curr_time += wait_time
puts "\ntime required, t = #{t}"
puts "line_assigned = #{line_assigned}"
puts "wait_time = #{wait_time}"
puts "curr_time = #{curr_time}"
remaining_time_by_line.map! { |rt| rt - wait_time }
remaining_time_by_line[line_assigned] = t
puts "remaining_times_by_line = #{remaining_time_by_line}"
end
puts "\nremaining_time_by_line.max = #{remaining_time_by_line.max}"
tot = curr_time + remaining_time_by_line.max
puts "curr_time + remaining_time_by_line.max = #{tot}"
tot
end
queue_time([2,3,4,1,2,5], 3)
#=> 8
显示如下。
time required, t = 2
line_assigned = 0
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 0, 0]
time required, t = 3
line_assigned = 1
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 0]
time required, t = 4
line_assigned = 2
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 4]
time required, t = 1
line_assigned = 0
wait_time = 2
curr_time = 2
remaining_times_by_line = [1, 1, 2]
time required, t = 2
line_assigned = 0
wait_time = 1
curr_time = 3
remaining_times_by_line = [2, 0, 1]
time required, t = 5
line_assigned = 1
wait_time = 0
curr_time = 3
remaining_times_by_line = [2, 5, 1]
remaining_time_by_line.max = 5
curr_time + remaining_time_by_line.max = 8
给定输入：
customers = [751, 304, 2, 629, 36, 674, 1]
n = 2
您可以创建一个数组：（每个数组本身就是一个数组）
tills = Array.new(n) { [] }
#=> [[], []]
现在，对于每个客户，您将其价值添加到最短的时间：
customers.each do |customer|
tills.min_by(&:sum) << customer
end
最后，这给你：
tills
#=> [[751, 36, 674], [304, 2, 629, 1]]
第一个总和为1,461。
您的问题属于离散事件仿真 (DES) 建模的范畴。对于简单的模型 DES 有时可以通过循环和条件处理（如提供的其他答案），但如果您计划扩展此模型或构建更复杂的模拟，您将需要使用某种事件调度框架，如所述在此 Winter Simulation Conference tutorial. A gem called simplekit 中提供了教程中概念的 Ruby 实现。 （完全披露——我是论文的作者和 gem。）
一个简短的总结是“事件”发生在离散的时间点并更新系统状态。它还可以安排进一步的事件。 DES 框架维护一组未决事件作为优先级队列，以便事件以正确的顺序发生，尽管在事件被安排和执行之间存在时间延迟。所有这些都由框架提供的方法相对透明地处理。
这里是你的模型的一个实现，带有不同的参数化，有大量注释：
require 'simplekit'
class MyModel
include SimpleKit
# Constructor - initializes the model parameters.
# param: service_times - An array of service times for each customer
# param: max_servers - The total number of servers in the system.
def initialize(service_times, max_servers)
@service_times = service_times.clone
@max_servers = max_servers
end
# Initialize the model state and schedule an initial set of events.
def init
@num_available_servers = @max_servers
# As long as servers remain available and there are customers
# remaining, schedule the end_service for the next customer
# to occur after a delay equal to the customer's service time.
# The number of available servers gets reduced by one.
while @num_available_servers > 0 && !@service_times.empty? do
schedule(:end_service, @service_times.shift)
@num_available_servers -= 1
end
end
# Every time there's an end of service, see if there's another customer
# waiting in line. If so, schedule their end_service (and the current
# server remains tied up), otherwise the current server gets freed up.
#
# This model will terminate when there are no more events scheduled,
# which happens when all the end_services have completed.
def end_service
if @service_times.empty?
@num_available_servers += 1
else
schedule(:end_service, @service_times.shift)
end
end
end
model_params = [
[[5,3,4], 1],
[[10,2,3,3], 2],
[[2,3,10], 2],
[[2,3,4,1,2,5], 3],
[[751, 304, 2, 629, 36, 674, 1], 2]
]
# SimpleKit models track and update the model_time automatically for you,
# so the current_model's model_time reflects what time it was in the
# model when the last event occurred.
model_params.each do |svc_times, servers|
current_model = MyModel.new(svc_times, servers)
current_model.run
puts "#{svc_times}, #{servers} => #{current_model.model_time}"
end
产生以下输出：
[5, 3, 4], 1 => 12.0
[10, 2, 3, 3], 2 => 10.0
[2, 3, 10], 2 => 12.0
[2, 3, 4, 1, 2, 5], 3 => 8.0
[751, 304, 2, 629, 36, 674, 1], 2 => 1461.0
与基本相同。不同之处在于，此答案仅跟踪每次结帐时的总和 运行 总数，而不是跟踪客户并在每次新客户到达时重新汇总他们的价值。
def queue_time(customers, n)
till = Struct.new(:sum)
tills = Array.new(n) { till.new(0) }
customers.each do |customer|
tills.min_by(&:sum).sum += customer
end
tills.map(&:sum).max
end
假设超市的自助收银台排起了长队。我正在尝试编写一个函数来计算所有客户结账所需的总时间！
输入：
customers：代表队列的正整数数组。每个整数代表一个客户，它的值是他们结账所需的时间。
n：正整数，结账次数。
输出：
函数应该return一个整数，需要的总时间。示例：
queue_time([5,3,4], 1)
# should return 12
# because when n=1, the total time is just the sum of the times
queue_time([10,2,3,3], 2)
# should return 10
# because here n=2 and the 2nd, 3rd, and 4th people in the
# queue finish before the 1st person has finished.
queue_time([2,3,10], 2)
# should return 12
只有一个队列服务于多个收银机，并且 队列的顺序永远不会改变。 队列中最前面的人（array/list 中的第一个元素）一有空就去收银台。 我试过了，但它不能正常工作，我不确定如何让下一个人进入 直到它打开。
def queue_time(customers, n)
if customers == []
n=0
else
x= customers.reduce(:+) / n
if x < customers.max
customers.max
else
x
end
end
end
例如，测试
customers = [751, 304, 2, 629, 36, 674, 1]
n = 2
expected: 1461, instead got: 1198
。谢谢:-)
def queue_time(time_required, n)
remaining_time_by_line = Array.new(n) { 0 }
curr_time = 0
time_required.each do |t|
wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
curr_time += wait_time
remaining_time_by_line.map! { |rt| rt - wait_time }
remaining_time_by_line[line_assigned] = t
end
curr_time + remaining_time_by_line.max
end
queue_time([5,3,4], 1)
#=> 12
queue_time([10,2,3,3], 2)
#=> 10
queue_time([2,3,10], 2)
#=> 12
queue_time([2,3,4,1,2,5], 3)
#=> 8
queue_time([751, 304, 2, 629, 36, 674, 1], 2)
#=> 1461
在用 puts 语句加盐后执行该方法，我可以最轻松地解释计算。
def queue_time(time_required, n)
remaining_time_by_line = Array.new(n) { 0 }
curr_time = 0
time_required.each do |t|
wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
curr_time += wait_time
puts "\ntime required, t = #{t}"
puts "line_assigned = #{line_assigned}"
puts "wait_time = #{wait_time}"
puts "curr_time = #{curr_time}"
remaining_time_by_line.map! { |rt| rt - wait_time }
remaining_time_by_line[line_assigned] = t
puts "remaining_times_by_line = #{remaining_time_by_line}"
end
puts "\nremaining_time_by_line.max = #{remaining_time_by_line.max}"
tot = curr_time + remaining_time_by_line.max
puts "curr_time + remaining_time_by_line.max = #{tot}"
tot
end
queue_time([2,3,4,1,2,5], 3)
#=> 8
显示如下。
time required, t = 2
line_assigned = 0
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 0, 0]
time required, t = 3
line_assigned = 1
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 0]
time required, t = 4
line_assigned = 2
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 4]
time required, t = 1
line_assigned = 0
wait_time = 2
curr_time = 2
remaining_times_by_line = [1, 1, 2]
time required, t = 2
line_assigned = 0
wait_time = 1
curr_time = 3
remaining_times_by_line = [2, 0, 1]
time required, t = 5
line_assigned = 1
wait_time = 0
curr_time = 3
remaining_times_by_line = [2, 5, 1]
remaining_time_by_line.max = 5
curr_time + remaining_time_by_line.max = 8
给定输入：
customers = [751, 304, 2, 629, 36, 674, 1]
n = 2
您可以创建一个数组：（每个数组本身就是一个数组）
tills = Array.new(n) { [] }
#=> [[], []]
现在，对于每个客户，您将其价值添加到最短的时间：
customers.each do |customer|
tills.min_by(&:sum) << customer
end
最后，这给你：
tills
#=> [[751, 36, 674], [304, 2, 629, 1]]
第一个总和为1,461。
您的问题属于离散事件仿真 (DES) 建模的范畴。对于简单的模型 DES 有时可以通过循环和条件处理（如提供的其他答案），但如果您计划扩展此模型或构建更复杂的模拟，您将需要使用某种事件调度框架，如所述在此 Winter Simulation Conference tutorial. A gem called simplekit 中提供了教程中概念的 Ruby 实现。 （完全披露——我是论文的作者和 gem。）
一个简短的总结是“事件”发生在离散的时间点并更新系统状态。它还可以安排进一步的事件。 DES 框架维护一组未决事件作为优先级队列，以便事件以正确的顺序发生，尽管在事件被安排和执行之间存在时间延迟。所有这些都由框架提供的方法相对透明地处理。
这里是你的模型的一个实现，带有不同的参数化，有大量注释：
require 'simplekit'
class MyModel
include SimpleKit
# Constructor - initializes the model parameters.
# param: service_times - An array of service times for each customer
# param: max_servers - The total number of servers in the system.
def initialize(service_times, max_servers)
@service_times = service_times.clone
@max_servers = max_servers
end
# Initialize the model state and schedule an initial set of events.
def init
@num_available_servers = @max_servers
# As long as servers remain available and there are customers
# remaining, schedule the end_service for the next customer
# to occur after a delay equal to the customer's service time.
# The number of available servers gets reduced by one.
while @num_available_servers > 0 && !@service_times.empty? do
schedule(:end_service, @service_times.shift)
@num_available_servers -= 1
end
end
# Every time there's an end of service, see if there's another customer
# waiting in line. If so, schedule their end_service (and the current
# server remains tied up), otherwise the current server gets freed up.
#
# This model will terminate when there are no more events scheduled,
# which happens when all the end_services have completed.
def end_service
if @service_times.empty?
@num_available_servers += 1
else
schedule(:end_service, @service_times.shift)
end
end
end
model_params = [
[[5,3,4], 1],
[[10,2,3,3], 2],
[[2,3,10], 2],
[[2,3,4,1,2,5], 3],
[[751, 304, 2, 629, 36, 674, 1], 2]
]
# SimpleKit models track and update the model_time automatically for you,
# so the current_model's model_time reflects what time it was in the
# model when the last event occurred.
model_params.each do |svc_times, servers|
current_model = MyModel.new(svc_times, servers)
current_model.run
puts "#{svc_times}, #{servers} => #{current_model.model_time}"
end
产生以下输出：
[5, 3, 4], 1 => 12.0
[10, 2, 3, 3], 2 => 10.0
[2, 3, 10], 2 => 12.0
[2, 3, 4, 1, 2, 5], 3 => 8.0
[751, 304, 2, 629, 36, 674, 1], 2 => 1461.0
与
def queue_time(customers, n)
till = Struct.new(:sum)
tills = Array.new(n) { till.new(0) }
customers.each do |customer|
tills.min_by(&:sum).sum += customer
end
tills.map(&:sum).max
end