هل هناك طريقة للحصول على hashcode من تعويم مع ابسيلون?

Question

ومن المعروف أن مقارنة يطفو من قبل == عادة ما يكون خطأ.في 3D-ناقلات فئة (مع تعويم العناصر X, Y, Z) كتبت متجهين تعتبر متساوية إذا كانت المسافة تعتبر صفر.

    public override bool Equals(object obj)
    {
        if (obj == null) {
            return false;
        }

        if (GetType () != obj.GetType ()) {
            return false;
        }

        float d = DistSq ((Vec) obj);

        return IsConsideredZero (d);
    }

    public float DistSq(Vec p)
    {
        Vec d = this - p;
        return d.LengthSq ();
    }

    public float LengthSq()
    {
        return X * X + Y * Y + Z * Z;
    }

    private const float VEC_COMPARE_EPSILON_ABS = 1E-05f;
    public static bool IsConsideredZero(float f)
    {
        return Math.Abs (f) < VEC_COMPARE_EPSILON_ABS;
    }

حتى الآن كل شيء يعمل على ما يرام.ولكن الآن أود أن الحصول على hashcode من ناقلات.أستطيع أن أرى أن شيئا مثل hash = (int)X^(int)Y^(int)Z لا بد أن تفشل.

أفضل ما يمكن أن يأتي:

    public override int GetHashCode()
    {
        return 0;
    }

هذا بالطبع سيء نوعا ما.هل هناك أي طريقة للحصول على معقول hashcode?NaNs و غيرها من القيم الممكنة ، ولكن من غير المرجح في حال المهم.

Answer 1

من المستحيل افتراض أنك تريد الحصول على خصائص Hashcode / المساواة العادية:

• إذا كان x = y و y = z ثم x = z (الابتعاد)
• إذا كان x = y ثم y = x (commutility)
• x = x لجميع x (الانعكاس)

القاعدة الأولى هي المشكلة - لأنه إذا كانت كل قيمة تعتبر "متساويا" للرقم القابل للتمثيل المجاني التالي، فأنت في نهاية المطاف الكل الأرقام تكون متساوية. على سبيل المثال، افترض أن هناك عددا يعتبر مساويا لآخر في 0.1:

0 يساوي 0.08 0.08 يساوي 0.16 0.16 يساوي 0.24

=> 0 يساوي 0.16 بواسطة قاعدة التحويلية => 0 يساوي 0.24 بواسطة قاعدة العباسية

(إلخ)

إذا تجاهلت قاعدة العباسية، فستظل (يفترض) تريد قيم "متساوية" أن يكون لها هاشمكودات متساوية. هذا يفرض بشكل فعال قاعدة التحويلية - في المثال أعلاه، 0 و 0.08 يجب أن يكون لديه هاشمكودات متساوية، كما يفعل 0 و 0.16. لذلك 0 و 0.16 يجب أن يكون لديهم هاشمكودات متساوية، وهلم جرا. لذلك لا يمكنك أن لا يكون مفيد hashcode - يجب أن يكون ثابتا.

Answer 2

لا أعتقد أنه يمكنك الحصول على شاشة حاشية تتوافق مع طريقة المقارنة الخاصة بك لأن الأخير غير متعدي: لأي ناقلات ثلاثة أ، ب، ج، إذا A.Equals(B) و B.Equals(C) صحيحون، لا يزال من الممكن أن يكون الأمر كذلك A.Equals(C) هو زائف. (تخيل ما إذا كانت المسافة بين A و B هي 6E-6، بين B و C هي 6E-6، وبين A و C هو 1.2E-5) ولكن المساواة في Hashcodes متعدية دائما، لأنها مجرد أرقام.

في هذه الحالة، أود فقط إنشاء طريقة Hashcode تقوم بتحسين التجزئة على أساس القيم الدقيقة للإحداثيات العائمة، ونذكر في الوثائق بأنها غير متسقة مع تساوي. أعلم أنه ليس حل حقا ولكن بالنظر إلى أنني لا أعتقد أن الحل الحقيقي موجود، فمن الأفضل أن يكون لديك حاوية غير خالية من 0.

Answer 3

أخشى أن الأمر ليس في القضية العامة. رسم برهان يذهب مثل هذا:

خذ أي رقمين أ و ب. دع الفرق بينهما يكون د. ثم إذا قمت بإنشاء أرقام D / EPSILON مع خطوة EPSILON بين ما بينها، يجب أن تكون كل خطوة "متساوية" إلى الخطوة السابقة، والتي من خلال دلالات Hashcode لها نفس الحشاشة. لذلك يجب أن تحتوي جميع الأرقام على نفس الحاكم.

يمكنك فقط حل هذه المشكلة فقط إذا قمت بإضافة بعض القيد الأخرى.

كقدم، لديك تعريف يساوي خطأ كذلك، حيث يمكن أن يكون صحيحا أن A. Aquales (B) و B.aleaLes (ج) ولكن ليس A. وليس A. هذا هو المعروف باسم كسر عبورية خاصية.

ماذا يمكنني أن أفعل بعد ذلك؟

يعتمد الحل على ما تستخدمه. حل واحد سيكون لتقديم شبكة مفاهيمية. تغيير المساواة و hashcode لذا فإن رقمين متساوون إذا كان في نفس الشبكة مكعب، عن طريق التقريب إلى عدد ثابت من الأماكن العشرية، ثم أخذ متساوين ومساكنا على الرقم المستدير. إذا كانت كونها قريبة من الصفر هي حالة مهمة، أضف إزاحة EPSILON / 2 قبل التقريب، لذلك صفر هو مركز المكعب. هذا صحيح، ولكن يمكنك الحصول على رقمين قريبين بشكل تعسفي معا (تحت حدود تعويم) دون أن تكون متساوية. لذلك بالنسبة لبعض التطبيقات، سيكون الأمر على ما يرام، والبعض الآخر لن يكون. هذا يشبه فكرة من mghie..

Answer 4

الجميع صحيح ...

ومع ذلك، فإن الشيء الوحيد الذي يتم القيام به في كثير من الأحيان هو تمديد مفهوم التجزئة قليلا. النظر في قسم الفضاء ثلاثي الأبعاد مع صناديق مع جانب >> Epsilon.

التجزئة من النقطة هي الصندوق الذي ينتمي إليه. عندما تريد البحث عن نقطة، لا تحقق من النقطة مع المربع المقابل (كما تفعل من أجل التجزئة العادية) ولكن بالنسبة للصناديق المجاورة أيضا. في ثلاثي الأبعاد يجب أن تفلت بعيدا مع صناديق 8 كحد أقصى.

Answer 5

مهما كنت تستخدم تقنية لديهم مشاكل لأنك طرحت شيء ليس من الممكن حل.

ما تريده هو 1) موزعة بالتساوي تجزئة هذه أن معظم الأعداد a و b حيث a != ب ثم.GetHashCode() != ب.GetHashCode() ولكن 2) حيث a == b ثم a.GetHashCode() == ب.GetHashCode() يجب أن يكون صحيحا.

العودة ثابت يفي (2) ولكن ليس (1).

يمكنك إثبات أن التقريب في 1E-5 الحدود التي تجزئة ينتهك يفي (1) ولكن ينتهك (2).تأخذ 1E-5 2E-5, على سبيل المثال.التقريب من شأنها أن تنتج نوعين مختلفين تجزئة القيم ولكن يقارنون متساوية.هذا يخالف القيد (2) أعلاه.يمكنك بسهولة تعميم هذا لإثبات أن أي التقريب من عدد واجهت مشكلة مماثلة.

أنصحك اختيار نهج مختلف.أنا أعتقد أن المشكلة الأساسية هي تحديد ما إذا كان بعض نقطة قريبة من نقطة لديك بالفعل.أوصي recusively تقسيم تنسيق الفضاء في النصف (حيث نقاط على طول الحدود (أي<=1E-5 من الحدود) في كل شطر).إذا كنت تدريجيا تقسيم لك مساحة (اعتقد شجرة ثنائية) يمكنك بناء بنية البيانات التي سوف يعود بسرعة على النتيجة التي تريدها و يكون من السهل بناء.

إذا فاتني تخميني و يجب استخدام تجزئة ثم يمكن أن تفعل ما تريد مع اثنين من قيم التجزئة لكل التقريب إلى 1E-5 ولكن يقابله 5E-6.كل تساوي نقطة مقارنة متساوية على واحد من اثنين من قيم التجزئة.هذا يتطلب منك إدخال نقطة في جدول التجزئة مرتين ، مرة واحدة لكل تجزئة الروتينية.