बड़े संग्रह के लिए LINQ प्रदर्शन

Question

मेरे पास तारों का एक बड़ा संग्रह (1 एम तक) वर्णानुक्रम से क्रमबद्ध है। मैंने हैशसेट, सॉर्टेड डिक्शनरी और डिक्शनरी का उपयोग करके इस संग्रह के खिलाफ LINQ प्रश्नों के साथ प्रयोग किया है। मैं संग्रह को स्थिर कैशिंग कर रहा हूं, यह आकार में 50 एमबी तक है, और मैं हमेशा कैश संग्रह के खिलाफ LINQ क्वेरी को कॉल कर रहा हूं। मेरी समस्या निम्नानुसार है:

संग्रह प्रकार के बावजूद, प्रदर्शन SQL (200ms तक) से अधिक गरीब है। अंतर्निहित SQL तालिकाओं के खिलाफ एक समान क्वेरी करते समय, प्रदर्शन बहुत तेज़ (5-10 मिमी) होता है।

public static string ReturnSomething(string query, int limit) 
{ 
    StringBuilder sb = new StringBuilder(); 
    foreach (var stringitem in MyCollection.Where(
     x => x.StartsWith(query) && x.Length > q.Length).Take(limit)) 
    { 
     sb.Append(stringitem); 
    } 

    return sb.ToString(); 
} 

यह मेरी समझ है कि HashSet, शब्दकोश, आदि मानक गणना के बजाय द्विआधारी पेड़ खोज का उपयोग कर लुकअप लागू है: इस प्रकार मैं अपने LINQ प्रश्नों को लागू किया है। उन्नत प्रदर्शन प्रकारों में उच्च प्रदर्शन LINQ क्वेरी के लिए मेरे विकल्प क्या हैं?

Answer 1

अपने वर्तमान कोड आप Dictionary/SortedDictionary/HashSet संग्रह में से विशेष सुविधाओं में से किसी का उपयोग नहीं करते हैं, आपको उन्हें उसी तरह है कि आप एक List का प्रयोग करेंगे प्रयोग कर रहे हैं। यही कारण है कि आप प्रदर्शन में कोई अंतर नहीं देखते हैं।

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

मैंने इसका परीक्षण करने के लिए नीचे दिया गया वर्ग लिखा था। यदि मैं इसे दस लाख स्ट्रिंग के साथ पॉप्युलेट करता हूं और आठ वर्ण स्ट्रिंग के साथ खोज करता हूं तो यह लगभग 3 एमएस में सभी संभावित मैचों के माध्यम से चिपक जाता है। एक वर्ण स्ट्रिंग के साथ खोज सबसे खराब मामला है, लेकिन यह लगभग 4 एमएस में पहले 1000 मैचों को पाता है। एक चरित्र तार के लिए सभी मैचों को ढूंढना लगभग 25 एमएस लगता है।

कक्षा 1, 2, 4 और 8 वर्ण कुंजी के लिए अनुक्रमणिका बनाता है। यदि आप अपने विशिष्ट डेटा और जो खोजते हैं उसे देखते हैं, तो आप यह चुनने में सक्षम होना चाहिए कि आपकी स्थितियों के लिए इसे अनुकूलित करने के लिए कौन से इंडेक्स बनाना है।

public class IndexedList { 

    private class Index : Dictionary<string, List<string>> { 

     private int _indexLength; 

     public Index(int indexLength) { 
      _indexLength = indexLength; 
     } 

     public void Add(string value) { 
      if (value.Length >= _indexLength) { 
       string key = value.Substring(0, _indexLength); 
       List<string> list; 
       if (!this.TryGetValue(key, out list)) { 
        Add(key, list = new List<string>()); 
       } 
       list.Add(value); 
      } 
     } 

     public IEnumerable<string> Find(string query, int limit) { 
      return 
       this[query.Substring(0, _indexLength)] 
       .Where(s => s.Length > query.Length && s.StartsWith(query)) 
       .Take(limit); 
     } 

    } 

    private Index _index1; 
    private Index _index2; 
    private Index _index4; 
    private Index _index8; 

    public IndexedList(IEnumerable<string> values) { 
     _index1 = new Index(1); 
     _index2 = new Index(2); 
     _index4 = new Index(4); 
     _index8 = new Index(8); 
     foreach (string value in values) { 
      _index1.Add(value); 
      _index2.Add(value); 
      _index4.Add(value); 
      _index8.Add(value); 
     } 
    } 

    public IEnumerable<string> Find(string query, int limit) { 
     if (query.Length >= 8) return _index8.Find(query, limit); 
     if (query.Length >= 4) return _index4.Find(query,limit); 
     if (query.Length >= 2) return _index2.Find(query,limit); 
     return _index1.Find(query, limit); 
    } 

} 

Answer 2

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

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

इनमें से कोई भी LINQ का उपयोग नहीं करता है, और यह आपके विशेष मामले के लिए बहुत विशिष्ट है, लेकिन इसे काम करना चाहिए। अगर मुझे इनमें से कोई भी समझ में नहीं आता है तो मुझे बताएं।

Answer 3

बस अपने कोड को देखते हुए, मैं कहूँगा कि आप तुलना शॉर्ट सर्किट का लाभ लेने के लिए जब बूलियन ऑपरेटरों के उपयोग को पुन: व्यवस्थित करना चाहिए:

foreach (var stringitem in MyCollection.Where(
    x => x.Length > q.Length && x.StartsWith(query)).Take(limit)) 

लंबाई की तुलना हमेशा एक हे होने के लिए (जा रहा है 1) ऑपरेशन (चूंकि लंबाई स्ट्रिंग के हिस्से के रूप में संग्रहीत की जा रही है, यह प्रत्येक चरित्र को हर बार गिनती नहीं करता है), जबकि स्टार्ट्सविथ को कॉल ओ (एन) ऑपरेशन होने जा रहा है, जहां एन क्वेरी की लंबाई है (या स्ट्रिंग की लंबाई, जो भी छोटा हो)।

स्टार्ट्स के साथ कॉल से पहले लंबाई की तुलना करके, यदि यह तुलना विफल हो जाती है, तो आप अपने आप को कुछ अतिरिक्त चक्र बचाते हैं जो बड़ी संख्या में वस्तुओं को संसाधित करते समय जोड़ सकते हैं।

मुझे नहीं लगता कि एक लुकअप टेबल आपकी मदद करने जा रही है, क्योंकि जब आप पूरी कुंजी की तुलना कर रहे हैं, तो कुंजी के कुछ भाग नहीं, जैसे कि आप स्टार्ट्सविथ को कॉल के साथ कर रहे हैं।

इसके बजाय, आप एक वृक्ष संरचना का उपयोग करके बेहतर हो सकते हैं जो सूची में शब्दों में अक्षरों के आधार पर विभाजित होता है।

हालांकि, उस बिंदु पर, आप वाकई बस पुन: प्रयास कर रहे हैं कि SQL सर्वर क्या कर रहा है (इंडेक्स के मामले में) और यह आपके हिस्से पर प्रयास का एक दोहराव होगा।

Answer 4

मुझे लगता है कि आपके पास कॉलम पर एक अनुक्रमणिका है, इसलिए SQL सर्वर O (n) के बजाय ओ (लॉग (एन)) संचालन में तुलना कर सकता है।SQL सर्वर व्यवहार का अनुकरण करने के लिए, एक क्रमबद्ध संग्रह का उपयोग करें और सभी स्ट्रिंग्स जैसे कि s> = क्वेरी खोजें और तब मानों को देखें जब तक कि आपको कोई ऐसा मान न मिले जो एस से शुरू नहीं होता है और फिर मानों पर एक अतिरिक्त फ़िल्टर करता है। यह एक रेंज स्कैन (ओरेकल) या एक इंडेक्स तलाश (एसक्यूएल सर्वर) कहा जाता है।

यह कुछ उदाहरण कोड है जो असीमित लूप में जाने की संभावना है या एक-ऑफ त्रुटियां हैं क्योंकि मैंने इसका परीक्षण नहीं किया है, लेकिन आपको यह विचार मिलना चाहिए।

// Note, list must be sorted before being passed to this function 
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) { 
    int low = 0, high = list.Count - 1; 
    while (high > low) { 
     int mid = (low + high)/2; 
     if (list[mid] < query) 
      low = mid + 1; 
     else 
      high = mid - 1; 
    } 

    while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length) 
     yield return list[low]; 
     low++; 
    } 
} 

Answer 5

आप दिए गए उपसर्ग आप को लागू करने पर एक नज़र लेने के लिए चाहते हो सकता है के साथ स्ट्रिंग की एक सूची को देख अनुकूलन करने के लिए कोशिश कर रहे हैं एक Trie (नहीं एक नियमित रूप से tree साथ ही समझा जाता है) सी # में डेटा संरचना।

कोशिशें बहुत तेज उपसर्ग लुकअप प्रदान करती हैं और इस तरह के ऑपरेशन के लिए अन्य डेटा संरचनाओं की तुलना में बहुत छोटी मेमोरी ओवरहेड होती हैं।

सामान्य रूप से LINQ से ऑब्जेक्ट्स के बारे में। एसक्यूएल की तुलना में गति में कमी करना असामान्य नहीं है। नेट littered with articles अपने प्रदर्शन का विश्लेषण कर रहा है।

Answer 6

मुझे लगता है कि समस्या यह है कि लिंक का इस तथ्य का उपयोग करने का कोई तरीका नहीं है कि आपका अनुक्रम पहले से ही क्रमबद्ध है। विशेष रूप से यह नहीं पता कि StartsWith फ़ंक्शन लागू करने से ऑर्डर बरकरार रहता है।

मैं के साथ List.BinarySearch विधि का उपयोग करने का सुझाव दूंगा जो केवल पहले क्वेरी वर्णों की तुलना करता है (यह मुश्किल हो सकता है, क्योंकि यह स्पष्ट नहीं है, अगर क्वेरी स्ट्रिंग हमेशा पहला या दूसरा पैरामीटर होगा ())।

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

फिर आप अपनी क्वेरी स्ट्रिंग से मेल खाने वाले सभी तत्वों को खोजने के लिए लौटाए गए इंडेक्स (दोनों दिशाओं में!) से शुरू करना चाहते हैं।