2

我有一个 .txt 文件，其中包含 Pi 的 5 亿位二进制表示。

我需要在我的程序中使用它的字符串表示。我还需要能够在其中搜索子字符串等 - 换句话说，我需要能够将其视为正常大小的字符串。我会尝试找到很多子字符串，所以速度是必要的。

我最初的逻辑是简单地将字符串直接复制并粘贴到程序中并将其用作静态变量。但是我无法真正打开 .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 的二进制形式的表示，那么它只是零和一。如果将每个位存储在实际位中，则每个二进制数字使用 1/8 个字节，而如果将其存储为文本，则每个位将使用两个字节。通过以更紧凑的形式存储，您将使用 1/16 的内存。

然后，您的班级将不得不处理您如何在数据中搜索位模式。这将是棘手的部分，但如果您创建八个不同版本的搜索模式，并转移以匹配一个字节中的八个可能位置，则搜索可能比在字符串中搜索更有效。

编辑：

这是一个开始...

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

因此，有了可用的信息，我只需声明一个位数组（初始大小为 file.length），然后我会打开文件并按 4096 个块读取它，然后你会看到这 4096 个字符

在循环中，您只需执行一个简单的 if text = 1 then set true else set false

这样做直到你到达文件的末尾，然后你将完整的东西放入一个巨大的位数组变量中

从那时起，您只需要找到您的模式

于 2012-07-01T14:46:28.473 回答
1

在应用程序中读取文本文件一次，将其转换为位数组，一次一个段，然后写入一个包含以二进制形式保存的数组的新文件。此后，只需使用真正的二进制文件。

要进行搜索，您可以创建目标模式的位掩码并将其沿位数组滑动，一次一位，执行按位 XOR 比较位，按位 AND 过滤掉您不关心的位。如果剩下的任何东西都是非零的，那么你就没有匹配项。

试验以确定数据类型之间的性能有何不同。例如，您可以使用字节一次搜索 8 位，也可以使用整数一次搜索 32 位。如果您的模式小于所选数据类型，则按位与丢弃额外的位。较大的模式通过查找初始匹配来处理，然后尝试匹配模式的下一段，依此类推。

编辑：可能有帮助的优化。假设您有一个长的（例如大于 128 位的）模式。根据模式构造一个包含 64 个 64 位值的数组：位 0-63、1-64、2-65、...。然后，您可以快速通过尝试将任何数组值与 pi 数组中的每个长整数值匹配。在发生匹配的地方，根据需要检查任何先前的位是否匹配，然后测试后续位。这个想法是充分利用对齐的内存访问。

根据模式长度，组装一个二维移位值数组可能是值得的，这样您就可以轻松地继续匹配移位模式而无需重新计算值。（只需在比赛中转一圈，然后使用相同的移位拾取下一个模式值。）您需要允许在每一端屏蔽未使用的位。请注意，您希望以最短的步幅进行最频繁的数组访问，以充分利用缓存。

BigInteger结构在摆弄时可能会有一些用处。

于 2012-07-01T15:15:49.297 回答
0

如果查找多个不同子字符串的速度是关键，那么这里有一种方法可能会给您带来更好的结果。

将其保留在文本文件中。扫描它并构建一棵树，树的顶部有 10 个节点，其中包含数字 0..9。这些节点中的每一个都包含 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 位操作系统。由于您正在处理数字，因此仅尝试使用字符串以外的其他数据类型。

于 2012-07-01T15:17:51.670 回答