विशिष्ट गुण वाले उच्च आयाम वाले सरणी में खोजें

Question

मेरे पास एक 3 डी सरणी है जिसमें मूल्य monotonic हैं। सभी कैसे खोजें (एक्स, वाई), | एफ (एक्स, वाई, जेड) - v1 | < टी।

Answer 1

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

Answer 2

प्रत्येक मान के लिए, निम्न चरणों पर अमल (जैसे v1।):

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

सबसे खराब मामला जटिलता ओ (ओ (2 डी एल्गोरिदम) * एन) होगी।

एकाधिक मानों के लिए (v2, आदि) फ़ंक्शन मूल्यांकन का कैश रखें, और प्रत्येक मान के लिए एल्गोरिदम को फिर से निष्पादित करें। 100^3 के लिए, एक घने सरणी पर्याप्त होगी।

यह एक आइसोसुरफेस निष्कर्षण एल्गोरिदम के रूप में सोचने के लिए उपयोगी हो सकता है, हालांकि आपकी monotonicity बाधा इसे आसान बनाता है।

Answer 3

चूंकि फ़ंक्शन कम नहीं हो रहा है, मुझे लगता है कि आप बाइनरी खोजों के साथ कुछ कर सकते हैं।
(x, 1, 1) (कॉलम) वेक्टर के अंदर आप अपनी आवश्यकता से मेल खाने वाली सीमा को खोजने के लिए बाइनरी खोज कर सकते हैं जो O(log(n)) होगा।
यह जानने के लिए कि कौन से कॉलम वैक्टर देखने के लिए आप (x, y, 1) (स्लाइस) वैक्टर पर बाइनरी खोज कर सकते हैं, यह पता लगाने के लिए कि क्या वे मूल्य O(log(n)) ले सकते हैं, यह जानने के लिए केवल पहले और अंतिम बिंदुओं की जांच कर रहे हैं।
यह जानने के लिए कि कौन से स्लाइस आपको देखने के लिए बाइनरी कर सकते हैं पूरे घन को 4 अंक ((0, 0), (x, 0), (x, y), (0, y)) की जांच कर सकते हैं जो O(log(n)) ले जाएगा।
कुल मिलाकर, एल्गोरिदम log(z) + a * log(y) + b * log(x) ले जाएगा जहां a मिलान स्लाइस की संख्या और b मेल खाने वाले कॉलम की संख्या है।
खराब तरीके से खराब स्थिति की गणना O(y * z * log(x)) है।

Answer 4

3 डी सरणी होगा- है प्रत्येक आयाम में गैर-घटते तो हम जानते हैं कि अगर

f(x0, y0, z0) < v1 - t 
      or 
f(x1, y1, z1) > v1 + t 

तो उप सरणी f(x0...x1, y0...y1, z0...z1) का कोई तत्व किसी भी दिलचस्प बात हो सकती है। इस उदाहरण के लिए विचार है कि

f(x0, y0, z0) <= f(x, y0, z0) <= f(x, y, z0) <= f(x, y, z) 

(x1, y1, z1) के लिए उप सरणी के प्रत्येक (x, y, z) लिए रखती है, और एक समान संबंध (उलट दिशा के साथ) रखती है देखने के लिए। इस प्रकार f(x0, y0, z0) और f(x1, y1, z1) क्रमशः उप-सरणी का न्यूनतम और अधिकतम मान हैं।

template<typename T, typename CBack> 
int values(Mat3<T>& data, T v0, T v1, CBack cback, 
      int x0, int y0, int z0, int x1, int y1, int z1) { 
    int count = 0; 
    if (x1 - x0 <= 2 && y1 - y0 <= 2 && z1 - z0 <= 2) { 
     // Small block (1-8 cells), just scan it 
     for (int x=x0; x<x1; x++) { 
      for (int y=y0; y<y1; y++) { 
       for (int z=z0; z<z1; z++) { 
        T v = data(x, y, z); 
        if (v >= v0 && v <= v1) cback(x, y, z); 
        count += 1; 
       } 
      } 
     } 
    } else { 
     T va = data(x0, y0, z0), vb = data(x1-1, y1-1, z1-1); 
     count += 2; 
     if (vb >= v0 && va <= v1) { 
      int x[] = {x0, (x0 + x1) >> 1, x1}; 
      int y[] = {y0, (y0 + y1) >> 1, y1}; 
      int z[] = {z0, (z0 + z1) >> 1, z1}; 
      for (int ix=0; ix<2; ix++) { 
       for (int iy=0; iy<2; iy++) { 
        for (int iz=0; iz<2; iz++) { 
         count += values<T, CBack>(data, v0, v1, cback, 
                x[ix], y[iy], z[iz], 
                x[ix+1], y[iy+1], z[iz+1]); 
        } 
       } 
      } 
     } 
    } 
    return count; 
} 

कोड मूल रूप से एक उप सरणी स्वीकार करता है और बस खोज करता है, तो सबसे कम तत्व बहुत बड़ी है या उच्चतम तत्व को छोड़ देता है:

एक साधारण खोज दृष्टिकोण तो एक पुनरावर्ती उपखंड योजना का उपयोग करके लागू किया जा सकता बहुत छोटा है, और अन्यथा 8 उप-cubes में सरणी विभाजित करता है। रिकर्सन समाप्त होता है जब उप-सरणी छोटी होती है (2x2x2 या उससे कम) और इस मामले में एक पूर्ण स्कैन किया जाता है।

प्रयोगात्मक मैंने पाया कि यह काफी सरल दृष्टिकोण के साथ 100x200x300 max(f(i-1,j,k), f(i,j-1,k), f(i,j,k-1)) + random(100) के तत्व f(i,j,k) की स्थापना द्वारा उत्पन्न तत्वों के साथ एक सरणी (25 तत्वों से प्रत्येक के लिए जाँच की बीच मूल्य और टी = 1 तत्वों का केवल 3% की जाँच के लिए खोजा जा सकता है तत्व सीमा के भीतर पाया गया)।

Data 100x200x300 = 6000000 elements, range [83, 48946] 
Looking for [24594-1=24593, 24594+1=24595] 
Result size = 6850 (5.4 ms) 
Full scan = 6850 (131.3 ms) 
Search count = 171391 (25.021x, 2.857%)