Для любой системы пакетов Linux Distro найдите максимальное количество одновременно устанавливаемых пакетов

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

  1. составить список всевозможных имен пакетов, т.е. dglob -a > list
  2. из этого сделать списки slist1 slist2 slist3 ... каждой возможной комбинации пакетов. В моей системе dglob -a | wc -l возвращает 91327, что потребует неоправданно большого количества (1,467 × 10 ^ 27492) файлов.
  3. бежать apt-get install в каждом списке, и rm те, которые вызывают конфликты.
  4. Сортируйте оставшиеся списки по количеству строк и покажите самый длинный.wc -l slist* | head -n -1 | sort -g | tail -1,

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

Из этого вытекают различные связанные вопросы, такие как:

  • с учетом пакета 'foo' как найти максимальное количество устанавливаемых пакетов, которые не конфликтуют с 'foo'?

  • Для всех возможных пакетов, у которых наименьший такой максимум (что делает его наиболее "ссорящимся" пакетом)?

(Примечание. Этот вопрос относится к Debian, Red Hat и любому дистрибутиву или ОС с системой упаковки, которая отображает конфликты пакетов. Ответы для любой применимой платформы будут действительными.)

Фон:

Debian имеет десятки тысяч пакетов. dglob (из пакета debian-goodies) удобен для быстрого подсчета:

# show how many packages installed and available on the current system
echo $(dglob    | wc -l) packages installed of \
     $(dglob -a | wc -l) packages.

Пример вывода (оба числа могут периодически колебаться после обновлений и обновлений и будут различаться в зависимости от системы):

5107 packages installed of 91327 packages.

Число 5107, конечно, не максимум, но максимум должен быть.

Источник

2 ответа

Вариант грубой силы - единственный вариант в этом случае. Вот статья , в которой подробно описывается, почему, но проблема в том, что установка пакета и разрешение зависимости / конфликтов - это проблема NP-Complete.

Проблема в NP, если каждые TRUEответ имеет легко проверяемое объяснение размера полинома. В этом случае это можно сделать, перечислив установленные пакеты и доступные пакеты.

Установка пакета Debian является NP-сложной, если эффективное решение проблемы может быть адаптировано к эффективным решениям любой другой проблемы в NP. Я обращусь к упомянутой выше статье, поскольку здесь немного сложно доказать, но ее можно закодировать как 3-SAT.

Поскольку установка пакета Debian выполняется в NP и NP-hard, то есть NP-полная.

Вот несколько способов default решатель в APT пытается избежать NP-полноты:

  • Использование эвристики
  • Предпочтение первому элементу в или-группе
  • Строгое соглашение о версии пакета
  • Сдается, когда сталкивается с серьезным конфликтом.

По сути, ограничения должны быть специально разработаны, чтобы проблема попала в известные поддающиеся обработке классы для задачи NP-Complete, такой как HORN-SAT.

к несчастью find the maximum possible number of installable packages for a given system в значительной степени исключает все известные поддающиеся обработке классы, о которых я знаю.

Таким образом, грубая сила - единственный и дорогостоящий вариант, пока не будет обнаружен подходящий управляемый класс или пока кто-то не докажет, что P=NP.

Источник

apt list > tmp.filevi tmp.fileЗатем нажмите G в vi. Это даст вам количество доступных пакетов, но, к сожалению, не учитывает конфликты.

Источник
Другие вопросы по тегам