मैंने चारों ओर खोज की और बिट्ससेट :: गिनती() के लिए प्रदर्शन समय विनिर्देश नहीं मिला। क्या कोई जानता है कि यह क्या है (ओ (एन) या बेहतर) और इसे कहां मिलना है?एसटीएल बिटसेट :: गिनती() विधि का प्रदर्शन क्या है?
एसटीएल द्वारा संपादित करें मैं केवल मानक टेम्पलेट लाइब्रेरी का संदर्भ देता हूं।
मैं इस फ़ाइल को पढ़ने (C: \ cygwin \ lib \ जीसीसी \ i686-पीसी-cygwin \ 3.4.4 \ \ C++ \ bitset में शामिल) पर अपने कंप्यूटर।
BTW इन
/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }
size_t
_M_do_count() const
{
size_t __result = 0;
for (size_t __i = 0; __i < _Nw; __i++)
__result += __builtin_popcountl(_M_w[__i]);
return __result;
}
देखें, इस जगह है जहाँ _Nw निर्दिष्ट किया जाता है:
template<size_t _Nw>
struct _Base_bitset
इस प्रकार यह जीसीसी कार्यान्वयन में हे (एन) है। हमने निष्कर्ष निकाला है कि विनिर्देशन को ओ (एन) से बेहतर की आवश्यकता नहीं है। और उनके दाहिने दिमाग में कोई भी इससे भी बदतर तरीके से इसे लागू नहीं करेगा। फिर हम सुरक्षित रूप से मान सकते हैं कि यह सबसे खराब ओ (एन) है। शायद बेहतर है लेकिन आप उस पर भरोसा नहीं कर सकते हैं।
हालांकि यह एक विनिर्देशन नहीं है! : पी –
@ tomalak-geretkal जीसीसी कार्यान्वयन में, यह ओ (एन) है। हमने निष्कर्ष निकाला है कि विनिर्देशन को ओ (एन) से बेहतर की आवश्यकता नहीं है। और इससे भी बदतर तरीके से इसे लागू करने के लिए कोई भी बेवकूफ नहीं होगा। फिर हम सुरक्षित रूप से मान सकते हैं कि यह हमेशा कम से कम ओ (एन) होता है। शायद बेहतर है लेकिन आप उस पर भरोसा नहीं कर सकते हैं। – Haozhun
@ जीन: इस मामले में मैं सहमत हूं, यह प्रदर्शन विनिर्देशों के मूल प्रश्न का सख्ती से जवाब नहीं देता है। हालांकि, यह एक अच्छी कटौती है। –
"SGI की संदर्भ कार्यान्वयन बिट्स स्टोर करने के लिए की जरूरत बाइट्स की संख्या के संबंध में रेखीय समय में चलाता है। यह 256 पूर्णांकों का एक स्थिर सरणी बनाने करके करता है। Ith सूचकांक पर संग्रहीत मूल्य सरणी में i में सेट बिट्स की संख्या i। "
यह सटीक भी हो सकता है, लेकिन यहां केवल एक चेतावनी है कि cplusplus।कॉम त्रुटियों के साथ छेड़छाड़ करने के लिए जाना जाता है। –
इसके अलावा, यह एक निश्चित कार्यान्वयन का विवरण होगा। –
@ डेविड थॉर्नले: वास्तव में, cplusplus.com सामान्य रूप से लाइब्रेरी के बारे में बहुत भ्रमित है (मैं कहता हूं, उलझन में?)। यह "एसटीएल" शब्द का स्पष्ट रूप से संकेत देता है कि इसका अर्थ वास्तव में सी ++ मानक पुस्तकालय है, लेकिन फिर मंचों पर लोग वास्तविक एसटीएल के बारे में बात करते हैं। लिंक के लिए –
मुझे यकीन है कि आप के लिए एक विनिर्देश को खोजने के लिए जा रहे हैं नहीं कर रहा हूँ के बाद से एसटीएल आम तौर पर प्रदर्शन का एक निश्चित स्तर नहीं की आवश्यकता है। मैंने संकेत देखा है कि यह "तेज़" है, सेट के आकार में लगभग 1 चक्र प्रति बिट। आप निश्चित रूप से क्या उम्मीद कर सकते हैं यह जानने के लिए आप अपने विशेष कार्यान्वयन के कोड को पढ़ सकते हैं।
एसटीएल को आमतौर पर एसिम्प्टोटिक प्रदर्शन (बड़े-ओ) के कुछ स्तरों की आवश्यकता होती है। –
सी ++ समुदाय में शब्द के प्रचलित दुरुपयोग के कारण, मुझे यह सुनिश्चित नहीं हो सकता कि आप "एसटीएल" द्वारा वास्तव में क्या मतलब रखते हैं।
सी ++ स्टैंडर्ड (2003) std::bitset::count() के प्रदर्शन के लिए कोई जनादेश बनाता है (या वास्तव में, जहां तक std::bitset के किसी भी सदस्य के रूप में मैं देख सकते हैं)।
मुझे एसटीएल के bitset::count() के प्रदर्शन के लिए एक जनादेश का सुझाव देने वाला कोई संदर्भ नहीं मिल रहा है।
मुझे लगता है कि कोई भी सायन कार्यान्वयन इसे निरंतर (या सबसे खराब रैखिक) समय में प्रदान करेगा। हालांकि, यह केवल एक भावना है। आपको वास्तव में क्या मिलेगा यह जानने के लिए अपनी जांच करें।
क्या आप साझा कर सकते हैं एसटीएल सी ++ के संदर्भ में क्या अन्य चीजें संदर्भित करता है? – yasouser
वही टिप्पणी जैसा मैंने आपको दिया [यहां] (http://stackoverflow.com/questions/2297164/stl-deque-accessing-by-index-is-o1/4694218#4694218)। पैडेंट्री के लिए एक समय है, यह नहीं है। प्रश्न पर टिप्पणी करें कि क्या आप "एसटीएल" के ओपी के उपयोग को स्पष्ट करना चाहते हैं, लेकिन इसे अपने उत्तर का हिस्सा न बनाएं और इस बात का जिक्र न करें कि आप किसी भी तरह से समझने में असमर्थ हैं, इसका मतलब है कि यह अहंकारी और उपहासपूर्ण है। * ओपी को चीजें समझाएं, केवल इतना न कहें "मैं इसे संभवतः नहीं प्राप्त कर सकता, यह सख्ती से परिभाषित नहीं है!" – GManNickG
@GMan मैंने सोचा होगा कि उसका प्रश्न अस्पष्ट था और फिर उन दोनों चीजों के लिए उत्तर प्रदान कर रहा था जो वह पूछ रहे थे। मैं नहीं देखता कि यह कैसे घोषित करता है कि मैं कुछ नहीं कर सकता "अहंकारी" है; एक शब्दकोश पढ़ें। और ऐसा नहीं है कि मेरा पूरा जवाब था "मुझे नहीं पता कि आपका क्या मतलब है, पुनः प्रयास करें"। –
क्या Tomalak उल्लेख किया है कि एसटीएल है (मानक टेम्पलेट लायब्रेरी) एक अस्पष्ट शब्द है (लेकिन * समझाने * क्योंकि वह जाहिरा तौर पर असुरक्षित है और दूसरों पर अपने ज्ञान का दावा करने की जरूरत है विफल)। सी ++ समुदाय में हम में से कुछ ने इस पर [टैग के लिए जानकारी-विकी] (http://stackoverflow.com/tags/stl/info) में विस्तार किया है, जो स्रोत टोमालक की टिप्पणी को स्पष्ट करना चाहिए। संक्षेप में, आपको केवल "मानक लाइब्रेरी" या "stdlib" कहना चाहिए, लेकिन जब आप एसटीएल कहेंगे तो हम जानेंगे कि आपका क्या मतलब है। – GManNickG
@GMan: व्यक्तिगत हमलों की कोई ज़रूरत नहीं है। StackOverflow पर उनका स्वागत नहीं है। कृपया भविष्य में अपना स्वर समायोजित करें। –