大文本文件中的字频率

Question

我正在尝试读取一个大文本文件并输出其中的不同单词及其计数.到目前为止,我已经尝试了几次尝试,这是迄今为止我提出的最快的解决方案.

private static readonly char[] separators = { ' ' };

public IDictionary<string, int> Parse(string path)
{
    var wordCount = new Dictionary<string, int>();

    using (var fileStream = File.Open(path, FileMode.Open, FileAccess.Read))
    using (var streamReader = new StreamReader(fileStream))
    {
        string line;
        while ((line = streamReader.ReadLine()) != null)
        {
            var words = line.Split(separators, StringSplitOptions.RemoveEmptyEntries);

            foreach (var word in words)
            {
                if (wordCount.ContainsKey(word))
                {
                    wordCount[word] = wordCount[word] + 1;
                }
                else
                {
                    wordCount.Add(word, 1);
                }
            }
        }
    }

    return wordCount;
}

我如何衡量我的解决方案

我有一个200MB的文本,我知道(通过文本编辑器)的总字数.我正在使用Stopwatch class和计算单词以确保准确性并测量所花费的时间.到目前为止,大约需要9秒钟.

其他尝试

• 我试图利用多线程通过TPL库拆分工作.这涉及批处理多行,将批处理行的处理发送到单独的任务并将读/写操作锁定在字典中.然而,这似乎并没有为我提供任何性能改进.
• 花了大约30秒.我怀疑读取/写入字典的锁定成本太高,无法获得任何性能.
• 我也查看了ConcurrentDictionary类型,但该 AddOrUpdate方法确实需要调用代码来处理我的理解同步,并且没有带来性能优势.

我相信有更快的方法来实现这一目标!是否有更好的数据结构可用于此问题？

欢迎对我的解决方案提出任何建议/批评 - 尝试在这里学习和改进!

干杯.

更新:这是我正在使用的测试文件的链接.

Answer 1

我能给出的最佳答案是衡量,衡量和衡量.Stopwatch很高兴能够感受到花费时间的地方,但最终你最终会用它来大量喷洒代码,否则你将不得不为此找到更好的工具.我建议为此获得一个专用的探查器工具,有很多可用于C#和.NET.

我已经设法通过三个步骤削减了总运行时间的43%.

首先,我测量了你的代码并得到了这个:

这似乎表明我们可以尝试打击两个热点:

1. 字符串拆分(SplitInternal)
2. 字典维护(FindEntry,Insert,get_Item)

花费的最后一段时间是阅读文件,我真的怀疑我们可以通过改变代码的这一部分来获得更多.这里的另一个答案提到使用特定的缓冲区,我试过这个并且无法获得可测量的差异.

第一个,字符串拆分,有点简单,但涉及将一个非常简单的调用重写为string.Split更多的代码.处理一行的循环我重写了这个:

while ((line = streamReader.ReadLine()) != null)
{
    int lastPos = 0;
    for (int index = 0; index <= line.Length; index++)
    {
        if (index == line.Length || line[index] == ' ')
        {
            if (lastPos < index)
            {
                string word = line.Substring(lastPos, index - lastPos);
                // process word here
            }
            lastPos = index + 1;
        }
    }
}

然后我重写了一个单词的处理:

int currentCount;
wordCount.TryGetValue(word, out currentCount);
wordCount[word] = currentCount + 1;

这取决于以下事实:

1. TryGetValue 比检查单词是否存在然后检索其当前计数便宜
2. 如果TryGetValue无法获取值(键不存在),那么它会将currentCount变量初始化为其默认值,即0.这意味着我们实际上不需要检查该单词是否确实存在.
3. 我们可以通过索引器向字典添加新单词(它将覆盖现有值或向字典添加新键+值)

最终循环因此如下所示:

while ((line = streamReader.ReadLine()) != null)
{
    int lastPos = 0;
    for (int index = 0; index <= line.Length; index++)
    {
        if (index == line.Length || line[index] == ' ')
        {
            if (lastPos < index)
            {
                string word = line.Substring(lastPos, index - lastPos);
                int currentCount;
                wordCount.TryGetValue(word, out currentCount);
                wordCount[word] = currentCount + 1;
            }
            lastPos = index + 1;
        }
    }
}

新的测量表明:

细节:

1. 我们从6876ms到5013ms
2. 我们浪费了时间SplitInternal,FindEntry和get_Item
3. 我们花了很多时间在TryGetValue和Substring

这里有不同的细节:

正如您所看到的,我们失去了比获得新时间更多的时间,这导致了净改善.

但是,我们可以做得更好.我们在这里进行2次字典查找,包括计算单词的哈希码,并将其与字典中的键进行比较.第一次查找是其中的一部分,TryGetValue第二次查找是其中的一部分wordCount[word] = ....

我们可以通过在字典中创建更智能的数据结构来删除第二个字典查找,代价是使用更多堆内存.

我们可以使用Xanatos将对象存储在对象中的技巧,以便我们可以删除第二个字典查找:

public class WordCount
{
    public int Count;
}

...

var wordCount = new Dictionary<string, WordCount>();

...

string word = line.Substring(lastPos, index - lastPos);
WordCount currentCount;
if (!wordCount.TryGetValue(word, out currentCount))
    wordCount[word] = currentCount = new WordCount();
currentCount.Count++;

这只会从字典中检索计数,增加1次额外出现不涉及字典.该方法的结果也将更改为将此WordCount类型作为字典的一部分而不是仅返回int.

净结果:节省约43%.

最后一段代码:

public class WordCount
{
    public int Count;
}

public static IDictionary<string, WordCount> Parse(string path)
{
    var wordCount = new Dictionary<string, WordCount>();

    using (var fileStream = new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.None, 65536))
    using (var streamReader = new StreamReader(fileStream, Encoding.Default, false, 65536))
    {
        string line;
        while ((line = streamReader.ReadLine()) != null)
        {
            int lastPos = 0;
            for (int index = 0; index <= line.Length; index++)
            {
                if (index == line.Length || line[index] == ' ')
                {
                    if (lastPos < index)
                    {
                        string word = line.Substring(lastPos, index - lastPos);
                        WordCount currentCount;
                        if (!wordCount.TryGetValue(word, out currentCount))
                            wordCount[word] = currentCount = new WordCount();
                        currentCount.Count++;
                    }
                    lastPos = index + 1;
                }
            }
        }
    }

    return wordCount;
}

Answer 2

你的方法似乎符合大多数人的解决方法.你是正确的注意到使用多线程并没有带来任何显着的好处,因为瓶颈很可能是IO绑定的,无论你有什么样的硬件,你读取的速度都比硬件支持的速度快.

如果你真的在寻找速度改进(我怀疑你会得到任何改进),你可以尝试实现一个生产者 - 消费者模式,其中一个线程读取文件而其他线程处理这些行(可能然后并行化检查单词中的单词)线).这里的折衷是你要添加更复杂的代码以换取边际改进(只有基准测试可以确定这一点).

http://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem

编辑:还看看ConcurrentDictionary

Answer 3

我已经获得了很多(从一个200mb的文件上25秒到20秒)只是改变:

int cnt;

if (wordCount.TryGetValue(word, out cnt))
{
    wordCount[word] = cnt + 1;
}
else
....

基于ConcurrentDictionary<>和Parallel.ForEach(使用IEnumerable<>重载)的变体.注意,代替使用int,我使用的是InterlockedInt使用Interlocked.Increment来增加自身.作为参考类型,它可以正常使用ConcurrentDictionary<>.GetOrAdd...

public class InterlockedInt
{
    private int cnt;

    public int Cnt
    {
        get
        {
            return cnt;
        }
    }

    public void Increment()
    {
        Interlocked.Increment(ref cnt);
    }
}

public static IDictionary<string, InterlockedInt> Parse(string path)
{
    var wordCount = new ConcurrentDictionary<string, InterlockedInt>();

    Action<string> action = line2 =>
    {
        var words = line2.Split(separators, StringSplitOptions.RemoveEmptyEntries);

        foreach (var word in words)
        {
            wordCount.GetOrAdd(word, x => new InterlockedInt()).Increment();
        }
    };

    IEnumerable<string> lines = File.ReadLines(path);
    Parallel.ForEach(lines, action);

    return wordCount;
}

请注意,使用Parallel.ForEach比使用每个物理核心直接使用一个线程效率低(您可以在历史记录中看到).虽然两种解决方案在我的PC上只需不到10秒的"挂机"时钟,但Parallel.ForEach在33秒的Thread解决方案中使用55秒的CPU时间.

还有另一种技巧,价值约为5-10%:

public static IEnumerable<T[]> ToBlock<T>(IEnumerable<T> source, int num)
{
    var array = new T[num];
    int cnt = 0;

    foreach (T row in source)
    {
        array[cnt] = row;
        cnt++;

        if (cnt == num)
        {
            yield return array;
            array = new T[num];
            cnt = 0;
        }
    }

    if (cnt != 0)
    {
        Array.Resize(ref array, cnt);
        yield return array;
    }
}

您将数据包中的行"分组"(选择10到100之间的数字),以便减少线程内通信.然后工人必须对foreach收到的行进行处理.