Какой хороший алгоритм для наиболее эффективного редактирования «графика»? - PullRequest
2 голосов
/ 05 октября 2008

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

РЕДАКТИРОВАТЬ: Как и предполагалось, я значительно сократил вопрос.

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

У меня также есть вторая таблица (таблица B), в которой в качестве внешнего ключа используется идентификатор из таблицы A.

Запись из таблицы A, соответствующая таблице B, будет иметь промежуток времени, который включает промежуток времени из таблицы B. Не все записи в таблице A будут иметь запись в таблице B.

Я предоставляю пользователям интерфейс для редактирования расписания ресурсов в Таблице А. Они в основном предоставляют новый набор данных для Таблицы А, который мне нужно рассматривать как diff из версии в БД. * +1021 *

Если они полностью удаляют объект из таблицы A, на который указывает таблица B, я также хочу удалить запись из таблицы B.

Итак, учитывая следующие 3 комплекта:

  • Исходные объекты из таблицы A (из БД)
  • Исходные объекты из таблицы B (из БД)
  • Отредактированный набор объектов из таблицы A (от пользователя, поэтому нет уникальных идентификаторов)

Мне нужен алгоритм, который будет:

  • Оставьте строки в Таблице A и Таблице B без изменений, если для этих объектов не требуется никаких изменений.
  • При необходимости добавьте строки в таблицу A.
  • При необходимости удалите строки из таблицы A и таблицы B.
  • Измените строки в Таблице A и Таблице B по мере необходимости.

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

Опять же, пожалуйста, ответьте как конкретно или обычно , как вам нравится, я ищу совет, но если у кого-то есть полный алгоритм, который просто сделает мой день. :)

РЕДАКТИРОВАТЬ: В ответ на lassvek, я предоставляю некоторые дополнительные детали:

Элементы таблицы B всегда полностью содержатся в элементах таблицы A, а не просто перекрываются.

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

Например (использовать сокращение):

Table A
ID Resource    Start         End
01 Resource A  10/6 7:00AM   10/6 11:00AM
02 Resource A  10/6 1:00PM   10/6 3:00PM

Table B
ID Table_A_ID  Start         End
01 02          10/6 1:00PM   10/6 2:00PM

Итак, я хочу следующее поведение:

  • Если я удаляю ID 02 из таблицы A или сокращаю его до 14:00 - 15:00, я должен удалить ID 01 из таблицы B.
  • Если я добавлю таблицу A ID 01 туда, где она заканчивается в 13:00, эти две записи должны быть объединены в одну строку , и таблица B ID 01 теперь должна указывать на таблицу A ID 01.
  • Если я удаляю 8:00 утра-10:00 утра из таблицы A ID 01, эту запись следует разделить на две записи: одну для 7:00 AM-8:00AM и новую запись (ID 03) для 10:00 AM. -11: 00 AM.

Ответы [ 5 ]

7 голосов
/ 06 октября 2008

Я много работал с периодами, но, боюсь, я не совсем понимаю, как таблицы А и В работают вместе, возможно, это слово включает , которое я не понимаю.

Можете ли вы привести конкретные примеры того, что вы хотите сделать?

Вы имеете в виду, что временные промежутки, записанные в таблице A, полностью содержат временные промежутки в таблице B, как это?

|---------------- A -------------------|
    |--- B ----|      |--- B ---|

или совпадает с?

    |---------------- A -------------------|
|--- B ----|                        |--- B ---|

или наоборот, интервалы времени в B содержат / перекрываются с A?

Скажем, это первый случай, когда временные интервалы в B находятся внутри / совпадают с временным интервалом в таблице A.

Означает ли это, что:

* A removed A-timespan removes all the linked timespans from B
* An added A-timespan, what about this?
* A shortened A-timespan removes all the linked timespans from B that now falls outside A
* A lenghtened A-timespan, will this include all matching B-timespans now inside?

Вот пример:

|-------------- A1 --------------|    |-------- A2 --------------|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

и затем вы удлиняете А1, укорачиваете и перемещаете А2, так что:

|-------------- A1 ---------------------------------|  |--- A2 --|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

это означает, что вы хотите изменить данные следующим образом:

1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead

как насчет этой модификации, A1 удлиняется, но недостаточно для полного содержания B3, а A2 перемещается / укорачивается таким же образом:

|-------------- A1 -----------------------------|      |--- A2 --|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

Поскольку B3 теперь не полностью находится внутри A1 или A2, удалите его?

Мне нужны конкретные примеры того, что вы хотите сделать.


Редактировать Дополнительные вопросы

Хорошо, а как же:

|------------------ A -----------------------|
  |------- B1 -------|  |------- B2 ------|
                           |---|                   <-- I want to remove this from A

Как насчет этого?

Или:

|------------------ A1 ----|   |---- A2 -----|
  |------- B1 -------|  |B3|   |--- B2 ---|

или

|------------------ A1 ----|   |---- A2 -----|
  |------- B1 -------|

Подводя итог, как я это вижу, с вопросами, пока:

  • Вы хотите иметь возможность выполнять следующие операции с А
    • Сократить
    • удлиняет
    • Объедините, когда они смежные, объединяя два или более в один
    • Пробейте в них отверстия, удалив точку и, таким образом, разделив ее
  • B, которые все еще содержатся в A после вышеприведенного обновления, перепривязать при необходимости
  • Б, которые содержались, но теперь полностью снаружи, удалите их
  • B, которые содержались, но теперь частично снаружи, Редактировать: Удалить их, ref целостность данных
  • Для всех вышеперечисленных операций выполните как минимум минимальную работу, необходимую для приведения данных в соответствие с операциями (вместо того, чтобы просто удалить все и вставить заново)

Я буду работать над реализацией в C #, которая может сработать, когда я вернусь с работы, я вернусь с более поздним вечером.


Редактировать Вот пример алгоритма.

  1. Сначала оптимизировать новый список (т.е. объединить смежные периоды и т. Д.)
  2. «объединить» этот список с основными периодами в базе данных следующим образом:
    1. отслеживать, где в обоих списках (т. Е. Новых и существующих) вы
    2. если текущий новый период полностью предшествует текущему существующему периоду, добавьте его, а затем переходите к следующему новому периоду
    3. если текущий новый период полностью после текущего существующего периода, удалить существующий период и все его дочерние периоды, а затем перейти к следующему существующему периоду
    4. если два перекрываются, откорректируйте текущий существующий период, чтобы он был равен новому периоду, следующим образом, затем перейдите к следующему новому и существующему периоду.
      1. если новый период начинается раньше существующего, просто переместите начало
      2. если новый период начинается после существующего периода, проверьте, есть ли какие-либо дочерние периоды в разностном периоде, и запомните их, затем переместите начало
      3. сделать то же самое с другим концом
  3. с любыми периодами, которые вы "запомнили", посмотрите, нужно ли их повторно связать или удалить

Вам следует создать огромный набор юнит-тестов и убедиться, что вы охватили все комбинации модификаций.

2 голосов
/ 06 октября 2008

Я предлагаю вам разделить ваши вопросы на два отдельных: Первым должно быть что-то вроде: «Как мне рассуждать о планировании ресурсов при представлении атома расписания как ресурса с временем начала и конца?» Здесь предложение ADept об использовании интервальной алгебры кажется подходящим. См. Запись в Википедии «График интервалов» и Запись репозитория алгоритма SUNY при планировании . Второй вопрос - это вопрос базы данных: «Учитывая алгоритм, который планирует интервалы и указывает, перекрываются ли два интервала или один содержится в другом, как я могу использовать эту информацию для управления базой данных в данной схеме?» Я считаю, что, как только алгоритм планирования будет создан, вопрос с базой данных будет гораздо легче решить. НТН, Юваль

1 голос
/ 05 октября 2008

Насколько я понимаю, ваши пользователи могут напрямую влиять только на таблицу А. Предполагая, что вы программируете на C #, вы можете использовать простой набор данных ADO.Net для управления изменениями в таблице А. Адаптер таблиц знает, что нужно оставить только нетронутыми строки обрабатывать новые, измененные и удаленные строки соответствующим образом.

Кроме того, вы должны определить каскадное удаление, чтобы автоматически удалять соответствующие объекты в таблице B.

Единственный случай, который не обрабатывается таким образом, - это если временной интервал в таблице A сокращен s.t. он больше не включает соответствующую запись в таблице B. Вы можете просто проверить этот случай в хранимой процедуре обновления или альтернативно определить триггер обновления в таблице A.

1 голос
/ 05 октября 2008

Мне кажется, что любой алгоритм для этого будет включать в себя пропуск через NewA, сопоставление ResourceID, StartTime и EndTime и отслеживание попадания элементов из OldA. Затем у вас есть два набора несоответствующих данных, UnmatchedNewA и UnmatchedOldA.

Самый простой способ, которым я могу придумать, - это начать все сначала: Запишите все UnmatchedNewA в БД, перенесите элементы B из UnmatchedOldA в новые ключи A (только что сгенерированные), где это возможно, удалив, когда нет. Затем уничтожить все UnmatchedOldA.

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


Невозможно знать, имеет ли это окончательное предложение какой-либо смысл без дополнительной информации, но есть вероятность, что вы не подумали об этом таким образом:

Вместо того, чтобы передавать всю коллекцию A взад и вперед, могли бы вы использовать прослушиватели событий или что-то подобное для обновления модели данных только там, где нужны изменения? Таким образом, изменяемые объекты смогут определять, какие операции БД требуются на лету.

1 голос
/ 05 октября 2008

Вы публикуете статью почти в категории "слишком долго; не читал" - сокращение ее, вероятно, даст вам больше отзывов.

Во всяком случае, по теме: вы можете попробовать заглянуть в вещь под названием "Интервальная алгебра"

...