4
\$\begingroup\$

I've been working on a project where I am importing a large document of documents and tokenizing each document. I then make a hashset of the tokens I have, and for each of these unique tokens I am looking to find their frequency in each of the documents I have. There are about 130000 documents total.

I've run the code and unfortunately, it's taking 150 hrs to run. Do you have any suggestions on improving my code?

This is my Tokenizer() function, which surprisingly works okay:

static private IEnumerable<string> Tokenizer(ref StreamReader sr, ref List<string> tokenz, ref List<string> stopwords)//function for tokenizing
{
    string line;
    var comparer = StringComparer.InvariantCultureIgnoreCase;
    var StopWordSet = new HashSet<string>(stopwords, comparer);
    List<string> tokens = new List<string>();//list of strings called tokens
    while ((line = sr.ReadLine()) != null)//as long as the streamreader has something
    {
        foreach (string item in line.Split(' '))//split amongst strings
        {
            if (item.StartsWith("<") & item.EndsWith(">"))
            {
                item.Trim();//trims the item of spaces
                if (item == "</DOC>")
                {
                    //return item;
                    tokenz.Add(item);//adds the doc tags for later separation use
                }
            }
            else
            {
                string newitem;
                item.Trim();//trims the item of spaces
                if (item != "")//ensures item is not blank
                {
                    newitem = Regex.Replace(item, @"[^A-Za-z0-9]+", "", RegexOptions.IgnoreCase);//regex allows us to ignore case and remove any special characters
                    string newitem2 = newitem.ToLower();
                    {
                        if (StopWordSet.Contains(newitem2))
                        {
                        }
                        else
                        {
                            tokenz.Add(newitem2);
                        }
                        //tokens.Add(newitem.ToLower());//makes all lower case
                    }
                }
            }
        }
    }
    return tokens;
}

The real issue is here:

static public void AddToDictionaryAndCount(ref int doccounter2, ref HashSet<string> MyLexicon, ref List<string> tokens, ref Dictionary<int, int> DocFreqCounter, ref Dictionary<string, Dictionary<int, int>> MyDictionary, ref Dictionary<int, int> DocWordCounter)
{
    foreach (string item in MyLexicon)
    {
        int counter = 0;
        int secondcounter = 0;
        int doccounter = 1;
        int termcounter = 0;
        while (counter <= tokens.LastIndexOf("</DOC>"))
        {
            if (tokens[counter] == "</DOC>")
            {
                DocFreqCounter.Add(doccounter, termcounter);
                if (doccounter2 < doccounter)
                {
                    DocWordCounter.Add(doccounter, (counter - secondcounter));
                    doccounter2++;
                }
                termcounter = 0;
                secondcounter = counter;
                doccounter++;
            }
            if (tokens[counter] == item)
            {
                termcounter++;
                //words.termCount = termcounter;
            }
            counter++;
        }
        MyDictionary.Add(item, new Dictionary<int, int>(DocFreqCounter));
        DocFreqCounter.Clear();
    }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Have you profiled your code? This should always be the first step when optimising. \$\endgroup\$ – Jack Aidley Feb 22 '13 at 11:34
  • \$\begingroup\$ Are you sure this is a CPU bound performance issue? \$\endgroup\$ – Dave Van den Eynde Feb 22 '13 at 12:14
  • 1
    \$\begingroup\$ @user2094139, in addition to profiling and identifying the problem, do go through suggestions provided by almaz. Not all of them may help improve performance, but would definitely help improve readability and maintainability. \$\endgroup\$ – publicgk Feb 22 '13 at 12:40
  • \$\begingroup\$ This smells like a high-memory-activity application. I wouldn't be surprised to find that your data structures are huge and that the paging subsystem is thrashing. Profiling is important to optimization. \$\endgroup\$ – Ross Patterson Feb 23 '13 at 14:28
9
\$\begingroup\$

Tokenizer method:

  • You use ref incorrectly, all reference types are always passed by reference, please read the MSDN or any other online resource to understand the ref
  • Your code doesn't follow naming conventions: local variables, parameters should be camelCased (e.g. StopWordSet)
  • use string.Split(new char[0], StringSplitOptions.RemoveEmptyEntries) overload to split on all whitespace characters and remove empty strings during tokenizing, rather than trimming result
  • strings are immutable, so the statement item.Trim() is useless unless you assign it to something
  • Tokenizer method always returns an empty list since tokens (not tokenz) is only intialized and not used. It looks like tokenz parameter is redundant and tokens variable should be used instead
  • To improve performance it might be better to change the type of stopwords parameter to ISet<string> and use it for matching, rather than create a new StopWordSet each time As a result you'll get a cleaner version of Tokenizer:

    private static IEnumerable<string> Tokenizer(StreamReader sr, ISet<string> stopwords)//function for tokenizing
    {
        string line;
        List<string> tokens = new List<string>();//list of strings called tokens
    
        while ((line = sr.ReadLine()) != null)//as long as the streamreader has something
        {
            foreach (string item in line.Split(new char[0], StringSplitOptions.RemoveEmptyEntries))//split amongst strings
            {
                if (item.StartsWith("<") & item.EndsWith(">"))
                {
                    if (item == "</DOC>")
                        tokens.Add(item); //adds the doc tags for later separation use
                }
                else
                {
                    string newitem = Regex.Replace(item, @"[^A-Za-z0-9]+", "", RegexOptions.IgnoreCase).ToLower();
                    if (!stopwords.Contains(newitem))
                        tokens.Add(newitem);
                }
            }
        }
        return tokens;
    }
    

Now let's look at the AddToDictionaryAndCount method:

  • naming conventions - do name your variables/parameters properly, it's absolutely not clear what is the difference between doccounter2 parameter, doccounter and secondcounter variables. Rename them to smth. like documentIndex, numberOfTermOccurances etc.
  • while (counter <= tokens.LastIndexOf("</DOC>")) is the killer, you're looking for "</DOC>" entry on each iteration. Cache the calculated value instead.
  • since you know the number of iterations and you always increment the index it's better to use for instead of while
  • not sure why you pass docFreqCounter as parameter, it looks like is being used as a local variable.

As to performance improvements (other than caching LastIndexOf) - currently you scan the through the tokens list for each and every item in myLexicon. Assuming that lexicon is built from tokens it would be much better to scan the tokens list only once, tracking which items you've already counted and where are the doc boundaries. Since you haven't provided the meaning of all parameters participating in this method it's hard to suggest a proper solution, but here is the first approximation:

public static Dictionary<string, Dictionary<int, int>> AddToDictionaryAndCount(List<string> tokens)
{
    var result = new Dictionary<string, Dictionary<int,int>>();
    var documentIndex = 0; //tracks the current document index

    var lastDocumentIndex = tokens.LastIndexOf("</DOC>");
    for (int i = 0; i <= lastDocumentIndex; i++)
    {
        var token = tokens[i];
        if (token == "</DOC>")
        {
            //finalize stats for the document. not sure what goes here.
            //add the logic corresponding to "doccounter2 < doccounter"
            documentIndex++;
            continue;
        }

        Dictionary<int, int> documentStats;
        if (!result.TryGetValue(token, out documentStats))
            documentStats = result[token] = new Dictionary<int, int>();

        documentStats[documentIndex]++;
    }
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks so much for the help almaz! I really appreciate it! :D \$\endgroup\$ – user2094139 Feb 24 '13 at 5:11
3
\$\begingroup\$

Since the tokens array doesn't change in the while loop, you can pull out the check for LastIndexOf so that it doesn't get called on every loop.

The only other thing I can suggest is grab a copy of dottrace performance (or ANTS performance) and see exactly where you have a problem.

\$\endgroup\$
  • \$\begingroup\$ Hey Robert, thanks for the reply. I'm not sure what you mean by actually pulling out the check, do you mean by storing the position where lastindexof</DOC> is and then substituting that in instead? \$\endgroup\$ – user2094139 Feb 22 '13 at 3:53
  • \$\begingroup\$ Yes that's what I meant: var loopTill = tokens.LastIndexOf("</DOC>")l; while (counter <= loopTill) \$\endgroup\$ – Robert Wagner Feb 22 '13 at 3:53
  • \$\begingroup\$ Thanks a lot! I'll use that for now, let me know if you possibly know of any other ways to optimize the code. I'll also look up the dottrace/ANTS performance programs you suggested and try that. \$\endgroup\$ – user2094139 Feb 22 '13 at 3:58
  • \$\begingroup\$ Just a heads up, WOW. I am thoroughly impressed at the speed that you just saved me, already. I tested it once and you already cut down around 3 seconds of time per addition to the dictionary. Thanks so much already! \$\endgroup\$ – user2094139 Feb 22 '13 at 4:00
  • 2
    \$\begingroup\$ As a side note, I think you misunderstand how the "ref" keyword works. You don't need them as you are not assigning new instances to the parameters \$\endgroup\$ – Robert Wagner Feb 22 '13 at 4:01
1
\$\begingroup\$

In addition to the great answers from almaz and Robert Wagner, I would do one more thing: make the Regex compiled and pull it out of the loop. So your original code looks like:

newitem = Regex.Replace(item, @"[^A-Za-z0-9]+", "", RegexOptions.IgnoreCase);//regex allows us to ignore case and remove any special characters
string newitem2 = newitem.ToLower();

and the modified code would look like:

private static readonly Regex replacer = new Regex(@"[^A-Za-z0-9]+", RegexOptions.Compiled | RegexOptions.IgnoreCase);

private static IEnumerable<string> Tokenizer(TextReader sr, ICollection<string> stopwords)
{
    // original codestuffs
    var newitem = replacer.Replace(item, string.Empty).ToLower();
    // more original codestuffs
}
\$\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.