logo标签列表

Ruby - 计算超市排队时间

arraysrubymethodsevent-simulation
3
假设在超市的自助结账处有一个队列。我正在尝试编写一个函数来计算所有顾客结账所需的总时间！
输入:
customers: 代表队列的正整数数组。每个整数都代表一个顾客，其值是他们需要结账的时间。
n: 正整数，结账台的数量。
输出:
函数应返回一个整数，即所需的总时间。示例：
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

只有一个队列为多个收银机提供服务，而队列的顺序永远不会改变。队列中前面的人（数组/列表中的第一个元素）会在收银机空闲时立即前往收银机。我尝试过这样做，但它不能正确地工作，我不确定如何使下一个人在收银机可用时进入收银机。

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

谢谢 :-)

5个回答
5

提供以下输入：

customers = [751, 304, 2, 629, 36, 674, 1]
n = 2

您可以创建一个 till 数组，其中每个元素本身也是一个数组。
tills = Array.new(n) { [] }
#=> [[], []]

现在，对于每个客户，您将其价值添加到最短的收银台：
customers.each do |customer|
  tills.min_by(&:sum) << customer
end

最终，这将为您提供：
tills
#=> [[751, 36, 674], [304, 2, 629, 1]]

第一个的总和为1,461。
非常好，Stefan。你可以考虑保持运行总数而不是为每个客户重新计算所有的收银机：customers.each do |customer|; till_assigned = tills.each_with_index.min_by(&:first).last; tills[till_assigned] += customer; end; tills.max。 - Cary Swoveland
将最终的“tills”数组转换为所需的输出，请使用“tills.map（&：sum）。max”。 - 3limin4t0r
2
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
2
您的问题属于离散事件模拟（DES）建模类别。对于简单模型，DES有时可以通过循环和条件处理（如其他答案所述），但如果您计划扩展此模型或构建更复杂的模拟，则需要使用某种事件调度框架，如在此Winter Simulation Conference tutorial中所述。名为simplekit的宝石提供了该教程概念的Ruby实现。（完全披露-我是论文和宝石的作者。）
一个快速的总结是，“事件”在离散时间点发生并更新系统状态。它还可以安排进一步的事件。 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
很高兴了解到你的宝石。 - Cary Swoveland
1

本质上与Stefan的答案相同。不同之处在于，该答案仅跟踪每个收银台的总和运行总数，而不是跟踪顾客并在每次新顾客到来时重新计算其价值。

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
0

我真的很喜欢Stefan's answer，这个答案的工作原理基本相同，但不使用嵌套数组。

首先创建一个收银台数量的数组，每个值都为0。

tills = [0] * 3

然后，遍历客户数组，将每个客户项目添加到找到的最小值索引引用的 till 项目中。

customers.each { |customer| till[till.index(till.min)] += customer }

隐式返回具有最大值的 till 项。

till.max

完整代码：

def queue_time(customers, n)
  till = [0] * n
  customers.each { |customer| till[till.index(till.min)] += customer }
  till.max
end
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接