Вопросы Теги

Дополнительно: Как оптимизировать мой сложный алгоритм O (n²)

У меня есть люди, и я размещаю данные как:

  • Человек объект имеет
    • IList , каждый из которых имеет
      • IList возможных мест
    • Расписание дневной образец как т.е. 10 дней доступно 4 недоступно

В пределах определенного диапазона дат DateRangePlaces необходимо подчиняться шаблону Расписание , независимо от того, может ли человек пойти в определенное место или нет.

  • Объект места имеет
    • IList , каждый из которых определяет время открытия / закрытия в каждом диапазоне дат

Перекрывающиеся диапазоны дат работают как 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 )

и, вероятно, приблизительно соответствует сложности этого алгоритма:

O (n 3 )

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

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

Person.IList<DateRangePlaces>.IList<Place>

на 

Person.IList<DateRangePlaces>.IDictionary<int, Place>

, что дало бы мне более быстрый результат, сможет ли человек пойти в какое-то место в определенный день, потому что я бы только проверял, присутствует ли Place.Id в словаре по сравнению с предложением IList.Where () LINQ, которое каждый раз будет сканировать весь список.

Вопрос

  1. Не могли бы вы предложить какие-либо дополнительные оптимизации, которые я мог бы внедрить в свой алгоритм, чтобы сделать его быстрее или даже сделать его менее сложным с точки зрения большой нотации O?

  2. Какие типы структур памяти вы бы использовали, где и почему (списки, словари, стеки, очереди ...) для повышения производительности?

Приложение: Вся проблема еще сложнее

Есть также дополнительные сложности, о которых я не упомянул, так как хотел упростить свой вопрос чтобы было понятнее. Так. Также есть: 

Place.IList<Permission>
Person.IList<DateRangePermission>

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

В дополнение к этому, есть также 

Person.IList<DateRangeTimingRestriction>

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

Person.IList<DateRangePlacePriorities>

, который определяет приоритизацию мест для определенного диапазона дат.

И во время этого процесса поиска подходящих людей я также должен рассчитать определенный коэффициент на каждого человека для каждого места, который связан с:

  • количеством мест, которые человек может посетить в определенный день
  • фактор приоритета места человека в тот конкретный день

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

Я думаю, что такую ​​хранимую процедуру будет сложно обрабатывать и поддерживать. Поэтому я предпочитаю сначала получить все данные (поместить их в соответствующие структуры памяти для повышения производительности), а затем обработать их в памяти.

10
задан Robert Koritnik 20 September 2011 в 16:50
поделиться