😅 👨🏾 👴🏼 Google से C ++ लाइब्रेरी मानचित्र के साथ और बी-पेड़ों पर कंटेनर सेट करें 🧒 👩🏽‍🤝‍👩🏼 🏏

Google के कर्मचारियों में से एक, अपने खाली समय के 20% में, cpp-btree लाइब्रेरी (C ++ B-Tree) के निशुल्क लाइसेंस के तहत विकसित और बिछा हुआ है, जिसमें मानक टेम्पलेट लाइब्रेरी (STL) से मैप, सेट, मल्टीमैप और मल्टीसेट जैसे कंटेनर होते हैं।

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

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

परीक्षणों के अनुसार, बी-पेड़ों पर डेटा संरचनाएं लाल-काले पेड़ों की तुलना में 50-80% कम जगह लेती हैं। तालिका विभिन्न प्रकार के सेट / मैप कंटेनरों में प्रति तत्व बाइट्स की औसत संख्या दर्शाती है। उदाहरण के लिए, मानक सेट <int32_t> कंटेनर कई छोटे तत्वों में से प्रत्येक के लिए 16 बाइट्स का एक ओवरहेड बनाता है, जबकि वैकल्पिक btree_set <int32_t> कंटेनर प्रति तत्व केवल 1 बाइट का ओवरहेड बनाता है।

टाइप	डालने	बी-ट्री (32-बिट)	लाल-काला (32-बिट)	बी-ट्री (64-बिट)	लाल-काला (64-बिट)
<int32_t> सेट करें	क्रमबद्ध	4.19	20.00	4.40	40.00
	बिना सोचे समझे	4.90	20.00	5.15	40.00
<int64_t> सेट करें	क्रमबद्ध	8.39	24.00	8.80	40.00
	बिना सोचे समझे	9.96	24.00	10.47	40.00
<string> सेट करें	क्रमबद्ध	24.57	40.00	33.60	64.00
	बिना सोचे समझे	29.49	40.00	40.74	64.00
मानचित्र <int32_t, void *>	क्रमबद्ध	8.39	24.00	8.80	48.00
	बिना सोचे समझे	9.96	24.00	10.47	48.00
मानचित्र <int64_t, void *>	क्रमबद्ध	12.60	28.00	13.20	48.00
	बिना सोचे समझे	15.16	28.00	15.92	48.00
नक्शा <स्ट्रिंग, शून्य *>	क्रमबद्ध	28.67	44.00	38.16	72.00
	बिना सोचे समझे	34.49	44.00	46.53	72.00

कुछ बड़े कंटेनरों पर, कैश के अधिक कुशल उपयोग के कारण पहुंच की गति में भी बढ़त है। ग्राफ़ कंटेनर के आकार के आधार पर औसत सम्मिलन समय दिखाता है।

^{विशेष रूप से "रूसी दोस्तों" के लिए, पुस्तकालय के लेखक ने समझाया कि उसने वाई अक्ष पर हस्ताक्षर नहीं किया था, क्योंकि ऑपरेशन का विशिष्ट समय उपयोग किए गए उपकरणों पर निर्भर करता है।} ^{इस मामले में, 10 मिलियन तत्वों के लिए, ऑपरेशन लाल-काले पेड़ों पर 1.6 माइक्रोसेकंड लेता है, बी-पेड़ों पर 400 नैनोसेकंड के खिलाफ।} ^{कंप्यूटर इंटेल Xeon CPU E5-1650 @ 3.20GHz L1 = 32K, L2 = 256K, L3 = 12M के साथ।}

डेवलपर cpp-btree और मानक कंटेनरों के बीच के अंतर के बारे में चेतावनी देता है: चूंकि बी-ट्री में नोड्स डालने और हटाने के किसी भी संचालन को मौजूदा पुनरावृत्तियों को अमान्य करता है, इसलिए यदि आवश्यक हो, तो सुरक्षित संस्करणों का उपयोग करें।

Google ओपन सोर्स ब्लॉग के माध्यम से

Google से C ++ लाइब्रेरी मानचित्र के साथ और बी-पेड़ों पर कंटेनर सेट करें

More articles: