Bagaimana menerapkan hashing float dengan perkiraan kesetaraan

Katakanlah kita memiliki kelas Python berikut (masalahnya ada di Jawa sama dengan equalsdan hashCode)

class Temperature:
    def __init__(self, degrees):
        self.degrees = degrees

di mana degreessuhu di Kelvin sebagai pelampung. Sekarang, saya ingin menerapkan pengujian kesetaraan dan hashing Temperaturedengan cara itu

• membandingkan mengapung hingga perbedaan epsilon alih-alih pengujian kesetaraan langsung,
• dan menghormati kontrak yang a == bmenyiratkan hash(a) == hash(b).

def __eq__(self, other):
    return abs(self.degrees - other.degrees) < EPSILON

def __hash__(self):
    return # What goes here?

Dokumentasi Python berbicara sedikit tentang hashing angka untuk memastikan itu hash(2) == hash(2.0)tetapi ini bukan masalah yang sama.

Apakah saya bahkan berada di jalur yang benar? Dan jika demikian, apa cara standar untuk menerapkan hashing dalam situasi ini?

Pembaruan : Sekarang saya mengerti bahwa jenis pengujian kesetaraan untuk pelampung ini menghilangkan transitivitas ==dan equals. Tetapi bagaimana hal itu sejalan dengan "pengetahuan umum" yang mengapung tidak harus dibandingkan secara langsung? Jika Anda menerapkan operator kesetaraan dengan membandingkan pelampung, alat analisis statis akan mengeluh. Apakah mereka benar?

menerapkan pengujian kesetaraan dan hashing untuk Suhu dengan cara yang membandingkan mengapung hingga perbedaan epsilon alih-alih pengujian kesetaraan langsung,

Kesetaraan fuzzy melanggar persyaratan bahwa Java menempatkan pada equalsmetode, yaitu transitivitas , yaitu bahwa jika x == ydan y == z, kemudian x == z. Tetapi jika Anda melakukan persamaan fuzzy dengan, misalnya, epsilon 0,1, maka 0.1 == 0.2dan 0.2 == 0.3, tetapi 0.1 == 0.3tidak berlaku.

Sementara Python tidak mendokumentasikan persyaratan seperti itu, masih implikasi memiliki kesetaraan non-transitif membuatnya menjadi ide yang sangat buruk; alasan tentang jenis-jenis tersebut adalah sakit kepala.

Jadi saya sangat menyarankan Anda tidak melakukan itu.

Entah memberikan kesetaraan yang tepat dan mendasarkan hash Anda pada itu dengan cara yang jelas, dan menyediakan metode terpisah untuk melakukan pencocokan fuzzy, atau pergi dengan pendekatan kelas ekivalensi yang disarankan oleh Kain. Meskipun dalam kasus terakhir, saya sarankan Anda memperbaiki nilai Anda ke anggota perwakilan dari kelas kesetaraan di konstruktor, dan kemudian pergi dengan kesetaraan tepat sederhana dan hashing untuk yang lain; itu jauh lebih mudah untuk alasan tentang jenis dengan cara ini.

(Tetapi jika Anda melakukannya, Anda mungkin juga menggunakan representasi titik tetap alih-alih titik mengambang, yaitu Anda menggunakan integer untuk menghitung seperseribu derajat, atau presisi apa pun yang Anda butuhkan.)

Semoga berhasil

Anda tidak akan dapat mencapai itu, tanpa menjadi bodoh dengan hash, atau mengorbankan epsilon.

Contoh:

Asumsikan bahwa setiap titik hash ke nilai hash uniknya sendiri.

Karena angka floating point berurutan akan ada hingga k angka sebelum nilai floating point yang diberikan, dan hingga k angka setelah nilai floating point tertentu yang berada dalam beberapa epsilon dari titik yang diberikan.

1. Untuk masing-masing dua titik dalam epsilon satu sama lain yang tidak memiliki nilai hash yang sama.

   • Sesuaikan skema hashing sehingga dua poin ini memiliki nilai hash yang sama.
2. Menginduksi untuk semua pasangan seperti itu seluruh urutan angka floating point akan runtuh menuju nilai tunggal.

Ada beberapa kasus di mana ini tidak berlaku:

• Infinity Positif / Negatif
• NaN
• Beberapa rentang De-normalisasi yang mungkin tidak dapat dihubungkan ke rentang utama untuk epsilon yang diberikan.
• mungkin beberapa contoh format spesifik lainnya

Namun> = 99% dari rentang titik apung akan hash ke nilai tunggal untuk setiap nilai epsilon yang mencakup setidaknya satu nilai titik apung di atas atau di bawah beberapa nilai titik apung yang diberikan.

Hasil

Entah> = 99% seluruh hash rentang titik apung ke nilai tunggal yang secara serius mengkompromikan maksud nilai hash (dan perangkat / wadah yang mengandalkan hash tabrakan rendah yang didistribusikan secara adil).

Atau epsilon sedemikian rupa sehingga hanya pencocokan persis yang diizinkan.

Butiran

Tentu saja Anda bisa menggunakan pendekatan granular.

Di bawah pendekatan ini, Anda menentukan bucket persis ke resolusi tertentu. yaitu:

[0.001, 0.002)
[0.002, 0.003)
[0.003, 0.004)
...
[122.999, 123.000)
...

Setiap bucket memiliki hash yang unik, dan titik apung apa pun di dalam bucket sebanding dengan float lainnya di bucket yang sama.

Sayangnya masih mungkin untuk mengapung dua menjadi jarak epsilon, dan memiliki dua hash yang terpisah.

Anda dapat memodel suhu Anda sebagai bilangan bulat di bawah tenda. Temperatur memiliki batas bawah alami (-273,15 Celcius). Jadi, double (-273.15 sama dengan 0 untuk integer dasar Anda). Elemen kedua yang Anda butuhkan adalah rincian pemetaan Anda. Anda sudah menggunakan rincian ini secara implisit; itu adalah EPSILON kamu.

Bagilah temperatur Anda dengan EPSILON dan ukur, sekarang hash dan persamaan Anda akan berperilaku selaras. Dalam Python 3 bilangan bulat tidak terikat, EPSILON bisa lebih kecil jika Anda suka.

WASPADALAH Jika Anda mengubah nilai EPSILON dan Anda telah membuat serial objek, mereka tidak akan kompatibel!

#Pseudo code
class Temperature:
    def __init__(self, degrees):
        #CHECK INVALID VALUES HERE
        #TRANSFORM TO KELVIN HERE
        self.degrees = Math.floor(kelvin/EPSILON)

Menerapkan tabel hash floating-point yang dapat menemukan hal-hal yang "kira-kira sama" dengan kunci yang diberikan akan membutuhkan beberapa pendekatan atau kombinasi dari semuanya:

1. Bulatkan setiap nilai hingga selisih yang agak lebih besar dari rentang "fuzzy" sebelum menyimpannya di tabel hash, dan saat mencoba menemukan nilai, periksa tabel hash untuk nilai-nilai bulat di atas dan di bawah nilai yang dicari.

2. Simpan setiap item dalam tabel hash menggunakan kunci yang di atas dan di bawah nilai yang dicari.

Perhatikan bahwa menggunakan salah satu pendekatan kemungkinan akan membutuhkan entri tabel hash yang tidak mengidentifikasi item, melainkan daftar, karena kemungkinan akan ada beberapa item yang terkait dengan setiap kunci. Pendekatan pertama di atas akan meminimalkan ukuran tabel hash yang diperlukan, tetapi setiap pencarian untuk item yang tidak ada dalam tabel akan membutuhkan dua pencarian tabel hash. Pendekatan kedua akan dengan cepat dapat mengidentifikasi bahwa item tidak ada dalam tabel, tetapi umumnya akan membutuhkan tabel untuk menampung entri sebanyak dua kali lebih banyak dari yang seharusnya diperlukan. Jika seseorang mencoba menemukan objek dalam ruang 2D, mungkin berguna untuk menggunakan satu pendekatan untuk arah X dan satu untuk arah Y, sehingga alih-alih meminta setiap item disimpan sekali tetapi membutuhkan empat operasi kueri untuk setiap pencarian, atau menjadi dapat menggunakan satu pencarian untuk menemukan item tetapi harus menyimpan setiap item empat kali,

Anda tentu saja dapat mendefinisikan "hampir sama" dengan menghapus katakan delapan bit terakhir dari mantissa dan kemudian membandingkan atau hashing. Masalahnya adalah bahwa angka yang sangat dekat satu sama lain mungkin berbeda.

Ada beberapa kebingungan di sini: jika dua angka floating point dibandingkan sama, mereka sama. Untuk memeriksa apakah keduanya sama, Anda menggunakan "==". Terkadang Anda tidak ingin memeriksa kesetaraan, tetapi ketika Anda melakukannya, “==“ adalah jalan yang harus ditempuh.

Ini bukan jawaban, tetapi komentar panjang yang mungkin membantu.

Saya telah mengerjakan masalah yang sama, saat menggunakan MPFR (berdasarkan GNU MP). Pendekatan "bucket" seperti yang digariskan oleh @ Kain0_0 tampaknya memberikan hasil yang dapat diterima, tetapi perhatikan batasan yang disorot dalam jawaban itu.

Saya ingin menambahkan bahwa - tergantung pada apa yang Anda coba lakukan - menggunakan sistem aljabar komputer "tepat" ( peringatan ) seperti Mathematica dapat membantu menambah atau memverifikasi program numerik yang tidak tepat. Ini akan memungkinkan Anda untuk menghitung hasil tanpa khawatir tentang pembulatan, misalnya, 7*√2 - 5*√2akan menghasilkan 2bukan 2.00000001atau serupa. Tentu saja, ini akan menimbulkan komplikasi tambahan yang mungkin atau mungkin tidak sepadan.