2017-12-15 165 views
9

this answer में यह उल्लेख किया गया है कि वर्णों की संख्या प्राप्त करने के लिए s.chars().count() कर रहे स्ट्रिंग के लिए एक ओ (एन) ऑपरेशन है। सरल ASCII तारों के लिए s.len() का उपयोग करके बाइट्स की संख्या प्राप्त करने के लिए भी काम करता है। यह सुनिश्चित करने के लिए चेक का उपयोग करते समय कि वे सभी बाइट वास्तव में ASCII हैं, यह शायद सुरक्षित है।मुझे ऑपरेशन की जटिलता कहां मिलती है?

मैं जानना चाहता हूं कि उस ऑपरेशन की जटिलता क्या है। इसे अभी भी सी में स्ट्रिंग का अंत ढूंढना पड़ सकता है जैसे कि सी और ओ (एन) हो।

मैंने इसे देखने की कोशिश की और documentation of the std::string::String, पाया जो उचित s के लिए लागू होता है। हालांकि यह इसकी जटिलता नहीं बताता है। स्रोत को देखते हुए यह self.vec.len() करता है। तो हम vector docs को देखने के लिए जाते हैं और पाते हैं कि यह बस एक संग्रहित लंबाई self.len देता है जिसका अर्थ है कि यह वास्तव में एक ओ (1) ऑपरेशन है।

हालांकि यह बहुत काम था। अब इस मामले के बारे में क्या है कि s एक std::str है? मैंने ऐसा करने की कोशिश की लेकिन this mess में फंस गया।

क्या जंग में ऑपरेशन जटिलताओं के लिए एक अधिक आसानी से सुलभ संसाधन है?

इस तरह कुछ list for Python बहुत अच्छा होगा।

+0

ध्यान दें कि सभी वर्ण असीसी हैं ओ (एन) बस 's.chars()। गिनती()' की तरह है, इसलिए जब तक आपको किसी अन्य कारण की जांच की आवश्यकता न हो, तो आप 's.chars () .count() '। – Jmb

+1

जटिलताओं को सभी डेटाटाइप के लिए दस्तावेज किया जाना चाहिए। जहां वे गायब हैं, पीआर भेजने या किसी समस्या को दर्ज करने में संकोच न करें। मुझे नहीं लगता कि सभी जटिलताओं के साथ केंद्रीकृत सूची इस के लिए सही जगह है; यह केवल संग्रहों के लिए समझ में आता है, जहां आपको यह तय करने के लिए एक सिंहावलोकन की आवश्यकता है कि किस संग्रह का उपयोग करना है। –

उत्तर

6

performance section on collections के अलावा मुझे नहीं लगता कि वर्तमान में आपके द्वारा संदर्भित पायथन जैसे एक आम सूची है।

// We can re-build a str out of ptr and len. This is all unsafe because 
// we are responsible for making sure the two components are valid: 
let s = unsafe { 
    // First, we build a &[u8]... 
    let slice = slice::from_raw_parts(ptr, len); 

    // ... and then convert that slice into a string slice 
    str::from_utf8(slice) 
}; 
+1

सटीक होने के लिए, 'str :: len' कोड इकाइयों में लंबाई निर्धारित करता है (जैसे' स्ट्रिंग :: लेन ')। कोड बिंदुओं में लंबाई प्राप्त करने के लिए, आपको 'str :: chars :: count' को कॉल करने की आवश्यकता है जो ओ (1) है (जैसा कि' स्ट्रिंग' के समान है)। – Jmb

+2

@ जेएमबी मुझे पता है कि आपका मतलब ओ (एन) है, लेकिन मुझे लगा कि मैं किसी और के साथ आने के मामले में इसका उल्लेख करूँगा और उलझन में था :) – trentcl

3

String और str प्रस्ताव सभी कार्यों के लिए एक ही जटिलता की गारंटी देता है:

str का सवाल है, इसकी लंबाई निर्धारित करने के लिए एक हे (1) आपरेशन, क्योंकि a string slice consists of a pointer and length है। वास्तव में, अधिकांश ऑपरेशन String (chars() सहित) are actually operations on str जो String से str पर अंतर्निहित रूपांतरण का उपयोग करते हैं (यह रूपांतरण मुक्त है क्योंकि वे समान निम्न-स्तरीय प्रतिनिधित्व साझा करते हैं)।

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