सूची <T> से कुशलता से कैसे निकालें (सी #)?

यदि मैं सही ढंग से समझ गया (और अगर मैं गलत हूं तो कृपया मुझे सही करें), सूची .NET में सरणी द्वारा कार्यान्वित की गई है, जिसका अर्थ है कि सूची में किसी आइटम का प्रत्येक हटाना सभी सूची का पुन: आवंटन करेगा (जिसमें बारी का मतलब O(n)) है।सूची <T> से कुशलता से कैसे निकालें (सी #)?

मैं एक खेल विकसित कर रहा हूं, इस खेल में मेरे पास किसी भी क्षण में हवा में कई गोलियां उड़ती हैं, आइए 100 गोलियां कहें, प्रत्येक फ्रेम मैं उन्हें कुछ पिक्सेल से ले जाता हूं और गेम में ऑब्जेक्ट्स के साथ टकराव की जांच करता हूं, मुझे टकराए गए प्रत्येक बुलेट की सूची से हटाना होगा।

तो मैं एक और अस्थायी सूची में टकरा गई गोली को इकट्ठा करने और उसके बाद निम्न:

foreach (Bullet bullet in bulletsForDeletion) 
    mBullets.Remove(bullet);

क्योंकि पाश O(n) है और निकालें O(n) है, मैं O(n^2) समय दूर करने के लिए खर्च करते हैं।

क्या इसे हटाने का बेहतर तरीका है, या उपयोग करने के लिए अधिक उपयुक्त संग्रह है?

स्रोत

2012-12-29 OopsUser

क्षमा न करें। हम सब यहाँ सीखने के लिए। –

क्या आप वाकई एक वास्तविक समस्या है, या आप समय से अनुकूलित कर रहे हैं? – Oded

मुझे वास्तविक समस्या नहीं है, यह 60 एफपीएस पर चलता है, मैं बस "महसूस" करता हूं जैसे कि मैं कुछ गलत लिख रहा हूं क्योंकि ऐसा ऑपरेशन ओ (एन^2) नहीं होना चाहिए। – OopsUser

एक नई सूची बनाएं:

var newList = `oldList.Except(deleteItems).ToList()`.

कोशिश कार्यात्मक मुहावरों जहां भी संभव हो उपयोग करने के लिए। मौजूदा डेटा संरचनाओं को संशोधित न करें, नए बनाएं।

यह एल्गोरिदम ओ (एन) हैशिंग के लिए धन्यवाद है।

स्रोत

2012-12-29 13:21:49 usr

क्यों है यह हे (एन) जब वह प्रतियां एक और सूची में चर वह प्रत्येक आइटम के लिए जाँच करने के लिए अगर वह "deleteItems" सूची में मौजूद हैं की जरूरत है, यह की तरह लग रहा? ओ (एन^2) – OopsUser

@ ओप्स यूज़र 'एक्सेप्ट' आंतरिक रूप से हैश टेबल बनाता है, इसलिए मौजूद है 'पुरानी सूची' में प्रति आइटम ओ (1) है। यह 'ओ (oldList.Count + deleteItems.Count) ~ O के लिए बनाता है (एन) ' – usr

+1। @OopsUser, ['except' एक्सटेंशन विधि] (http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except.aspx) प्रत्येक आइटम को स्रोत गणना से पढ़ता है और जो आउटपुट करता है 'हटाएं' में नहीं। आंतरिक रूप से यह 'deleteItems' का हैश बनाता है, और उस हैश के खिलाफ प्रत्येक इनपुट की उपस्थिति का परीक्षण करता है। केवल आइटम जो हैश में नहीं पाए जाते हैं, आउटपुट के माध्यम से पारित किए जाते हैं। यह ओ (एन) है, हालांकि इसके परिणामस्वरूप नए हैंश और नए सरणी आवंटित किए जाएंगे ('toList' द्वारा निर्मित)। ऐसा हो सकता है कि आपको इस स्मृति के ऊपर की चिंता करने की आवश्यकता नहीं है, लेकिन आपको पता होना चाहिए कि यह वहां है। –

क्या आप List (जावा को ArrayList के समतुल्य रूप से उस पर प्रकाश डालने के लिए) से LinkedList पर स्विच नहीं कर सकते हैं? लिंक्डलिस्ट एक विशिष्ट तत्व को हटाने के लिए ओ (1) लेता है, लेकिन ओ (एन) इंडेक्स

स्रोत

2012-12-29 13:18:41

आंतरिक रूप से एक सूची कैसे लागू की जाती है, ऐसा कुछ नहीं है जिसके बारे में आपको सोचना चाहिए। आपको उस अमूर्त स्तर में सूची के साथ बातचीत करनी चाहिए।

यदि आपके पास प्रदर्शन समस्याएं हैं और आप उन्हें सूची में इंगित करते हैं, तो यह देखने का समय है कि इसे कैसे कार्यान्वित किया जाता है।

किसी सूची से आइटम को निकालने के लिए - आप mBullets.RemoveAll(predicate) का उपयोग कर सकते हैं, जहां predicate एक अभिव्यक्ति है जो टकराव वाली वस्तुओं की पहचान करती है।

स्रोत

2012-12-29 13:19:06 Oded

सेट और लिंक सूचियों में निरंतर समय निकालना है। क्या आप इनमें से किसी भी डेटा संरचना का उपयोग कर सकते हैं?

List<T> से निकालने की ओ (एन) लागत से बचने का कोई तरीका नहीं है। यदि यह आपके लिए एक समस्या है तो आपको एक अलग डेटा संरचना का उपयोग करने की आवश्यकता होगी। यह कोड बना सकता है जो बुलेट्स की गणना करता है, ठीक है, ठीक है।

ISet<T> वस्तुओं के सेट के बीच मतभेदों और चौराहे की गणना के लिए अच्छी विधियां हैं।

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

आपके मामले में, आप लिख सकते हैं:

mBullets.ExceptWith(bulletsForDeletion);

स्रोत

2012-12-29 13:19:11

.NET में "सेट" कैसे कहा जाता है? मुझे कोई जेनेरिक कॉल नहीं दिखता है। लिंक की गई सूची (और सेट) के साथ समस्या यह है कि डेटा स्मृति में एक ही स्थान पर नहीं बैठता है, इसलिए जब मैं किसी सूची से पढ़ता हूं, तो मुझे कैशिंग का लाभ होता है, लेकिन जब मैं सेट/लिंक्ड सूचियों का उपयोग करता हूं I इस लाभ को ढीला करो। हालांकि मुझे दूसरी बार एक बार सूची से वस्तुओं को हटाना है, मुझे 100 बार अधिक (टकराव की जांच आदि ..) – OopsUser

@OopsUser सूची से पढ़ने की जरूरत है, आप 'ISet 'की तलाश में हैं, जो आप कर सकते हैं [ यहां के बारे में पढ़ें] (http://msdn.microsoft.com/en-us/library/dd412081.aspx)। –

@ ओप्स यूसर, यह भी उपयोगी होगा कि आप 'bulletsForDeletion' की गणना कैसे करते हैं। शायद यह भी अधिक इष्टतम बनाने का एक तरीका है। –

RemoveAt(int index)Remove(T item) से तेज़ है क्योंकि बाद में इसके अंदर पहले उपयोग करते हैं, प्रतिबिंब करते हैं, यह प्रत्येक फ़ंक्शन के अंदर कोड है।

इसके अलावा, Remove(T) में IndexOf फ़ंक्शन है, जिसमें प्रत्येक आइटम के सूचकांक को evalute करने के लिए इसमें दूसरा लूप है।

public bool Remove(T item) 
{ 
    int index = this.IndexOf(item); 
    if (index < 0) 
    return false; 
    this.RemoveAt(index); 
    return true; 
} 


public void RemoveAt(int index) 
{ 
    if ((uint) index >= (uint) this._size) 
    ThrowHelper.ThrowArgumentOutOfRangeException(); 
    --this._size; 
    if (index < this._size) 
    Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index); 
    this._items[this._size] = default (T); 
    ++this._version; 
}

मैं इस तरह एक पाश करना होगा:

for (int i=MyList.Count-1; i>=0; i--) 
{ 
    // add some code here 
    if (needtodelete == true) 
    MyList.RemoveAt(i); 
}

स्रोत

2012-12-29 13:25:58 sharp12345

आपका अंतिम कोड ब्लॉक 'MyList.Clear()' का एक अक्षम संस्करण है। क्या आप कुछ और लिखना चाहते थे? –

@DrewNoakes, हां, मुझे लगता है कि पूछताछ करने वाला उपयोगकर्ता कुछ आइटम हटाने के लिए कुछ शर्तों को जोड़ देगा, वह वास्तव में सभी आइटमों को हटा नहीं देगा, मेरी पोस्ट संपादित करेगा। – sharp12345

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

स्रोत

2012-12-29 14:20:17 Griffin

सूची <T> से कुशलता से कैसे निकालें (सी #)?

उत्तर

संबंधित मुद्दे