Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Assume that we have a .txt file that has one word per line. Find out the word that occurs the most.

Here's what I was able to write (I used array of strings instead of a file in this example):

string[] source = { "test1", "test2", "test3", "test4", "test1", "test1", "test3" };
Dictionary<string, int> dic = source.Distinct().ToDictionary(p => p, p => 0);
var keys = new List<string>(dic.Keys);
foreach (string key in keys)
{
  dic[key]=source.Count(f => f == key);
}
int max = dic.Values.Max();
foreach (KeyValuePair<string, int> kvp in dic)
{
    if (kvp.Value == max)
    {
        Console.WriteLine(kvp.Key + " " + max);
        break;
    }
}

Questions:

  1. Can this be done better and more efficient way (speed/ memory)?
  2. What if file size is 10GB. How would you do it differently from my approach?
share|improve this question
    
In addition to other answers listed here, if you have a 10GB file, then you should consider parallel computations. The trick is to keep reading the file sequentially, but hand off the work in reasonable sized chunks to several threads. stackoverflow.com/questions/9314042/… If a single-threaded approach works fast enough for you, then do not bother with the extra complexity, of course. –  Leonid Apr 28 '12 at 15:49
3  
cat file.txt | sort | uniq -c | sort -rn | head -n1 –  Quentin Pradet May 1 '12 at 14:56
add comment

5 Answers 5

up vote 6 down vote accepted

You are trying to count each key separately. This means you need to iterate through the entire list to count each key. Instead you can keep a running total of your key's and only have to iterate through your list once:

string[] source = { "test1", "test2", "test3", "test4", "test1", "test1", "test3" };
Dictionary<string, int> dic = new Dictionary<string, int>();

foreach(string s in source){
    if(dic.Keys.Contains(s))
         dic[s] = dic[s]++;
    else
       dic.Add(s, 1);
}

EDIT: I did not include getting the max value as what you have works for that and has already been re-written by thantos

share|improve this answer
    
+1 for efficiency and simplicity in your code. Contains is a much more efficient method than operations on the values collection of a Dictionary. Plus it doesn't have those notoriously overused lambda expressions. –  maple_shaft Apr 27 '12 at 19:06
3  
You can avoid reading the dictionary twice by using TryGetValue(), but the gain is probably going to be minuscule when compared with reading the file. –  svick Apr 27 '12 at 19:23
    
True I hadnt thought of that with the short time I threw it together. I was more focused on not iterating the entire list to get each count(which would result in terrible performance) –  jzworkman Apr 27 '12 at 19:27
2  
You also should consider casting all words to lower case, because it won't work if the case of the words are different. Moreover, the initial input requires a preprocessing via stemming, if you want words like "cat" and cats to be counted as the same word - en.wikipedia.org/wiki/Stemming –  Sergei Apr 28 '12 at 6:37
add comment

I wrote this little business back in 2009. It counts unique words in a file (separated by certain delimiters) and spits them out in frequency order, highest to lowest.

    private static readonly char[] delimiters = { ' ', '.', ',', ';', '\'', '-', ':', '!', '?', '(', ')', '<', '>', '=', '*', '/', '[', ']', '{', '}', '\\', '"', '\r', '\n' };

    private static readonly Func<string, string> theWord = Word;

    private static readonly Func<IGrouping<string, string>, KeyValuePair<string, int>> theNewWordCount =
        NewWordCount;

    private static readonly Func<KeyValuePair<string, int>, int> theCount = Count;

    private static void Main(string[] args)
    {
        foreach (var wordCount in File.ReadAllText(args.Length > 0 ? args[0] : @"C:\Test\WarAndPeace.txt")
            .Split(delimiters, StringSplitOptions.RemoveEmptyEntries)
            .AsParallel()
            .GroupBy(theWord, StringComparer.OrdinalIgnoreCase)
            .Select(theNewWordCount)
            .OrderByDescending(theCount))
        {
            Console.WriteLine(
                "Word: \""
                + wordCount.Key
                + "\" Count: "
                + wordCount.Value);
        }

        Console.ReadLine();
    }

    private static string Word(string word)
    {
        return word;
    }

    private static KeyValuePair<string, int> NewWordCount(IGrouping<string, string> wordCount)
    {
        return new KeyValuePair<string, int>(wordCount.Key, wordCount.Count());
    }

    private static int Count(KeyValuePair<string, int> wordCount)
    {
        return wordCount.Value;
    }
share|improve this answer
add comment

I think it is worth mentioning that for large data a different approach could be used, since keeping exact frequency counts of words is too time consuming.

Streaming Algorithms like "Count Sketch" makes a single pass over the data, uses low amount of space, and based on the amount of space you allocate to it, can guarantee to get the Maximum Frequency Word with say 99% probability.

Algorithms like these are used every day in routers to approximate which IP addresses are requested the most frequently, given that routers do not have enough memory to store everything it sees and only sees each IP address once.

For large data, I would recommend this approach.

Not sure if 10 GB of text counts as big data for this problem though, however if every word in the file was unique (except one word which occurs twice), you probably don't want to try storing them all in a Dictionary :p.

As an aside,

Multi-threading may be able to help give a speed-up, although pulling data from a single .txt file seems intrinsically IO bound. It seems possible to pre-partition the .txt file into parts for each thread to process independently, using "unsafe" code with pointers directly at the partition locations in memory, and writing the line parsing yourself from the bit representations of chars.

I doubt the above would be worth doing in C#, since you might as well manage memory as well using C or another low-level language for that extra gain in speed-up.

Multiple threads would exhibit higher speed-ups on certain processors like the intel i7 which has 3 channels to memory, and this is a highly IO dependent task.

If it happened to be hundreds of thousands of 10 GB .txt files across a cluster of computers, I would consider using an approach utilizing MapReduce on a distributed file system.

share|improve this answer
add comment

Can this be done better and more efficient way (speed/ memory)?

Your code iterates once over the input, Distinct internally creates a set, of which you then create a dictionary (redundant work).

You then copy the keys of the dictionary to a list to iterate over them (redundant work).

You then iterate over all keys, and for each, iterate over the input again (redundant work).

Then you iterate over the dictionary again (redundant work).

This code has almost more redundant operations than lines.

This can be vastly simplified, both conceptually and concerning runtime. Unfortunately, the resulting code will be slightly longer and still contain one redundancy since C#’s dictionary implementation has a fatal error in its interface: it doesn’t allow querying and updating a value at the same time.

string[] source = { "test1", "test2", "test3", "test4", "test1", "test1", "test3" };

var frequencies = new Dictionary<string, int>();
string highestWord = null;
int highestFreq = 0;

foreach (string word in source) {
    int freq;
    frequencies.TryGetValue(word, out freq);
    freq += 1;

    if (freq > highestFreq) {
        highestFreq = freq;
        highestWord = word;
    }
    frequencies[word] = freq;
}

Console.WriteLine(highestWord);

What if file size is 10GB. How would you do it differently from my approach?

If you expect comparably few different word (say, less than 100.000), use the same approach as above, just don’t load the whole input at once, instead, do it in chunks. You can also process chunks in parallel, with each thread working on its own dictionary, and afterwards you merge those dictionaries in one final step.

If you expect that almost every word in the input is distinct (not realistic with natural language words, but if your “words” are generated strings, this could happen) then the frequency dictionary could become quite large in size and might require special treatment. But this is an extreme scenario.

share|improve this answer
add comment

You could use a collection type which is called Bag. A bag counts the items added to it. Here is a suggestion of how a bag can be implemented. (It is not necessarily feature-complete; however you get the idea.)

public class Bag<T>
{
    private Dictionary<T, int> _dict = new Dictionary<T, int>();

    public void Add(T item)
    {
        int count;
        if (_dict.TryGetValue(item, out count)) {
            _dict[item] = count + 1;
        } else {
            _dict.Add(item, 1);
        }
    }

    public bool Remove(T item)
    {
        int count;
        if (_dict.TryGetValue(item, out count)) {
            if (count == 1) {
                _dict.Remove(item);
            } else {
                _dict[item] = count - 1;
            }
            return true;
        }
        return false;
    }

    public IEnumerator<KeyValuePair<T, int>> GetEnumerator()
    {
        return _dict.GetEnumerator();
    }

    public int CountOf(T item)
    {
        int count;
        _dict.TryGetValue(item, out count);
        return count;
    }
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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