ऑर्डरबी से कैसे बचें - मेमोरी उपयोग की समस्याएं

Question

मान लीजिए कि हमारे पास List<Point> pointList (पहले से ही स्मृति में संग्रहीत) की एक बड़ी सूची है, जहां प्रत्येक Point में एक्स, वाई, और जेड समन्वय शामिल है।

अब, उदाहरण के लिए, मैं pointList में संग्रहीत सभी बिंदुओं के सबसे बड़े जेड-वैल्यू वाले अंकों का एन% चुनना चाहता हूं। अभी मैं ऐसा कर रहा हूँ:

N = 0.05; // selecting only 5% of points 
double cutoffValue = pointList 
    .OrderBy(p=> p.Z) // First bottleneck - creates sorted copy of all data 
    .ElementAt((int) pointList.Count * (1 - N)).Z; 

List<Point> selectedPoints = pointList.Where(p => p.Z >= cutoffValue).ToList(); 

लेकिन मैं यहाँ दो स्मृति उपयोग बाधाओं है: पहला दौरान OrderBy (अधिक महत्वपूर्ण) और दूसरे अंक (यह कम महत्वपूर्ण है, क्योंकि हम आम तौर पर करना चाहते हैं का चयन दौरान अंक की केवल छोटी मात्रा का चयन करें)।

क्या कम स्मृति का उपयोग करने वाली किसी चीज़ के साथ ऑर्डरबी (या शायद इस कटऑफ पॉइंट को ढूंढने का अन्य तरीका) को बदलने का कोई तरीका है?

समस्या काफी महत्वपूर्ण है, क्योंकि LINQ पूरे डेटासेट की प्रतिलिपि बनाता है और बड़ी फ़ाइलों के लिए मैं इसे संसाधित कर रहा हूं कभी-कभी कुछ सैकड़ों एमबी हिट करता है।

Answer 1

आप List<T>.Sort का उपयोग करके सूची को क्रमबद्ध कर सकते हैं, जो क्विक्सोर्ट एल्गोरिदम का उपयोग करता है। लेकिन निश्चित रूप से, अपने मूल सूची हल हो जाएगा, जो शायद है कि तुम क्या नहीं करना चाहता ...

pointList.Sort((a, b) => b.Z.CompareTo(a.Z)); 
var selectedPoints = pointList.Take((int)(pointList.Count * N)).ToList(); 

आप मूल सूची पर आपत्ति नहीं है हल कर जा रहा है, यह शायद स्मृति के उपयोग और के बीच सबसे अच्छा संतुलन है गति

Answer 2

यदि आप गठबंधन दो इस बात की संभावना थोड़ा कम काम हो जाएगा है:

List<Point> selectedPoints = pointList 
    .OrderByDescending(p=> p.Z) // First bottleneck - creates sorted copy of all data 
    .Take((int) pointList.Count * N); 

लेकिन मूल रूप से रैंकिंग के इस प्रकार छँटाई, तुम्हारी सबसे बड़ी लागत की आवश्यकता है।

कुछ और विचार:

• यदि आप एक वर्ग प्वाइंट (एक struct प्वाइंट के बजाय) का उपयोग वहाँ बहुत कम नकल हो जाएगा।
• आप एक कस्टम प्रकार लिख सकते हैं जो केवल शीर्ष 5% ऊपर जाने के लिए परेशान है। BubbleSort की तरह कुछ (हंसो मत)।

Answer 3

आप कुछ इस तरह इस्तेमाल कर सकते हैं:

pointList.Sort(); // Use you own compare here if needed 

// Skip OrderBy because the list is sorted (and not copied) 
double cutoffValue = pointList.ElementAt((int) pointList.Length * (1 - N)).Z; 

// Skip ToList to avoid another copy of the list 
IEnumerable<Point> selectedPoints = pointList.Where(p => p.Z >= cutoffValue); 

Answer 4

आप Indexed LINQ उपयोग कर सकते हैं डेटा जो आप कार्रवाई कर रहे हैं पर सूचकांक डाल करने के लिए। इसके परिणामस्वरूप कुछ मामलों में उल्लेखनीय सुधार हो सकते हैं।

Answer 5

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

Answer 6

एक ऐसी विधि लिखें जो एक बार सूची के माध्यम से पुनरावृत्त हो और एम सबसे बड़े तत्वों का एक सेट बनाए रखे। सेट को बनाए रखने के लिए प्रत्येक चरण को केवल ओ (लॉग एम) काम की आवश्यकता होगी, और आपके पास ओ (एम) मेमोरी और ओ (एन लॉग एम) चलने का समय हो सकता है।

public static IEnumerable<TSource> TakeLargest<TSource, TKey> 
    (this IEnumerable<TSource> items, Func<TSource, TKey> selector, int count) 
{ 
    var set = new SortedDictionary<TKey, List<TSource>>(); 
    var resultCount = 0; 
    var first = default(KeyValuePair<TKey, List<TSource>>); 
    foreach (var item in items) 
    { 
     // If the key is already smaller than the smallest 
     // item in the set, we can ignore this item 
     var key = selector(item); 
     if (first.Value == null || 
      resultCount < count || 
      Comparer<TKey>.Default.Compare(key, first.Key) >= 0) 
     { 
      // Add next item to set 
      if (!set.ContainsKey(key)) 
      { 
       set[key] = new List<TSource>(); 
      } 
      set[key].Add(item); 
      if (first.Value == null) 
      { 
       first = set.First(); 
      } 

      // Remove smallest item from set 
      resultCount++; 
      if (resultCount - first.Value.Count >= count) 
      { 
       set.Remove(first.Key); 
       resultCount -= first.Value.Count; 
       first = set.First(); 
      } 
     } 
    } 
    return set.Values.SelectMany(values => values); 
} 

कि एक से अधिक count तत्वों अगर वहाँ, संबंधों के रूप में अपने कार्यान्वयन अब करता है शामिल होंगे।

Answer 7

यदि आपकी सूची पहले से ही स्मृति में है, तो मैं इसे प्रतिलिपि बनाने के बजाय इसे क्रमबद्ध कर दूंगा - जब तक कि आपको इसे फिर से अन-क्रमबद्ध करने की आवश्यकता न हो, यानी, इस मामले में आपको स्मृति में दो प्रतियां रखना होगा बनाम इसे फिर से लोड हो रहा है भंडारण से):

pointList.Sort((x,y) => y.Z.CompareTo(x.Z)); //this should sort it in desc. order 

इसके अलावा, यकीन नहीं यह कितना मदद मिलेगी, लेकिन ऐसा लगता है कि आप दो बार अपनी सूची के माध्यम से जा रहे हैं की तरह - चयन करने के लिए कटऑफ मूल्य खोजने के लिए एक बार और एक बार फिर उन्हें। मुझे लगता है कि आप ऐसा कर रहे हैं क्योंकि आप सभी संबंधों को इसके माध्यम से देना चाहते हैं, भले ही इसका मतलब 5% से अधिक अंक चुनना है। हालांकि, चूंकि वे पहले से ही क्रमबद्ध हैं, आप इसका उपयोग अपने लाभ के लिए कर सकते हैं और समाप्त होने पर रोक सकते हैं।

double cutoffValue = pointlist[(int) pointList.Length * (1 - N)].Z; 
List<point> selectedPoints = pointlist.TakeWhile(p => p.Z >= cutoffValue) 
             .ToList(); 

Answer 8

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

सीपीयू समय में सुधार करने के लिए, सबसे स्पष्ट बात यह है कि सूची का उपयोग न करें। इसके बजाए एक आईनेमरेबल का प्रयोग करें। आप अपनी क्वेरी के अंत में .ToList() पर कॉल करके ऐसा नहीं करते हैं। यह ढांचे को सूची के एक पुनरावृत्ति में सबकुछ जोड़ने की अनुमति देगा जो केवल आवश्यकतानुसार चलता है। यह आपके मेमोरी उपयोग में भी सुधार करेगा क्योंकि यह पूरी क्वेरी को एक बार में स्मृति में लोड करने से बचाता है, और इसके बजाय इसे आवश्यकतानुसार एक ही समय में लोड करने के लिए इसे रोकता है। इसके अलावा, का उपयोग .ElementAt() के बजाय करें। यह बहुत अधिक कुशल है।

double N = 0.05; // selecting only 5% of points 
int count = (1-N) * pointList.Count; 
var selectedPoints = pointList.OrderBy(p=>p.Z).Take(count); 

इस तरह से बाहर है, वहाँ तीन मामलों में जहां स्मृति उपयोग वास्तव में एक समस्या हो सकती हैं:

1. आपका संग्रह वास्तव में इतनी बड़ी है के रूप में स्मृति को भरने के लिए। एक आधुनिक प्रणाली पर एक साधारण बिंदु संरचना के लिए हम लाखों वस्तुओं की बात कर रहे हैं। यह वास्तव में असंभव है। ऑफ मौके पर आपके पास यह प्रणाली बहुत बड़ी है, आपका समाधान एक रिलेशनल डेटाबेस का उपयोग करना है, जो इस आइटम को डिस्क पर अपेक्षाकृत कुशलता से रख सकता है।
2. आपके पास मध्यम आकार का संग्रह है, लेकिन बाहरी प्रदर्शन बाधाएं हैं, जैसे सिस्टम संसाधनों को कई अन्य प्रक्रियाओं के साथ साझा करने की आवश्यकता है जैसा कि आप एएसपीनेट वेबसाइट में पा सकते हैं। इस मामले में, उत्तर या तो 1) फिर से एक रिलेशनल डेटाबेस या2) क्लाइंट मशीनों पर काम को ऑफ़लोड करें।
3. आपका संग्रह बड़े ऑब्जेक्ट हीप पर समाप्त होने के लिए काफी बड़ा है, और ऑर्डरबी() कॉल में उपयोग किए गए हैशसेट को भी LOH पर रखा गया है। अब क्या होता है कि कचरा कलेक्टर आपके ऑर्डरबी() कॉल के बाद मेमोरी को ठीक से कॉम्पैक्ट नहीं करेगा, और समय के साथ आपको बहुत सारी मेमोरी मिलती है जिसका उपयोग नहीं किया जाता है लेकिन फिर भी आपके प्रोग्राम द्वारा आरक्षित होता है। इस मामले में, समाधान, दुर्भाग्यवश, आपके संग्रह को कई समूहों में विभाजित करने के लिए है जो प्रत्येक व्यक्तिगत रूप से छोटे हैं जो LOH के उपयोग को ट्रिगर नहीं करते हैं।

अद्यतन:

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

Answer 9

आपने लिखा है, आप डेटासेट के साथ काम कर रहे हैं। यदि ऐसा है, तो आप एक बार अपने डेटा को सॉर्ट करने के लिए डेटाव्यू का उपयोग कर सकते हैं और पंक्तियों तक पहुंचने के लिए भविष्य में उनका उपयोग कर सकते हैं।

बस 50,000 पंक्तियों के साथ प्रयास किया और 100% उनमें से 30% तक पहुंचने की कोशिश की। मेरे प्रदर्शन परिणाम हैं:

LINQ के साथ

1. क्रमबद्ध करें: 5.3 सेकंड
2. उपयोग DataViews: 0.01 सेकंड

इसे आज़मा कर देखें।

[TestClass] 
    public class UnitTest1 { 
     class MyTable : TypedTableBase<MyRow> { 
     public MyTable() { 
      Columns.Add("Col1", typeof(int)); 
      Columns.Add("Col2", typeof(int)); 
     } 

     protected override DataRow NewRowFromBuilder(DataRowBuilder builder) { 
      return new MyRow(builder); 
     } 
     } 

     class MyRow : DataRow { 
     public MyRow(DataRowBuilder builder) : base(builder) { 
     } 

     public int Col1 { get { return (int)this["Col1"]; } } 
     public int Col2 { get { return (int)this["Col2"]; } } 
     } 

     DataView _viewCol1Asc; 
     DataView _viewCol2Desc; 
     MyTable _table; 
     int _countToTake; 

     [TestMethod] 
     public void MyTestMethod() { 
     _table = new MyTable(); 


     int count = 50000; 
     for (int i = 0; i < count; i++) { 
      _table.Rows.Add(i, i); 
     } 

     _countToTake = _table.Rows.Count/30; 
     Console.WriteLine("SortWithLinq"); 
     RunTest(SortWithLinq); 
     Console.WriteLine("Use DataViews"); 
     RunTest(UseSoredDataViews); 
     } 

     private void RunTest(Action method) { 
     int iterations = 100; 
     Stopwatch watch = Stopwatch.StartNew(); 
     for (int i = 0; i < iterations; i++) { 
      method(); 
     } 
     watch.Stop(); 
     Console.WriteLine(" {0}", watch.Elapsed); 
     } 

     private void UseSoredDataViews() { 
     if (_viewCol1Asc == null) { 
      _viewCol1Asc = new DataView(_table, null, "Col1 ASC", DataViewRowState.Unchanged); 
      _viewCol2Desc = new DataView(_table, null, "Col2 DESC", DataViewRowState.Unchanged); 
     } 

     var rows = _viewCol1Asc.Cast<DataRowView>().Take(_countToTake).Select(vr => (MyRow)vr.Row); 
     IterateRows(rows); 
     rows = _viewCol2Desc.Cast<DataRowView>().Take(_countToTake).Select(vr => (MyRow)vr.Row); 
     IterateRows(rows); 
     } 

     private void SortWithLinq() { 
     var rows = _table.OrderBy(row => row.Col1).Take(_countToTake); 
     IterateRows(rows); 
     rows = _table.OrderByDescending(row => row.Col2).Take(_countToTake); 
     IterateRows(rows); 
     } 

     private void IterateRows(IEnumerable<MyRow> rows) { 
     foreach (var row in rows) 
      if (row == null) 
       throw new Exception("????"); 
     } 
    } 

Answer 10

int resultSize = pointList.Count * (1-N); 
FixedSizedPriorityQueue<Point> q = 
    new FixedSizedPriorityQueue<Point>(resultSize, p => p.Z); 
q.AddEach(pointList); 
List<Point> selectedPoints = q.ToList(); 

अब तुम सब करने की एक FixedSizedPriorityQueue कि एक समय में तत्वों एक कहते हैं और सबसे बड़ा तत्व को छोड़ देता है जब यह भरा हुआ है लागू है।

Answer 11

मैं इसे "आधा" एक क्विकॉर्ट लागू करके करूँगा।

अपने मूल अंक, पी, जहां आप जेड समन्वय द्वारा "शीर्ष" एन आइटम की तलाश में हैं, पर विचार करें।

पी में चुनें कोई धुरी एक्स एल में

विभाजन पी = {पी में y | वाई < एक्स} और यू = {वाई में पी | एक्स < = वाई}।

यदि एन = | यू | तो आप कर रहे हैं।

यदि एन < | यू | फिर पी: = यू

अन्यथा आपको यू में कुछ आइटम जोड़ने की आवश्यकता है: शेष वस्तुओं को जोड़ने के लिए एन: = एन - | यू |, पी: = एल के साथ रिकर्स।

यदि आप बुद्धिमानी से अपना पिवोट चुनते हैं (उदाहरण के लिए, कहते हैं, पांच यादृच्छिक नमूने कहते हैं) तो यह ओ (एन लॉग एन) समय में चलाएगा।

हम्मम्म, कुछ और सोचते हुए, आप नए सेट को पूरी तरह से बनाने से बचने में सक्षम हो सकते हैं, क्योंकि अनिवार्य रूप से आप मूल सेट से एनएचटी सबसे बड़ी वस्तु को ढूंढने के लिए ओ (एन लॉग एन) तरीका ढूंढ रहे हैं। हां, मुझे लगता है कि यह काम करेगा, इसलिए यहां सुझाव संख्या 2:

क्रमशः कम से कम और सबसे बड़ी वस्तुओं, ए और जेड को खोजने के लिए पी का एक ट्रैवर्सल बनाएं।

एम को ए और जेड का मतलब बनने दें (याद रखें, हम केवल जेड निर्देशांक पर विचार कर रहे हैं)।

गणना कितने आइटम वहाँ रेंज [एम, जेड] में कर रहे हैं, इस प्र फोन

क्यू < एन तो पी में वां सबसे बड़ी मद में कहीं है [ए, एम) । एम का प्रयास करें: = (ए + एम)/2।

यदि एन < क्यू तो पी में एनएच सबसे बड़ी वस्तु कहीं [एम, जेड] में है। एम का प्रयास करें: = (एम + जेड)/2।

दोहराएँ जब तक हम एक एम लगता है इस तरह के क्यू = एन

अब पार पी, सभी आइटम से अधिक या एम

निश्चित रूप से ओ है कि के बराबर को हटाने (एन एन लॉग इन करें कि) और कोई अतिरिक्त डेटा संरचनाएं नहीं बनाता है (परिणाम को छोड़कर)। हाउज़ैट?