इन 2 डी सरणी में सबसे आम int कैसे ढूंढें?

Question

ठीक है, तो मैं बस सोच रहा हूं कि पेंट.नेट के लिए एक नई ग्राफिकल प्लगइन को कैसे कार्यान्वित किया जाए और मुझे यह जानने की आवश्यकता होगी कि पूर्णांक के 2 डी सरणी में सबसे आम पूर्णांक कैसे प्राप्त करें। क्या ऐसा करने के लिए सी # तरीके से अंतर्निहित है? या, क्या किसी के पास ऐसा करने का एक आसान तरीका है?

सरणी कुछ इस तरह दिखेगा:

300 300 300 300 300 300 300 
    0 150 300 300 300 300 300 
    0 0 150 300 300 300 300 
    0 0 0 0 300 300 300 
    0 0 0 0 150 300 300 
    0 0 0 0 0 150 300 
    0 0 0 0 0 0 300 

मुझे पता है कि 300 सरणी में सबसे आम संख्या है की आवश्यकता होगी। यदि कोई "सबसे आम" नहीं है तो बस केंद्र संख्या लौटाएं (सरणी की कमी हमेशा विषम x विषम होगी) 0.

मैं इसे "ब्रूट फोर्स" एल्गोरिदम का उपयोग करके कार्यान्वित कर दूंगा जब तक कि आप विशेषज्ञ नहीं आ सकते कुछ तेजी से।

किसी भी मदद की बहुत सराहना की जाएगी।

धन्यवाद!

संपादित करें: अधिक जानकारी ...

मूल्यों लगभग हमेशा बहुत (मेरे उदाहरण सरणी की तुलना में अधिक विविध) विविध किया जाएगा। मान 0-360 की सीमा में होंगे। एल्गोरिदम की गति के आधार पर सरणी का आकार 5x5 से लगभग 17x17 होगा। परिणाम एक पिक्सेल के लिए एक बड़ी छवि में एक बार गणना की जाएगी ... इतना तेज़ है। ;)

Answer 1

पेंट.नेट में स्थानीय हिस्टोग्राम इफेक्ट कोड पर नज़र डालें, विशेष रूप से LocalHistorgramEffect.RenderRect।

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

आरजीबी तीव्रता के बजाय ह्यू का समर्थन करने के लिए इसे अनुकूलित करना बल्कि मामूली होगा।

प्रदर्शन काफी अच्छा है, और आपके उद्देश्यों के लिए यह ओ (आर^2 + डब्ल्यू आर + एन डब्ल्यू) में संचालित होता है, जहां आर त्रिज्या है, डब्ल्यू छवि की चौड़ाई है, और एन है हिस्टोग्राम में स्तरों की संख्या।

-tjackson

Answer 2

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

मुझे लगता है कि आप भी मौजूदा संख्या एक्स, वर्तमान ऊपर और के लिए "सबसे आम" और जल्दी से बाहर दूसरी निकटतम उम्मीदवार के y जैसे ही आप की तुलना में (एन * मीटर कम है के रूप में रख सकता है) - (xy) कोशिकाओं को देखने के लिए छोड़ दिया गया, क्योंकि उस बिंदु पर रनर-अप शीर्ष उम्मीदवार को आगे बढ़ा सकता है।

इस तरह के इंटीजर ऑप्स बहुत तेज हैं; यहां तक ​​कि एक मेगापिक्सेल छवि के लिए ब्रूट फोर्स एल्गोरिदम केवल कुछ मिलीसेकंड लेना चाहिए।

मुझे लगता है कि आपने अपना मूल प्रश्न यह कहने के लिए संपादित किया है कि पिक्सेल 0..255 से मूल्य है - उस मामले में, निश्चित रूप से एक साधारण फ्लैट सरणी के साथ जाएं; यह आसानी से l1 dcache में फिट करने के लिए काफी छोटा है और एक फ्लैट सरणी में एक लुकअप तेज़ है।

[संपादित करें]: "कोई सबसे आम संख्या" मामले के साथ काम बहुत आसान है एक बार आप हिस्टोग्राम सरणी का निर्माण किया है: सब यह "सबसे" और उसे ढूंढने के लिए "दूसरा चलना है क्या करने के लिए आपके पास सबसे अधिक "सामान्य संख्याएं; यदि वे समान रूप से लगातार होते हैं, तो परिभाषा के अनुसार कोई भी सबसे आम नहीं है।

const int numLevels = 360; // you said each cell contains a number [0..360) 
int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i" 
int mostCommon = 0, runnerUp = 0; 
for (int i = 1 ; i < numLevels ; ++i) 
{ 
    if (levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon]) 
    { 
    runnnerUp = mostCommon; 
    mostCommon = i; 
    } 
} 

if (levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp]) 
{ 
    return mostCommon; 
} 
else 
{ 
    return CenterOfInputData; // (something like InputData[n/2][m/2]) 
} 

Answer 3

मैं सी # में कुछ इस तरह कैसे करना होगा?

कुछ इस तरह:

Dictionary<int, int> d = new Dictionary<int, int>(); 
foreach (int value in matrix) 
{ 
if (!d.ContainsKey(value)) 
    d.Add(value, 1); 
else 
    d[value] = d[value] + 1; 
} 
KeyValuePair<int, int> biggest = null; 
foreach (KeyValuePair<int, int> found in d) 
{ 
    if ((biggest == null) || (biggest.Value < found.Value)) 
    biggest = found; 
} 

Answer 4

एक विकल्प LINQ है - थोड़ा अक्षम गैर विशाल सरणी के लिए ठीक है, लेकिन:

var max = (from cell in data.Cast<int>() 
       group cell by cell into grp 
       select new { Key = grp.Key, Count = grp.Count() } into agg 
       orderby agg.Count descending 
       select agg).First(); 
    Console.WriteLine(max.Key + ": " + max.Count); 

या एक दांतेदार सरणी के साथ:

var max = (from row in data 
       from cell in row 
       group cell by cell into grp 
       select new {Key = grp.Key, Count = grp.Count()} into agg 
       orderby agg.Count descending 
       select agg).First(); 
    Console.WriteLine(max.Key + ": " + max.Count); 

असल में, मैं शायद एक शब्दकोश/गणना का उपयोग करता हूं। LINQ के बिना यह उदाहरण, केवल "क्योंकि":

Dictionary<int, int> counts = new Dictionary<int, int>(); 
    foreach (int value in data) 
    { 
     int count; 
     counts.TryGetValue(value, out count); 
     counts[value] = count + 1; 
    } 
    int maxCount = -1, maxValue = 0; 
    foreach (KeyValuePair<int, int> pair in counts) 
    { 
     if (pair.Value > maxCount) 
     { 
      maxCount = pair.Value; 
      maxValue = pair.Key; 
     } 
    } 
    Console.WriteLine(maxCount + ": " + maxValue); 

Answer 5

यदि गति आपकी प्राथमिक चिंता है, तो शब्दकोश का उपयोग न करें। बाइट्स की एक सरणी के साथ चिपकाओ। इसे आज़माएं:

// stores hit counts (0-360) 
short[] hitCounts = new short[361]; 

// iterate through 2d array and increment hit counts 
for (int i = 0; i < toEvaluate.Length; i++) 
{ 
    for (int j = 0; j < toEvaluate[i].Length; j++) 
     hitCounts[toEvaluate[i][j]]++; 
} 

int greatestHitCount = 0; // the hit count of the current greatest value 
int greatest = -1; // the current greatest valeu 

// iterate through values (0-360) and evalute hit counts 
for (int i = 0; i < hitCounts.Length; i++) 
{ 
    // the hit count of hitCounts[i] is higher than the current greatest hit count value 
    if (hitCounts[i] > greatestHitCount) 
    { 
     greatestHitCount = vals[i]; // store the new hit count 
     greatest = i; // store the greatest value 
    } 
    // there is already a value with the same hit count (which is the greatest) 
    else if (hitCounts[i] == greatestHitCount) 
     greatest = -1; // there are more than one value, we can't use this if it ends up being the greatest 
} 

if (greatest >= 0) // no greatest value found 
    return greatest; 

// figure out the middle x and y value 
int x = (toEvaluate.Length - 1)/2 + 1; 
int y = (toEvaluate[x].Length - 1)/2 + 1; 

// return the value at the center of the 2d array as the value 
return toEvaluate[x][y]; 

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

Answer 6

माइकल मुझे पोस्ट करने के लिए हरा, लेकिन मैं भी ऐसा होता है, कुछ इस तरह:

 int MaxValueIn2dArray(int[,] matrix) 
    { 
     var d = new int[360]; 
     int MaxValue = 0; 
     for (int x = 0; x <= matrix.GetUpperBound(0); x++) 
     { 
      for (int y = 0; y <= matrix.GetUpperBound(1); y++) 
      { 
       d[matrix[x, y]]++; 
      } 
     } 
     foreach (int value in d) 
     { 
      if (value > MaxValue) MaxValue = value; 
     } 
     return MaxValue; 
    } 

यह अपने विशेष जरूरतों के लिए अनुकूलित करने की आवश्यकता होगी।

Answer 7

आपकी छवि:

300+ 300+ 300+ 300 300 300 300 
    0+ 150+ 300+ 300 300 300 300 
    0+ 0+ 150+ 300 300 300 300 
    0 0 0 0 300 300 300 
    0 0 0 0 150 300 300 
    0 0 0 0 0 150 300 
    0 0 0 0 0 0 300 

में चिह्नित किए गए (+) संख्या अपने विंडो कर रहे हैं। डब्ल्यू, एच आपकी खिड़की आयाम है। bucket sorting लागू करें (जैसा कि अन्य लोगों ने सुझाया है क्योंकि आपकी मूल्य सीमाएं काफी सीमित हैं)। Crashworks सुझाव के अनुसार अपना मूल्यांकन आधे रास्ते में कटौती न करें। अभी तक अपना परिणाम न फेंकें। यह पहला चरण हैं।

300- 300- 300- 300 300 300 300 
    0. 150. 300. 300 300 300 300 
    0. 0. 150. 300 300 300 300 
    0+ 0+ 0+ 0 300 300 300 
    0 0 0 0 150 300 300 
    0 0 0 0 0 150 300 
    0 0 0 0 0 0 300 

अपनी विंडो को बदलें। जोड़ने के बजाय, पिछली पंक्ति/कॉलम में बाल्टी घटाएं और नई बाल्टी जोड़ें। इस तरह आप प्रत्येक पिक्सेल 2 (डब्ल्यू + एच) टाइम्स की जांच करते हैं, यानी जब यह विंडो सीमा पार हो जाता है, तो w * h times के बजाय, यानी यह पिक्सेल विंडो में है, एक निष्पक्ष कार्यान्वयन में।

दूसरे शब्दों में, आप इस तरह अपने खिड़की बढ़ने की जरूरत है:

| ^->|^
| | | | 
| | | | 
V->| V->| 

मैं तुम्हें एक nonlinear घुमाव फिल्टर लागू करने के लिए कोशिश कर रहे हैं मान।

सुधार स्वागत है।

Answer 8

सभी मैं प्रदान करेंगे किसी एल्गोरिथ्म कि हर कोशिका की जाँच करता है के लिए है दो अतिरिक्त बातें करते हैं (जो काफी आपको बस इतना करना उम्मीद थी क्या है):

1.) यकीन है कि नियमित बाहर निकलता बनाओ जब गिनती वर्तमान में सबसे आम मूल्य> (एम एक्स एन/2) के लिए। अगर आपके ग्रिड पर 50% कवरेज है तो यह सबसे आम मूल्य है, जारी रखने की कोई आवश्यकता नहीं है। यदि आपका दिनचर्या केवल उस समय का सही होना चाहिए तो आप प्रतिशत को कम कर सकते हैं और इसे एक ह्युरिस्टिक के रूप में देख सकते हैं। आप कुछ विश्लेषण भी चला सकते हैं जो कवरेज की तरह कुछ थूकता है> 37.6% तब 99.9% समय यह सबसे आम मूल्य होगा और फिर उस प्रतिशत का उपयोग करें।

2.) यदि कोई तरीका है कि आप किन पक्ष, कोने या सामान्य स्थान (बाहरी किनारों, मध्य, आदि) में निर्धारित कर सकते हैं तो सबसे आम मान होने की संभावना है, तो आप उस क्रम में स्कैन कर सकते हैं जो एक साथ ऊपर ऑप्टिमाइज़ेशन 1 के साथ आपके बहुत सारे स्कैनिंग को बंद कर दिया जा सकता है। उदाहरण के लिए आपके उदाहरण में शीर्ष दाएं सामान्य मूल्य पर भारी है। यदि यह कुछ ह्युरिस्टिक द्वारा निर्धारित किया गया था तो आप कुछ फैशन में ऊपरी दाएं से नीचे बाईं ओर स्कैन कर सकते हैं। यदि आवश्यक स्कैनिंग का पैटर्न जटिल है, तो इसे पूर्व-उत्पन्न करें।