4
\$\begingroup\$

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

            }
        }
\$\endgroup\$
  • \$\begingroup\$ sim is set to 0 in every iteration of the middle loop; isn't sim supposed to be the output value? \$\endgroup\$ – S.L. Barth - Reinstate Monica Oct 14 '11 at 8:56
  • \$\begingroup\$ Can you post the declaration of dict? Seeing the type will make it easier to follow. I am guessing its a Dictionary<string, Dictionary<string, double>>? Also what are the keys of the inner dictionary? And are most of them common to all words or present on only a few words each? \$\endgroup\$ – finnw Oct 14 '11 at 9:28
  • \$\begingroup\$ @S.L.Barth yes,it is. but it take too much time to find all cosines between every posible pair of 500k strings and their definitions. \$\endgroup\$ – Stanislav O Chernykh Oct 14 '11 at 15:11
  • \$\begingroup\$ @finnw SortedDictionary<string, SortedDictionary<string, double>> dict = new SortedDictionary<string, SortedDictionary<string, double>>(); \$\endgroup\$ – Stanislav O Chernykh Oct 14 '11 at 15:12
  • \$\begingroup\$ @finnw sparse matrix is used to construct term-document matrixlink ,where words ( as documents) are used as keys for outer SortedDictionary and unique terms in word definitions(as terms).unique terms are keys for inner SortedDictionary \$\endgroup\$ – Stanislav O Chernykh Oct 14 '11 at 16:56
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for your comment. Sim is used to find k nearest neigbors. maybe i can reduce amount of calculations because of sim(word_i,word_j)=sim(word_j,word_i). how can i modify this algorithm from sequential to run in parallel? \$\endgroup\$ – Stanislav O Chernykh Oct 14 '11 at 15:02
1
\$\begingroup\$

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.

\$\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.