1

我有一个二进制文件，可以看作是不同子文件的串联：

输入文件：

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

这些是我关于每个子文件的信息：

  • 起始偏移
  • 字节长度
  • 最终序列顺序

您认为生成排序输出文件的最快方法是什么？

例如 OUTPUT FILE 将按以下顺序包含 SubFile：

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

我曾想过：

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

还要考虑以下信息：

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

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

提前致谢

4

2 回答 2

2

此外，如果文件很大，则 ID 的数量不会那么大。

您可以在 RAM 中获取所有 ID、排序索引、偏移量、长度，然后使用简单的快速排序在 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 个项目，它会很快并且会使用少量内存。

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

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

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

还要考虑你需要寻找，或者在阅读或写作中，在某些时候，你需要寻找。此外，如果您将原始文件拆分为几个较小的文件，您将使操作系统寻找较小的文件，这没有任何意义，它会变得混乱和缓慢，并且可能也更难以编码。还要考虑如果文件是碎片化的，操作系统会自行寻找，这是你无法控制的。

于 2011-10-29T16:04:48.680 回答
1

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

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

于 2011-10-29T16:06:18.947 回答