33

そのため、奇妙な理由で、100 GBのログファイルが並べ替えられていない（実際には部分的に並べ替えられている）ことになりますが、適用しようとしているアルゴリズムには並べ替えられたデータが必要です。ログファイルの行は次のようになります

data <date> data data more data

ワークステーションでC＃4.0と約4GBのRAMにアクセスできます。ここではマージソートが最適だと思いますが、これらのアルゴリズムを自分で実装することはできません。私が取ることができるショートカットがあるかどうかを尋ねたいと思います。

ちなみに、日付文字列の解析DateTime.Parse()は非常に遅く、多くのCPU時間を消費します-チャギングレートはわずか10MB/秒です。以下よりも速い方法はありますか？

    public static DateTime Parse(string data)
    {            
        int year, month, day;

        int.TryParse(data.Substring(0, 4), out year);
        int.TryParse(data.Substring(5, 2), out month);
        int.TryParse(data.Substring(8, 2), out day);

        return new DateTime(year, month, day);
    }

私はスピードアップするためにそれを書きましたDateTime.Parse()、そしてそれは実際にうまくいきます、しかしそれでもバケツの負荷のサイクルを取っています。

現在のログファイルについては、時間、分、秒にも関心があることに注意してください。DateTime.Parse（）にフォーマットを提供できることは知っていますが、それほど高速化されていないようです。

よろしくお願いします。

編集：日付を比較するために文字列比較を使用することを提案する人もいます。これは並べ替えフェーズでは機能しますが、アルゴリズムの日付を解析する必要があります。手動で行わずに、4GBの無料RAMで100GBのファイルを並べ替える方法がまだわかりません。

編集2 ：ええと、私がWindowsソートを使用するといういくつかの提案のおかげで、Linux用の同様のツールがあることがわかりました。基本的に、sortを呼び出すと、すべてが修正されます。私たちが話すとき、それは何かをしている、そして私はそれがすぐに終わることを願っている。私が使用しているコマンドは

sort -k 2b 2008.log > 2008.sorted.log

-kは、通常の形式の日時文字列である2番目の行でソートすることを指定しYYYY-MM-DD hh:mm:ss.msekます。マンページにはすべてのオプションの説明が不足していることを認めなければなりませんが、を実行して多くの例を見つけましたinfo coreutils 'sort invocation'。

結果とタイミングを報告します。ログのこの部分は約27GBです。2009年と2010年を別々に並べ替えてから、sort-mオプションを使用して結果を1つのファイルにマージすることを考えています。

編集3ええと、iotopをチェックすると、データファイルの小さなチャンクを読み込んで、それらを処理するために猛烈に何かをしていることがわかります。このプロセスはかなり遅いようです。=（

sortはメモリを使用せず、単一のコアのみを使用しています。ドライブからデータを読み取る場合、何も処理していません。私は何か間違ったことをしていますか？

編集43時間経っても、同じことを続けています。今、私は関数のパラメーターを試してみたい段階にありますが、3時間投資しています...約4時間で中止し、よりスマートなメモリを使用して一晩計算するようにしますおよびスペースパラメータ...

編集5家に帰る前に、次のコマンドでプロセスを再開しました。

sort -k 2b --buffer-size=60% -T ~/temp/ -T "/media/My Passport" 2010.log -o 2010.sorted.log

今朝、これを返しました：

sort: write failed: /media/My Passport/sortQAUKdT: File too large

Wraawr！このプロセスをスピードアップするために、できるだけ多くのハードドライブを追加するだけだと思いました。どうやらUSBドライブを追加することはこれまでで最悪のアイデアでした。現時点では、FAT / NTFSなどの問題であるかどうかさえわかりません。これは、fdiskがUSBドライブが「間違ったデバイス」であると言っているためです...冗談ではありません。後でもう一度試してみます。とりあえず、このプロジェクトを失敗した可能性のある山に入れましょう。

最終通知 今回は、上記と同じコマンドで動作しましたが、問題のある外付けハードドライブはありませんでした。よろしくお願いします！

ベンチマーク

同じSATAコントローラーで2つのワークステーショングレード（少なくとも70mb /秒の読み取り/書き込みIO）のハードディスクを使用すると、30GBのログファイルを並べ替えるのに162分かかりました。今夜、さらに52 GBのファイルを並べ替える必要があります。その方法については、投稿します。

4

16 に答える 16

18

このようなコードは、ディスクからデータを取得する速度に完全に拘束されます。ファイルはファイルシステムキャッシュに収まらないため、常にディスクがデータを提供するのを待っています。あなたは10MB/秒でかなりうまくやっています、コードを最適化することは決して認識できる効果をもたらすことはありません。

より高速なディスクを入手してください。中間ステップとして、取得したものをデフラグします。

于 2010-09-25T18:42:18.247 に答える
16

文字列の並べ替えが機能する場合は、WindowsのSORTコマンドを使用してください。ファイルを並べ替えて、それで終わります。100GBのファイルを問題なく並べ替えることができ、使い方も簡単です。

ファイル、特に日付フィールドをフィルタリングして変換する必要がある場合は、データフィールドを0で埋められた整数（1970年以降の秒数など）に変換する小さな変換プログラムを作成するだけです。レコードを書き換えます。次に、出力をsortコマンドにパイプ（|）して、ユーティリティプログラムでより簡単に解析できる最終的なソート済みファイルを作成できます。

あなたが犯している間違いは、単にこれをすべて一度にやろうとしていることだと思います。100GBのデータは大量で、コピーには時間がかかりますが、それほど時間はかかりません。並べ替える必要があるため、マージソートなどの外部並べ替えルーチンを使用する場合でも、ある時点でファイルのコピーを処理する必要があります（つまり、両方のコピーを処理するために、マシン上にできるだけ多くの空き領域が必要です）。 。

単純なリフォーマッターを作成し、それをパイプで並べ替えると、必然的に2つのコピーが必要になるため、ファイルを数回移動したり、ディスクのスペースを節約したりできます。

また、フォーマッターを微調整して、本当に関心のあるフィールドのみをプルし、その時点ですべての「重い」解析を実行して、最終的にレポートルーチンで簡単に処理できるフォーマット済みファイルになるようにします。 。そうすれば、後でレポートを複数回実行する可能性があるときに時間を節約できます。

可能であれば、出力には単純なCSVを使用するか、さらに良いのは固定長のファイル形式を使用します。

整数を使用する場合は、日付情報のすべてのフィールドの長さが同じであることを確認してください。そうしないと、SORTユーティリティはそれらを正しくソートしません（1 2310.ではなく1102 3になります）。

編集 -

別のタクトからアプローチしてみましょう。

最大の問題は、「このすべてのデータが必要ですか」です。これは、最初に重い構文解析を行うことについての以前の提案に関連しています。明らかに、初期セットを減らすことができるほど良いです。たとえば、データの10％を削除するだけで10GBになります。

経験則として、特に大量のデータを処理する場合に考えたいことがあります。「100万個のデータがある場合、1ミリ秒ごとに節約されるのは収益から20分です。」

通常、私たちは実際にミリ秒単位で作業を考えていません。それは、より「ズボンの座席」、「より速く感じる」ということです。ただし、1ms == 20min / millionは、処理しているデータの量と、処理にかかる時間/必要な時間を把握するための適切な指標です。

あなたの場合、100GBのデータ。レコードあたり100バイトのスワッグで、10億行を取得しています。ミリ秒あたり20,000分。-5時間半。gulp（これは経験則です。計算を行うと、これにはうまくいきません。）

したがって、可能な限り生データを削減したいという願望を理解することができます。

これが、私がWindowsSORTコマンドを延期した理由の1つです。これは基本的なプロセスですが、ニュアンスの影響を受け、最適化を使用できるプロセスです。SORTを書いた人々には、多くの点でそれを「最適」にする時間と機会がありました。彼らがしたかどうかにかかわらず、私は言うことができません。しかし、厳しい締め切りに直面しているあなたとは対照的に、彼らがSORTを実用的なものと同じくらい良くするために、このプロセスにより多くの時間と注意を払うであろうというのは公正な仮定です。

大規模なデータセット用のサードパーティの並べ替えユーティリティがありますが、おそらく（理想的には）その場合に適しています。しかし、それらはあなたには利用できません（あなたはそれらを手に入れることができますが、私はあなたが急いで他のユーティリティをすぐに手に入れたいとは思わなかったと思います）。したがって、SORTは今のところ最善の推測です。

とは言うものの、データセットを減らすことはどんなソートユーティリティよりも多くを得るでしょう。

本当に必要な詳細はどれくらいですか？そして、あなたは実際にどのくらいの情報を追跡していますか？たとえば、Web統計の場合、サイトに1000ページある可能性があります。しかし、1年間の1時間あたりの数値が365 * 24 * 1000であっても、それは8.7Mの「バケット」の情報にすぎません。1Bとはかけ離れています。

では、並べ替えを必要としない前処理はありますか？情報をより粗い粒度に要約しますか？ソートせずに、メモリベースのハッシュマップを使用するだけでそれを行うことができます。100GBのデータすべてを1回のスローで処理するための「十分なメモリ」がない場合でも、おそらくチャンク（5チャンク、10チャンク）で処理し、中間結果を書き出すのに十分です。

また、データを分割する方がはるかに幸運である可能性もあります。月次または週次のファイルチャンクに。データが「ほとんど」ソートされているため、これは簡単にはできないかもしれません。しかし、その場合、それが日付によるものである場合、違反者（つまり、分類されていないデータ）はファイル内にクラスター化され、「順序が狂っている」ものが期間の障壁に混同されている可能性があります（日の遷移のように、11：58 pm、11：59 pm、00：00 am、00：01 am、11：58 pm、00：02pmのような行があるかもしれません。そのヒューリスティックも活用できる可能性があります。

目標は、順序が狂っているサブセットをある程度決定論的に決定し、ファイルを「順序データ」と「順序外データ」のチャンクに分割できる場合、並べ替えタスクがはるかに小さくなる可能性があることです。順序が狂っているいくつかの行を並べ替えると、マージの問題が発生します（並べ替えの問題よりもはるかに簡単です）。

だから、それらはあなたが問題に取り組むために取ることができる戦術です。要約は明らかに最良の方法です。測定可能なデータの負荷を軽減するものは、問題を起こす価値があると思われるからです。もちろん、それはすべて、データから本当に必要なものに要約されます。明らかに、レポートがそれを推進します。これは、「時期尚早の最適化」についての良い点でもあります。彼らがそれについて報告していない場合は、それを処理しないでください:)。

于 2010-09-25T19:33:00.883 に答える
13

簡単な答え-データをリレーショナルデータベース（SQL Expressなど）にロードし、インデックスを作成し、カーソルベースのソリューション（DataReaderなど）を使用して各レコードを読み取り、ディスクに書き込みます。

于 2010-09-25T19:53:04.423 に答える
9

logparserと呼ばれるMicrosoftのこの比較的知られていないツールを試してみませんか。基本的に、CSVファイル（またはその他のフォーマットされたテキストファイル）に対してSQLクエリを実行できます。

データベースにポンプで送り、ソートを実行し、再度ポンプで戻す手間を省きます。

于 2010-09-25T21:18:49.353 に答える
8

メモリに収まらない長いファイルの並べ替えに関する質問に答えるだけです。マージソートなどの外部並べ替えアルゴリズムを使用する必要があります。プロセスはおおまかに次のとおりです。

  • 入力をメモリに収まるいくつかの部分に分割し、標準のメモリ内並べ替えアルゴリズムを使用して並べ替えることができます（たとえば、100 MB以上-一度に最大4つの部分をメモリに保持する必要があります）。すべてのパーツを並べ替えて、ディスクに書き戻します。

  • ディスクから2つの部分を読み取り（両方ともソートされています）、それらをマージします。これは、2つの入力を同時に繰り返すだけで実行できます。マージされたデータセットをディスク内の別の場所に書き込みます。部分全体をメモリに読み込む必要はないことに注意してください。読みながらブロックに書き込むだけです。

  • パーツが1つになるまで、パーツのマージを繰り返します（元の入力データセットのすべてのデータでファイルが並べ替えられます）。

データはすでに部分的に並べ替えられているとのことですが、この場合に効率的なメモリ内並べ替え（最初のフェーズ）のアルゴリズムを選択することをお勧めします。この質問でいくつかの提案を見ることができます（ただし、非常に大きなデータセットで答えが同じになるかどうかはわかりませんが、入力が部分的に並べ替えられているかどうかによって異なります）。

于 2010-09-25T19:09:51.140 に答える
4

日付の解析を最適化する最良の方法は、日付をまったく解析しないことです。

日付はISO8601形式であるため、文字列として比較できます。解析はまったく必要ありません。

並べ替えに関しては、部分的に並べ替えられているという事実を有効に活用できるはずです。1つのアプローチは、ファイルを読み取り、時間範囲（たとえば、毎日または1時間ごと）に分割された別々のファイルに書き込むことです。各ファイルを十分に小さくすると、それらをメモリに読み込んで並べ替えてから、すべてのファイルをマージすることができます。

別のアプローチは、ファイルを読み取り、順番に並んでいるレコードを1つのファイルに書き込み、他のレコードを別のファイルに書き込むことです。2番目のファイルを並べ替え（サイズが大きい場合は、このプロセスを再帰的に使用する可能性があります）、2つのファイルを一緒に圧縮します。つまり、変更されたマージソート。

于 2010-09-25T18:50:31.177 に答える
4

ソートには、ファイルベースのバケットソートを実装できます。

  1. 入力ファイルを開く
  2. ファイルを1行ずつ読み取る
  3. 行から文字列として日付を取得します
  4. ファイルに行を追加<date>.log

結果は、日ごとに個別のログファイル、または時間ごとに個別のログファイルになります。簡単に並べ替えることができるサイズのファイルを取得できるように選択してください。

残りのタスクは、作成されたファイルをソートし、場合によってはファイルを再度マージすることです。

于 2010-09-27T18:49:25.917 に答える
3

アルゴリズムの日付を解析する必要があります。

* NIXでは、通常、最初に日付をテキスト比較に適した単純なものに変換し、文字列の最初の単語にします。日付/時刻オブジェクトを作成するには時期尚早です。私のいつもの日付のプレゼンテーションはYYYYMMDD-hhmmss.millisです。すべてのファイルが同じ日付形式になるようにします。

手動で行わずに、4GBの無料RAMで100GBのファイルを並べ替える方法がまだわかりません。

すでに理解しているように、マージソートが唯一のオプションです。

したがって、私にとって、タスクは次のステップに分類されます。

  1. 日付をソート可能にするためのダム変換。複雑さ：100GBを順次読み取り/書き込みします。

  2. データを使用可能なサイズ（たとえば1GB）のチャンクに分割し、ディスクに書き込む前にプレーンクイックソートを使用してすべてのチャンクをソートします。複雑さ：連続して100GBの読み取り/書き込み。クイックソート用のメモリ。

  3. マージ-小さなファイルを1つの大きなファイルにソートします。2つのファイルを取得し、それらを新しいファイルにマージするプログラムを使用して、段階的に実行できます。複雑さ：100GB log（N）回連続して読み取り/書き込み（Nはファイルの数）。HDDスペース要件：2 * 100GB（2 x 50GBファイルの単一の100GBファイルへの最後のマージ）。

  4. 前のステップを自動化するプログラム：2つの（たとえば最小の）ファイルを選択し、プログラムを開始してそれらを新しいファイルにソートマージし、2つの元のファイルを削除します。ファイルの数が1より大きくなるまで繰り返します。

  5. （オプション）100GBのソート済みファイルを管理可能なサイズの小さなチャンクに分割します。結局のところ、あなたは彼らと何かをするつもりです。それらに順番に番号を付けるか、ファイル名に最初と最後のタイムスタンプを入れます。

一般的な概念：高速で実行する方法を見つけようとしないでください。100GBの配管にはとにかく時間がかかります。あなたの注意なしに、プログラムをすべてのステップで一晩バッチとして実行するように計画します。

Linuxでは、shell / sort / awk / Perlですべて実行可能であり、他のプログラミング言語ですべてを書くことは問題ではないと思います。これは潜在的に4つのプログラムですが、それらはすべてコーディングがかなり簡単です。

于 2010-09-25T19:37:36.217 に答える
3

ログファイルの行の順序が1〜2％しかない場合、ログ全体を1回通過して、2つのファイルを出力できます。1つは順序どおりのファイルで、もう1つは1〜2％の行を含むファイルです。それは故障しています。次に、メモリ内の順序が正しくない行を並べ替えて、以前は順序が正しくなかった行と順序が合っていない行を1回マージします。これは、より多くのパスを実行する完全なマージソートよりもはるかに高速です。

ログファイルにN行を超える行がない場合、N行の深さの並べ替えられたキューを使用してログを1回通過できます。順序が狂っているログ行に遭遇したときはいつでも、それをキューの適切な場所に挿入するだけです。これにはログの1回のパスのみが必要なため、可能な限り高速になります。

于 2010-09-26T17:19:23.773 に答える
2

実際、私は日付変換について多くのアイデアを持っていませんが、それを行うために使用しようとするものは次のとおりです。

  1. 日付列にインデックスがあるデータベース（後でこのデータを簡単に検索できるようにするため）。
  2. このベースに挿入するには、一括挿入を使用します。
  3. そして、読み取りを並列化するいくつかの方法（並列LINQは優れていて、非常に使いやすいと思います）。
  4. たくさんの忍耐（最も重要/難しいこと）
于 2010-09-25T20:23:52.313 に答える
2

先制的なコメント：私の答えは、日時値の解析のサブ問題にのみ対処しています。

DateTime.Parse可能なすべての日付形式のチェックが含まれています。修正フォーマットがある場合は、解析を非常にうまく最適化できます。簡単な最適化は、文字を直接変換することです。

class DateParserYyyyMmDd
{
    static void Main(string[] args)
    {
        string data = "2010-04-22";

        DateTime date = Parse(data);
    }

    struct Date
    {
        public int year;
        public int month;
        public int day;
    }

    static Date MyDate;

    static DateTime Parse2(string data)
    {
        MyDate.year = (data[0] - '0') * 1000 + (data[1] - '0') * 100 
            + (data[2] - '0') * 10 + (data[3] - '0');
        MyDate.month = (data[5] - '0') * 10 + (data[6] - '0');
        MyDate.day = (data[8] - '0') * 10 + (data[9] - '0');

        return new DateTime(MyDate.year, MyDate.month, MyDate.day);
    }
}
于 2010-09-27T18:33:10.457 に答える
1

あなたがしていることとは別に（おそらく、willwの提案は役に立ちます）、複数のプロセッサまたはプロセッサコアがあれば、複数のスレッドで解析を行うことができます。

于 2010-09-25T18:51:05.013 に答える
0

USBからLinuxフレーバーを起動し、whileコマンドを使用してファイルを読み取ります。grep、フィルター、パイプを利用してデータを分離します。これはすべて、BASHスクリプトの3行で実行できます。Grepはすぐにデータをリッピングします。45秒で700万行を調べました

于 2010-12-17T10:49:58.687 に答える
0

実際には解決策としてではありませんが、興味がないので、次のようにする1つの方法です。

  • まず、ファイルを1GBのファイルに分割します
  • 次に、一度に2つのファイルを読み取り、その内容を文字列のリストにロードして並べ替えます
  • 個々のファイルに書き戻します。

問題は、データが確実にソートされるように、パスごとに100個のファイルを読み取り/書き込みし、100回のパスを実行する必要があることです。

私の計算が正しければ：それは10000GBの読み取りと10000GBの書き込みであり、平均10MB/秒は20000 000秒、つまり231日です。

うまくいく可能性のある方法の1つは、ファイルを1回スキャンして、日や時間などの期間ごとに1つずつ、小さなファイルに書き込むことです。次に、これらの個々のファイルを並べ替えます。

于 2010-09-26T20:24:46.990 に答える
0

基数ソートアルゴリズムの実装を試すことができます。基数はリスト全体を順番に数回しかスキャンしないため、100GBファイルの膨大な数のスキャンとシークを防ぐのに役立ちます。

基数ソートは、反復ごとにレコードを1つの部分で分類することを目的としています。この部分は、数字、または年、月、日のような日時の部分にすることができます。この場合、文字列をDateTimeに変換する必要はなく、特定の部分のみをintに変換できます。

編集：

並べ替えの目的で、DateTime（DateTime.ToBinary（）as Int64）とソースファイルの行アドレス（Int64）の2つの列のみを含む一時バイナリファイルを作成できます。

次に、固定サイズのレコード（レコードあたりわずか16バイト）を含むはるかに小さいファイルを取得すると、ファイルをはるかに高速に並べ替えることができます（IO操作は少なくとも高速になります）。

一時ファイルの並べ替えが完了したら、完全に並べ替えられた100GBのログファイルを作成し直すことができます。

于 2010-09-25T21:49:59.417 に答える
0

わお。まず第一に、それはまったく新しいレベルの文書化-執着です。

私の実際の教育は、このファイルが実際にどれほど必要かを考えてみてください。

並べ替えについては、これが機能するかどうかはわかりませんが、ハードディスクから直接データを返す列挙子を作成して（おそらくいくつかのポインターを保存するだけで）、LINQのOrderByを使用してみてください。 、IEnumeratorも返します。これは、うまくいけば、列挙してディスクに直接保存できます。

唯一の問題は、OrderByがRAMに何かを保存するかどうかです。

于 2010-09-27T16:55:27.563 に答える