c# - パフォーマンス - Python と C#/C++/C の 1 文字ずつの読み取り

Question

したがって、私はこれらの巨大な XML ファイル (巨大とは、1.5GB 以上という意味です) を持っていますが、それらには CRLF がありません。これらのファイルの違いを見つけるために、差分のようなプログラムを実行しようとしています。

メモリ不足のために爆発しない差分プログラムをまだ見つけていないので、タグを閉じた後に CRLF を追加するのが最善の策であると判断しました。

文字ごとに読み取り、「>」の後に改行を追加するPythonスクリプトを作成しました。問題は、これを 1995 年頃のシングルコア PC かばかげたもので実行していて、両方を同時に変換した場合、1 時間あたり約 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: すばらしい回答をありがとう。読み取りサイズを増やすと、信じられないほど速度が向上しました。問題が解決しました。

score 11 · Accepted Answer

ディスクは文字ベースのデバイスではなくブロックベースのデバイスであるため、一度に 1 文字の読み取りと書き込みはほとんどの場合遅くなります。余分な部品は廃棄する必要があります。

8192 バイト (8KB) など、一度に読み書きを増やしてから、文字列を書き出す前にその文字列に改行を見つけて追加してみてください。必要な I/O が大幅に減るため、パフォーマンスが大幅に節約されます。

LBushkin が指摘しているように、I/O ライブラリはバッファリングを行っている可能性がありますが、これが実際に行われることを示す形式のドキュメントがない限り (読み取りと書き込みについて)、別の言語で書き直す前に試すのはかなり簡単です。

score 3 · Accepted Answer

3

sedを使ってみませんか？猫giant.xml| sed's /> /> \ x0a \ x0d / g'>giant-with-linebreaks.xml

于 2009-08-26T18:29:45.060 に答える

score 1 · Accepted Answer

あなたが説明する問題のタイプについては、データを比較するために使用するアルゴリズムが、I/Oモデルまたは言語よりもはるかに重要な効果をもたらすと思います。実際、文字列の割り当てと検索は、ここでは他の何よりもコストがかかる可能性があります。

これを自分で書く前のいくつかの一般的な提案：

使用可能なマシンがある場合は、より高速なマシンで実行してみてください。それは大きな違いを生むでしょう。
XML差分を実行するための既存のツールをオンラインで探してください...自分で作成しないでください。

これをC＃（またはJavaまたはC / C ++）で作成する場合は、次のようにします。

かなり大きなブロックを一度にメモリに読み込みます（たとえば、200kから1Mの間）
そのサイズの2倍の空のブロックを割り当てます（これは、すべての文字の最悪のケースが'>'であると想定しています）
入力ブロックから出力ブロックにコピーし、条件付きで各「>」文字の後にCRLFを追加します。
新しいブロックをディスクに書き込みます。
すべてのデータが処理されるまで繰り返します。

さらに、このようなプログラムを複数のスレッドで実行するように作成して、スレッドがメモリに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;
        }
    }
}

score 1 · Accepted Answer

バイト単位で読み取るのではなく、読み取るバイトごとにディスクアクセスが発生します。一度に最大 20 MB を読み取って、検索と置換を実行してみてください :)

おそらくメモ帳でこれを行うことができます....

ビリー3

score 0 · Accepted Answer

他の人が言ったように、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)

等々。もっと良い方法があることは間違いありませんが、自分でコーディングしてローリングウィンドウを管理する場合は、それを試してみます。

score 0 · Accepted Answer

一般的に言及されているすべての言語は、ある時点で、バイトごとのファイルアクセスのために C ランタイムライブラリに戻ります。これを C で書くのがおそらく最速のオプションです。

しかし、それが大幅な速度向上をもたらすとは思えません。正しく実行していれば、Python はかなり高速です。

速度を大幅に向上させる主な方法は、スレッド化を導入することです。1 つのスレッドで大きなブロックのファイルからデータを読み取り、改行処理 + 差分処理を行う別のスレッドがあれば、このアルゴリズムの速度を劇的に向上させることができます。これは、C または CPython で直接実装するよりも、C++、C#、または IronPython で実装する方がおそらく簡単です。これらは、スレッド化の問題を処理するための非常に簡単で高レベルの同期ツールを提供するためです (特に .NET を使用する場合)。

score 0 · Accepted Answer

あなたはxmldiffを試すことができます - http://msdn.microsoft.com/en-us/library/aa302294.aspx

そのような巨大なデータには使用していませんが、合理的に最適化されると思います

score 0 · Accepted Answer

これを別の回答にコメントとして入れましたが、見逃した場合はThe Shootoutをご覧ください。これは、多くの言語のさまざまな問題に対して高度に最適化されたコードセットです。

これらの結果によると、Python は c よりも約 50 倍遅い傾向にあります (ただし、他のインタープリター言語よりは高速です)。比較すると、Java は c よりも約 2 倍遅いです。より高速にコンパイルされた言語の 1 つに行った場合、同様の増加が見られない理由がわかりません。

ちなみに、銃撃戦で得られた数字は驚くほど攻撃不可能であり、好きな言語で問題を解決するためのコードが最適化されていないために数字が公平であると信じていない場合は、実際にそれらに挑戦することはできません.適切であれば、より良いコードを自分で提出できます。多くの人がこれを行っているということは、そこにあるコードのほとんどが、すべての一般的な言語に対してかなり最適化されていることを意味します。より最適化されたコンパイラまたはインタープリタを提示すると、その結果も含まれる可能性があります。

Oh: C# を除いて、それは MONO でしか表されないので、Microsoft のコンパイラがより最適化されている場合は表示されません。すべてのテストは Linux マシンで実行されているようです。私の推測では、Microsoft の C# は Java とほぼ同じ速度で実行されるはずですが、銃撃戦では mono が少し遅い (C の約 3 倍遅い) と記載されています。

c# - パフォーマンス - Python と C#/C++/C の 1 文字ずつの読み取り

8 に答える 8

Related

Reference