基于二进制文件索引排序

本文关键字：排序 索引 二进制文件 | 更新日期: 2023-09-27 18:12:49

我有一个二进制文件，可以看作是不同子文件的连接:

输入文件:

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

这些是我对每个子文件的信息:

  • 字节长度
  • 最终序列命令

在你看来，什么是最快的方式来产生一个排序输出文件?

例如，OUTPUT FILE将按以下顺序包含子文件:

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

我想过:

    分割输入文件提取每个子文件到磁盘，然后按正确的顺序将它们连接起来
  • 使用FileSeek来移动文件并将每个子文件添加到BinaryWriter流。

还要考虑以下信息:

  • 输入文件可能非常大(200MB~1GB)
  • 对于那些知道的人，我说的是IBM AFP文件。

我的两个解决方案都很容易实现，但在我看来，看起来真的不执行。

Thanks in advance

基于二进制文件索引排序

如果文件很大，id的数量也不会那么大。

你可以在RAM中获取所有id,sortindex，偏移量，长度，然后在RAM中使用简单的快速排序进行排序，当你完成后，你可以按照排序数组中的顺序重写整个文件。我希望这种方法比其他方法更快。所以…让我们编写一些伪代码。

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);

在RAM中排序FileItem结构是O(n log n)，但是对于100000个项目，它将很快并且将使用少量内存。

拷贝是最慢的部分，使用256kb ..2兆字节用于块复制，以确保将文件A的大块复制到文件B的速度很快，但是您可以通过一些测试来调整块复制内存的数量，始终记住每台机器都是不同的。

尝试多线程方法是没有用的，它只会减慢复制速度。

这很明显，但是，如果您从驱动器C:复制到驱动器D:，它会更快(当然，不是分区，而是两个不同的串行数据驱动器)。

还考虑到你需要seek，或者在阅读或写作中，在某些时候，你需要seek。另外，如果您将原始文件分割成几个较小的文件，您将使操作系统寻找较小的文件，这是没有意义的，它将是混乱的，速度较慢，并且可能也更难编写代码。还要考虑到，如果文件碎片化，操作系统将自行查找，这是您无法控制的。

我想到的第一个解决方案是依次读取输入文件，并为每个子文件构建一个subfile -object。这些对象一旦被创建，就会被放入b+树中。树将根据子文件的SortIndex排序。一个好的b-tree实现将具有链接的子节点，使您能够以正确的顺序遍历子文件并将它们写入输出文件

另一种方法是使用随机访问文件。你可以加载所有的SortIndexes和偏移量。然后对它们进行排序，并以排序的方式写入输出文件。在这种情况下，一切都取决于随机访问文件的工作方式。在这种情况下，一切都取决于随机访问文件读取器的实现。如果它只是读取文件，直到指定的位置，它将不是很性能。老实说，我不知道它们是怎么工作的……(

相关文章：