0

所以我有这些巨大的 XML 文件（我的意思是 1.5GB+）而且它们没有 CRLF。我正在尝试运行类似 diff 的程序来查找这些文件之间的差异。

由于我还没有找到一个不会因内存耗尽而爆炸的差异程序，我决定最好的选择是在关闭标签后添加 CRLF。

我编写了一个 python 脚本来逐个读取字符并在“>”之后添加换行符。问题是我在大约 1995 年的单核 PC 上运行它，或者一些荒谬的东西，当我同时转换时，它只处理大约 20MB/小时。

知道如果用 C#/C/C++ 编写它会产生任何好处吗？如果没有，是否有人知道将逐字节进行的差异程序？谢谢。

编辑：

这是我的处理功能的代码...

def read_and_format(inputfile, outputfile):
    ''' Open input and output files, then read char-by-char and add new lines after ">" '''
    infile = codecs.open(inputfile,"r","utf-8")
    outfile = codecs.open(outputfile,"w","utf-8")

    char = infile.read(1) 
    while(1):
        if char == "":
            break
        else:
            outfile.write(char)
            if(char == ">"):
                outfile.write("\n")
        char = infile.read(1)

    infile.close()
    outfile.close()

EDIT2： 感谢您的精彩回复。增加读取大小带来了令人难以置信的速度提升。问题解决了。

4

8 回答 8

11

一次读取和写入一个字符几乎总是很慢，因为磁盘是基于块的设备，而不是基于字符的设备——它读取的内容远不止你所追求的一个字节，而且多余的部分需要丢弃。

尝试一次读取和写入更多内容，例如 8192 字节 (8KB)，然后在该字符串中查找并添加换行符，然后再将其写入 - 您应该会节省很多性能，因为需要的 I/O 会少很多。

正如 LBushkin 所指出的，您的 I/O 库可能正在进行缓冲，但除非有某种形式的文档表明这确实发生了（用于读取和写入），否则在用不同的语言重写之前尝试这是一件相当容易的事情。

于 2009-08-26T17:17:43.177 回答
3

为什么不直接使用 sed？猫巨人.xml | sed 's/>/>\x0a\x0d/g' > Giant-with-linebreaks.xml

于 2009-08-26T18:29:45.060 回答
1

而不是逐字节读取，这会导致每个字节读取的磁盘访问，尝试一次读取〜20 MB并进行搜索+替换:)

您可能可以在记事本中执行此操作....

比利3

于 2009-08-26T17:18:53.360 回答
1

对于您描述的问题类型，我怀疑您用于比较数据的算法将比 I/O 模型或语言产生更显着的影响。事实上，字符串分配和搜索在这里可能比其他任何事情都更昂贵。

在您自己编写此内容之前，一些一般性建议：

  1. 如果有可用的机器，请尝试在更快的机器上运行。这将产生巨大的影响。
  2. 在网上寻找一个现有的工具来做 XML 差异......不要自己写。

如果要用 C#（或 Java 或 C/C++）编写，我会执行以下操作：

  1. 一次将一个相当大的块读入内存（假设在 200k 和 1M 之间）
  2. 分配一个两倍大小的空块（假设每个字符的最坏情况是'>'）
  3. 从输入块复制到输出块，有条件地在每个“>”字符后附加一个 CRLF。
  4. 将新块写入磁盘。
  5. 重复直到处理完所有数据。

此外，您还可以编写这样的程序以在多个线程上运行，这样一旦线程在内存中执行 CRLF 插入，就会从磁盘中读取一个单独的线程块。这种类型的并行化很复杂......所以我只会在你真的需要最高性能的情况下这样做。

如果需要，这里有一个非常简单的 C# 程序可以帮助您入门。它在命令行上接受输入文件路径和输出路径，并执行您正在寻找的替换 ('>' ==> CRLF)。这个示例还有很多需要改进的地方（并行处理、流式传输、一些验证等）......但它应该是一个不错的开始。

using System;
using System.IO;

namespace ExpandBrackets
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length == 2)
            {
                using( StreamReader input = new StreamReader( args[0] ) )
                using( StreamWriter output = new StreamWriter( args[1] ) )
                {
                    int readSize = 0;
                    int blockSize = 100000;
                    char[] inBuffer = new char[blockSize];
                    char[] outBuffer = new char[blockSize*3];
                    while( ( readSize = input.ReadBlock( inBuffer, 0, blockSize ) ) > 0 )
                    {
                        int writeSize = TransformBlock( inBuffer, outBuffer, readSize );
                        output.Write( outBuffer, 0, writeSize );
                    }
                }
            }
            else
            {
                Console.WriteLine( "Usage:  repchar {inputfile} {outputfile}" );
            }
        }

        private static int TransformBlock( char[] inBuffer, char[] outBuffer, int size )
        {
            int j = 0;
            for( int i = 0; i < size; i++ )
            {
                outBuffer[j++] = inBuffer[i];
                if (inBuffer[i] == '>') // append CR LF
                {
                    outBuffer[j++] = '\r';
                    outBuffer[j++] = '\n';
                }
            }
            return j;
        }
    }
}
于 2009-08-26T17:29:47.253 回答
0

通常提到的所有语言在某些时候都会恢复到 C 运行时库以进行逐字节文件访问。用 C 语言编写它可能是最快的选择。

但是，我怀疑它会提供巨大的速度提升。如果您正确地做事，Python 相当快。

真正大幅提高速度的主要方法是引入线程。如果您在一个线程中以大块的形式从文件中读取数据，并且有一个单独的线程进行换行处理+差异处理，则可以显着提高该算法的速度。这可能在 C++、C# 或 IronPython 中比直接在 C 或 CPython 中更容易实现，因为它们提供了非常简单的高级同步工具来处理线程问题（尤其是在使用 .NET 时）。

于 2009-08-26T17:16:46.110 回答
0

你可以试试 xmldiff - http://msdn.microsoft.com/en-us/library/aa302294.aspx

我没有将它用于如此庞大的数据，但我认为它会得到合理的优化

于 2009-08-26T17:17:30.697 回答
0

我将此作为对另一个答案的评论，但如果您错过了它 - 您可能想看看The Shootout。它是针对多种语言的各种问题的高度优化的代码集。

根据这些结果，Python 往往比 c 慢 50 倍左右（但它比其他解释语言快）。相比之下，Java 比 c 慢大约 2 倍。如果您使用一种更快的编译语言，我不明白为什么您不会看到类似的增长。

顺便说一句，从枪战中获得的数字非常无懈可击，你不能真正挑战它们，相反，如果你不相信数字是公平的，因为用你最喜欢的语言解决问题的代码没有优化正确，然后您可以自己提交更好的代码。许多人这样做意味着那里的大多数代码都针对每种流行语言进行了非常优化。如果您向他们展示更优化的编译器或解释器，他们可能也会包含其中的结果。

哦：除了C#，只用MONO表示，所以如果微软的编译器更优化，就不显示了。所有测试似乎都在 Linux 机器上运行。我的猜测是微软的 C# 应该以与 Java 差不多的速度运行，但枪战将单声道列为慢一点（大约是 C 的 3 倍）。

于 2009-08-26T17:41:37.573 回答
0

正如其他人所说，如果您在 C 中执行此操作，那将是无与伦比的，因为 C 缓冲 I/O，并且 getc() 是内联的（在我的记忆中）。

您真正的性能问题将在差异中。

也许那里有一个相当不错的文件，但是对于那些大小的文件，我对此表示怀疑。为了好玩，我是一个自己动手的人。我将使用的策略是在每个文件中都有一个滚动窗口，长几兆字节。不匹配的搜索策略是对角搜索，如果你在第 i 行和第 j 行，按以下顺序进行比较：

line(i+0) == line(j+0)

line(i+0) == line(j+1)
line(i+1) == line(j+0)

line(i+0) == line(j+2)
line(i+1) == line(j+1)
line(i+2) == line(j+0)

等等。毫无疑问，有更好的方法，但如果我要自己编写代码并管理滚动窗口，那就是我会尝试的。

于 2009-08-26T20:25:15.480 回答