Cosine simularity perfomance c#

Question

I am using 2 nested SortedDictionaries to construct sparse matrix

Here is the custom simularity(sim) function I wrote . Now it has O(n^2) complexity. I looking for suggestions to improve robustness and efficiency.Thanks for any help.

       double 
            a = 0, b = 0,
            sqrta = 0,
            sqrtb = 0,
            sim = 0; 

        foreach (var word_i in dict)
        {
            foreach (var word_j in dict)                   
            {
                if (word_i.Key == word_j.Key) continue;

                sim=a=b=sqrta=sqrtb=0;                                   
                foreach (var term in word_j.Value.Keys)
                {
                    if (word_i.Value.ContainsKey(term))
                    {
                        word_i.Value.TryGetValue(term,out a);
                        word_j.Value.TryGetValue(term,out b);
                        sim += a * b;
                        sqrta += Math.Pow(a,2);                                
                        sqrtb += Math.Pow(b,2);
                    }

                }

                sim /= Math.Sqrt(sqrta) * Math.Sqrt(sqrtb);              

            }
        }

Answer 1

As you are doing calculations on all values where the result depends on both loops, there isn't much that can be done about the complexity, at least not without knowing what you do with the result (which seems to be just discarded in the code shown).

There are some things that you can do in the innermost loop:

Instead of first using Contains and then get the value, you can use TryGetValue directly.

You know that term exists in the other collection, so you don't need TryGetValue for that one.

Squaring is done a lot faster by just multiplying instead of using Math.Pow.

if (word_i.Value.TryGetValue(term,out a)) {
  b = word_j.Value[term];
  sim += a * b;
  sqrta += a * a;                                
  sqrtb += b * b;
}

Answer 2

You can try this

public class Term
{
    public string Value { get; set; }
    public Dictionary<string, double> Definitions { get; set; }

    public Term(string value, Dictionary<string, double> definitions)
    {
        this.Value = value;
        this.Definitions = definitions;
    }
}

public class TermPair
{
    public Term Left { get; private set; }
    public Term Right { get; private set; }
    public double Similarity { get; private set; }

    public TermPair(Term left, Term right)
    {
        this.Left = left;
        this.Right = right;
    }

    public void CalculateSimilarity()
    {
        var sim = 0D;
        var sqrta = 0D;
        var sqrtb = 0D;

        var leftDefinitions = this.Left.Definitions;
        var rightDefinitions = this.Right.Definitions;

        foreach (var kv in leftDefinitions)
        {
            double a;
            var term = kv.Key;
            if (rightDefinitions.TryGetValue(term, out a))
            {
                var b = kv.Value;
                sim += a * b;
                sqrta += a * a;
                sqrtb += b * b;
            }
        }

        sim /= Math.Sqrt(sqrta) * Math.Sqrt(sqrtb);

        this.Similarity = sim;
    }
}

Use these classes like this:

List<Term> terms = ...

var idx = 0;
var totalTerms = terms.Count;
var pairs = new TermPair[((totalTerms - 1) * (totalTerms)) / 2];
for (var i = 0; i < totalTerms; i++)
{
    for (var j = 0; j < totalTerms; j++)
    {
        if (i > j)
        {
            pairs[idx++] = new TermPair(terms[i], terms[j]);
        }
    }
}

foreach (var pair in pairs.AsParallel())
{
    pair.CalculateSimilarity();
}

I don't know your scenario but I hope this help. You can experiment with SortedDictionary & Dictionary. BTW I'm not quite sure if TryGetValue is thread safe for reading from multiple threads.