logo标签列表

在C#中高效解析大型文本文件

c#algorithmparsingtext-processing
6

我需要读取一个大的以空格分隔的文本文件并计算文件中每个代码实例的数量。基本上，这些是运行成千上万次实验的结果。系统会输出一个看起来像这样的文本文件：

A7PS A8PN A6PP23 ...

有数十万条这样的条目，我需要计算每个代码的出现次数。
我想我可以打开一个StreamReader，逐行处理，以空格字符为分隔符。查看代码是否已经被遇到，并将该代码的计数加1。然而，考虑到数据的大小，这可能相当天真。
有人知道处理这种处理的有效算法吗？
更新：
好吧，大家的共识似乎是我的方法是正确的
我想听听的是 - 哪个更有效率 - StreamReader. TextReader, BinaryReader 什么是最好的结构来存储我的结果字典？HashTable、SortedList、HybridDictionary
如果文件中没有换行符（我还没有收到示例），那么仅仅在空格上分割整个文件是否效率低下？
基本上，我正在努力使它尽可能高效。
再次感谢。
7
可以先试一下，检查时间是否合适，如果不合适再问一次。 - RvdK
老实说，你的解决方案似乎还不错，在任何情况下，你都必须查看整个文件以计算不同代码的出现次数。你可以优化检查某个代码是否被找到的方式，例如使用集合或映射。 - tchrikch
1
如果您要按行读取它，请确保文件实际上包含多于一行 :) - Constantin
1
数据是在不同的行上吗？还是整个文件都在一行上？ - Binary Worrier
我将使用StreamReader并读取字符块（如我解决方案所述）。读取字节（二进制）的问题在于，您需要在其上处理编码 - 以从字节中获取字符。因此，除非您确定只处理ascii集，否则读取字节不是很有吸引力 - 更不用说不能在字节数组上使用字符串函数了。 - VinayC
8个回答
5

你的方法看起来不错。

  1. 逐行读取
  2. 按空格拆分每一行
  3. 如果字典中不存在该记录，则添加一个记录，如果存在，则将值加1
这取决于每行有多长。在长行上，string.split可能会成为瓶颈。 - jgauffin
如果没有换行符呢？ - chriszero
4
我认为您的方法基本正确，但可以进行并行处理。建议使用多个线程或任务（在.NET 4中）来解析文件的每个部分/块。 此外，不要逐行读取，而是读取一块字节 - 这将从磁盘IO角度提供更好的性能。
以下是解决方案概述：
1. 假设我们将处理M个块，每个块的大小为N个字符（因为我们想限制所需的内存量和使用的线程数）。 2. 分配N*M个字符缓冲区。我们将循环使用此缓冲区。 3. 使用生产者-消费者模式。生产者将填充缓冲区。它将尝试在块边界附近找到单词边界（即每个第N个字符附近）。因此，我们将具有大约N个字符的M个块，并且在缓冲区内具有起始和结束索引。 4. 现在启动M个工作线程以处理每个块。每个工作线程将使用自己的字典计算单词计数 - 这将消除线程同步的需要。 5. 将在迭代结束时聚合结果。必须重复该过程，直到读取整个文件为止。
当然，我假设这是针对非常大的文件采用的方法。我可能会在缓冲区中使用旧式字符查找来查找单词边界，将查找代码标记为不安全以避免边界检查。
但请确保不要拆分令牌。 - Scoregraphic
当然 - 这是一个有点困难的解决方案。我会编辑我的回复来概述它。 - VinayC
1

我同意PoweRoy的评论：为什么不试一下呢？也许在实践中没有问题。

如果你需要其他东西，可以尝试编写一些代码，它接受一个Stream并返回一个IEnumerable<string>。它将逐个从输入中读取字符 - 如果您需要缓冲以提高效率，您可以始终将您实际提供给此代码的FileStream包装在BufferStream中 - 并检查它是否是空格（或可能是EOL？）。如果不是，则将字符添加到字符串缓冲区（也许是StringBuilder？），但如果是，则yield return当前字符串缓冲区并清除它。

之后，您只需对文件内容调用此代码的结果进行foreach，就可以逐个获取文件中的代码。

然后，您可以使用某种数据结构，例如Dictionary<string,int>来计算每个代码的出现次数，将代码作为键，计数作为值。但是，如果您按行读取文件并使用string.Split将其拆分为空格，则此步骤将相同。

1
如果你想尝试一些不同的东西，你可以尝试使用 BinaryReader，逐字节读取流，并在遇到空格时将计数器增加一。
1
十万条记录并不算太多。我会使用一个 Dictionary<string,int> 来存储键和计数。
但如果遇到内存问题，为什么不使用数据库，即使是像 SQL Compact 或 SQLite 这样的数据库。创建一个包含键和计数的记录的表。
将数据保留在内存中对于小量数据来说是最快的，但当您达到计算机内存限制时，数据库将更快。
0
    static string LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static string NUMBERS = "1234567890";
    static Random rdGen = new Random();
    static Dictionary<string, int> myDic = new Dictionary<string, int>();
    static void WriteTest(int max)
    {
        myDic = new Dictionary<string, int>();
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < max; i++)
        {
            string code = LETTERS[rdGen.Next(0, 26)].ToString() + NUMBERS[rdGen.Next(0, 10)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString();
            if (myDic.ContainsKey(code)) myDic[code]++;
            else
            {
                myDic[code] = 1;
            }
        }
        sw.Stop();
        Console.WriteLine(max.ToString() + " itérations : " + sw.ElapsedMilliseconds.ToString());

    }

WriteTest(10000000); // 耗时7.5秒。

对我来说看起来相当高效。

0

在非常基本的层面上，我会从一个Dictionary<string, int>开始，通过对文档进行字符串分割并通过简单解析数据来计数。

string.split是一个相对强大的方法，如果我说错了，肯定有人会纠正我，它是建立在正则表达式之上的，比你在这种情况下需要的要复杂得多。

编写自己的分割方法可能比框架中的方法更可行。我建议首先使用现成的版本，如上所述，然后如果确定性能存在问题，则重写自己的版本。

Ian

在 Reflector 中查看 string.Split，显然没有正则表达式的魔法 - 它实际上使用指针迭代字符串，寻找分隔符。但是，你说得对，它可能过于复杂；MSDN 页面指出它可能会使用大量内存，建议改用 IndexOf 来查找分隔符。 - Samuel
“string.split ... was built to use regular expressions”我会感到非常惊讶，如果是这样的话，更有可能它会迭代整个字符串并尝试匹配传递给它的令牌。然而，我没有证据来支持这一点。 - Binary Worrier
0

如果没有其他限制，你必须像你描述的那样完整地阅读文件。

为了保存代码和数量，你应该使用一个数据结构，在O（log n）时间内允许搜索和插入。在C#中，SortedDictionary可以做到这一点。

编辑：

什么是存储我的结果字典的最佳结构？HashTable、SortedList、HybridDictionary

因为排序顺序似乎不是必需的，所以在大多数情况下，使用HybridDictionary或Dictionary会更好。SortedList可能是最慢的解决方案，因为插入需要O（n）时间。如果性能很重要，你应该对不同的实现进行一些测试。

我会选择使用 HybridDictionary（http://msdn.microsoft.com/en-us/library/system.collections.specialized.hybriddictionary.aspx），因为（至少我们）不知道集合中最终有多少元素。 - Scoregraphic
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接