Какой хороший алгоритм для наиболее эффективного редактирования «расписания»?

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

Во всяком случае, по теме: вы можете попробовать заглянуть в штуку под названием «Алгебра интервалов»

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

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

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

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

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

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

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

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

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

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

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

Вы имеете в виду, что промежутки времени, записанные в таблице 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 --|

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

|-------------- 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 -------|

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

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

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

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

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

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