12
\$\begingroup\$

I've am trying to read a large text file and output the distinct words in it along with it's count. I've tried a couple of attempts so far, and this is by far the fastest solution I have come up with.

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;
}

How I am measuring my solution

I have a 200MB text, which I know the total word count for (via a text editor). I'm using the Stopwatch class and counting the words to ensure accuracy and measuring the time taken. So far, it is taking around 9 seconds.

Other attempts

I have tried to utilise multithreading to split out the work via the TPL library. This involved batching multiple lines, sending out the processing of the batch of lines to a separate task and locking the read/write operations in the dictionary. This however, seems to not provide me any performance improvements.

It took around 30 seconds. I suspect the locking to read/write to the dictionary is too costly to gain any performance.I am sure there is a faster way to achieve this! Any suggestions/criticisms to my solution are welcome.

Here is the link to the test file I'm using.

\$\endgroup\$
  • \$\begingroup\$ The only potential speed improvement I see is to rewrite without using Split, read relatively large chunks in a buffer, and tokenize. See also this related post: stackoverflow.com/questions/568968/… \$\endgroup\$ – janos May 16 '15 at 21:17
  • \$\begingroup\$ Interesting point. Will look into that. \$\endgroup\$ – Prabu May 16 '15 at 21:22
  • \$\begingroup\$ In an odd coincidence, I was considering writing a frequency parser for Italian. My question is not related to the performance aspect of your code but to the idea of word. How are you handling things like I'm vs. I am and noun vs. verb forms like I part and he parts (i.e. Moses) compared to 1 part and 3 parts? \$\endgroup\$ – Robert Kaucher May 16 '15 at 23:41
  • \$\begingroup\$ What kind of disk are you reading the file from? If for example it's an external USB2 disk then that's absolutely your bottle neck, and there isn't really anything you can do to get to the data any quicker. \$\endgroup\$ – Guffa May 17 '15 at 0:22
  • \$\begingroup\$ I'm working on top of an SSD at the moment. \$\endgroup\$ – Prabu May 17 '15 at 10:00
6
\$\begingroup\$

Let's set up code to benchmark different approaches. Every word counter will implement this interface:

interface IWordCounter
{
    IDictionary<string, int> CountWords(string path);
}

And here's our benchmark runner:

var wordCounters = new IWordCounter[]
{
    // ...
};

foreach (var wordCounter in wordCounters)
{
    GC.Collect();
    GC.WaitForPendingFinalizers();

    var sw = Stopwatch.StartNew();
    var wordCount = wordCounter.CountWords(path);
    sw.Stop();

    Console.WriteLine("{0}, {1} entries, {2}", wordCounter.GetType().Name, wordCount.Count, sw.Elapsed);
}

Timings were taken with a release build, on the test file provided, no debugger attached, on .NET 4.5.2.

Here's the original code:

class OriginalWordCounter : IWordCounter
{
    private static readonly char[] separators = { ' ' };

    public IDictionary<string, int> CountWords(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;
    }
}

On my machine, this takes about 8.2s.

We see an improvement using Heslacher's suggestion to use TryGet:

class OriginalTryGetWordCounter : IWordCounter
{
    private static readonly char[] separators = { ' ' };

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

        foreach (var line in File.ReadLines(path, Encoding.UTF8))
        {
            var words = line.Split(separators, StringSplitOptions.RemoveEmptyEntries);
            foreach (var word in words)
            {
                int count;
                wordCount.TryGetValue(word, out count);
                wordCount[word] = count + 1;
            }
        }

        return wordCount;
    }
}

This takes about 6.7s. (The use of File.ReadLines here doesn't seem to effect the timing, it's just a bit cleaner.)

We get another improvement with Parallel.ForEach together with a ConcurrentDictionary:

class ParallelWordCounter : IWordCounter
{
    public IDictionary<string, int> CountWords(string path)
    {
        var result = new ConcurrentDictionary<string, int>();
        Parallel.ForEach(File.ReadLines(path, Encoding.UTF8), line =>
        {
            var words = line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            foreach (var word in words)
            {
                result.AddOrUpdate(word, 1, (_, x) => x + 1);
            }
        });

        return result;
    }
}

This takes about 5.2s.

You might want to try some of the Parallel.Foreach overloads to see if you can get any further improvements, and remember to take these results with a grain of salt.

\$\endgroup\$
4
\$\begingroup\$

Instead of using the ContainsKey() method of the Dictionary<T,T> you should use the TryGetValue() method.

See: what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem

This would look like

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

Nowadys 200MB isn't that much so you should consider to read the whole file using any of the overloaded File.ReadAllLines() methods.

If you want to process each individual line but you don't want to wait until the whole file is read by using the mentioned ReadAllLines() method you can use the ReadLines() method which returns an IEnumerable<string>.

\$\endgroup\$
1
\$\begingroup\$

These are my thoughts on how the multi-threaded solution should look like. This is only a pseudo code, so don't take it literally.

A few notes:

  1. Most likely your bottleneck is reading from a file, so I would consider reading the largest possible bulk into memory and only then reading it line by line.
  2. Same goes to the processing task. You generally don't want to run more than 2-5 processes in parallel, so use a larger bulk of lines to process.
  3. I don't see any reason to use locking at all in my solution, since you don't access any shared resources while processing partial results and merging happens on the main thread.
  4. Since you mentioned you're using SSD, it might be worthwhile to research parallel read access to the file. You might get some performance gains there. If that is true, then combine the logic of reading and processing the bulk of lines in my solution.

public void ProccessFile(){
    var List<Dictionary<string,int>> partialResults = new List....

    while file has lines
    {
        var (bulkLines = file.readNLines()
        var t = Task.StartNew((ProcessLines(bulkLines));
        partialResults.add(t.Result);
    }

    Dictionary<string,int> wordFreq = MergeResults(partialResults);    
}
public Dictionary<string,int> MergeResults(partialResults)
{
    Dictionary<string,int> wordFreq = new Dictionary<string,int>();
    foreach(var p in partialResults){
        foreach(var key in p.Keys){
            var totalWordCnt;
            var partialWordCount = p[key];
            if(wordFreq.TryGetValue(key, out totalWordCnt)){
                wordFreq[key] = totalWordCnt + partialWordCount;
            }else{
                wordFreq.Add(key,partialWordCount );
            }
        }
    }

    return wordFreq;
}
\$\endgroup\$
0
\$\begingroup\$

Use a hashset to do the searching. It's faster. If you want just the unique instances of the word return the hashset instead. If you still want the counts I've left it the same. Might be more memory intensive but it should be faster.

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

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

        foreach(var line in File.ReadAllLines(path))
        {
            var words = line.Split(separators, StringSplitOptions.RemoveEmptyEntries);

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

        return wordCount;
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you think that a hash set is faster than a dictionary? \$\endgroup\$ – Guffa May 18 '15 at 10:14
  • \$\begingroup\$ @Guffa - Please see stackoverflow.com/questions/150750/hashset-vs-list-performance for a comparision. \$\endgroup\$ – d347hm4n May 18 '15 at 10:36
  • \$\begingroup\$ That's a comparison between lists and hash sets, not dictionaries and hash sets. The only thing in that question about dictionaries is a comment that mentions that dictionaries has values. \$\endgroup\$ – Guffa May 18 '15 at 11:54
0
\$\begingroup\$

You have a subtle problem with your code - different casing will mean two entries in your dictionary:

  • ankle
  • ankLe
  • Ankle

will all be counted seperately in your solution.

You can fix that by passing an IEqualityComparer<string> which ignores casing when you create your dictionary.

var wordCount = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

For what it's worth - I'm going to give you a Linq alternative which on my machine is comparable to your solution in terms of speed (on a smaller file though) with significantly less code.

var wordCounts =
        File.ReadLines(path)
            .SelectMany(l => l.Split(seperators, StringSplitOptions.RemoveEmptyEntries))
            .GroupBy(word => word.ToLower())
            .Select(group => new { Word = group.Key, Count = group.Count() })
            .ToDictionary(group => group.Word, group => group.Count);

Notice that I'm normalizing to lowercase.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.