История изменений

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

Окей.

Ты делаешь какое-то действие с пакетами.

У тебя есть очень сложный граф (зависимости всех ебилдов * их юз-флаги), в котором некоторые пакеты изменились (поставлены на обновление или новые).

Тебе нужно починить и «распутать» этот граф:

1) Определить конфликты (циклы, отсутствующие связиюз-флаги), мешающие распутыванию

2) Понять, какие пакеты необходимо компилять и в каком порядке. Причем, этот порядок тоже будет графом, т.к. компилять можно несколько пакетов одновременно.

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

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

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

Окей.

Ты обновляешь систему.

У тебя есть очень сложный граф (зависимости всех ебилдов * их юз-флаги), в котором некоторые пакеты изменились (поставлены на обновление или новые)

Тебе нужно «распутать» этот граф:

1) Определить конфликты (циклы, отсутствующие связиюз-флаги), мешающие распутыванию

2) Понять, какие пакеты необходимо компилять и в каком порядке. Причем, этот порядок тоже будет графом, т.к. компилять можно несколько пакетов одновременно.

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

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