Bin packing problem (0)
Терпел я, терпел, но похоже эта штуковина переросла тему одного поста. Итак, встречайте:
Bin packing problem - Intro
Понадобилось мне забэкапить на DVD-болванки залежи фото, музыки, фильмов и прочей фигни на своем файл-сервере. Больше шести сотен гигабайт, между прочим. Место занимает, а стереть жалко. Но хотя бы с RAID5 на незарезервированные (JBOD) разделы перенести можно будет при наличии бэкапов, а часть и поудалять насовсем. Болванок накупил, благо что те по 15 рублей стали.
А тут трабл - как бэкапить? Выделять файлы/каталоги кучками, приблизительно влазящими на болванки, мне решительно не хотелось. Не то чтобы я пожалел немножечко денюжков™ на лишние DVD-R, просто делать это руками 670/4.7 = 143 раза посчитал неразумным и недостойным программиста занятием.
Админ бы нашел готовую программу для бэкапов, а программист написал бы свою. Ура, я программист! Ведь я могу написать python-скрипт для автоматической выборки групп файлов и генерации ISO-образов, чтобы потом только болванки в резак толкать...
Сказано - сделано. В процессе написания программы возник вопрос: а по какому, собственно, алгоритму надо выбирать файлы, чтобы они плотно улеглись в болванки, дабы не пропадало зря свободное место?.. Ну, думаю, можно наверное просто решить проблему "в лоб" - тупо попробовать все возможные перестановки файлов и выбрать те, где "хвосты" меньше. Фиг-то там: число возможных перестановок оказалось числом Стирлинга второго рода, полный перебор оказался неподъемной задачей даже для небольшого числа файлов/каталогов.
Ладно, думаю. Полез глубже - а проблема-то давно сформулирована. Встречайте: Bin packing problem (по-русски Задача об упаковке в контейнеры). NP-hard, между прочим. Однако придуманы неплохие эвристические алгоритмы...
Продолжение следует (про чтение научных трудов, про FirstFit и BestFit, про генетические алгоритмы и прочую лабуду)
Bin packing problem - Intro
Понадобилось мне забэкапить на DVD-болванки залежи фото, музыки, фильмов и прочей фигни на своем файл-сервере. Больше шести сотен гигабайт, между прочим. Место занимает, а стереть жалко. Но хотя бы с RAID5 на незарезервированные (JBOD) разделы перенести можно будет при наличии бэкапов, а часть и поудалять насовсем. Болванок накупил, благо что те по 15 рублей стали.
А тут трабл - как бэкапить? Выделять файлы/каталоги кучками, приблизительно влазящими на болванки, мне решительно не хотелось. Не то чтобы я пожалел немножечко денюжков™ на лишние DVD-R, просто делать это руками 670/4.7 = 143 раза посчитал неразумным и недостойным программиста занятием.
Админ бы нашел готовую программу для бэкапов, а программист написал бы свою. Ура, я программист! Ведь я могу написать python-скрипт для автоматической выборки групп файлов и генерации ISO-образов, чтобы потом только болванки в резак толкать...
Сказано - сделано. В процессе написания программы возник вопрос: а по какому, собственно, алгоритму надо выбирать файлы, чтобы они плотно улеглись в болванки, дабы не пропадало зря свободное место?.. Ну, думаю, можно наверное просто решить проблему "в лоб" - тупо попробовать все возможные перестановки файлов и выбрать те, где "хвосты" меньше. Фиг-то там: число возможных перестановок оказалось числом Стирлинга второго рода, полный перебор оказался неподъемной задачей даже для небольшого числа файлов/каталогов.
Ладно, думаю. Полез глубже - а проблема-то давно сформулирована. Встречайте: Bin packing problem (по-русски Задача об упаковке в контейнеры). NP-hard, между прочим. Однако придуманы неплохие эвристические алгоритмы...
Продолжение следует (про чтение научных трудов, про FirstFit и BestFit, про генетические алгоритмы и прочую лабуду)