c++ - C++寻求复杂性

Question

我在二进制文件中存储了许多不同大小的对象。为了允许随机访问该文件，我正在考虑创建第二个文件来存储每个对象的第一个（也可能是结束）位置。然后，当我需要一个特定对象时，我会查找它所在的位置，然后我可以使用seekg它导航到该位置并阅读它。

我的问题是，什么是复杂性seekg？是 O(1) 还是取决于我设置位置指针的文件开头有多远？如果它的位置是线性的，我的解决方案就没有意义，我可以在对象之间使用一些分隔符，并始终从头到尾读取整个文件直到分隔符。

标签： c++

Answer 1

在二进制流模式下，寻找（什么seekg是）在内核内部的文件系统代码中完成所有工作（无论它在 C++ 端做多少工作都是无关紧要的），所以如果你想知道它的计算复杂度，你需要查看您正在使用的特定文件系统驱动程序（在 Linux 上它是开源的，在 Windows 上，如果您在学术界，则需要学术访问权限）。

但一般来说，有了文件系统如何组织数据的基本知识：成本可能是摊销对数或类似的东西，你需要强大的大文件来实际测量具有足够分辨率的计算成本，以便能够“看到”对数响应（在启用了零块压缩的 ramdisk 上具有类似大小的文件的 PB 卷，因此价值几 GB）。

在典型场景中，seekg具有固定成本。它在文件系统驱动程序中花费所有时间，等待从磁盘上提取一些带有文件系统元数据的额外块。无论您在文件中的哪个位置查找，都需要提取大约相同数量的新块（大文件和随机查找的限制情况）。但是，如果您根据在大文件上每次随机搜索读取的块数来衡量成本，那么它仍然足够接近固定成本：想象一下您的应用程序中将拥有的最大文件，以及其中的文件和较小的尺寸，块的数量将受您观察到的任何限制。因此，只要您对要处理的最大文件的实际延迟没有问题，其他一切都可以。

即使seekg有 O(N) 成本，它也不应该像读取文件一样长。例如，在具有多种磁带驱动器的 Linux 上，如果您打开/dev/st设备文件，在最坏的情况下查找具有O(N)“成本”，但缩放因子比读取文件时要好得多，因为磁带查找速度比读取速度快 :)在所有这些情况下，成本的概念也很奇怪：这不是花在计算上的时间，而是花在等待介质和头部在正确位置汇聚的时间:)

不要忘记打开fstreaminstd::ios::binary模式！如果您确实忘记了，那么seekg最终可能会花费与读取文件相同的成本，而您不希望这样。