-1

C# で double のベクトル クラスを実装する必要があり、オーバーライドする必要があるEqualsためGetHashCode、ベクトル クラスをディクショナリのキーとして使用したり、HashSets を使用したりできます。平等に対してある程度の許容範囲が必要なので、推移的な Equals メソッドと対応する GetHashCode メソッドを実装する方法がないことはわかっています。

同様のスレッドで答えを見つけました: https://stackoverflow.com/a/580972/5333340

そして、知りたいのですが、C# で HashSet / Dictionaries のルックアップ動作を変更して、1 つのバケットだけでなく複数のバケットをチェックする方法はありますか?

または、C# でこの動作をするクラスはありますか?

4

1 に答える 1

0

HashSet はバケット検索動作をカスタマイズする手段を提供しないため、複数のバケット検索を行うカスタム クラスを作成しました。実際の使用例が含まれています: 3 次元ベクトル クラス。

// Implementing this interface introduces the concept of neighbouring buckets.
public interface IHasNeighbourConcept
{
    int[] GetSeveralHashCodes();
    // The returned int[] must at least contain the return value of GetHashCode.
}

// Custom HashSet-like class that can search in several buckets.
public class NeighbourSearchHashSet<T> where T : IHasNeighbourConcept
{
    // Internal data storage.
    private Dictionary<int, List<T>> buckets;

    // Constructor.
    public NeighbourSearchHashSet()
    {
        buckets = new Dictionary<int, List<T>>();
    }

    // Classic implementation utilizing GetHashCode.
    public bool Add(T elem)
    {
        int hash = elem.GetHashCode();

        if(!buckets.ContainsKey(hash))
        {
            buckets[hash] = new List<T>();
            buckets[hash].Add(elem);
            return true;
        }

        foreach(T t in buckets[hash])
        {
            if(elem.Equals(t))
                return false;
        }

        buckets[hash].Add(elem);
        return true;
    }

    /// Nonclassic implementation utilizing GetSeveralHashCodes.
    public bool Contains(T elem)
    {
        int[] hashes = elem.GetSeveralHashCodes();

        foreach(int h in hashes)
            foreach(T t in buckets[h])
                if(elem.Equals(t))
                    return true;
        return false;
    }


}


// A 3-dimensional vector class. Since its Equals method is not transitive,
// there can be vectors that are considered equal but have different HashCodes.
// So the Contains method of HashSet<Vector> does not work as expected.
public class Vector : IHasNeighbourConcept
{
    private double[] coords;
    private static double TOL = 1E-10;
    // Tolerance for considering two doubles as equal

    public Vector(double x, double y, double z)
    {
        if(double.IsNaN(x) || double.IsInfinity(x) ||
           double.IsNaN(y) || double.IsInfinity(y) ||
           double.IsNaN(z) || double.IsInfinity(z))
            throw new NotFiniteNumberException("All input must be finite!");

        coords = new double[] { x, y, z };
    }

    // Two vectors are equal iff the distance of each
    // corresponding component pair is significantly small.
    public override bool Equals(object obj)
    {
        if(!(obj is Vector))
            throw new ArgumentException("Input argument is not a Vector!");

        Vector other = obj as Vector;

        bool retval = true;
        for(int i = 0; i < 2; i++)
            retval = retval && (Math.Abs(coords[i] - other.coords[i]) < TOL);

        return retval;

    }

    // The set of all Vectors with the same HashCode
    // is a cube with side length TOL.
    // Two Vectors considered equal may have different
    // HashCodes, but the x, y, z intermediate values
    // differ by at most 1.
    public override int GetHashCode()
    {
        int x =(int) Math.Truncate(coords[0] / TOL);
        int y =(int) Math.Truncate(coords[1] / TOL);
        int z =(int) Math.Truncate(coords[2] / TOL);
        return x + 3*y + 5*z; // The purpose of the factors is to make
                              // permuting the coordinates result
                              // in different HashCodes.
    }

    // Gets the HashCode of the given Vector as well as the 26
    // HashCodes of the surrounding cubes.
    public int[] GetSeveralHashCodes()
    {
        int[] hashes = new int[27];
        int x =(int) Math.Truncate(coords[0] / TOL);
        int y =(int) Math.Truncate(coords[1] / TOL);
        int z =(int) Math.Truncate(coords[2] / TOL);

        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j++)
                for(int k = -1; k <= 1; k++)
                    hashes[(i+1)+3*(j+1)+9*(k+1)] = (x+i) + 3*(y+j) + 5*(z+k);
        return hashes;
    }
}

編集：

上記の実装は HashSet の概念を拡張し、推移的EqualsなメソッドがなくてもContainsセットのメソッドが正しく機能するようにします。Contains探している要素が含まれている正確な等価クラスを知る必要がないため、これは機能します。

ただし、辞書の場合は異なります。正しい等価クラス (つまり、hashCode) を取得する必要があります。そうしないと、別のイメージが取得されます。したがって、異なる HashCode は要素が等しくないという結果にならなければなりません。

于 2016-07-04T17:16:14.517 に答える