एल्गोरिदम

Question

पर सहायता चाहिए मुझे एल्गोरिदम पर सहायता चाहिए। मेरे पास 6 अंकों के साथ यादृच्छिक रूप से जेनरेट की गई संख्याएं हैं I पसंद;

वहाँ लगभग 1 मिलियन उन्हें लाइन द्वारा एक फ़ाइल लाइन में बचाया के हैं। मुझे उन नियमों के अनुसार फ़िल्टर करना होगा जिन्हें मैं नीचे वर्णित करने का प्रयास करता हूं।

एक संख्या लें, इसे अन्य अंकों के अंकों से तुलना करें। यदि कोई संख्या एक अंकों के साथ तुलनात्मक संख्या में एक के साथ एक अंक के साथ आता है, तो इसे हटा दें। मुझे संख्याओं का उपयोग करके इसे दिखाने दें।

हमारा नंबर है: 123456 1 के साथ पहले अंक को बढ़ाएं, इसलिए संख्या बन जाती है: 223456. फ़ाइल से सभी 223456 हटाएं। दूसरे अंक को 1 से बढ़ाएं, संख्या बन जाती है: 133456. फ़ाइल से सभी 133456 हटाएं, और इसी तरह ...

मैं इसे ठीक से कर सकता हूं जैसा कि मैंने वर्णन किया है लेकिन मुझे इसे "तेज़" होने की आवश्यकता है।

तो क्या कोई इस पर मेरी सहायता कर सकता है?

धन्यवाद।

Answer 1

यह एल्गोरिदम स्मृति में बहुत सारी संख्या रखेगा, लेकिन यह एक समय में फ़ाइल को एक नंबर संसाधित करेगा ताकि आपको वास्तव में इसे एक साथ में पढ़ने की आवश्यकता न हो। इसे संचालित करने के लिए आपको केवल IEnumerable<int> की आपूर्ति करने की आवश्यकता है।

public static IEnumerable<int> FilterInts(IEnumerable<int> ints) 
    { 
     var removed = new HashSet<int>(); 

     foreach (var i in ints) 
     { 
      var iStr = i.ToString("000000").ToCharArray(); 

      for (int j = 0; j < iStr.Length; j++) 
      { 
       var c = iStr[j]; 

       if (c == '9') 
        iStr[j] = '0'; 
       else 
        iStr[j] = (char)(c + 1); 

       removed.Add(int.Parse(new string(iStr))); 

       iStr[j] = c; 
      } 

      if (!removed.Contains(i)) 
       yield return i; 
     } 
    } 

आप फ़ाइल से एक IEnumerable<int> बनाने के लिए इस विधि का उपयोग कर सकते हैं:

public static IEnumerable<int> ReadIntsFrom(string path) 
    { 
     using (var reader = File.OpenText(path)) 
     { 
      string line; 
      while ((line = reader.ReadLine()) != null) 
       yield return int.Parse(line); 
     } 
    } 

Answer 2

स्टार्टर्स के लिए, मैं बस सभी संख्याओं को एक सरणी में पढ़ूंगा।

जब आप अंत में कर लेंगे, तो फ़ाइल को फिर से लिखें।

Answer 3

, एक ArrayList करने के लिए फ़ाइल से सभी नंबरों को ले लो तो:

, अंकों की संख्या

वेतन वृद्धि पहले सूत्र में संख्या पर प्रथम अंक के रूप थ्रेड की संख्या ले दूसरा दूसरे में धागा और फिर संख्या के बाकी के साथ तुलना,

यह के रूप में यह समानांतर प्रसंस्करण द्वारा गुजरना होगा तेजी से होगा ...

Answer 4

यह नियम आप का वर्णन कर रहे हैं की तरह लगता है आप abdcef लक्ष्य संख्या के लिए है एक खोजना चाहते हैं ऐसी संख्याएं होंगी जिनमें उपयुक्त स्थान पर + 1, बी + 1, सी + 1, डी + 1, ई + 1, या एफ + 1 होगा। आप फ़ाइल में लाइनों पर लूप करके ओ (एन) में ऐसा कर सकते हैं और यदि कोई अंक मेल नहीं खाता है तो लक्ष्य संख्या में प्रत्येक छः अंकों की संख्या को तुलना करके, आउटपुट फ़ाइल में नंबर लिखें।

Answer 5

सबसे पहले, चूंकि यह लगभग 1 मिलियन है, इसलिए आपने रैम में एल्गोरिदम बेहतर प्रदर्शन किया था, डिस्क पर नहीं, पहले, पहले किसी सरणी में सामग्री लोड करें, फिर सरणी को संशोधित करें, फिर परिणामों को वापस फ़ाइल में पेस्ट करें ।

मैं निम्नलिखित एल्गोरिदम का सुझाव दूंगा - एक सीधा। इस मामले में सभी लक्ष्य संख्याओं को पूर्ववत करें, इस मामले में 223456, 133456, 124456, 123556, 123466, 123457. अब सरणी पास करें और यदि संख्या इनमें से कोई भी नहीं है, तो इसे किसी अन्य सरणी में लिखें। वैकल्पिक रूप से यदि यह इन संख्याओं में से एक है, तो इसे हटाएं (अनुशंसित है कि आपकी डेटा संरचना में ओ (1) निकालें)

Answer 6

यह एक बहुआयामी सरणी के लिए संभावित मामले की तरह लगता है, और संभवतः असुरक्षित सी # कोड ताकि आप पॉइंटर का उपयोग कर सकें गणित इतनी बड़ी मात्रा में संख्या के माध्यम से पुनरावृत्त करने के लिए।

मुझे इसे और अधिक खोदना होगा, लेकिन यदि आप अनुक्रम में नहीं हैं, तो तुलनात्मक रूप से मैं गैर-रैखिक लुकअप के लिए एक शब्दकोश का उपयोग भी करूँगा।

Answer 7

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

फिर अपनी चाबियों के माध्यम से फिर से शुरू करें। प्रत्येक कुंजी के लिए, मानचित्र को उन मानों के लिए गलत पर सेट करें जिन्हें आप सूची से हटा रहे हैं।

अपनी सूची के माध्यम से एक और बार Iterate और सभी चाबियाँ प्राप्त करें जहां मान सत्य है। यह शेष संख्याओं की सूची है।

public List<int> FilterNumbers(string fileName) 
{ 
    StreamReader sr = File.OpenTest(fileName); 
    string s = ""; 
    Dictionary<int, bool> numbers = new Dictionary<int, bool>(); 
    while((s = sr.ReadLine()) != null) 
    { 
     int number = Int32.Parse(s); 
     numbers.Add(number,true); 
    } 
    foreach(int number in numbers.Keys) 
    { 
     if(numbers[number]) 
     { 
      if(numbers.ContainsKey(100000+number)) 
       numbers[100000+number]=false; 
      if(numbers.ContainsKey(10000+number)) 
       numbers[10000+number]=false; 
      if(numbers.ContainsKey(1000+number)) 
       numbers[1000+number]=false; 
      if(numbers.ContainsKey(100+number)) 
       numbers[100+number]=false; 
      if(numbers.ContainsKey(10+number)) 
       numbers[10+number]=false; 
      if(numbers.ContainsKey(1+number)) 
       numbers[1+number]=false; 
     } 
    } 

    List<int> validNumbers = new List<int>(); 
    foreach(int number in numbers.Keys) 
    { 
     validNumbers.Add(number); 
    } 
    return validNumbers; 
} 

इस रूप में मैं इस कंप्यूटर पर एक सी # संकलक की जरूरत नहीं है और मैं थोड़ा जंग लगी हूँ परीक्षण किया जाना पड़ सकता है। एल्गोरिदम कुछ मेमोरी बिट लेगा जो रैखिक समय में चलता है।

** संपादित करें ** जब भी संख्या 9 में से एक है तो यह समस्याएं चलाता है। मैं बाद में कोड अपडेट करूंगा।

Answer 8

सभी सुझाव (अभी तक) इनपुट लाइन है, जो आवश्यक नहीं है प्रति छह तुलना की आवश्यकता है। संख्याएं तारों के रूप में आ रही हैं, इसलिए स्ट्रिंग तुलना का उपयोग करें।

प्रारंभ @Armen Tsirunyan के विचार के साथ:

Precalculate सभी लक्ष्य संख्या, इस मामले 223,456, 133,456, 124,456 में , 123,556, 123,466, 123457.

लेकिन एक के बजाय तुलना, इसे एक स्ट्रिंग में बनाएं:

string arg = "223456 133456 124456 123556 123466 123457"; 

फिर इनपुट के माध्यम से पढ़ें (या तो फ़ाइल से या याद में)। स्यूडोकोड:

86 अनुदेश सेट प्रोसेसर में (बस नहीं:

foreach (string s in theBigListOfNumbers) 
    if (arg.indexOf(s) == -1) 
     print s; 

यह जोड़ने के लिए

संपादित इनपुट लाइन, कोई शब्दकोशों, नक्शे, iterators, आदि प्रति सिर्फ एक तुलना है इंटेल ब्रांड), इस तरह की खोजों को बहुत तेज है। एक स्ट्रिंग के भीतर किसी चरित्र की खोज करने के लिए, उदाहरण के लिए, केवल एक मशीन निर्देश है।

मुझे दूसरों को वैकल्पिक आर्किटेक्चर पर वजन करने के लिए कहना होगा।

Answer 9

इसके बारे में कैसे। आप संख्याओं को एक-एक करके संसाधित करते हैं। नंबर हैश टेबल NumbersOK और NumbersNotOK में संग्रहीत किए जाएंगे।

1. यदि यह NumbersOK
2. की एक हैश में NumbersNotOK यह जगह में नहीं है एक नंबर
3. ले लो यह हैश में एकल नंबर वेतन वृद्धि के प्रसरण है जाओ - NumbersNotOK।
4. यदि वे किसी भी प्रकार से मेल खाते हैं तो NumbersOK सदस्यों को हटा दें।
5. 1 से दोहराएं, फ़ाइल के अंत तक
6. फ़ाइल में NumbersOK सहेजें।

इस तरह आप एक बार सूची को पास कर देंगे। हैश टेबल केवल इस तरह के उद्देश्यों के लिए बनाया गया है और यह बहुत तेज़ होगा (कोई महंगा तुलना विधियां नहीं)।

इस एल्गोरिथ्म के रूप में यह जब वहाँ कुछ दोहरा नंबर दिए गए हैं संभाल नहीं करता है, पूर्ण में नहीं है, लेकिन यह कुछ फेरबदल के साथ संभाला जा सकता है ...

Answer 10

फिर भी एक होमवर्क सवाल की तरह लगता है ... सबसे तेजी से एक मिलियन नंबरों पर सॉर्ट करें एन लॉग (एन) होगा जो 1000000log (1000000) है जो 6 * 1000000 है जो 6 मिलियन नंबरों की तुलना में 6 संख्याओं की तुलना में समान है। तो एक सीधी तुलना सॉर्ट और निकालने से तेज होगी, क्योंकि सॉर्ट करने के बाद भी आपको हटाने के लिए तुलना करना होगा। जब तक, मेरी गणना पूरी तरह से लक्ष्य को याद नहीं कर लेती है।

कुछ और दिमाग में आता है। जब आप संख्या उठाते हैं, इसे हेक्स के रूप में पढ़ें और आधार 10 नहीं। तो हो सकता है कि कुछ बिटवाई ऑपरेटर किसी भी तरह से मदद कर सकें। अभी भी इस पर विचार कर क्या किया जा सकता है। अगर यह

संपादित करता है तो अपडेट होगा: वर्तमान में ग्रे कोड की रेखाओं पर विचार करना। 123456 (हमारी मूल संख्या) और 223456 या 133456 केवल एक अंक से बंद हो जाएंगे और एक ग्रे कोड कनवर्टर इसे तेज़ी से पकड़ लेगा। यहां देर रात है, इसलिए अगर किसी और को यह उपयोगी लगता है और समाधान दे सकता है ...