كيفية تنفيذ IEqualityComparer<PointF> مع التسامح

Question

هذا السؤال مشابه ل واحد هنا.

نحن جميعا نعرف ما بوينتف هو، أليس كذلك؟هذا هو هيكل البيانات:

public struct PointF
{
  public float X;
  public float Y;
}

كيفية التنفيذ IEqualityComparer<PointF> مع التسامح؟دعنا نقول بلدي Equals الكود هو مثل هذا

public const float Epsilon = 0.01; //say
public bool Equals(PointF pt1, PointF pt2)
{
   return Math.Abs(pt1.X-pt2.X)<Epsilon && Math.Abs(pt1.Y-pt2.Y)<Epsilon;
}

سؤال:كيفية التنفيذ الصحيح GetHashCode بحيث لقاموس PointF, هل سأصل إلى العنصر بشكل صحيح؟

لقد صدع رأسي لبضعة أيام ولكني ما زلت غير قادر على إيجاد حل مرضٍ.

Answer 1

بدلًا من تحديد التفاوت حسب المسافة، يمكنك وضع النقاط في شبكة.
إذا كانت هناك نقطتان في نفس الخلية، فإنهما تعتبران متساويتين ولهما نفس رمز التجزئة.

public bool Equals(PointF pt1, PointF pt2)
{
   return GetCell(pt1.X) == GetCell(pt2.X)
       && GetCell(pt1.Y) == GetCell(pt2.Y);
}

public int GetHashCode(PointF pt)
{
   return GetCell(pt.X) ^ GetCell(pt.Y);
}

private static int GetCell(float f)
{
    return (int)(f / 10); // cell size is 10 pixels
}

---

أُطرُوحَة: لا يوجد تنفيذ Equals و GetHashCode الذي يلبي متطلباتك.

دليل: خذ بعين الاعتبار النقاط الثلاث التالية، أ، ب، ج:

وفقا لمتطلباتك،

Equals(A, B) == true              // (i)
Equals(B, C) == true              // (ii)
Equals(A, C) == false             // (iii)
GetHashCode(A) == GetHashCode(B)  // (iv)
GetHashCode(B) == GetHashCode(C)  // (v)
GetHashCode(A) != GetHashCode(C)  // (vi)

ولكن من (الرابع) و (الخامس) يتبع

GetHashCode(A) == GetHashCode(C)

وبالتالي

Equals(A, C) == true

وهو ما يتناقض مع (ثالثًا) و(سادسًا).

منذ Equals و GetHashCode لا يمكن إرجاع قيم مختلفة لنفس الوسائط، فلا يوجد تطبيق يلبي متطلباتك.سؤال وجواب.

Answer 2

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

Answer 3

حسنًا، الإجابة المبنية على الشبكات جيدة، لكن في بعض الأحيان تحتاج إلى تجميع النقاط القريبة على أي حال، حتى لو لم تكن في نفس خلية الشبكة.طريقتي هي تنفيذ ذلك من خلال مجموعة:تكون نقطتان في نفس المجموعة إذا كانتا قريبتين أو كان هناك سلسلة من النقاط القريبة التي تربط بينهما.لا يمكن القيام بهذه الدلالات بطريقة صحيحة IEqualityComparer, لأنه يحتاج إلى معرفة جميع العناصر مسبقًا قبل إنتاج المجموعات.لقد قمت بإجراء عامل تشغيل بسيط على طراز LINQ GroupByCluster, ، وهو ما يحقق ذلك بشكل أساسي.

الكود هنا: http://ideone.com/8l0LH.يتم تجميعه على VS 2010 الخاص بي، لكنه فشل في التجميع على Mono بسبب HashSet<> لا يمكن تحويلها ضمنيا إلى IEnumerable<> (لماذا؟).

هذا النهج عام وبالتالي ليس فعالاً للغاية:انها تربيعية على حجم الإدخال.بالنسبة لأنواع الخرسانة يمكن جعلها أكثر كفاءة:على سبيل المثال، بالنسبة لـ T = double، يمكننا فقط فرز مصفوفة الإدخال والحصول عليها O(n log n) أداء.تنطبق الحيلة المماثلة، وإن كانت أكثر تعقيدًا، على النقاط ثنائية الأبعاد أيضًا.

---

ملاحظة جانبا:اقتراحك الأولي من المستحيل تنفيذه IEqualityComparer, ، نظرًا لأن "المساواة التقريبية" ليست متعدية (لكن المساواة في IEqualityComparer يجب أن يكون كذلك).