एक्सोबोटोस: सी # बाइनरी पेड़ बेंचमार्क एक संरचना का उपयोग क्यों करता है?

Question

xobotos में reputed performance gains के बारे में उत्सुक, मैंने बाइनरी पेड़ benchmark code की जांच की।

binary tree node की

जावा संस्करण है:

private static class TreeNode 
{ 
    private TreeNode left, right; 
    private int item; 
} 

C# version है:

struct TreeNode 
{ 
    class Next 
    { 
    public TreeNode left, right; 
    } 

    private Next next; 
    private int item; 
} 

मैं सोच रहा हूँ क्या यहाँ एक struct उपयोग करने का लाभ, अगला व पिछला संकेत के बाद से अभी भी एक कक्षा में encapsulated हैं।

ठीक है, एक पत्ती नोड शुद्ध मूल्य प्रकार हैं क्योंकि उन्हें बाएं और दाएं पॉइंटर्स की आवश्यकता नहीं है। एक ठेठ बाइनरी पेड़ में जहां आधा नोड पत्तियां हैं, इसका मतलब है वस्तुओं की संख्या में 50% की कमी। फिर भी, सूचीबद्ध प्रदर्शन लाभ बहुत अधिक प्रतीत होता है।

प्रश्न: क्या इसके लिए और कुछ है?

इसके अलावा, चूंकि मैंने सी # (धन्यवाद Xamarin!) में पेड़ नोड्स को परिभाषित करने के बारे में सोचा नहीं होगा, तो अन्य डेटा संरचनाओं को गैर-स्पष्ट तरीके से structs का उपयोग करने से क्या फायदा हो सकता है? (भले ही यह थोड़ा ऑफ-विषय और खुला समाप्त हो।)

Answer 1

यह समूह दो आवंटन में दो नोड्स, आदर्श रूप से कुल आवंटन की संख्या को कम करता है।

आईएमओ यह तुलना को बहुत अर्थहीन बनाता है।

Answer 2

मुझे नहीं लगता कि यहां संरचना का उपयोग करने से कोई फर्क पड़ता है। विशेष रूप से TreeNode के स्रोत कोड को देखने के बाद, जहां ट्रीनोड के उदाहरण हमेशा कन्स्ट्रक्टर और रिकर्सिव तलअपट्री कॉल में कॉपी किए जाते हैं।

Answer 3

संरचनाओं को ढेर के बजाय ढेर पर आवंटित किया जा सकता है (हालांकि हर मामले में नहीं), जिसका अर्थ है कि जैसे ही वे गुंजाइश से बाहर निकलते हैं - कचरा कलेक्टर उस परिदृश्य में शामिल नहीं होता है। इसके परिणामस्वरूप छोटे मेमोरी दबाव और कम कचरा संग्रह हो सकता है। इसके अलावा, ढेर (ज्यादातर) मेमोरी का संक्रामक क्षेत्र है, इसलिए इसकी पहुंच में बेहतर इलाका है, जो सीपीयू स्तर पर कैश हिट अनुपात में सुधार कर सकता है (फिर से, संभवतः)। choosing between classes and structures पर

माइक्रोसॉफ्ट के दिशा निर्देशों:

• संरचनाओं होना चाहिए छोटे (16 बाइट्स आम तौर पर) और अल्पकालिक
• उन्हें होना चाहिए अपरिवर्तनीय

तो उन से मुलाकात कर रहे है, तो एक संरचना पर उपयोग करते हुए एक वर्ग के परिणामस्वरूप प्रदर्शन लाभ होगा।

Answer 4

मैं बस इस विषम कोड में भाग गया और एक ही सवाल था। यदि आप जावा संस्करण से मेल खाने के लिए कोड बदलते हैं तो यह थोड़ा धीमा हो जाएगा। मेरा मानना ​​है कि अधिकांश 'स्ट्रक्चर ट्रीनोड' को नीचे पंक्ति के अलावा, बॉक्स किया जाएगा और वैसे भी आवंटित किया जाएगा। हालांकि, प्रत्येक नोड के परिणाम 2 आवंटन में होते हैं: बॉक्स किए गए वृक्ष नोड और कक्षा अगला। आवंटन बचत जल्दी गायब हो जाती है। आईएमओ, यह संरचना का उचित उपयोग नहीं है।