Какой хороший алгоритм для наиболее эффективного редактирования “расписания”?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Это для небольшого приложения для планирования.Мне нужен алгоритм для эффективного сравнения двух "расписаний", поиска различий и обновления только тех строк данных, которые были изменены, а также записей в другой таблице, имеющей эту таблицу в качестве внешнего ключа.Это большой вопрос, поэтому я сразу скажу, что я ищу либо общие рекомендации или конкретные решения.
Редактировать: Как и было предложено, я значительно сократил вопрос.
В одной таблице я связываю ресурсы с промежутком времени, когда они используются.
У меня также есть вторая таблица (таблица B), которая использует идентификатор из таблицы A в качестве внешнего ключа.
Запись из таблицы A, соответствующая таблице B, будет иметь промежуток времени, который включает в себя промежуток времени из таблицы B.Не все записи в таблице A будут содержать запись в таблице B.
Я предоставляю пользователям интерфейс для редактирования расписания ресурсов в таблице A.Они в основном предоставляют новый набор данных для таблицы A, которые мне нужно рассматривать как разница из версии в базе данных.
Если они полностью удаляют объект из таблицы A, на который указывает таблица B, я хочу также удалить запись из таблицы B.
Итак, учитывая следующие 3 набора:
- Исходные объекты из таблицы A (из базы данных)
- Исходные объекты из таблицы B (из базы данных)
- Отредактированный набор объектов из таблицы A (от пользователя, поэтому уникальных идентификаторов нет)
Мне нужен алгоритм, который будет:
- Оставьте строки в таблицах A и B нетронутыми, если для этих объектов не требуется никаких изменений.
- Добавляйте строки в таблицу A по мере необходимости.
- Удаляйте строки из таблиц A и B по мере необходимости.
- Измените строки в таблицах A и B по мере необходимости.
Простой сортировки объектов таким образом, чтобы я мог применять соответствующие операции с базой данных, более чем достаточно для решения.
Еще раз, пожалуйста, ответьте следующим образом в частности или в целом как вам угодно, я ищу совета, но если у кого-то есть полный алгоритм, который просто улучшил бы мой день.:)
Редактировать: В ответ на лассвека я привожу некоторые дополнительные подробности:
Элементы таблицы 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
Итак, я хочу, чтобы было следующее поведение:
- Если я удалю идентификатор 02 из таблицы A или сокращу его до 14:00 - 15:00, я должен удалить идентификатор 01 из таблицы B.
- Если я расширю таблицу с идентификатором 01 до того места, где она заканчивается в 13:00, эти две записи должны быть объединены в одну строку, и таблица B ID 01 теперь должна указывать на таблицу A ID 01.
- Если я удалю 8:00-10:00 из таблицы с идентификатором 01, эта запись должна быть разделена на две записи:Один для 7:00-8:00 утра и новая запись (ID 03) для 10:00-11:00 утра.
Решение
Я много работал с периодами, но, боюсь, я не совсем понимаю, как таблицы 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 -------|
Подводя итог тому, как я это вижу, с вопросами, пока:
- Вы хотите иметь возможность выполнять следующие операции над
- Укоротить
- Удлинить
- Объединяйте, когда они находятся рядом, объединяя два или более в один
- Пробейте в них отверстия, удалив точку и таким образом разделив ее
- B, которые все еще содержатся в A после вышеупомянутого обновления, при необходимости повторно свяжите
- B, которые содержались, но теперь полностью находятся снаружи, удалите их
- B, которые были сохранены, но теперь частично находятся снаружи, Редактировать:Удалите их, восстановив целостность данных
- Для всех вышеперечисленных операций выполните минимум работы, необходимой для приведения данных в соответствие с операциями (вместо того, чтобы просто удалять все и вставлять заново)
Я буду работать над реализацией на C #, которая может сработать, когда я вернусь домой с работы, я вернусь с большим количеством позже сегодня вечером.
Редактировать Вот примерный пример алгоритма.
- Сначала оптимизируйте новый список (т.е.объединять смежные периоды и т.д.)
- "объедините" этот список с основными периодами в базе данных следующим образом:
- следите за тем, где в обоих списках (т.е.новые и существующие) вы
- если текущий новый период полностью предшествует текущему существующему периоду, добавьте его, затем перейдите к следующему новому периоду
- если текущий новый период полностью заканчивается текущим существующим периодом, удалите существующий период и все его дочерние периоды, затем перейдите к следующему существующему периоду
- если они перекрываются, отрегулируйте текущий существующий период так, чтобы он был равен новому периоду, следующим образом, затем переходите к следующему новому и существующему периоду
- если новый период начинается раньше существующего периода, просто переместите начало
- если новый период начинается после существующего периода, проверьте, есть ли какие-либо дочерние периоды в периоде разницы, и запомните их, затем переместите начало
- проделайте то же самое с другим концом
- с любыми периодами, которые вы "запомнили", посмотрите, нужно ли их повторно связать или удалить
Вам следует создать огромный набор модульных тестов и убедиться, что вы охватываете все комбинации модификаций.
Другие советы
Я предлагаю вам разделить ваши вопросы на два отдельных:Первый должен быть чем-то вроде:"Как мне рассуждать о планировании ресурсов, представляя атом расписания как ресурс со временем начала и окончания?" Здесь предложение ADept использовать интервальную алгебру кажется подходящим.Пожалуйста, посмотрите Статья в Википедии "Интервальный график" и Запись в репозитории алгоритма SUNY о планировании.Второй вопрос - это вопрос о базе данных:"Учитывая алгоритм, который планирует интервалы и указывает, перекрываются ли два интервала или один содержится в другом, как мне использовать эту информацию для управления базой данных в данной схеме?" Я считаю, что как только алгоритм планирования будет внедрен, решить проблему с базой данных будет намного легче.HTH, Юваль
Ваш пост находится почти в разделе "слишком длинный;не читал " категория - сокращение, вероятно, даст вам больше отзывов.
Во всяком случае, по теме:вы можете попробовать заглянуть в вещь, называемую "Интервальная алгебра"
Как я вас понимаю, ваши пользователи могут напрямую влиять только на таблицу A.Предполагая, что вы программируете на C #, вы могли бы использовать простой ADO.Net DataSet для управления изменениями в таблице A.TableAdapter знает, что нужно оставлять нетронутые строки в покое и соответствующим образом обрабатывать новые, измененные и удаленные строки.
Кроме того, вы должны определить каскадное удаление, чтобы автоматически удалять соответствующие объекты в таблице B.
Единственный случай, который не обрабатывается таким образом, - это сокращение временного интервала в таблице A и т.д.он больше не включает соответствующую запись в таблицу B.Вы могли бы просто проверить этот случай в хранимой процедуре обновления или, альтернативно, определить триггер обновления в таблице A.
Мне кажется, что любой алгоритм для этого будет включать прохождение через NewA, сопоставление resourceId, startTime и EndTime и отслеживание того, какие элементы из OldA попадают под удар.Тогда у вас есть два набора несовпадающих данных, UnmatchedNewA и UnmatchedOldA.
Самый простой способ, который я могу придумать, - это, по сути, начать все сначала с этих:Запишите все UnmatchedNewA в базу данных, перенесите элементы B из UnmatchedOldA в Новые ключи A (только что сгенерированные), где это возможно, удалив, когда нет.Затем уничтожьте всю несравненную Ольду.
Если изменений много, это, безусловно, неэффективный способ продолжения работы.Однако в тех случаях, когда размер данных не является чрезмерным, я предпочитаю простоту продуманной оптимизации.
Невозможно узнать, имеет ли это последнее предложение какой-либо смысл без дополнительной подготовки, но на тот случай, если вы не подумали об этом таким образом:
Вместо того чтобы передавать всю коллекцию A туда и обратно, не могли бы вы использовать прослушиватели событий или что-то подобное для обновления модели данных только там, где необходимы изменения?Таким образом, изменяемые объекты смогут определять, какие операции с базой данных требуются "на лету".
