Java:PriorityQueue - 杂货店模拟

Question

在过去的 10-12 个小时里，我一直在努力解决这个问题，并且想知道你们是否可以帮助我调试/指出正确的总体方向。 该程序的目标是模拟杂货店排队，我试图使用以下方法来完成:

• PriorityQueue (FIFO) 数据结构
• System.nanoTime() - 跟踪耗时
• SimpleDateFormat - 跟踪客户何时进入队列(时间戳)

---

我咨询了同事、校内辅导服务、教授和给定的类(class)教科书:“Java How To Program: Deitel & Deitel”，但都无济于事。

为该问题提供的伪代码如下(我不是想让你帮我做):

Run the supermarket simulation for a 12-hour day (720 minutes), using the following algorithm:

---

1. 选择一个介于 1 和 4 之间的随机整数来确定第一个客户到达的时间
2. 在客户第一次到达时，执行以下操作:
   • 确定客户的服务时间(1到4的随机整数)
3. 开始为客户提供服务
   • 安排下一位顾客的到达时间(当前时间加上 1 到 4 的随机整数)
4. 对于一天中的每一分钟，请考虑以下事项:
   • 如果下一位顾客到达，请执行以下操作:
   • 这么说。
   • 让客户排队。
   • 安排下一位顾客的到达时间。
   • 如果为最后一位客户完成了服务，请执行以下操作:
     • 这么说。
     • 出队下一个要服务的客户
     • 确定客户的服务完成时间(1到4的随机整数加到当前时间)

我遇到的问题:

1. 尝试在客户到达/接受服务时“延迟”程序是无效的(也许是 System.nanoTime() 计算错误？(我已经仔细检查了所有计算，可能仍然是错误的) - 请参阅:newCustomer()、serveCustomer()
2. 84983 名顾客在 1 分钟结束时，不合逻辑，因为顾客到达之间有 1-4 分钟的延迟(时间问题)
3. 队列的大小从不增加，客户被添加，然后线性删除(错误)

注意

• 出于测试目的，我已将模拟时间缩短为 1 分钟
• 我不能使用多线程方法来解决这个问题，必须在单线程上使用 FIFO 来解决
• 客户每隔 1 到 4 秒到达一次，出于测试目的缩短

这是我的代码:

package grocerystoresimulation;
/*
* @import
*/
import java.util.PriorityQueue;
import java.util.Random;
import java.util.ArrayList;
import java.util.Date;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
/*
* @author: Tyler J Fisher
* Date: 2/27/2012
*/
public class GroceryStoreSimulation {

/*
* @fields 
*/
private PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
private Random rand = new Random(); //instantiate new Random object    

private Date date = new Date();
private DateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd - hh:mm:ss a"); 
private ArrayList<String> timeStamp = new ArrayList<String>(); //store timestamps

private int totalCustomers; //# of customers served during simulation

private long startTime = System.nanoTime(); //time of initial build
private long simulationTime = 1; //desired time in minutes
private long firstWaitTime = generateWaitTime(); 
private long serviceCustomerAt;

/*
* @constuctor
*/
public GroceryStoreSimulation(){
    System.out.println("Instantiated new GroceryStoreSimulation @ ["
            + dateFormat.format(date) + "]\n" + insertDivider());
} //GroceryStoreSimulation()

public void run(){
    //Main program body
    try {
        Thread.sleep(firstWaitTime); //generate wait time for first customer
        System.out.println("Delay until first customer: " + firstWaitTime);
        newCustomer(totalCustomers);
        serveCustomer();
    } catch (InterruptedException e){/*Catch 'em all*/}

    while((System.nanoTime()-startTime)<=(simulationTime*60000000000L)-firstWaitTime){
        try {
            newCustomer(totalCustomers); //enque customer 
            serveCustomer();
        } catch(Exception e){/*Catch 'em all*/}
    }
    System.out.println("Exit");
    System.exit(0); //stop runtime
} //run()

/*
* @return String
*/ 
@Override 
public String toString(){
    return this.pq.toString();
} //toString()

private void serveCustomer(){
    long elapsedTime = System.nanoTime()-startTime;
    while((elapsedTime)<(serviceCustomerAt)){ 
        elapsedTime += System.nanoTime()/10000000;
    }
    if(pq.size()!=0){
        System.out.println("Dequeued customer @[" + dateFormat.format(new Date())
                + "]");
        pq.poll(); //remove first element of queue
    } else {
        System.out.println("ERROR: Queue is empty!");
    }
} //serveCustomer()

/*
* @param String ID
*/ 
private void newCustomer(int ID){
    long elapsedTime = System.nanoTime()-startTime;
    long waitTime = (long)generateWaitTime()*1000000;
    long generateAt = elapsedTime+waitTime;

    while((elapsedTime)<(generateAt)){/*Wait*/    
        elapsedTime += System.nanoTime()/10000000; //increment elapsed time
    }      
    serviceCustomerAt = 0; //reset service wait time value
    System.out.println("Customer # " + totalCustomers + " added to queue. . .");
    totalCustomers++;
    pq.offer(ID); //insert element into PriorityQueue
    System.out.println("Queue size: " + pq.size()); //output linesize
    assignTimestamp(ID); //call assignArrivalTime() method

    //Calculate time until customer served
    waitTime = (long)generateWaitTime()*1000000;
    elapsedTime = System.nanoTime()-startTime;

    serviceCustomerAt = elapsedTime + waitTime;
    System.out.println("Service delay: " + waitTime/1000000);
} //newCustomer()

/*
* @param String ID 
*/
private void assignTimestamp(int ID){
    timeStamp.add(ID + ": " + dateFormat.format(new Date()));
    System.out.println(timeStamp.get(totalCustomers-1));
} //assignArrivalTime()

* @return int 
*/
private int generateWaitTime(){
    //Local variables
    int Low = 1000;  //1000ms
    int High = 4000; //4000ms
    return rand.nextInt(High-Low) + Low;
}//generateWaitTime()

/*
* @return String
*/
private static String insertDivider(){
    return ("****");
}//insertDivider()

输出:

run:
Instantiated new GroceryStoreSimulation @ [2012/03/13 - 01:55:23 AM]

---

Delay until first customer: 1263
Customer # 0 added to queue. . .
Queue size: 1
0: 2012/03/13 - 01:55:24 AM
Service delay: 1373
Dequeued customer @[2012/03/13 - 01:55:24 AM]
Customer # 1 added to queue. . .
Queue size: 1
1: 2012/03/13 - 01:55:24 AM
Service delay: 2188
Dequeued customer @[2012/03/13 - 01:55:24 AM]
Customer # 2 added to queue. .
.
.
.
Service delay: 3379
Dequeued customer @[2012/03/13 - 01:55:24 AM]
Customer # 927 added to queue. . .
Queue size: 1
927: 2012/03/13 - 01:55:24 AM
Service delay: 2300
Service delay: 2300BUILD STOPPED (total time: 1 second)

Answer 1

需要考虑的几件事:

您正在模拟一天 12 小时，分辨率为 1 分钟，没有必要让您的程序实际运行任何特定的时间(即任何时候都不需要 Thread.sleep()。

您确实需要一个 FIFO 队列，PriorityQueue 根据定义不是 FIFO 队列。 (我还没有检查它是否真的对你的情况有所影响，但你应该知道其中的区别)。

做这样的事情:

try {
  newCustomer(totalCustomers); //enque customer
  serveCustomer();
} catch(Exception e){/*Catch 'em all*/}

只会导致沮丧和拉头发。

编辑

除非有使用 sleep() 为您的代码计时的特定要求(不清楚，但我假设没有)，像这样的事情会容易得多:

for(int minute = 0; minute < 720; minute++){
  // process customer arrival and service
}

希望这能给你一些想法。