Как я могу предсказать размер файловой системы ISO 9660?

Question

Я архивирую данные на DVD и хочу полностью упаковать DVD. Я знаю имена и размеры всех файлов, которые мне нужны на DVD, но я не знаю, сколько места занимают метаданные. Я хочу разместить как можно больше файлов на каждом DVD, поэтому я использую эвристику Bubblesearch с жадной упаковкой в ​​мусорное ведро. Я пробую 10000 альтернатив и получаю лучший. В настоящее время я знаю размеры всех файлов и, поскольку я не знаю, как файлы хранятся в файловой системе ISO 9660, я добавляю много отстойных метаданных. Я хотел бы сократить помои.

Я мог бы использовать genisoimage -print-size, за исключением того, что он слишком медленный - учитывая, что 40 000 файлов занимают 500 МБ, это занимает около 3 секунд. Взятие 8 часов на DVD не в карточках. Я уже модифицировал исходный код genisoimage и на самом деле не хочу пытаться выжать алгоритм из исходного кода; Я надеюсь, что кто-то знает лучший способ получить оценку или может указать мне полезную спецификацию.

---

Разъяснение проблемы и вопроса:

• Мне нужно записать архивы, которые разбиты на несколько DVD, обычно около пяти одновременно. Проблема, которую я пытаюсь решить, состоит в том, чтобы решить, какие файлы поместить на каждый DVD, чтобы каждый DVD (кроме последнего) был максимально полным. Эта проблема NP-сложная.

• Я использую стандартный жадный алгоритм упаковки, в котором вы сначала размещаете самый большой файл и помещаете его в первый DVD, на котором достаточно места. Итак, j_random_hacker, я определенно не , начиная со случайного. Я начинаю с сортировки и использую Bubblesearch, чтобы изменить порядок, в котором файлы упакованы. Эта процедура улучшает мою упаковку с примерно 80% от расчетной емкости до более чем 99,5% от расчетной емкости. Этот вопрос о делает лучшую работу по оценке мощности ; в настоящее время моя расчетная мощность ниже реальной.

• Я написал программу, которая пробует 10 000 возмущений, каждое из которых включает в себя два шага:

  1. Выберите набор файлов
  2. Оцените, сколько места будут занимать эти файлы на DVD

  Шаг 2 - это шаг, который я пытаюсь улучшить. В настоящее время я «ошибаюсь на стороне осторожности», как предполагает Тайлер Д. Но я хотел бы сделать лучше. Я не могу позволить себе использовать genisomage -print-size, потому что это слишком медленно. Точно так же я не могу заархивировать файлы на диск, потому что только он слишком медленный, но размер файла tar отличается от размера ISO 9660. Это размер ISO 9660 изображения, который мне нужно предсказать. В принципе это можно сделать с полной точностью, но я не знаю, как это сделать. Вот в чем вопрос.

---

Примечание. Эти файлы находятся на компьютере с 3 ТБ дискового пространства. Во всех случаях средний размер файлов составляет не менее 10 МБ; иногда это значительно больше. Таким образом, возможно, что genisomage будет достаточно быстрым в конце концов, но я сомневаюсь в этом - похоже, он работает, записывая образ ISO в / dev / null, и я не могу себе представить, что это будет достаточно быстро, когда размер изображения приближается к 4.7GB. У меня нет доступа к этой машине сейчас, или когда я отправил оригинальный вопрос. Когда у меня будет доступ к вечеру, я постараюсь получить лучшие номера по этому вопросу. Но я не думаю, что genisomage будет хорошим решением - хотя это может быть хорошим способом изучения модели файловой системы. это говорит мне, как это работает. Знать, что размер блока составляет 2 КБ, уже полезно.

Также может быть полезно знать, что файлы в одном и том же каталоге записываются на саме DVD, что упрощает поиск. Я хочу получить доступ к файлам напрямую, что исключает tar перед записью. (Большинство файлов являются аудио или видео, что означает, что нет смысла пытаться поразить их gzip.)

Answer 1

Я не совсем уверен, как вы в настоящее время делаете это - согласно моему поиску в Google, «Bubblesearch» относится к способу выбора порядка элементов, который в некотором смысле около жадный , но в вашем случае порядок добавления файлов на DVD-диск не меняет требований к пространству, поэтому такой подход тратит время с учетом нескольких разных порядков, которые равны набору файлов.

Другими словами, если вы делаете что-то вроде следующего для генерации списка файлов кандидатов:

1. Случайно перемешать список файлов.
2. Начиная с верхней части списка, жадно выбирайте все файлы, которые, по вашим оценкам, будут помещаться на DVD, пока не перестанут.

Тогда вы неэффективно ищете пространство решения - для любого окончательного набора кандидатов из n файлов вы потенциально рассматриваете все n ! способы производства этого набора. Мое предложение:

1. Сортировка всех файлов в порядке убывания размера файла.
2. Пометьте верхний (самый большой) файл как «включенный» и удалите его из списка. (Он должен быть включен в некоторые DVD, поэтому мы могли бы также включить его сейчас.)
3. Можно ли включить в список самый верхний файл в списке без превышения (предполагаемого) размера файловой системы ISO объема DVD? Если так:
   • С вероятностью p (например, p = 0,5) пометьте файл как «включенный».
4. Удалить самый верхний файл из списка.
5. Если список теперь пуст, у вас есть список кандидатов файлов. В противном случае перейдите к 3.

Повторите это много раз и выберите лучший список файлов.

Предложение Tyler D также хорошо: если у вас ~ 40000 файлов общим объемом ~ 500 МБ, это означает, что средний размер файла составляет 12,5 КБ. ISO 9660 использует размер блока 2 КБ, что означает, что эти файлы занимают в среднем 1 КБ дискового пространства, или около 8% их размера. Таким образом, упаковка их вместе со смолой сначала сэкономит около 8% пространства.

Answer 2

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

Что касается вопроса: " Точно Сколько накладных расходов включает файловая система ISO 9660 для n файлов общим объемом b байт?" есть только 2 возможных ответа:

1. Кто-то уже написал эффективный инструмент для измерения именно этого. Быстрый поиск в Google ничего не дал, но это обескураживает. Возможно, кто-то в SO ответит ссылкой на свой домашний инструмент, но если вы не получите больше ответов в течение нескольких дней, то, вероятно, это тоже не так.
2. Вам необходимо прочитать легкодоступные спецификации ISO 9660 и создать такой инструмент самостоятельно.

На самом деле, есть третий ответ:

(3) Вам не нужно использовать каждый последний байт на каждом DVD. В этом случае возьмите небольшую репрезентативную горстку файлов разных размеров (скажем, 5), дополняйте их, пока они не будут кратны 2048 байтам, и введите все 2 ^ 5 возможных подмножеств через genisoimage -print-size. Затем поместите уравнение nx + y = iso_size - total_input_size в этот набор данных, где n = количество файлов в данном прогоне, чтобы найти x , что количество байтов служебной информации на файл и y , что является постоянной величиной служебной информации (размер файловой системы ISO 9660, не содержащей файлов). Округлите x и y и используйте эту формулу для оценки размеров файловой системы ISO для заданного набора файлов. В целях безопасности убедитесь, что вы используете самые длинные имена файлов, которые появляются в любом месте вашей коллекции, для тестовых имен файлов и помещаете каждое из них в отдельную иерархию каталогов, которая настолько же глубока, как самая глубокая иерархия в вашей коллекции.

Answer 3

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

Предположения:

• все файлы содержат ровно 8,3 символа.
• все файлы находятся в корневом каталоге.
• без расширений, таких как Joliet.

Формула:

174 + floor(count / 42) + sum( ceil(file_size / 2048) )

• количество файлов
• file_size - размер каждого файла в байтах
• результат в 2048 байтных блоках.

Пример сценария:

#!/usr/bin/perl -w
use strict;
use POSIX;

sub sum {
    my $out = 0;
    for(@_) {
        $out += $_;
    }
    return $out;
}

my @sizes = ( 2048 ) x 1000;
my $file_count = @sizes;

my $data_size = sum(map { ceil($_ / 2048) } @sizes);
my $dir_size = floor( $file_count / 42 ) + 1;
my $overhead = 173;

my $size = $overhead + $dir_size + $data_size;

$\ = "\n";
print $size;

Я проверил это на дисках с размером файла до 150 КБ, размером от 200 байт до 1 МБ.

Answer 4

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

Может быть, поэкспериментируйте и допустите ошибку - если свободное место на диске не помешает.

Каким-то образом я представляю, что вы уже рассмотрели это, или что в моем ответе отсутствует смысл.

Answer 5

Хорошее мышление, Дж. Рэндом. Конечно, мне не нужен каждый последний байт, это в основном для развлечения (и хвастовство правами на обед). Я хочу, чтобы можно было набрать du на компакт-диске, чтобы оно было очень близко к 4700000000.

Я посмотрел на спецификацию ECMA, но, как и большинство спецификаций, она очень болезненная, и я не уверен в своей способности сделать это правильно. Также кажется, что он не обсуждает расширения Rock Ridge, или, если это так, я пропустил это.

Мне нравится ваша идея №3, и я думаю, что я продолжу ее немного дальше: я постараюсь построить довольно богатую модель того, что происходит, а затем использую genisoimage -print-size на ряде наборов файлов для оценки параметров модель. Тогда я могу использовать модель, чтобы сделать мою оценку. Это хобби-проект, поэтому он займет некоторое время, но в конце концов я обойду его. Я опубликую ответ здесь, чтобы сказать, сколько потерь устранено!