Поскольку вы сказали, что для вас будет достаточно псевдокода, я верю вам на слово.Следующее реализовано в Ruby, который похож на выполняемый псевдокод.Я также прокомментировал это довольно широко.
Подход, изложенный здесь, требует только одной очереди приоритетов.Ваша модель концептуально вращается вокруг двух событий - когда начинается задача и когда она заканчивается.Очень гибкий механизм реализации дискретных событий состоит в том, чтобы использовать очередь приоритетов для хранения уведомлений о событиях, упорядоченных к моменту возникновения события.Каждое событие реализовано в виде отдельного метода / функции, которая выполняет любые переходы состояний, связанные с событием, и может планировать дальнейшие события, помещая их уведомления о событиях в приоритетную очередь.Затем вам нужен исполнительный цикл, который продолжает извлекать уведомления о событиях из приоритетной очереди, обновляет часы до времени текущего события и вызывает соответствующий метод события.Для получения дополнительной информации об этом подходе см. этот документ .В документе эти концепции реализованы в Java, но они могут быть (и реализованы) на многих других языках.
Без лишних слов, вот рабочая реализация для вашего случая:
# User needs to type "gem install simplekit" on the command line to
# snag a copy of this library from the public gem repository
require 'simplekit' # contains a PriorityQueue implementation
# define an "event notice" structure which stores the tag for an event method,
# the time the event should occur, and what arguments are to be passed to it.
EVENT_NOTICE = Struct.new(:event, :time, :args) {
include Comparable
def <=>(other) # define a comparison ordering based on my time vs other's time
return time - other.time # comparison of two times is positive, zero, or negative
end
}
@pq = PriorityQueue.new # @ makes globally shared (not really, but close enough for illustration purposes)
@num_tasks = 0 # number of tasks currently active
@clock = 0 # current time in the simulation
# define a report method
def report()
puts "#{@clock}: #{@num_tasks}" # print current simulation time & num_tasks
end
# define an event for starting a task, that increments the @num_tasks counter
# and uses the @clock and task duration to schedule when this task will end
# by pushing a suitable EVENT_NOTICE onto the priority queue.
def start_task(current_task)
@num_tasks += 1
@pq.push(EVENT_NOTICE.new(:end_task, @clock + current_task.duration, nil))
report()
end
# define an event for ending a task, which decrements the counter
def end_task(_) # _ means ignore any argument
@num_tasks -= 1
report()
end
# define a task as a suitable structure containing start time and duration
task = Struct.new(:start, :duration)
# Create a set of three tasks. I've wired them in, but they could
# be read in or generated dynamically.
task_set = [task.new(2, 5), task.new(4, 23), task.new(7, 4)]
# Add each of the task's start_task event to the priority queue, ordered
# by time of occurrence (as specified in EVENT_NOTICE)
for t in task_set
@pq.push(EVENT_NOTICE.new(:start_task, t.start, t))
end
report()
# Keep popping EVENT_NOTICE's off the priority queue until you run out. For
# each notice, update the @clock and invoke the event contained in the notice
until @pq.empty?
current_event = @pq.pop
@clock = current_event.time
send(current_event.event, current_event.args)
end
Я использовал Ruby, потому что, хотя он выглядит как псевдокод, он на самом деле работает и выдает следующий вывод:
0: 0
2: 1
4: 2
7: 1
7: 2
11: 1
27: 0
C РЕАЛИЗАЦИЯ
Наконец-то я потерял время, чтобы почиститьизучите двадцатилетние навыки и внедрите их в C. Структура очень похожа на структуру Ruby, но есть гораздо больше деталей, которыми нужно управлять.Я учел это в модели, механизме моделирования и куче, чтобы показать, что исполнительный цикл отличается от специфики любой конкретной модели.Вот сама реализация модели, которая иллюстрирует ориентацию «события - функции» построения модели.
model.c
#include <stdio.h>
#include <stdlib.h>
#include "sim_engine.h"
// define a task as a suitable structure containing start time and duration
typedef struct {
double start;
double duration;
} task;
// stamp out new tasks on demand
task* new_task(double start, double duration) {
task* t = (task*) calloc(1, sizeof(task));
t->start = start;
t->duration = duration;
return t;
}
// create state variables
static int num_tasks;
// provide reporting
void report() {
// print current simulation time & num_tasks
printf("%8.3lf: %d\n", sim_time(), num_tasks);
}
// define an event for ending a task, which decrements the counter
void end_task(void* current_task) {
--num_tasks;
free(current_task);
report();
}
// define an event for starting a task, that increments the num_tasks counter
// and uses the task duration to schedule when this task will end.
void start_task(void* current_task) {
++num_tasks;
schedule(end_task, ((task*) current_task)->duration, current_task);
report();
}
// all event graphs must supply an initialize event to kickstart the process.
void initialize() {
num_tasks = 0; // number of tasks currently active
// Create an initial set of three tasks. I've wired them in, but they could
// be read in or generated dynamically.
task* task_set[] = {
new_task(2.0, 5.0), new_task(4.0, 23.0), new_task(7.0, 4.0)
};
// Add each of the task's start_task event to the priority queue, ordered
// by time of occurrence. In general, though, events can be scheduled
// dynamically from trigger events.
for(int i = 0; i < 3; ++i) {
schedule(start_task, task_set[i]->start, task_set[i]);
}
report();
}
int main() {
run_sim();
return 0;
}
Обратите внимание на сильное сходство компоновки с реализацией Ruby.За исключением времени с плавающей запятой, вывод идентичен версии Ruby.(Ruby также дал бы десятичные знаки, если бы они были необходимы, но с пробными заданиями, заданными OP, в этом не было необходимости.)
Далее идут заголовки и реализация механизма моделирования.Обратите внимание, что это разработано, чтобы изолировать построителя модели от непосредственного использования очереди с приоритетами.Детали обрабатываются schedule() внешним интерфейсом для помещения вещей в список событий и исполнительным циклом для извлечения и запуска вещей в нужный момент времени.
sim_engine.h
typedef void (*event_p)(void*);
void initialize();
void schedule(event_p event, double delay, void* args);
void run_sim();
double sim_time();
sim_engine.c
#include <stdlib.h>
#include "sim_engine.h"
#include "heap.h"
typedef struct {
double time;
event_p event;
void* args;
} event_notice;
static heap_t *event_list;
static double sim_clock;
// return the current simulated time on demand
double sim_time() {
return sim_clock;
}
// schedule the specified event to occur after the specified delay, with args
void schedule(event_p event, double delay, void* args) {
event_notice* en = (event_notice*) calloc(1, sizeof(event_notice));
en->time = sim_clock + delay;
en->event = event;
en->args = args;
push(event_list, en->time, en);
}
// simulation executive loop.
void run_sim() {
event_list = (heap_t *) calloc(1, sizeof(heap_t));
sim_clock = 0.0; // initialize time in the simulation
initialize();
// Keep popping event_notice's off the priority queue until you run out. For
// each notice, update the clock, invoke the event contained in the notice,
// and cleanup.
while(event_list->len > 0) {
event_notice* current_event = pop(event_list);
sim_clock = current_event->time;
current_event->event(current_event->args);
free(current_event);
}
}
И, наконец, реализация очереди приоритетов подняла весь код с кода Розетты, подверглась рефакторингу и переключилась на использование void* для полезной нагрузки данных, а не для строк.
heap.h
typedef struct {
double priority;
void *data;
} node_t;
typedef struct {
node_t *nodes;
int len;
int size;
} heap_t;
void push(heap_t *h, double priority, void *data);
void *pop(heap_t *h);
heap.c
#include <stdlib.h>
#include "heap.h"
void push(heap_t *h, double priority, void *data) {
if (h->len + 1 >= h->size) {
h->size = h->size ? h->size * 2 : 4;
h->nodes = (node_t *)realloc(h->nodes, h->size * sizeof (node_t));
}
int i = h->len + 1;
int j = i / 2;
while (i > 1 && h->nodes[j].priority > priority) {
h->nodes[i] = h->nodes[j];
i = j;
j = j / 2;
}
h->nodes[i].priority = priority;
h->nodes[i].data = data;
h->len++;
}
void *pop(heap_t *h) {
int i, j, k;
if (!h->len) {
return NULL;
}
void *data = h->nodes[1].data;
h->nodes[1] = h->nodes[h->len];
h->len--;
i = 1;
while (i!=h->len+1) {
k = h->len+1;
j = 2 * i;
if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) {
k = j;
}
if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) {
k = j + 1;
}
h->nodes[i] = h->nodes[k];
i = k;
}
return data;
}
Итог: этот подход к планированию событий чрезвычайно гибок и довольно прост в реализации заданных реализаций для очереди с приоритетамии двигатель моделирования.Как видите, двигатель на самом деле довольно тривиальный.