Java: PriorityQueue - продуктовый магазин моделирования

Question

Я работал над этой проблемой последние 10-12 часов , и мне было интересно, если вы, ребята, могли бы помочь мне отладить / указать мне правильное общее направление. Цель программы - смоделировать строку очереди продуктового магазина , которую я пытаюсь выполнить, используя:

• Структура данных PriorityQueue (FIFO)
• System.nanoTime () - для отслеживания прошедшего времени
• SimpleDateFormat - для отслеживания того, когда клиенты входят в очередь (отметка времени)

---

Я проконсультировался с коллегами, службами репетиторства на кампусе, преподавателями и данным учебником курса: «Как программировать на Java: Deitel & Deitel», но безрезультатно.

Предоставленный псевдокодпроблема в следующем ( Я не пытаюсь заставить вас сделать это для меня ):

Запустить симуляцию супермаркета на 12-часовой рабочий день (720 минут), используя следующий алгоритм:

---

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:
Создан новый GroceryStoreSimulation @ [2012/03/13 -01:55:23 AM]

---

Задержка до первого клиента: 1263
Клиент # 0 добавлен в очередь.,.
Размер очереди: 1
0: 2012/03/13 - 01:55:24 AM
Задержка обслуживания: 1373
Заказчик отказался @ [2012/03/13 - 01:55:24AM]
Клиент # 1 добавлен в очередь.,.
Размер очереди: 1
1: 2012/03/13 - 01:55:24 AM
Задержка обслуживания: 2188
Заказчик отказался @ [2012/03/13 - 01:55:24AM]
Клиент # 2 добавлен в очередь..
.
.
.
Задержка обслуживания: 3379
Заказчик, которому отказались @ [2012/03/13 - 01:55:24 AM]
Клиент # 927 добавлен в очередь.,.
Размер очереди: 1
927: 2012/03/13 - 01:55:24 *
Задержка обслуживания: 2300
Задержка обслуживания: 2300BUILD STOPPED (общее время: 1 секунда)

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
}

Надеюсь, это может дать вам некоторые идеи.

Answer 2

Попробуйте изменить

   while((elapsedTime)<(generateAt)){/*Wait*/    
       elapsedTime += System.nanoTime()/10000000; //increment elapsed time
   }

на

   while((elapsedTime)<(generateAt)){/*Wait*/    
       elapsedTime = System.nanoTime()-startTime; //update elapsed time
   }   

ПРИМЕЧАНИЕ. Я полагаю, что вам следует переделать два метода, чтобы не ждать, а просто проверить, пришло ли времяставить в очередь / исключать из очереди клиента.В основном цикле while вы можете добавить Thread.sleep (1000), чтобы каждую 1 секунду вызывать каждый метод, который проверяет, пришло ли время поставить клиента в очередь или снять с нее очередь.После успешного обновления обновите время, в которое следующий человек должен быть обслужен / сгенерирован.