2

Pi の 5 億桁のバイナリ表現を含む .txt ファイルがあります。

プログラムでその文字列表現を使用する必要があります。また、部分文字列などを検索できる必要があります。つまり、通常のサイズの文字列のように処理できる必要があります。多くの部分文字列を見つけようとするので、速度が必要です。

私の最初のロジックは、単に文字列をコピーしてプログラムに直接貼り付け、それを静的変数として使用することでした..しかし、.txt ファイルを実際に開くことができなかったため、コピーして貼り付けることができませんでした。私の次の試みは、ファイルから文字列全体を読み取ることでしたが、静的メソッドではこれを行うことができず、WAAAY に時間がかかりすぎます (実際にかかる時間は正確にはわかりません。最終的にプログラムを閉じました)。

これを行うことは可能ですか？どんな助けでも大歓迎です。

編集:潜在的に関連する情報:

このコードで：

/// <summary>
    /// Gets a 500 million binary digit representation of Pi.
    /// </summary>
    public static string GetPi()
    {
        //as per http://msdn.microsoft.com/en-us/library/db5x7c0d.aspx
        StreamReader piStream = new StreamReader(@"C:\binaryPi.txt");
        string pi = "";
        string line;

        while ((line = piStream.ReadLine()) != null)
        {
            pi += line;
        }

        return pi;
    }

私は OutOfMemoryException を取得します..そのため、何かが欠けていない限り、ファイルを実際にスキャンすることはできないようです..

4

5 に答える 5

7

そのようなデータを処理できるカスタム クラスを作成することをお勧めします。

ファイルの内容が pi のバイナリ形式の表現である場合、それは単なる 0 と 1 です。各ビットを実際のビットに格納する場合、各 2 進数はバイトの 1/8 を使用しますが、テキストとして格納する場合、各ビットは 2 バイトを使用します。コンパクトに収納することで、1/16のメモリを使用します。

クラスは、データ内のビット パターンを検索する方法を処理する必要があります。これは難しい部分ですが、検索パターンの 8 つの異なるバージョンを作成し、1 バイト内の 8 つの可能な位置に一致するようにシフトすると、検索は文字列で検索するよりもさらに効率的になります。

編集：

ここから始めましょう...

public class BitList {

  private byte[] _data;
  private int _count;

  public BitList(string fileName) {
    using (FileStream s = File.OpenRead(fileName)) {
      _data = new byte[(s.Length + 7) / 8];
      _count = 0;
      int len;
      byte[] buffer = new byte[4096];
      while ((len = s.Read(buffer, 0, buffer.Length)) > 0) {
        for (int i = 0; i < len; i++) {
          switch (buffer[i]) {
            case 48: Add(0); break;
            case 49: Add(1); break;
          }
        }
      }
    }
  }

  public void Add(int bit) {
    _data[_count / 8] |= (byte)(bit << (_count % 8));
    _count++;
  }

  public int this[int index] {
    get {
      return (_data[index / 8] >> (index % 8)) & 1;
    }
  }

}

(注: このコードはテストされていませんが、少なくとも原則は理解しておく必要があります。)

于 2012-07-01T14:30:19.277 に答える
2

したがって、利用可能な情報を使用して、bitarray (初期サイズは file.length として) を宣言するだけで、ファイルを開いて、おそらく 4096 のチャンクで読み取り、これらの 4096 文字を調べます。

ループでは、単純な if text = 1 then set true を実行するか、false を設定するだけです

ファイルの最後に到達するまでこれを行うと、完全なものが巨大なbitarray変数になります

その時点から、パターンを見つける必要があります

于 2012-07-01T14:46:28.473 に答える
1

一度に 1 セグメントずつ、ビットの配列に変換するアプリケーションでテキスト ファイルを 1 回読み取り、バイナリで永続化された配列を含む新しいファイルを書き込みます。その後、実際のバイナリ ファイルを使用します。

検索するには、ターゲット パターンのビット マスクを作成し、ビット配列に沿って一度に 1 ビットずつスライドさせます。ビット単位の XOR を実行してビットを比較し、ビット単位の AND を実行して不要なビットを除外します。残っているものがゼロ以外の場合は、一致していません。

実験して、データ型間でパフォーマンスがどのように異なるかを判断してください。たとえば、バイトを使用して一度に 8 ビットを検索したり、整数を使用して一度に 32 ビットを検索したりできます。パターンが選択したデータ型よりも小さい場合、ビットごとの AND は余分なビットを破棄します。より大きなパターンは、最初の一致を見つけることによって処理され、次にパターンの次のセグメントとの一致が試行されます。

EDIT：役立つかもしれない最適化。たとえば、128 ビットを超える長いパターンがあるとします。パターンから 64 個の 64 ビット値の配列を作成します: ビット 0 ～ 63、1 ～ 64、2 ～ 65、...。次に、配列値のいずれかを pi 配列内の各長整数値に一致させようとすることで、高速パスを作成できます。一致が発生した場合は、必要に応じて一致する前のビットをチェックしてから、後続のビットをテストします。アイデアは、アラインされたメモリアクセスを最大限に活用することです。

パターンの長さによっては、値を再計算せずにシフトされたパターンのマッチングを簡単に続行できるように、シフトされた値の 2 次元配列を組み立てる価値がある場合があります。（マッチでターンを行い、同じシフトで次のパターン値を取得するだけです。）両端で未使用のビットをマスキングできるようにする必要があります。キャッシュを最大限に活用するために、最も頻繁な配列アクセスが最短ストライドで発生するようにする必要があることに注意してください。

BigInteger構造は、いじるのに役立つかもしれません。

于 2012-07-01T15:15:49.297 に答える
0

複数の異なる部分文字列を見つける速度が重要な場合は、より良い結果が得られるアプローチを次に示します。

テキストファイルに残します。それをスキャンして、ツリーの最上部に 0 ～ 9 の数字を保持する 10 個のノードがあるツリーを構築します。これらのノードのそれぞれは、10 個のノードを保持し、それらの数字のシーケンスと 0..9 が続きます。最上位は 0..9、次は 00..09、..、90..99 です。次は 000..009、... 990..999 です。

また、各レベルで、そのシーケンスに一致するすべてのオカレンスのテキスト ファイルにオフセットも格納します (子がない場合のみ)。子なしのルールは多くのメモリを節約することであり、定義により、すべての子ノードには親シーケンスが存在するオフセットが含まれます。つまり、「123456」を探している場合、「123456789」の出現が一致します。

これは膨大な量のメモリを使用しますが、ルックアップは非常に高速です。

追加:メモリ使用量を最小限に抑えるために実装できる多くのトリックがあります。数値をニブル (4 ビット) として格納します。ツリー内の要素のオブジェクトの代わりに、ベースからのオフセットを格納し、すべてを少数の大きな固定サイズの配列に配置します。ツリーを一度作成すると読み取り専用になるため、これを行うことができます。

于 2012-07-01T14:44:55.387 に答える
0

MSDNによると、メモリ内の String オブジェクトの最大サイズは 2 GB、つまり約 10 億文字です。そのサイズの文字列を割り当てるには、おそらく 64 ビット OS が必要です。数字のみを扱っているため、文字列以外のデータ型を使用してみてください。

于 2012-07-01T15:17:51.670 に答える