fastest way for accessing double array as key in dictionary

Question

I have a double[] array, i want to use it as key （not literally, but in the way that the key is matched when all the doubles in the double array need to be matched)

What is the fastest way to use the double[] array as key to dictionary?

Is it using Dictionary<string, string> (convert double[] to a string) or anything else like converting it

Answer 1

Given that all key arrays will have the same length, either consider using a Tuple<,,, ... ,>, or use a structural equality comparer on the arrays.

With tuple:

var yourDidt = new Dictionary<Tuple<double, double, double>, string>();
yourDict.Add(Tuple.Create(3.14, 2.718, double.NaN), "da value");

string read = yourDict[Tuple.Create(3.14, 2.718, double.NaN)];

With (strongly typed version of) StructuralEqualityComparer:

class DoubleArrayStructuralEqualityComparer : EqualityComparer<double[]>
{
    public override bool Equals(double[] x, double[] y)
    {
        return System.Collections.StructuralComparisons.StructuralEqualityComparer
            .Equals(x, y);
    }

    public override int GetHashCode(double[] obj)
    {
        return System.Collections.StructuralComparisons.StructuralEqualityComparer
            .GetHashCode(obj);
    }
}

...

var yourDict = new Dictionary<double[], string>(
    new DoubleArrayStructuralEqualityComparer());

yourDict.Add(new[] { 3.14, 2.718, double.NaN, }, "da value");

string read = yourDict[new[] { 3.14, 2.718, double.NaN, }];

Also consider the suggestion by Sergey Berezovskiy to create a custom class or (immutable!) struct to hold your set of doubles. In that way you can name your type and its members in a natural way that makes it more clear what you do. And your class/struct can easily be extended later on, if needed.

Answer 2

Thus all arrays have same length and each item in array have specific meaning, then create class which holds all items as properties with descriptive names. E.g. instead of double array with two items you can have class Point with properties X and Y. Then override Equals and GetHashCode of this class and use it as key (see What is the best algorithm for an overriding GetHashCode):

Dictionary<Point, string>

Benefits - instead of having array, you have data structure which makes its purpose clear. Instead of referencing items by indexes, you have nice named property names, which also make their purpose clear. And also speed - calculating hash code is fast. Compare:

double[] a = new [] { 12.5, 42 };
// getting first coordinate a[0];
Point a = new Point { X = 12.5, Y = 42 };
// getting first coordinate a.X

Answer 3

[Do not consider this a separate answer; this is an extension of @JeppeStigNielsen's answer]

I'd just like to point out that you make Jeppe's approach generic as follows:

public class StructuralEqualityComparer<T>: IEqualityComparer<T>
{
    public bool Equals(T x, T y)
    {
        return StructuralComparisons.StructuralEqualityComparer.Equals(x, y);
    }

    public int GetHashCode(T obj)
    {
        return StructuralComparisons.StructuralEqualityComparer.GetHashCode(obj);
    }

    public static StructuralEqualityComparer<T> Default
    {
        get
        {
            StructuralEqualityComparer<T> comparer = _defaultComparer;

            if (comparer == null)
            {
                comparer = new StructuralEqualityComparer<T>();
                _defaultComparer = comparer;
            }

            return comparer;
        }
    }

    private static StructuralEqualityComparer<T> _defaultComparer;
}

(From an original answer here: https://stackoverflow.com/a/5601068/106159)

Then you would declare the dictionary like this:

var yourDict  = new Dictionary<double[], string>(new StructuralEqualityComparer<double[]>());

Note: It might be better to initialise _defaultComparer using Lazy<T>.

---

[EDIT]

It's possible that this might be faster; worth a try:

class DoubleArrayComparer: IEqualityComparer<double[]>
{
    public bool Equals(double[] x, double[] y)
    {
        if (x == y)
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (int i = 0; i < x.Length; ++i)
            if (x[i] != y[i])
                return false;

        return true;
    }

    public int GetHashCode(double[] data)
    {
        if (data == null)
            return 0;

        int result = 17;

        foreach (var value in data)
            result += result*23 + value.GetHashCode();

        return result;
    }
}

...

var yourDict = new Dictionary<double[], string>(new DoubleArrayComparer());

Answer 4

Ok this is what I found so far:

I input an entry (length 4 arrray) to the dictionary, and access it for 999999 times on my machine:

Dictionary<double[], string>( new DoubleArrayStructuralEqualityComparer()); takes 1.75 seconds

Dictionary<Tuple<double...>,string> takes 0.85 seconds

The code below takes 0.1755285 seconds, which is the fastest now! (in line with the comment with Sergey.)

The fastest - The code of DoubleArrayComparer by Matthew Watson takes 0.15 seconds!

    public class DoubleArray
    {
        private double[] d = null;
        public DoubleArray(double[] d)
        {
            this.d = d;
        }

        public override bool Equals(object obj)
        {
            if (!(obj is DoubleArray)) return false;

            DoubleArray dobj = (DoubleArray)obj;
                if (dobj.d.Length != d.Length) return false;

                for (int i = 0; i < d.Length; i++)
                    {
                        if (dobj.d[i] != d[i]) return false;
                    }
                return true;

        }
        public override int GetHashCode()
        {
            unchecked // Overflow is fine, just wrap
            {
                int hash = 17;
                for (int i = 0; i < d.Length;i++ )
                {
                    hash = hash*23 + d[i].GetHashCode();
                }

                return hash;
            }
        }
    }