Блог

У меня есть двоичный файл, который можно рассматривать как объединение разных вложенных файлов:

ВХОДНОЙ ФАЙЛ:

 Hex Offset     ID           SortIndex
0000000        SubFile#1    3
0000AAA        SubFile#2    1
0000BBB        SubFile#3    2
...
FFFFFFF        SubFile#N    N
 

Это информация, которая у меня есть о каждом вложенном файле:

• Начальное смещение
• Длина в байтах
• Окончательный порядок последовательности

Каков, по вашему мнению, самый быстрый способ создания отсортированного выходного файла?

Например, ВЫХОДНОЙ ФАЙЛ будет содержать вложенный файл в следующем порядке:

 SubFile#2    
SubFile#3    
SubFile#1    
...
 

Я подумал о:

• Разделите входной файл, извлекая каждый вложенный файл на диск, затем объедините их в правильном порядке
• Использование FileSeek для перемещения по файлу и добавления каждого вложенного файла в поток BinaryWriter.

Рассмотрите также следующую информацию:

• Входной файл может быть действительно огромным (200 МБ ~ 1 ГБ)
• Для тех, кто знает, я говорю о файлах IBM AFP.

Оба моих решения просты в реализации, но, на мой взгляд, выглядят действительно неэффективно.

Заранее спасибо

Кроме того, если файл большой, то количество идентификаторов не так уж велико.

Вы можете просто получить все свои идентификаторы, sortindex, offset, length в ОЗУ, затем отсортировать в ОЗУ с помощью простой быстрой сортировки, когда вы закончите, вы перепишете весь файл в том порядке, который у вас есть в отсортированном массиве. Я ожидаю, что это будет быстрее, чем другие методы. Итак … давайте создадим некоторый псевдокод.

 public struct FileItem : IComparable<FileItem>
{
    public String Id;
    public int SortIndex;
    public uint Offset;
    public uint Length;

    public int CompareTo(FileItem other) { return this.SortIndex.CompareTo(other.SortIndex); }
}

public static FileItem[] LoadAndSortFileItems(FILE inputFile)
{
    FileItem[] result = // fill the array

    Array.Sort(result);
}

public static void WriteFileItems(FileItem[] items, FILE inputfile, FILE outputFile)
{
    foreach (FileItem item in items)
    {
        Copy from inputFile[item.Offset .. item.Length] to outputFile.
    }
}
 

Количество операций чтения линейно, O (n), но поиск требуется.
Единственная проблема с производительностью при поиске — это отсутствие кэша в кэше жесткого диска.
Современный жесткий диск имеет большой кеш от 8 до 32 мегабайт, поиск большого файла в случайном порядке означает промах кэша, но я бы не стал слишком беспокоиться, потому что, я полагаю, время, затрачиваемое на копирование файлов, превышает время, необходимое для поиска.

Если вместо этого вы используете твердотельный диск, время поиска равно 0

Однако запись выходного файла выполняется O (n) и последовательно, и это очень хорошо, поскольку вы будете полностью использовать кэш. Вы можете обеспечить лучшее время, если предварительно распределите размер файла перед началом его записи.

  FileStream myFileStream = ...
 myFileStream.SetLength(predictedTotalSizeOfFile);
 

Сортировка структур FileItem в ОЗУ — это O (n log n), но и с элементами 100000 это будет быстро и будет использовать небольшой объем памяти.

Копирование — самая медленная часть, используйте 256 килобайт .. 2 мегабайта для блочного копирования, чтобы гарантировать, что копирование больших фрагментов файла A в файл B будет быстрым, однако вы можете настроить объем памяти блочного копирования, выполнив некоторые тесты, всегда помня, что каждая машина отличается.

Бесполезно пробовать многопоточный подход, это просто замедлит копирование.

Это очевидно, но, например, если вы скопируете с диска C: на диск D:, это будет быстрее (конечно, не разделы, а два разных диска serial ata).

Учтите также, что вам нужно искать, или при чтении, или при записи, в какой-то момент вам нужно будет искать. Кроме того, если вы разделите исходный файл на несколько файлов меньшего размера, вы заставите ОС искать файлы меньшего размера, а это не имеет смысла, это будет грязно и медленнее, и, вероятно, также сложнее кодировать. Учтите также, что если файлы фрагментированы, ОС будет искать сама, и это вне вашего контроля.

Первое решение, о котором я подумал, состояло в том, чтобы последовательно читать входной файл и создавать объект Subfile для каждого вложенного файла. Эти объекты будут помещены в дерево b , как только они будут созданы. Дерево упорядочит вложенные файлы по их SortIndex. Хорошая реализация b-дерева будет иметь связанные дочерние узлы, что позволит вам перебирать вложенные файлы в правильном порядке и записывать их в выходной файл

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