7
\$\begingroup\$

I am working on a KNN implementation for sparse datasets (that I apply to text analysis). My points are represented by a Dictionary<string, double>, each key represents a word of the text and the value, its count or TFIDF.

I am using index inversion to reduce the number of distances to evaluate. However, evaluating the distance remains the bottleneck. It is represented in the following method:

    public static double Euclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
    {
        double distance = 0;
        foreach (KeyValuePair<string, double> kvp1 in sp1)
        {
            if (sp2.ContainsKey(kvp1.Key))
                distance += Math.Pow((kvp1.Value - sp2[kvp1.Key]), 2);
            else
                distance += Math.Pow((kvp1.Value), 2);
        }

        foreach (KeyValuePair<string, double> kvp2 in sp2)
            if (!sp1.ContainsKey(kvp2.Key))
                distance += Math.Pow((kvp2.Value), 2);

        return distance;
    }

How can I make it faster? Any help would be greatly appreciated.

I think I could reduce the time of evaluation using a Dictionary<int, double>, but I prefer to stick to strings, as it allows me to see at a glance what is going on (hashing words would compromise that).

The following yieled a 1.3~2.1x improvement (depending on the length of the input, but it is still not enough) :

    public static double FastEuclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
    {
        double distance = 0;
        foreach (KeyValuePair<string, double> kvp1 in sp1)
        {
            double sp1Value = kvp1.Value;

            if (sp2.ContainsKey(kvp1.Key))
            {
                double sp2Value = sp2[kvp1.Key],
                    diff = kvp1.Value - sp2[kvp1.Key];
                distance += diff * diff;
            }
            else
                distance += sp1Value * sp1Value;
        }
\$\endgroup\$
  • \$\begingroup\$ How often is this distance function being called? If you have an algorithm O(n^2) or worse in the number of nodes, then micro-optimizations shave off a small constant which lets you only run with slightly large problem sizes. This looks eerily similar to some force-directed layout code where the real bottleneck was dramatically handled by using quadtrees to efficiently find the closest nodes. \$\endgroup\$ – Rob Aug 6 '15 at 16:02
  • \$\begingroup\$ @Rob, thank you. So far, I am working with an inverted dictionary. Given a set of words (a new line in my data set that I want to predict) I can know how which lines share at least one word (I don't even consider the other lines). Calling m the number of lines I want to predict and k the average number of lines per set of word (roughly sqrt(n), but this is purely experimental), I am calling my distance m*sqrt(n) times. Can quadtrees help me ? \$\endgroup\$ – RUser4512 Aug 6 '15 at 16:30
  • \$\begingroup\$ To give a more general view of the input : the data set contains about 2 000 000 lines and there are around 25 000 possible words. My test set is roughly 100 000 lines long. Each line contains a dozen of different words. My current implementation runs in about 4 hours (the test elements are treated in parallel). Now I would like to cross-validate my models. Therefore, optimizations enabling me to gain a factor two are more than welcome (so that I can start my program at night and have a lot of results in the morning). \$\endgroup\$ – RUser4512 Aug 6 '15 at 16:44
  • \$\begingroup\$ quadtrees allow you to limit the distance you need to travel to find "nearby" neighbors. Without partitioning the space, you could literally be running thousands of times slower than is optimal. Imagine that the world is a 2D grid of 1 inch squares, and the world is 32inches squared in area, but you never need to search more than 4 inches away. If you run distance vs 8x as many nodes as you need, that's 64x as many calculations to compute all distances between all nodes. \$\endgroup\$ – Rob Aug 6 '15 at 17:15
  • \$\begingroup\$ also note that a quadtree is just a 2D generalization of the binary search. once data is 1D sorted, finding nearest neighbors is very efficient. read about z-order indexing and such. the solution stays conceptually pretty similar whether it's one dimensional or multi-dimensional; as it amounts to building an index once you get the data (pretty fast), and searching (almost instantaneous). \$\endgroup\$ – Rob Aug 6 '15 at 17:26
6
\$\begingroup\$

Calling ContainsKey() on a dictionary if you need to get the value later on should be replaced with TryGetValue() to reduce the processing time.

See: what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem

TryGetValue will be faster.

ContainsKey uses the same check as TryGetValue, which internally refers to the actual entry location. The Item property actually has nearly identical code functionality as TryGetValue, except that it will throw an exception instead of returning false.

Using ContainsKey followed by the item basically duplicates the lookup functionality, which is the bulk of the computation in this case


The next part to increase performance is to replace the call to Math.Pow() with multiplying the value by itself.

So instead of Math.Pow((kvp2.Value), 2) you should use kvp2.Value * kvp2.Value.

You just edited your question to do this but I will keep it in my review.


Using the said above will lead to

public static double Euclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
{
    double distance = 0;

    foreach (KeyValuePair<string, double> kvp1 in sp1)
    {
        double possibleValue = 0.0d;
        sp2.TryGetValue(kvp1.Key, out possibleValue);

        double currentValue = kvp1.Value - possibleValue;

        distance += currentValue * currentValue;
    }

    foreach (KeyValuePair<string, double> kvp2 in sp2)
    {
        if (!sp1.ContainsKey(kvp2.Key))
        {
            distance += kvp2.Value * kvp2.Value;
        }
    }
    return distance;
}

This

double possibleValue = 0.0d;
sp2.TryGetValue(kvp1.Key, out possibleValue);

double currentValue = kvp1.Value - possibleValue;

will store the value of the searched key inside possibleValue if the key is in the dictionary. If TryGetValue() does not succeed it will return default(T) which for a double is 0.0.


I have added braces {} for the for and the if which makes the code less error prone. I would like to encourage you to always use braces.

\$\endgroup\$
  • \$\begingroup\$ Thank you ! I was not familiar at all with the TryGetValue. And indeed, the main performance improvement came from replacing the Math.Pow... \$\endgroup\$ – RUser4512 Aug 6 '15 at 9:02
  • \$\begingroup\$ Regarding the curly braces, I agree with you. But as my team prefers to keep the code as short as possible, I took this habit... \$\endgroup\$ – RUser4512 Aug 6 '15 at 9:06
  • \$\begingroup\$ That's a brilliant use of TryGetValue but it did take me a couple of minutes to be sure it was the same functionality as the original code... Maybe a comment would help to explain the case when possibleValue is zero... \$\endgroup\$ – RobH Aug 6 '15 at 9:18
  • \$\begingroup\$ @RobH I added a short explanation \$\endgroup\$ – Heslacher Aug 6 '15 at 9:28
  • 1
    \$\begingroup\$ Since TryGetValue uses an out parameter rather than ref, you can skip initializing possibleValue to 0.0d. You need only declare it. \$\endgroup\$ – Dan Lyons Aug 6 '15 at 17:23
2
\$\begingroup\$

I'm sorry I'm not addressing your direct question, but I feel I need to mention this.

Any time you're writing mathematical type code, it's useful to leave a comment explaining yourself:

// This is So & So's formula....

Maybe even drop a link to a wiki article or something. The logic may be obvious to you now, but may not be in 6 months time or to someone else.

\$\endgroup\$
  • \$\begingroup\$ Yes, that is a good point. Besides, I am not exactly evaluating Euclide's distance since the final square root is not present, which makes it a very badly named function... All of this is corrected. \$\endgroup\$ – RUser4512 Aug 6 '15 at 9:31
1
\$\begingroup\$

Not really a code review: Have you tried using a sparse linear algebra library, like Math.NET? This would let you work with sparse vectors as:

var v1 = new SparseVector(1000000);
var v2 = new SparseVector(1000000);

var rnd = new Random();
for (int i = 0; i < 1000; i++)
{
    v1[rnd.Next(v1.Count)] = rnd.NextDouble();
    v2[rnd.Next(v2.Count)] = rnd.NextDouble();
}

And then you can just call (v1 - v2).L2Norm() to calculate the euclidean distance.

I would assume that Math.NET is optimized for operations like this.

\$\endgroup\$
1
\$\begingroup\$

Borrowing heavily from Heslacher's answer, can you perhaps parallelize the method? I took a stab at it using a range partitioner.

I added these usings:

using System.Threading;
using System.Collections.Concurrent;

And this method:

public static double ParallelEuclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
{
    double distance = 0;
    object lockableObject = new object();

    // CAUTION: may create a large list!
    var keys = sp1.Keys.ToList();

    var partitions = Partitioner.Create(0, keys.Count);

    Parallel.ForEach(partitions, range =>
        {
            double subtotal = 0;

            for (var i = range.Item1; i < range.Item2; i++)
            {
                double possibleValue = 0.0d;
                sp2.TryGetValue(keys[i], out possibleValue);

                double currentValue = sp1[keys[i]] - possibleValue;

                subtotal += currentValue * currentValue;
            }

            if (subtotal != 0.0)
            {
                lock (lockableObject)
                {
                    distance += subtotal;
                }
            }
        });

    // CAUTION: may create a large list!
    keys = sp2.Keys.ToList();

    partitions = Partitioner.Create(0, keys.Count);

    Parallel.ForEach(partitions, range =>
    {
        double subtotal = 0;

        for (var i = range.Item1; i < range.Item2; i++)
        {
            if (!sp1.ContainsKey(keys[i]))
            {
                subtotal += sp2[keys[i]] * sp2[keys[i]];
            }
        }

        if (subtotal != 0.0)
        {
            lock (lockableObject)
            {
                distance += subtotal;
            }
        }
    });

    return distance;
}

I have to run off to a meeting very soon, so apologize that I did not chop the one method up into 3 pieces. As is, it looks kind of ugly as one big code dump.

Admittedly, the biggest downside to this is memory. Dumping a dictionary's KeyCollection.ToList() can build an extremely large list of keys. But it should improve performance.

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