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

मैंने जल्दी से कुछ नमूना कोड एक साथ रखा है जो इस मुद्दे को काफी सरल तरीके से दिखाता है।

class Program
    {
        private static readonly Word[] _words =
        {
            new Word("Beef"),
            new Word("Bull"),
            new Word("Space")
        };

        static void Main()
        {
            var tasks = new List<Task>();

            foreach (var word in _words)
            {
                tasks.Add(CheckRelationShipsAsnc(word));
            }

            Task.WhenAll(tasks);
        }

        static async Task CheckRelationShipsAsnc(Word leftWord)
        {
            await Task.Run(() =>
            {
                foreach (var rightWord in _words)
                {
                    if(leftWord.Text.First() == rightWord.Text.First())
                    {
                        leftWord.RelationShips.Add(rightWord);
                    }
                }
            });
        }
    }

    class Word
    {
        public string Text { get; }
        public List<Word> RelationShips { get; } = new List<Word>();

        public Word(string text)
        {
            if(string.IsNullOrEmpty(text)) throw new ArgumentException();
            Text = text;
        }

        public override string ToString()
        {
            return $"{Text} ({RelationShips.Count} relationships)";
        }
    }

अपेक्षित परिणाम यह होगा कि "अंतरिक्ष" का कोई संबंध नहीं है जबकि "बुल" और "बीफ" शब्दों का एक दूसरे से एक संबंध है। मुझे जो मिलता है वह यह है कि सभी शब्दों का कोई संबंध नहीं है। मुझे यह समझने में परेशानी हो रही है कि वास्तव में समस्या क्या है।

0
Mats 31 मई 2020, 21:59

2 जवाब

सबसे बढ़िया उत्तर

आपको Main विधि async भी बनानी चाहिए और Task.WhenAll. अन्यथा WhenAll के लिए परिणाम कार्य अपना निष्पादन नहीं चलाएगा। आप Linq का उपयोग करके कार्यों के निर्माण को आसान भी बना सकते हैं

static async Task Main()
{
    var tasks = _words.Select(CheckRelationShipsAsync);
    await Task.WhenAll(tasks);
}

आप का भी इस्तेमाल कर सकते हैं Wait() या WaitAll विधि, जो समकालिक रूप से चलती है और वर्तमान थ्रेड को ब्लॉक करती है (इसलिए, यह अनुशंसित दृष्टिकोण नहीं है)। लेकिन इसके लिए Main विधि async बनाने की आवश्यकता नहीं है

var tasks = _words.Select(CheckRelationShipsAsync);
var task = Task.WhenAll(tasks);
task.Wait();

या

static void  Main()
{
    var tasks = _words.Select(CheckRelationShipsAsync);
    Task.WaitAll(tasks.ToArray());
}

दूसरा बिंदु यह है कि जब आप रिश्तों की जांच करते हैं तो आपने शब्द को ही नहीं छोड़ा है, और अंत में प्रत्येक शब्द का संबंध स्वयं के साथ होता है। अपेक्षित परिणाम प्राप्त करने के लिए आपको leftWord != rightWord स्थिति को foreach लूप के अंदर जोड़ना चाहिए

अपेक्षित परिणाम यह होगा कि "अंतरिक्ष" का कोई संबंध नहीं है जबकि "बुल" और "बीफ" शब्दों का एक दूसरे से एक संबंध है।

3
Pavel Anikhouski 1 जून 2020, 11:10

आपके एल्गोरिथ्म में एक O(n^2) समय जटिलता है। यदि आपके पास एक-दूसरे से तुलना करने के लिए बड़ी संख्या में आइटम हैं तो यह एक समस्या है। उदाहरण के लिए, यदि आपके पास 1000 आइटम हैं, तो यह आपको 1000 * 1000 = 1000000 (एक मिलियन) तुलना देता है।

दूसरे दृष्टिकोण का उपयोग करने पर विचार करें। मुझे नहीं पता कि यह आपकी वास्तविक समस्या पर लागू होता है या नहीं, लेकिन इस उदाहरण के लिए, यह मानते हुए कि प्रत्येक शब्द एक बड़े अक्षर A..Z से शुरू होता है, आप संबंधित शब्दों को पहले अक्षर द्वारा शब्द की लंबाई 26 की एक सरणी में संग्रहीत कर सकते हैं सूचियाँ।

var a = new List<Word>[26];

// Initialize array with empty lists
for (int i = 0; i < a.Length; i++) {
    a[i] = new List<Word>();
}

// Fill array with related words
foreach (var word in _words) {
    a[word.Text[0] - 'A'].Add(word); // Subtracting 'A' yields a zero-based index.
}

ध्यान दें कि आपके मूल समाधान में दो नेस्टेड लूप हैं (जहां एक CheckRelationShipsAsnc के कॉल के अंदर छिपा हुआ है)। इस समाधान में लूप का केवल एक स्तर है और यहां तक ​​O(n) की समय जटिलता है।

अब आप सभी संबंधित शब्दों को एक सूची में संबंधित सरणी स्थिति में पाते हैं। इस जानकारी को लेकर अब आप उसी सूची में आने वाले शब्दों को तार-तार कर सकते हैं। यह हिस्सा अभी भी O(n^2) है; हालांकि, यहां n बहुत छोटा है, क्योंकि केवल उन शब्दों को संदर्भित करता है जो संबंधित सूचियों में हैं, लेकिन प्रारंभिक _words सरणी की लंबाई नहीं है।

आपकी वास्तविक समस्या कैसे तैयार की जाती है, इस पर निर्भर करते हुए, मेरी सरणी a के स्थान पर Dictionary<char, List<Word>> का उपयोग करना बेहतर हो सकता है। सरणी समाधान के लिए एक अनुक्रमणिका की आवश्यकता होती है। वास्तविक दुनिया की समस्या में, संबंध स्थिति एक सूचकांक के रूप में तैयार करने योग्य नहीं हो सकती है। शब्दकोश को एक कुंजी की आवश्यकता होती है और किसी भी प्रकार की वस्तु को कुंजी के रूप में उपयोग किया जा सकता है। देखें: Dictionary<TKey,TValue> Class के टिप्पणियां अनुभाग।

इस तरह से अनुकूलित एक एल्गोरिदम एक मल्टीटास्किंग समाधान से भी तेज हो सकता है।

3
Olivier Jacot-Descombes 1 जून 2020, 16:39