Моделирование на основе событий с использованием очереди приоритетов, реализованной с помощью двоичной кучи

Question

Моделирование на основе событий с использованием очереди приоритетов, реализованной с помощью двоичной кучи

Мне нужно смоделировать выполнение поставленных задач. Это означает, что вам необходимо отслеживать, какие задачи являются активными в любой данный момент времени, и удалять их из активного списка по завершении.

Мне нужно использовать приоритетную очередь для этой проблемы, чтобы быть реализованным с использованием двоичной кучи.

Входные данные состоят из набора задач, заданных в порядке возрастания времени запуска, и каждая задача имеет определенную продолжительность. Первая строка - это количество задач, например

Это означает, что есть 3 задачи. Первый начинается в момент времени 2 и заканчивается в 7 (2+5). Второй начинается в 4, заканчивается в 27. Третий начинается в 7, заканчивается в 11.

Мы можем отслеживать количество активных задач:

Time       #tasks
0 - 2        0
2 - 4        1
4 - 11       2
11 - 27      1

Мне нужно найти:

Максимальное количество активных заданий в любой момент времени (в данном случае 2) и
Среднее количество активных заданий за всю продолжительность вычисляется здесь как:

[0 * (2-0) + 1 * (4-2) + 2 * (11-4) + 1 * (27-11)] / 27

Я написал следующий код для чтения значений времени в структуру:

#include "stdio.h"
#include "stdlib.h"

typedef struct
{
    long int start;
    long int end;
    int dur;
} task;

int main()
{
    long int num_tasks;
    scanf("%ld",&num_tasks);
    task *t = new task[num_tasks];
    for (int i=0;i<num_tasks;i++)
    {
        scanf("%ld %d",&t[i].start,&t[i].dur);
        t[i].end = t[i].start + t[i].dur;
    }
}

Я хотел бы понять, как это можно реализовать в виде очереди с приоритетом кучи, и получить необходимые выходные данные из кучи.

1

c priority-queue heap event-driven event-simulation

Источник

20 сен '18 в 16:57

2 ответа

Решение

Поскольку вы сказали, что для вас будет достаточно псевдокода, я верю вам на слово. Следующее реализовано в 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, потому что, хотя он выглядит как псевдокод, он на самом деле работает и выдает следующий результат:

С РЕАЛИЗАЦИЯ

Наконец-то я потерял некоторое время, чтобы освежить двадцатилетние навыки и реализовать их на 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);
  }
}

И, наконец, реализация очереди приоритетов подняла весь код Rosetta Code, реорганизовала и переключила на использование 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;
}

Итог: этот подход к планированию событий является чрезвычайно гибким и довольно простым для реализации заданных реализаций для очереди приоритетов и механизма моделирования. Как видите, двигатель на самом деле довольно тривиальный.

1

Источник

user2166798 20 сен '18 в 22:19

Другие вопросы по тегам c priority-queue heap event-driven event-simulation

user3386109 20 сен '18 в 17:16 2018-09-20 17:16 · Accepted Answer · 2018-09-20 17:16

Эта проблема может быть решена с помощью двух куч, одна из которых содержит время начала, а другая содержит время окончания. При чтении задач добавьте время начала и окончания к двум кучам. Тогда алгоритм выглядит так:

number_of_tasks = 0

while start_heap not empty
    if min_start_time < min_end_time
       pop min_start_time
       number_of_tasks += 1    
    else if min_end_time < min_start_time
       pop min_end_time
       number_of_tasks -= 1
    else 
       pop min_start_time
       pop min_end_time

while end_heap not empty
       pop min_end_time
       number_of_tasks -= 1