Алгоритм реализации регистра FIFO

Введение

В информационных системах использующих очереди часто используют стратегия FIFO (акроним First In, First Out — «первым пришёл — первым ушёл»).  Настоящая статья описывает алгоритм Лайтмана для реализации этой стратегии для очереди элементов приходящих и уходящих пакетами произвольных размеров.

Задачей алгоритма является построение соответствия между входящими и уходящими пакетами через включенные в них элементы. Говоря проще, алгоритм позволяет определить из элементов каких приходящих пакетов сформирован уходящий пакет, а также в какие уходящие пакеты попал элемент входящего пакета. Практически алгоритм необходим в широком круге задач, например, при учете серий партий произведенной фармацевтической продукции при ее реализации, или при учете себестоимости продукции, приобретенной партиями с непостоянной закупочной ценой.

Рисунок №1 содержит пример очереди из 24 элементов, которая была образована шестью приходящими пакетами от I:1 до I:6 и частично распределена в четыре уходящих пакета от O:1 до O:4, при этом в очереди еще остается 3 элемента. Замечание: шкалы времени входящих  и уходящих пакетов на рисунке №1 не согласованы и отражают только очередную последовательность пакетов обоих видов, но не их время.

Рисунок №1

Алгоритм

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

  1. в текущей очереди пришедших пакетов в обратном хронологическом порядке от последнего отсчитывается остаток очереди для определения самого раннего присутствующего в очереди пакета его (пакета) остатка.
  2. от найденного входящего пакета уже в прямом хронологическом порядке отсчитываются пакеты с нужным для уходящего пакета суммарным числом элементов.

Этот алгоритм плохо ложится на язык реляционной алгебры, требует выполнения неопределенного числа операций, и мне кажется громоздким и неэффективным.

Принцип алгоритма Лайтмана

Предлагаемый алгоритм основан на предварительной подготовке индексов по каждому приходящему и уходящему пакету.

queued
Рисунок №2
  1. Очередь осуществляет подсчет абсолютного количества пришедших и ушедших элементов от начала существования очереди, таким образом индексируя в хронологическом порядке каждый прошедших через очередь элемент (см. Рисунок №1).
  2.  Для учета приходящих пакетов формируется таблица, в которой пакет упорядочены в хронологическом порядке и при записи каждого пакета в таблице сохраняется его размер и индекс первого элемента. Дополнительно можно также избыточно формировать и хранить индекс последнего элемента пакета для ускорения реализации алгоритма поиска соответствий (см. Рисунок №2а).
  3.  Для учета уходящих пакетов формируется таблица  по структуре аналогичная таблице приходящих пакетов. В ней уходящие пакеты упорядочены в хронологическом порядке и при записи каждого пакета в таблице сохраняется его размер, индекс первого элемента и избыточный индекс последнего элемента (см. Рисунок №2б).
Построения соответствия приходящих пакетов для уходящего
queueo
Рисунок №3

При необходимости формирования состава уходящего пакета из приходящих пакетов (все источники):

  1. Для уходящего пакета из его записи извлекается индекс первого и последнего элемента.
  2. Из таблицы пришедших пакетов выполняется выборка записей пришедших пакетов для которых начальный индекс меньше или равен конечному индексу уходящего пакета, а конечный индекс больше или равен начальному индексу уходящего пакета. Результатом является полный набор входящих пакетов вошедших в уходящий.
  3. Начальный пограничный пакет отсекается как разность между конечным индексом приходящего пакета и начальным индексом уходящего пакета +1.
  4. Конечный пограничный пакет не требует обработки, но для полноты картины можно сказать, что его отсечение определятся как разность между начальным индексом приходящего пакета и конечным индексом уходящего пакета +1.
Построение соответствия уходящих пакетов для приходящего
queuei
Рисунок №4

При необходимости формирования состава приходящего пакета из уходящих пакетов (все получатели):

  1. Для приходящего пакета из его записи извлекается индекс первого и последнего элемента.
  2. Из таблицы ушедших пакетов выполняется выборка записей ушедших пакетов для которых начальный индекс меньше или равен конечному индексу приходящего пакета, а конечный индекс больше или равен начальному индексу приходящего пакета.
  3. Начальный пограничный пакет отсекается как разность между конечным индексом уходящего пакета и начальным индексом приходящего пакета +1.
  4. Конечный пограничный пакет не требует обработки, но для полноты картины можно сказать, что его отсечение определятся как разность между начальным индексом уходящего пакета и конечным индексом приходящего пакета +1.

Примеры реализации на SQL

Приведенные ниже sql-выражения в первую очередь созданы  для наглядности в ущерб эффективности.

Остаток очереди:

(select sum (In) from I) 
- (select sum (Out) from O)

Соответствие приходящих пакетов к уходящему (все источники):

select * from I where (I.first < O.last) and (O.first < I.last)

Соответствие уходящих пакетов приходящему (все получатели):

select * from O where (O.first < I.last) and (I.first < O.last)

В заключении

  1. Предложенный Лайтманом алгоритм легко ложится на язык реляционной алгебры.
  2. Если в таблицы входящих и уходящих пакетов добавить атрибут для позиционирования пакетов на шкале времени, то это позволит определять состояние очереди на любой произвольный момент времени.
  3. Алгоритм Лайтмана может быть реализован средствами регистра накопления 1С. Для этого необходимо в регистр добавить два ресурса ИндексПрихода и ИндексУхода. При проведении приходящего пакета в ИндексПрихода необходимо вносить количество прихода. В результате работы регистра накопительным итогом ИндексаПрихода будет начальный индекс следующего пакета, из которого можно вычислением получить индексы самого приходящего пакета. ИндексРасхода необходимо вносить количество для расхода, чтобы регистр накопления мог вычислить начальный индекс следующего уходящего пакета.
  4. Настоящая статья посвящена алгоритму построения соответствия между пакетами, а не способу индексирования. Приведенная индексация была выбрана по соображениям наглядности, поэтому более профессиональное индексирование элементов от 0 и индексирование первого элемента в следующем пакете вместо последнего элемента здесь не было применено намерено.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *