sorting - ह्यूरिस्टिक्स उनके पारस्परिक दूरी के अनुसार 2 डी/3 डी अंकों की सरणी को सॉर्ट करने के लिए




caching distance (2)

आप जिस समस्या को हल करने का प्रयास कर रहे हैं, IF का मतलब है, एक बिंदु पी और उसके एनएन क्यू के अनुसार, फिर यह सच है कि क्यू का एनएन पी है

यह तुच्छ नहीं है, क्योंकि उदाहरण के लिए दो बिंदु एक परिदृश्य में स्थितियों का प्रतिनिधित्व कर सकते हैं, इसलिए एक बिंदु एक पहाड़ में ऊंचा हो सकता है, इसलिए नीचे से पहाड़ की ओर बढ़कर अधिक खर्च होता है और दूसरी तरफ (पहाड़ से लेकर तल)। इसलिए, सुनिश्चित करें कि आप जांचते हैं कि आपके केस नहीं हैं।

चूंकि टिल्मेनज ने पहले ही एक समाधान का प्रस्ताव दिया है, मैं आपको एलएसएच पर ज़ोर देना चाहूंगा जो आपने उल्लेख किया था। मैं यह नहीं चुनूंगा, क्योंकि आपके बिंदु वाकई कम आयामी अंतरिक्ष में हैं , यह 100 भी नहीं है, इसलिए एलएसएच का उपयोग क्यों करना है?

मैं उस मामले पर सीएजीएल के एल्गोरिदम के लिए जाता हूं, जैसे कि 2 डी एनएनएस , या यहां तक ​​कि एक सरल केडी-पेड़ । और यदि गति महत्वपूर्ण है, लेकिन अंतरिक्ष नहीं है, तो क्यों नहीं quadtree (3 डी में octree) के लिए जा रहे हैं? मैंने एक बनाया था, यह 8 जीबी रैम में 10 आयामों से परे नहीं होगा।

यदि हालांकि, आपको लगता है कि आपका डेटा भविष्य में उच्च आयामी स्थान में हो सकता है, तो मैं इसका उपयोग करने का सुझाव दूंगा:

  1. अदोनि से एलएसएच, वास्तव में अच्छा लड़का
  2. फ्लैन , जो एक अन्य दृष्टिकोण प्रदान करता है
  3. केडी-जीआरएएफ , जो कि मेरे द्वारा विकसित किया गया है

2 डी, 3 डी, (4 डी ...) स्थान (जैसे असंरचित जाल के नोड्स) में अंक की सरणी पर विचार करें। शुरू में सरणी में एक बिंदु का सूचक स्थान में अपनी स्थिति से संबंधित नहीं है। सरल मामले में, मान लें कि मुझे पहले से ही पास के पड़ोसी कनेक्टिविटी ग्राफ़ को पता है।

मुझे कुछ ह्यूरिस्टिक्स पसंद हैं जो संभावना को बढ़ाते हैं, जो अंतरिक्ष में एक दूसरे के करीब हैं, समान सूचकांक (सरणी में बंद हो जाएगा) होगा।

मैं समझता हूं कि सटीक समाधान बहुत कठिन है (शायद यात्रा विक्रेता की समस्या के समान) लेकिन मुझे सटीक समाधान की आवश्यकता नहीं है, बस कुछ चीजें जो संभावना बढ़ जाती है

समाधान पर मेरे विचार:

कुछ भोलेपन का समाधान होगा:

1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise)
   E_i = -Sum_k ( abs( index(i)-index(k) ) ) 
   where "k" are spatial nearest neighbors of "i" 
2. for pairs of points (i,j) which have low fitness (E_i,E_j) 
   try to swap them, 
   if fitness improves, accept

लेकिन विस्तृत कार्यान्वयन और इसके प्रदर्शन अनुकूलन इतना स्पष्ट नहीं है

अन्य समाधान जो पूर्व-चुने निकटतम पड़ोसी देशों की जरूरत नहीं है, कुछ लोकैलिटी-संवेदनशील_हाशिंग पर आधारित होगा

मुझे लगता है कि यह काफी सामान्य समस्या हो सकती है, और अच्छे समाधान मौजूद हो सकते हैं , मैं पहिया को फिर से बदलने के लिए नहीं चाहता।

आवेदन:

  • कैश इलाके में सुधार, इस बात पर विचार करते हुए कि मेमोरी एक्सेस अक्सर ग्राफ-ट्रवर्सल की कमी है
  • यह अनस्ट्रक्टेड ग्रिड के प्रक्षेपण को तेज कर सकता है, अधिक विशेष रूप से नोड्स के लिए खोज करता है जो स्मापल के निकट हैं (जैसे रेडियल-बेस फंक्शन के केंद्र)।

मैं कहूंगा कि अंतरिक्ष भरने घटता (एसपीसी) एक रैखिक क्रम में अंतरिक्ष में निकटता के मानचित्र के मानक समाधान हैं। सबसे आम लोग हिल्बर्ट-क्यूव्स और जेड-कर्व्स (मॉर्टन ऑर्डर) हैं

हिल्बर्ट घटता का सबसे निकटता मानचित्रण है, लेकिन ये गणना करने के लिए कुछ महंगे हैं। Z- ऑर्डरिंग में अभी भी एक अच्छी निकटता मानचित्रण है लेकिन गणना करना बहुत आसान है। Z- ऑर्डरिंग के लिए, प्रत्येक आयाम के बिट्स को दबाने के लिए पर्याप्त है। पूर्णांक मानों को मानते हुए, यदि आपके पास 64 बिट 3 डी पॉइंट (एक्स, वाई, जेड) है, तो z- मान $ x_0, y_0, z_0, x_1, y_1, z_1, ... x_63, y_63, z_63 $, अर्थात् 1 9 2 बिट वैल्यू, प्रत्येक आयाम के पहले बिट से मिलकर, प्रत्येक आयाम के दूसरे बिट के बाद, और इसी तरह। यदि आपकी सरणी को उस z- मान के अनुसार ऑर्डर किया जाता है, तो अंक जो अंतरिक्ष में बंद हैं, वे आमतौर पर सरणी में भी बंद होते हैं।

ये उदाहरण फ़ंक्शन हैं जो एक z- मान ( nBitsPerValue आमतौर पर 32 या 64) में nBitsPerValue ( merge ) मान हैं:

public static long[] mergeLong(final int nBitsPerValue, long[] src) {
    final int DIM = src.length;
    int intArrayLen = (src.length*nBitsPerValue+63) >>> 6;
    long[] trg = new long[intArrayLen];

    long maskSrc = 1L << (nBitsPerValue-1);
    long maskTrg = 0x8000000000000000L;
    int srcPos = 0;
    int trgPos = 0;
    for (int j = 0; j < nBitsPerValue*DIM; j++) {
        if ((src[srcPos] & maskSrc) != 0) {
            trg[trgPos] |= maskTrg;
        } else {
            trg[trgPos] &= ~maskTrg;
        }
        maskTrg >>>= 1;
        if (maskTrg == 0) {
            maskTrg = 0x8000000000000000L;
            trgPos++;
        }
        if (++srcPos == DIM) {
            srcPos = 0;
            maskSrc >>>= 1;
        }
    }
    return trg;
}

आप फ्लोटिंग प्वाइंट वैल्यू (यदि आईईईई 754 के साथ एन्कोडेड हैं, जैसा कि वे आम तौर पर मानक कंप्यूटर में हैं) के बिट्स को भी छेड़ सकते हैं, लेकिन यह गैर-यूक्लिडियन दूरी गुणों में परिणाम है। आपको पहले नकारात्मक मानों को बदलना पड़ सकता है, यहां देखें, खंड 2.3।

संपादित करें दो टिप्पणियों के सवालों के जवाब:

1) मैं समझता हूं कि नियमित आयताकार ग्रिड के लिए जगह भरने की वक्र कैसे करें। हालांकि, अगर मैंने यादृच्छिक रूप से फ़्लोटिंग पॉइंट लगाए हैं, तो कई बिंदु एक बॉक्स में मैप कर सकते हैं। क्या वह एल्गोरिथ्म उस मामले में काम करेगा?

फ्लोटिंग पॉइंट (एफपी) वैल्यू का उपयोग करने के कई तरीके हैं सबसे सरल है उन्हें एक बड़े स्थिरांक के द्वारा उन्हें गुणा करके पूर्णांक मानों में बदलने के लिए। उदाहरण के लिए 6 अंकों की सटीकता को संरक्षित करने के लिए 10 ^ 6 तक सब कुछ गुणा करें।

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

यह निम्नानुसार काम करता है: चाल यह है कि अस्थायी बिंदु मानों में अनंत सटीक नहीं है, लेकिन यह 64 बिट तक सीमित है। इसलिए वे स्वचालित रूप से एक ग्रिड बनाते हैं। पूर्णांक मानों में अंतर यह है कि अस्थायी बिंदु मान एक वर्ग ग्रिड नहीं बनाते हैं, लेकिन एक आयताकार ग्रिड जहां आयत (0,0) से बढ़ते दूरी के साथ बड़ा हो जाता है। ग्रिड-आकार किसी निर्धारित बिंदु पर कितना सटीक उपलब्ध है, यह निर्धारित किया जाता है। (0,0) के करीब, सटीक (= ग्रिड_आकार) 10 ^ -28 है, करीब (1,1), यह 10 ^ -16 है यहाँ देखें। इस विकृत ग्रिड में अभी भी निकटता मानचित्रण है, लेकिन अब दूरी यूक्लिडियन नहीं है।

परिवर्तन करने के लिए यहां कोड है (जावा, यहां से लिया गया है ; सी ++ में आप केवल float को int डाल सकते हैं):

public static long toSortableLong(double value) {
    long r = Double.doubleToRawLongBits(value);
    return (r >= 0) ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}

public static double toDouble(long value) {
    return Double.longBitsToDouble(value >= 0.0 ? value : value ^ 0x7FFFFFFFFFFFFFFFL);
}

ये रूपांतरण रूपांतरित मूल्यों के क्रम को संरक्षित करता है, अर्थात् प्रत्येक दो एफपी मानों के लिए परिणामस्वरूप पूर्णांक के <,>, = के संबंध में एक ही क्रम होता है। गैर-यूक्लिडियन व्यवहार एक्सपोनेंट के कारण होता है जो बिट-स्ट्रिंग में एन्कोड किया जाता है। जैसा कि ऊपर उल्लेख किया गया है, यहां पर यहां पर चर्चा की गई है , हालांकि खंड 2.3, हालांकि कोड थोड़ा कम अनुकूलित है।

2) क्या कोई एल्गोरिथ्म है कि अंतरिक्ष में मेरे अंक चलने पर वक्र भरने वाली अवस्था के पुनरावृत्त अद्यतन कैसे करें? (यानी हर बार पूरे सरणी को पुन: क्रमबद्ध करने के बिना)

रिक्त स्थान भरने वाली वक्र एक विशिष्ट आदेश लगाती है, इसलिए प्रत्येक सेट के अंक के लिए केवल एक वैध ऑर्डरिंग है अगर कोई बिंदु स्थानांतरित हो जाता है, तो इसे नए स्तर पर निर्धारित किया जाता है, जो इसे z-value द्वारा निर्धारित किया जाता है।

अच्छी खबर यह है कि छोटे आंदोलन का मतलब होगा कि एक बिंदु अक्सर आपके सरणी के एक ही 'क्षेत्र' में रह सकता है। इसलिए यदि आप वास्तव में एक निश्चित सरणी का उपयोग करते हैं, तो आपको केवल इसके छोटे हिस्सों में बदलाव करना होगा।

यदि आपके पास कई चलती ऑब्जेक्ट हैं और सरणी बोझिल है, तो आप 'हिल ऑब्जेक्ट इंडेक्स' (एमएक्स-सीआईएफ-क्वाट्री, आदि) की जांच कर सकते हैं। मैं व्यक्तिगत तौर पर अपने पीएच-ट्री की सिफारिश कर सकता हूं। यह एक प्रकार का बिटवर्ड रेडिक्स-क्वैडिट्री है जो आंतरिक क्रम के लिए एक z- वक्र का उपयोग करता है। यह अद्यतन (और अन्य संचालन) के लिए काफी कुशल है हालांकि, मैं आमतौर पर केवल बड़े डेटासेट्स के लिए सुझाता हूं, छोटे डेटासेट के लिए एक सरल क्वाट्री आमतौर पर काफी अच्छा है।







nearest-neighbor