У меня есть данные о людях и местах:
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
}
}
Это означает, что количество шагов для выполнения моей задачи составляет приблизительно:
.
& sum; (мест) (& sum; (дней) × & sum; (чел.) )
Это, насколько я понимаю,
O (x × y x × z)
и, вероятно, приближается к этому алгоритму сложности:
* 1 065 ** * тысячу шестьдесят-шесть О (п 3 )
Я не специалист в теории, поэтому вы можете свободно корректировать мои предположения. Что правда, так это то, что подобная сложность определенно неприемлема, особенно учитывая тот факт, что я буду работать на больших диапазонах дат со многими местами и людьми.
Из аппроксимации формулы мы видим, что набор людей будет повторяться много раз. Поэтому я хотел бы оптимизировать хотя бы эту часть. Чтобы немного облегчить ситуацию, я изменился
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>
Определяет приоритеты мест для определенного диапазона дат.
И в процессе поиска подходящих людей мне также приходится рассчитывать определенный коэффициент на каждого человека в каждом месте, связанном с:
- количество мест, которые человек может посетить в определенный день
- фактор приоритета человека в этот день
Все это - причины, по которым я решил скорее манипулировать этими данными в памяти, чем использовать очень сложную хранимую процедуру, которая также выполняла бы многократное сканирование таблицы, чтобы получить факторы на человека, место и день.
Я думаю, что такая хранимая процедура была бы слишком сложной для обработки и обслуживания. Поэтому я предпочитаю сначала получить все данные (указать соответствующие структуры памяти, чтобы повысить производительность), а затем манипулировать ими в памяти.