У меня есть люди и помещает данные как:
-
Personобъект имеет-
IList<DateRangePlaces>, каждый из которых имеет-
IList<Place>возможных мест
-
-
Schedule. 10 дней доступно 4 недоступно
-
В течение определенного диапазона дат DateRangePlaces нужно подчиняться шаблону Schedule, может ли человек перейти в конкретное место или нет.
-
Placeобъект имеет-
IList<DateRangeTiming>каждое определение времени открытия/закрытия в пределах каждого диапазона дат
-
Диапазоны дат перекрытия работают как LIFO. Поэтому для каждого дня, который уже был определен ранее, предпочтение отдается новому определению времени.
Проблема
Теперь мне нужно сделать что-то вроде этого (в псевдокоде):
for each Place
{
for each Day between minimum and maximum date in IList<DateRangeTiming>
{
get a set of People applicable for Place and on Day
}
}
Это означает, что количество шагов для выполнения моей задачи примерно:
" → " →
Это, по моему мнению,
O (x × y x × z)
и, вероятно, приближается к сложности этого алгоритма:
О (п 3)Забастовкa >
Я не эксперт в теории, поэтому вы можете свободно корректировать мои предположения. Верно то, что такая сложность определенно неприемлема, особенно учитывая тот факт, что я буду работать на длинных диапазонах дат со многими местами и людьми.
Из аппроксимации формулы видно, что набор людей будет повторяться много раз. Поэтому я хотел бы оптимизировать, по крайней мере, эту часть. Чтобы немного изменить некоторые вещи, я изменил
Person.IList<DateRangePlaces>.IList<Place>
к
Person.IList<DateRangePlaces>.IDictionary<int, Place>
что даст мне более быстрый результат: может ли человек перейти в какое-либо место в определенную дату, потому что я бы только проверил, присутствует ли Place.Id в словаре в соответствии с предложением IList.Where() LINQ, которое должно было бы сканировать весь список каждый раз.
Вопрос
-
Можете ли вы предложить любые дополнительные оптимизации, которые я мог бы реализовать в своем алгоритме, чтобы сделать его быстрее или даже сделать его менее сложным с точки зрения большой записи O?
-
Какие типы структур памяти вы бы использовали где и почему (списки, словари, стеки, очереди...) для повышения производительности?
Добавление: вся проблема еще сложнее
Есть также дополнительные сложности, о которых я не упоминал, поскольку я хотел упростить свой вопрос, чтобы сделать его более понятным. Так. Там также:
Place.IList<Permission>
Person.IList<DateRangePermission>
Поэтому местам требуются особые разрешения, и у людей есть ограниченные разрешения времени, срок действия которых истекает.
Кроме того, там также
Person.IList<DateRangeTimingRestriction>
который говорит только о конкретных случаях, когда человек может пойти куда-то в течение определенного диапазона дат. И
Person.IList<DateRangePlacePriorities>
Определяет приоритет места для определенного диапазона дат.
И во время этого процесса получения применимых людей мне также приходится вычислять определенный коэффициент на каждого человека за каждое место, которое связано с:
- количество мест, которые человек может посетить в определенный день.
- персональный фактор приоритета в этот конкретный день.
Все эти причины я решил скорее манипулировать этими данными в памяти, чем использовать очень сложную хранимую процедуру, которая также будет выполнять несколько сканирований таблиц, чтобы получить факторы на человека, место и день.
Я думаю, что такая хранимая процедура будет сложной для обработки и поддержки. Поэтому я предпочел сначала получить все данные (поместив соответствующие структуры памяти для повышения производительности), а затем запустил их в памяти.
