我能给出的最好的简短答案是测量、测量、测量。Stopwatch
很高兴能了解时间花在哪里,但最终你会用它来散布大量的代码,或者你将不得不为此目的找到一个更好的工具。我建议为此使用一个专用的分析器工具,有许多可用于 C# 和 .NET。
我通过三个步骤成功地减少了大约 43% 的总运行时间。
首先我测量了你的代码并得到了这个:
这似乎表明这里有两个我们可以尝试解决的热点:
- 字符串分割(SplitInternal)
- 字典维护(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;
这取决于以下事实:
-
TryGetValue
比检查单词是否存在然后检索其当前计数便宜
- If
TryGetValue
获取值失败(key不存在)则初始化currentCount
此处的变量为其默认值,即 0。这意味着我们实际上不需要检查该单词是否确实存在。
- 我们可以通过索引器向字典添加新单词(它将覆盖现有值或向字典添加新的键+值)
最终的循环如下所示:
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;
}
}
}
新的测量表明:
Details:
- 我们从 6876 毫秒变为 5013 毫秒
- 我们失去了花在
SplitInternal
, FindEntry
and get_Item
- 我们赢得了花在
TryGetValue
and Substring
以下是差异细节:
正如您所看到的,我们损失的时间比获得的新时间多,这导致了净改进。
然而,我们可以做得更好。我们在这里进行两次字典查找,其中涉及计算单词的哈希码,并将其与字典中的键进行比较。第一个查找是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;
}