常数时间文本文件修改

Question

我有一组相当大的文件（每个文件大约50兆字节，至少100个），但我需要在每个文件中插入一个小标题（大约两打行）以进行处理。我希望编写一个bash或python脚本来完成此任务，但我找不到一个常数时间函数，让我能够在文本文件前面插入内容。如果它不是常数时间，我认为完成该任务将需要太长的时间。有没有人对这个问题有经验？

- user2401982

---

不，无法在常数时间内完成。你无法在不重写整个文件的情况下在文件前添加数据。这是文件系统的根本限制，而非编程语言。 - Chewie

但是，如果您稍后计划在Python（或其他语言）中“处理”这些文件，则可以伪造一个类似文件的对象，该对象“假装”它们已经在前面添加了“小标题”，而不是修改实际文件，假设这是可接受的替代方案。 - Aya

Answer 1

与Uwe的回答类似，但如果您的处理工具只能将参数作为文件名接受，则可以使用mkfifo(1)来伪造一个文件名。

例如，在bash中...

echo 'My header' > header.txt
echo 'My content' > content.txt
mkfifo fakefile.txt
cat header.txt content.txt > fakefile.txt &
cat fakefile.txt

...会流式传输这两个文件的内容，而不是创建一个新文件。

- Aya

Answer 2

在Unix文件中，无论是在开头还是中间，都无法以恒定时间插入文本。另一方面，根据您的处理方式，有一小部分可能可以完全避免插入。如果您的处理工具能够从管道读取，则可以这样做：

然后你可以执行如下操作：

cat headerfile datafile | myprocessingtool

因此，数据文件实际上并未被修改。

- Uwe

---

澄清一下，当我说常数时间时，是指相对于修改后的文件是常数时间。显然，相对于插入的文本来说，它必须是线性的。这是否仍然不可能？ - user2401982

@user2401982 当向文件追加内容时，所需的时间（至少在理论上）与您要追加的新数据的大小成正比，但如果您要进行前置或插入，则与原始文件和新数据的大小之和成正比。 - Aya

Answer 3

我认为这是你能做到的最好的（bash）：

MYHEADER=/path/to/the/header
HEADERSIZE=$(stat --format %s "$MYHEADER")

for FILENAME in $FILES; do
    OLDSIZE=$(stat --format %s "$FILENAME")
    cat "$MYHEADER" "$FILENAME" > /tmp/headerize.tmp
    NEWSIZE=$(stat --format %s /tmp/headerize.tmp)
    EXPECTEDSIZE=$(($HEADERSIZE+$OLDSIZE))
    if [ "$NEWSIZE" -eq "$EXPECTEDSIZE" ]; then
      mv /tmp/headerize.tmp "$FILENAME"
    else
      echo "Something odd happened when processing $FILENAME, headerization skipped for this file."
    fi
done

除非你的系统极度糟糕，或者对时间限制要求过高，否则这个过程应该在合理的时间内完成。并且包括错误检查。

当然，你应该确保你的头文件以换行符结束，否则最终的头文件行和第一行文本文件将被合并。

这里唯一剩下的优化就是确保临时文件写入与原始文件相同的文件系统；这可能会加快mv命令的速度。

总的来说，内容插入都很慢。无论是在内存中还是在磁盘上都是如此。我相信你永远不可能找到一个常数时间解决方案。但是，对于一次性批处理作业，你可能实际上并不需要一个。

这是我认为你可以在Python中实现的最快速度。由于它不创建临时文件，因此可能比bash版本更快：

MYHEADERPATH=/path/to/the/header
with open(MYHEADERPATH, 'r') as f:
    header = f.read()
for filename in files:
    with open(filename, 'r') as f:
        content = f.read()
    with open(filename, 'w') as f:
        f.write(header + content)

然而，如果你希望它绝对安全，你就必须像bash脚本一样去做，所以最终速度可能会有一些差异。

- kampu

---

OLDSIZE/NEWSIZE检查似乎是不必要的；在Python版本中你没有做类似的事情。使用临时文件并重命名与覆盖现有文件之间在性能上没有（有意义的）差异。 - chepner

@chepner：当且仅当临时文件位于相同的文件系统上时为True（/tmp通常位于自己的文件系统中。在Arch Linux上肯定是这样）。我故意使版本不同，因为这个原因。此外，cat命令可能会失败（空间不足），您不希望用截断的版本覆盖它。 - kampu

@chepner：我开始思考这个问题，并得出结论，除非让Python版本模仿Bash版本，否则我的唯一选择就是使用df，但对于如此微小的脚本来说，这太过繁琐了 :) 而且Bash脚本并不完全安全：可能会发生部分截断（其中n_truncated_bytes < header_size）。为了正确地执行它，我想我需要测量头文件大小并检查确切的期望大小值。编辑：完成 :) - kampu