В базе PostgreSQL лежат 3 таблицы: objects, relations, components.
Таблица objects:
Название поля | Тип данных | Описание |
---|---|---|
id | integer | Первичный ключ, идентификатор объекта |
Таблица relations:
Название поля | Тип данных | Описание |
---|---|---|
id | integer | Первичный ключ |
object_id | integer | Внешний ключ к таблице objects |
relative_ids | integer[] | Массив идентификаторов связанных объектов из таблицы objects |
Таблица components:
Название поля | Тип данных | Описание |
---|---|---|
id | integer | Первичный ключ, идентификатор компонента |
object_ids | integer[] | Внешний ключ к таблице objects |
Таблица objects содержит идентификаторы объектов, а таблица relations для каких-то объектов содержит массив связанных объектов с данным. Таблица components пустая.
Назовем компонентой такой набор идентификаторов объектов, что для любых двух идентификаторов из данного набора найдется цепочка связанных объектов (два объекта связаны, если в таблице relations есть строка c object_id=id1 и relation_ids содержит id2, или наоборот).
Необходимо написать программу на языке Python, которая на основе данных из таблиц objects и relations формирует компоненты связанных объектов наиболее быстрым способом, используя структуру disjoint-set. Сформированные компоненты должны быть загружены в таблицу components.
При наличии 16Гб оперативной памяти программа должна обрабатывать таблицу objects с количеством строк 20'000'000 строк и таблицу relations с 200'000'000 строк.
Для таблиц objects:
id |
---|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
и relations:
id | object_id | relative_ids |
---|---|---|
1 | 3 | {4,7,1} |
2 | 4 | {9} |
3 | 3 | {2,1} |
4 | 6 | {8} |
должна быть сформирована таблица components:
id | object_ids |
---|---|
1 | {1,2,3,4,7,9} |
2 | {5} |
3 | {6,8} |
Результат необходимо предоставить в виде дампа тестовой базы (размер не более 1MB) и исходного кода.