current community

your communities

more stack exchange communities

Stack Exchange
tour help
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.
up vote 4 down vote favorite

I am writing a text classifier, and in order to do so, I need TF/IDF values per every word of my single text.

Then I need to use the cosine similarity:

$$similarity = cos(\theta) = \dfrac{A \cdot B}{\lVert A \lVert \lVert B \lVert} = \dfrac{\overset{n}{\underset{i=1}{\LARGE\Sigma}}A_i \times B_i}{\sqrt{ \overset{n}{\underset{i=1}{\LARGE\Sigma}}(A_i)^2} \times \sqrt{\overset{n}{\underset{i=1}{\LARGE\Sigma}}(B_i)^2}}$$

This requires processing of a big data storage (all of the texts that already exists in my database). The problem is that my code is doing his job for about 2 hours (quite too long) and breaks giving me message that I have run out of memory. I think that the main method might be very, very unoptimised. 

public static void CreateCategoryClasses()
{
    deserializeClasses = Deserialize();
    howManyClasses = deserializeClasses.Count;
    ewhClass = new EventWaitHandle[howManyClasses];

    for (var i = 0; i < 5; ++i)
    {
        categoryClasses.Enqueue(new ConcurrentDictionary<string, double>());
        result.Enqueue(new ConcurrentDictionary<string, double>());
    }
    WaitCallback threadMethod = ParseCategories;
    ThreadPool.SetMaxThreads(howManyStudents, howManyClasses);

    for (var i = 0; i < howManyClasses; ++i)
    {
        ewhClass[i] = new EventWaitHandle(false, EventResetMode.AutoReset);
        ThreadPool.QueueUserWorkItem(threadMethod, i);
    }
    for (var i = 0; i < howManyClasses; ++i)
    {
        ewhClass[i].WaitOne();
    }
    threadMethod = AddIDF;
    ThreadPool.SetMaxThreads(howManyStudents, 5);

    for (var i = 0; i < 5; ++i)
    {
        ewhClass[i] = new EventWaitHandle(false, EventResetMode.AutoReset);
        ThreadPool.QueueUserWorkItem(threadMethod, i);
    }
    for (var i = 0; i < 5; ++i)
    {
        ewhClass[i].WaitOne();
    }

    List<List<SingleWords>> efekt = new List<List<SingleWords>>(5);

    for (int i = 0; i < 5; ++i)
    {
        foreach (var secondWord in categoryClasses.ToList()[i])
        {
            result[i].Add(new SingleWords(secondWord.Key, secondWord.Value));
        }
    }
    var xmls = new XmlSerializer(typeof(List<List<SingleWords>>));
    using (var sw = new StreamWriter(@"categoryClasses.xml"))
    {
        xmls.Serialize(sw, efekt);
    }
}

private static void AddIDF(object index)
{
    Console.WriteLine("Thread started with id:" + index + " and number: " + Thread.CurrentThread.ManagedThreadId);
    var i = index as int?;
    double sum;
    foreach (var word in categoryClasses.ElementAt(i.Value))
    {
        sum =
            deserializeClasses.Count(
                clas =>
                    clas.Bag.Where(x => clas.Category == ((Categories)i.Value).ToString())
                        .Contains(new Words(word.Key, 0, 0)));
        var temp = Convert.ToDouble(sum) /
                   Convert.ToDouble(
                       deserializeClasses.Count(x => x.Category == ((Categories)i.Value).ToString()));
        result.ElementAt(i.Value).AddOrUpdate(word.Key, temp, (s, d) => temp);
    }
    ewhClass[(i).Value].Set();
    Console.WriteLine("Thread ended with id:" + index + " and number: " + Thread.CurrentThread.ManagedThreadId);
}
share|improve this question
2  
"the main method seems very very unoptimized"... which main method? –  Vogel612 Jun 1 '14 at 19:50
    
I've pasted only two methods, only one of them calls the second one so the 'main method' refers to CreateCategoryClasses –  Cheslav Jun 1 '14 at 20:16
5  
I see assignments to undeclared variables in a static method, and my spidey senses are off the charts. Shared static state, in a multi-threaded program no less: brace yourself for more memory leaks and heisenbugs and various other goodness. –  abuzittin gillifirca Jun 2 '14 at 13:38
    
I would eliminate the use of xml and LINQ both. It is not that they are always inefficient. It is that you may waste a lot of time trying to optimize them. You need to use a profiler, and the quickest use of that will be with simple code. Also, abuzittin gillifirca's remarks are very important! –  Frank Hileman Sep 5 '14 at 16:07

2 Answers 2

up vote 7 down vote accepted

Edit in response to OP comment above:

CreateCategoryClasses may appear to be slow because of the WaitOne calls. You're essentially waiting waiting on either ParseCategories or AddIDF to complete before moving on. It would help if you could also post the ParseCategories method as well. Otherwise, you're just adding stuff to collections, which generally shouldn't perform too bad, except for some of my comments below.

Original answer:

Some of this is performance suggestions, some is just general advice...

  1. If you have one, run this through a performance profiler. This can point you directly to the lines that are using the most CPU time very quickly. Personally, I use ANTS from Red Gate. Another good one is DotTrace from JetBrains.

  2. Why is categoryClasses a ConcurrentQueue? As a general rule, a Queue is used for removing the items as you process them. If you just need to loop over a collection (possibly multiple times), a List<T> would be a better choice. This would also avoid the call to ToList() each time through your secondWord loop. ToList() will iterate through the entire collection every time you call it (granted it's only 5 element, but still...). This may also apply to result as well, depending on where else it might be used.

  3. You call ElementAt() every time through your foreach loop in AddIDF, even though i isn't changing. If you must use a ConcurrentQueue for categoryClasses, then ElementAt() is \$O(i)\$. If you can use a List, then it will be \$O(1)\$. You could save the current ConcurrentDictionary before the loop to avoid the repetitive indexing.

  4. String comparisons are slow compared to integers and enums (your Where() calls in AddIDF). If you changed Category to an enum or integer (or possibly add a second property for comparison purposes), that would improve the count performance.

  5. You pass an int into your AddIDF method, not an int?, so you can just do a direct cast to an int. This avoids the .Value property everywhere you access the index in AddIDF.

  6. sum is already a double, so there's no need to call Convert.ToDouble. Because sum is a double, temp will be a double, even if the result of Count is an int.

  7. What is this 5 I keep seeing? Typically it's good to assign this to a const value for clarity.

share|improve this answer
    
Welcome to Code Review! Nice answer, feel free to meet the site regulars in The 2nd Monitor anytime! –  Mat's Mug Jun 1 '14 at 20:23
up vote 4 down vote

You're doing a lot of needless work in AddIDF:

  • ((Categories)i.Value).ToString() can be computed just once per function call.

  • new Words(word.Key, 0, 0) can be computed just once per iteration.

  • The denominator of temp can be lifted out of the loop.

The body of the expression x => clas.Category == ((Categories)i.Value).ToString() does not refer to x, so you're iterating through every element of the bag, which you don't need to do.

The call to Contains is on a sequence, not the collection clas.Bag, making it an \$O(n)\$ operation, while if clas.Bag is a HashSet, it would be \$O(1)\$.

Putting that together would look like this:

private static void AddIDF(object index)
{
    var i = (index as int?).Value;
    var category = ((Categories)i).ToString();
    var bags = deserializeClasses.Where(clas => clas.Category == category)
        .Select(clas => clas.Bag)
        .ToList();
    var denominator = Convert.ToDouble(bags.Count);

    foreach (var word in categoryClasses.ElementAt(i))
    {
        var key = word.Key;
        var target = new Words(key, 0, 0);
        var sum = bags.Count(bag => bag.Contains(target));
        var temp = sum / denominator;

        result.ElementAt(i)
            .AddOrUpdate(key, temp, (s, d) => temp);
    }

    ewhClass[i].Set();
}

I added some classes to make your function compile, and have put up a gist here: https://gist.github.com/mjolka/7f5b6055028285e2eb68. On my machine, for a Release build running under Mono 3.4.0, the timings for the different implementations of AddIDF are ~ 00:00:00.6 vs ~ 00:01:26.4.

Other notes:

  • Posting a minimal complete code sample would greatly help -- one that readers can drop into LINQPad or similar and run.

  • Class names are usually singular, e.g. SingleWord instead of SingleWords, and Category instead of Categories.

share|improve this answer

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.