Анализ различных сетов и оптимизации. Лучший подход?

В течение последних нескольких дней я пытался выполнить следующую задачу, касающуюся анализа набора объектов, и решения, которые я придумал, в значительной степени зависят от памяти (в некоторых случаях получая исключения OutOfMemory) или занимают невероятно много времени. время на обработку. Теперь я думаю, что это хорошая идея опубликовать это здесь, так как у меня нет идей. Я подробно объясню проблему и предоставлю логику, которой я следовал до сих пор.

Сценарий:

Во-первых, у нас есть объект, который мы назовем Individual и который содержит следующие свойства:

1. Свидание
2. Пара долгота-широта

Во-вторых, у нас есть еще один объект, который мы назовем Группа. Его определение таково: набор лиц, которые вместе соответствуют следующим условиям:

• Все особи в наборе имеют даты, которые друг в друге не превосходят 10 дней. Это означает, что все Индивидуумы, если их сравнивать друг с другом, не отличаются друг от друга на 10 дней.

• Расстояние между каждым объектом меньше Y метров.

Группа может состоять из N>1 индивидуумов, если каждый из индивидуумов соответствует условиям друг друга. Все лица хранятся в базе данных. Все группы также будут храниться в базе данных.

Задача:

Теперь рассмотрим нового человека. Система должна проверить, если новый человек:

1. Принадлежит к существующей группе или группам

2. Индивидуум теперь формирует одну или несколько новых групп с другими индивидуумами.

Примечания:

• Новый человек может состоять в нескольких существующих группах или может создать несколько новых групп.

• Подгруппы отдельных лиц не допускаются, например, если у нас есть группа, содержащая отдельных лиц {A,B,C}, не может существовать группа, содержащая {A,B}, {A,C} или {B,C}.

Решение (ограничено по времени обработки и памяти)

Во-первых, мы фильтруем базу данных со всеми лицами, которые соответствуют начальным условиям. Это выведет перечисляемое FilteredIndividuals, содержащее всех людей, которые, как мы знаем, образуют группу (из 2) с новым.

Вкратце, Powerset — это набор, содержащий все возможные подмножества определенного набора. Например, набор мощности {A,B,C} будет следующим: {[пусто], A, B, C, AB, AC, BC, ABC}

Примечание. Powerset выведет новый набор из 2^N комбинаций, где N — длина исходного набора.

Идея использования powersets заключается в следующем:

• Во-первых, мы создаем powerset списка FilteredIndividuals. Это даст все возможные комбинации групп в списке FilteredIndividuals. Для целей анализа и по определению мы можем опустить все комбинации, в которых содержится менее 2 индивидуумов.

• Мы проверяем, соответствует ли каждое из Индивидуумов в комбинации набора мощности условиям друг друга. Если они совпадают, это означает, что все Индивидуумы в этой комбинации образуют Группу с новым Индивидуумом. Затем, чтобы избежать подгрупп, мы можем исключить все подмножества, содержащие комбинации отмеченной комбинации. Я делаю это, создавая набор мощности из проверенной комбинации, а затем удаляя новый набор мощности из исходного.

• На данный момент у нас есть список наборов, соответствующих условиям для формирования группы.

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

Это решение хорошо работает, когда перечисляемый объект FilteredIndividuals содержит менее 52 отдельных лиц. После этого выбрасываются исключения памяти (я знаю, что это из-за максимального размера, разрешенного для типов данных, но увеличение такого размера не помогает с очень большими наборами. На ваше усмотрение, максимальное количество индивидуумов, соответствующих условиям, я' найдено 345).

Примечание. У меня есть доступ к определению обеих сущностей. Если есть новое свойство, которое сократит время обработки, мы можем его добавить.

Я использую .NET framework с C#, но если язык требует изменения, мы можем согласиться с этим, если позже сможем преобразовать результаты в объекты, понятные нашей основной системе.