एकाधिक गुणों में सूची <T> सूची खोजने का सबसे तेज़ तरीका क्या है?

Question

मेरे पास एक प्रक्रिया है जिसे मैंने विरासत में मिला है कि मैं दूसरी भाषा से सी # में परिवर्तित हो रहा हूं। गणना करने के लिए बहुत सारे रिकॉर्ड (100K-200K) के माध्यम से प्रक्रिया लूप में कई कदम हो सकते हैं। उन प्रक्रियाओं के भाग के रूप में यह आमतौर पर कुछ मूल्यों को पुनर्प्राप्त करने के लिए एक और सूची में एक लुकअप करता है। मैं आम तौर पर इस तरह की चीज को एसक्यूएल कथन में ले जाऊंगा (और हमारे पास जहां हम सक्षम हैं) लेकिन इन मामलों में वास्तव में ऐसा करने का एक आसान तरीका नहीं है। कुछ स्थानों पर हमने कोड को संग्रहीत प्रक्रिया में बदलने का प्रयास किया है और फैसला किया है कि यह लगभग काम नहीं कर रहा था और साथ ही हमने आशा की थी।

प्रभावी ढंग से, कोड इस करता है:

var match = cost.Where(r => r.ryp.StartsWith(record.form.TrimEnd()) && 
         r.year == record.year && 
         r.period == record.period).FirstOrDefault(); 

लागत एक स्थानीय सूची प्रकार है। अगर मैं केवल एक फ़ील्ड पर खोज कर रहा था तो शायद मैं इसे सिर्फ एक शब्दकोश में ले जाऊंगा। रिकॉर्ड हमेशा अद्वितीय नहीं होते हैं।

जाहिर है, यह वास्तव में धीमा है।

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

क्या कोई अन्य परियोजनाएं (ओपन सोर्स या वाणिज्यिक) हैं जो इस तरह की चीज करते हैं?

संपादित करें:

मैं कुछ प्रतिक्रिया के आधार पर और खोज पाया Power Collections जो शब्दकोशों है कि कुंजी है कि अद्वितीय नहीं हैं का समर्थन करता है था।

मैंने ToLookup() का परीक्षण किया जो बहुत अच्छा काम करता है - यह अभी भी मूल कोड जितना तेज़ नहीं है, लेकिन यह कम से कम स्वीकार्य है। यह 45 सेकंड से 3-4 सेकंड तक नीचे है। मैं अन्य लुक अप के लिए ट्री संरचना पर एक नज़र डालेगा।

धन्यवाद।

Answer 1

100K-200K वस्तुओं की सूची के माध्यम से लूपिंग में बहुत लंबा समय नहीं लगता है। नेस्टेड लूप (एन^2) का उपयोग करके सूची में मेल खाने वाले आइटम ढूंढना लंबा लगता है। मैं अनुमान लगाता हूं कि आप क्या कर रहे हैं (क्योंकि आपके पास स्थानीय मिलान चर के लिए असाइनमेंट है)।

यदि आप आइटम को जल्दी से मिलान करना चाहते हैं, तो .ToLookup का उपयोग करें।

var lookup = cost.ToLookup(r => new {r.year, r.period, form = r.ryp}); 

foreach(var group in lookup) 
{ 
    // do something with items in group. 
} 

आपके प्रारंभिक मानदंड कुंजी-आधारित मिलान के लिए परेशानी है। उस समस्या से संपर्क करने का एक तरीका है कुंजी उत्पन्न करते समय इसे अनदेखा करना।

var lookup = cost.ToLookup(r => new {r.year, r.period }); 
var key = new {record.year, record.period}; 
string lookForThis = record.form.TrimEnd(); 
var match = lookup[key].FirstOrDefault(r => r.ryp.StartsWith(lookForThis)) 

आदर्श रूप से, आप एक बार लुकअप बनाएंगे और कई प्रश्नों के लिए इसका पुन: उपयोग करेंगे। भले ही आपने नहीं किया ... भले ही आपने हर बार लुकअप बनाया हो, फिर भी यह एन^2 से तेज होगा।

Answer 2

निश्चित रूप से आप इससे बेहतर कर सकते हैं। आइए इस बात पर विचार करें कि जब आप एक फ़ील्ड से पूछना चाहते हैं तो शब्दकोश केवल उपयोगी नहीं होते हैं; आप आसानी से एक शब्दकोश प्राप्त कर सकते हैं जहां कुंजी एक अपरिवर्तनीय मान है जो कई क्षेत्रों को जोड़ती है।

// should be immutable, GetHashCode and Equals should be implemented, etc etc 
struct Key 
{ 
    public int year; 
    public int period; 
} 

और फिर एक IDictionary<Key, ICollection<T>> या इसी तरह में अपने डेटा पैकेज जहां T अपनी वर्तमान सूची के प्रकार है: इस विशेष क्वेरी के लिए तो, एक तत्काल सुधार एक महत्वपूर्ण प्रकार बनाने के लिए किया जाएगा। इस तरह आप प्रत्येक पुनरावृत्ति में मानी गई पंक्तियों की संख्या पर भारी कटौती कर सकते हैं।

अगले कदम मान प्रकार के रूप में एक ICollection<T> लेकिन एक trie नहीं उपयोग करने के लिए होगा (this होनहार लग रहा है) है, जो तार एक निर्दिष्ट उपसर्ग कि खोजने के अनुरूप एक डेटा संरचना है।

अंत में, एक मुक्त माइक्रो-ऑप्टिमाइज़ेशन लूप से TrimEnd लेना होगा।

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