हैश एक फ्लोट वेक्टर के लिए अच्छा तरीका है?

Question

मैं फ्लोट की तुलना में शामिल सभी समस्याओं के बारे में अच्छी तरह से अवगत हूं। इस सवाल का यही कारण है।
मैं 3 डी वैक्टर (3 फ्लोट्स - एक्स, वाई, जेड) मानों के लिए एक तेज हैश तालिका बनाने के लिए देख रहा हूं। यह माना जा सकता है कि वेक्टर की लंबाई हमेशा 1.0 होती है (sqrt(x*x+y*y+z*z) 1.0)

अनिवार्य रूप से इसका मतलब है कि मैं एक हैश फ़ंक्शन ढूंढ रहा हूं जो मानों को लेता है जो लगभग उसी हस्ताक्षरित int मान के बराबर होते हैं और संबंधित समानता ऑपरेटर यह सच है अगर हैश मान बराबर (जरूरी नहीं केवल नहीं है अगर वे बराबर हैं) कर रहे हैं

संपादित -
गलत सकारात्मक (यानी वैक्टर कि अलग हैं, लेकिन एक ही बाल्टी के लिए नक्शे) एक के बाद दिया जाता है यह एक हैश टेबल है।
झूठी नकारात्मक (यानी वेक्टर जो निकट हैं लेकिन अलग-अलग बाल्टी के लिए नक्शा) अवांछित हैं लेकिन ऐसा लगता है कि उनसे बचने का कोई तरीका नहीं है। मेरे मामले में, वे कुल टूटने का कारण नहीं बनेंगे, केवल कुछ डेटा डुप्लिकेशंस जो मुझे जीना होगा।

Answer 1

मैं इस तरह पूर्णांकों में नाव मूल्यों परिवर्तित चाहते हैं:

unsigned int IntValue = (int)(floatValue * MULT) + MULT; 

ताकि आप पहले अंक में से कुछ मिलता है और उसके बाद का उपयोग कर

const MULT1 = (MULT << 1) + 1; 
unsigned long long HashValue = (xIntValue * MULT1 * MULT1) + (yIntValue * MULT1) + zIntValue; 

का प्रयोग कर एक हैश मान के रूप में ((MULT * 2) + 1 क्योंकि IntValues ​​0 और मल्टी * 2 समावेशी के बीच होगा)।

आवश्यक स्मृति गुणक मल्टी के आधार पर होगी। उदाहरण के लिए, 32 का उपयोग करके आपको 64 * 64 * 64 * (हैश आइटम आकार) = 262144 * (हैश आइटम आकार) बाइट्स का उपयोग करके एक हैशटेबल मिलेगा।

Answer 2

मुझे लगता है कि आप जो खोज रहे हैं वह सीधे संभव नहीं है। समानता की एक महत्वपूर्ण संपत्ति यह है कि यह संक्रमणीय है। (यानी यदि एक == बी और बी == सी, तो एक == सी)। दूरी माप के साथ, हालांकि, आप वास्तव में यह संपत्ति नहीं चाहते हैं। उदाहरण:

एक ही फ्लोट (सादगी के लिए) लें। मान लीजिए कि हम प्रत्येक फ्लोट को हैश करना चाहते हैं ताकि 1e-3 से कम दूर फ़्लोट समान मूल्य हो। अब, मान लें कि हम इस हैश तालिका में 1000 फ्लोट वैल्यू को सभी 1e-4 अलग-अलग जोड़ते हैं। किसी पड़ोसी 2 मानों को एक ही फ्लोट पर हैश होना चाहिए, क्योंकि वे 1e-3 के करीब हैं। हालांकि, पारगमन की वजह से, उन मूल्यों के पड़ोसियों को भी वही मूल्य होना चाहिए, और उनके पड़ोसियों और इसी तरह। नतीजतन, 1e-3 के अलावा जोड़े सहित सभी 1000 मान, एक ही पूर्णांक के लिए हैश होगा। आप एक तस्वीर पर इन बिंदुओं आकर्षित करने के लिए थे, तो:

A B C D E F G H ... Y Z 

मान लीजिए सभी अंतराल < 1e-3 अलग हैं, लेकिन एक और जेड हैं> 1e-3 अलग (पैमाने पर नहीं!)। यह संतुष्ट नहीं हो सकता है क्योंकि हैश (ए) == हैश (बी) और हैश (बी) == हैश (सी) और इतने सारे जोड़े के लिए, (क्योंकि वे < 1e-3 अलग हैं) हैश (ए) == हैश (जेड) होना चाहिए।

एक संभावित विकल्प अपने वेक्टर स्पेस के क्षेत्रों को परिभाषित करना है जिसमें सभी वैक्टर एक ही मूल्य के लिए हैश (यानी उन्हें धोने से पहले गोल करें), लेकिन आप अभी भी अपने संबंधित रिक्त स्थान के किनारों पर 2 वैक्टर प्राप्त कर सकते हैं एक साथ बंद करें लेकिन हैश एक अलग मूल्य के लिए। आप वेक्टर के लिए सभी पड़ोसी रिक्त स्थान खोजकर उस पर हो सकते हैं। (यानी उपरोक्त 1-डी मामले में, आप सभी वैक्टरों को 1e-3 के निकटतम एकाधिक में ले जाएंगे, और फिर पड़ोसियों की खोज करेंगे, इसलिए 5.3e-3 5e-3, 4e-3 और 6-e3 खोजेगा। उच्च-आयामी मामलों में, आपको पड़ोसियों को सभी आयामों में खोजना होगा।)

Answer 3

कुछ भाषाएं (सी, जावा 5) आपको अपनी फ्लोट के बाइनरी मूल्य तक पहुंचने की अनुमति देती हैं। इस तरह, आप मंथिसा के पहले एन बिट्स (पिछले कुछ बिट्स को अनदेखा कर सकते हैं जो तुलना के दौरान परेशानी का कारण बनते हैं) को निकाल सकते हैं और उस से हैश की गणना कर सकते हैं।

Answer 4

क्या आप अपनी समस्या पर विस्तार कर सकते हैं?

मान लें कि आप विशिष्ट वैक्टरों को कुछ अतिरिक्त डेटा मैप करने के लिए हैशैप का उपयोग कर रहे हैं, तो आप घटकों के बाइनरी प्रस्तुतियों के एक्सओआर का उपयोग कर सकते हैं (यदि यह आपकी पसंद की भाषा में संभव है)। फिर हैश मैप के लिए आवश्यकतानुसार कई एलएसबी (टकराव को कम करने के लिए) का उपयोग करें। इसमें निश्चित रूप से संपत्ति होगी जो दो बराबर (फ्लोटिंग पॉइंट तुलना द्वारा) वैक्टरों में एक ही हैश नहीं हो सकता है (उदाहरण के लिए आईईईई फ़्लोटिंग पॉइंट 0 -0 के बराबर है, लेकिन उनके पास अलग-अलग साइन बिट हैं)।

हालांकि, यदि आप हैश लुकअप करने के लिए विभिन्न कंप्यूटेशंस के परिणाम वाले वेक्टरों का उपयोग करने की योजना बना रहे हैं, तो आप गोलाकार त्रुटियों के कारण हैश कोड मिलान करने की संभावना पर खुद को स्थापित कर रहे हैं और आपको शायद कुछ और उपयोग करना चाहिए वैसे भी।

Answer 5

यह नहीं पता कि यह कितना तेज़ हो सकता है, लेकिन चूंकि आपके पास इकाई वैक्टर हैं, वे सभी एक क्षेत्र की सतह पर झूठ बोलते हैं। http://en.wikipedia.org/wiki/Spherical_coordinate_system में कनवर्ट करें। फिर एक बाल्टी चुनने के लिए फाई और थेटा का उपयोग करें। कोई झूठी सकारात्मक नहीं होगी। आप झूठी नकारात्मकताओं के लिए पड़ोसी कोशिकाओं में देख सकते हैं।

Answer 6

क्या आपको इसे तेज हैश टेबल होने की आवश्यकता है या पेड़ की संरचना क्या होगी?

ऐसा लगता है कि कुछ सॉर्ट के खोज पेड़ में मिलान करने वाली फ्लोट देखना आसान होगा। एक B-Tree कैश मिस की संख्या को कम करता है, यह मानते हुए कि आप सही नोड आकार चुनते हैं। इसे अभ्यास में बहुत तेजी से बनाना चाहिए।

Answer 7

मुझे लगता है कि आप प्रभावी रूप से के निकटतम समस्या को हल करने की कोशिश कर रहे हैं। मुझे विश्वास है कि आप जो खोज रहे हैं वह locality sensitive hashing है। इसके अलावा आप एक ही परिणाम प्राप्त करने के लिए क्वाड पेड़ संरचनाओं का उपयोग कर सकते हैं।