समय जटिलता()

Question

क्या जावा में String#substring() विधि के समय जटिलता है? के रूप में तो हर String एक char[] जो नहीं है किसी अन्य वस्तु के साथ साझा करने के लिए संदर्भित करता है, -

Answer 1

न्यू जवाब

जावा 7 के जीवन भर के भीतर अद्यतन 6 के रूप में, substring के व्यवहार प्रतिलिपि बनाने के लिए बदल गया जहां तक ​​मुझे पता है। उस बिंदु पर तो, substring() एक हे (एन) आपरेशन जहां n-स्ट्रिंग में संख्या है बन गया।

पुराना जवाब: पूर्व जावा 7

Undocumented - लेकिन व्यवहार में हे (1) आप कोई कचरा संग्रहण की आवश्यकता होती है, आदि ग्रहण करता है, तो

यह बस एक नया String वस्तु की चर्चा करते हुए बनाता है वही अंतर्निहित char[] लेकिन अलग ऑफसेट और गिनती मूल्यों के साथ। तो लागत सत्यापन करने और एक नई (उचित रूप से छोटी) वस्तु बनाने के लिए लिया गया समय है। यही कारण है कि हे (1) यह आपरेशन जो कचरा संग्रहण, सीपीयू कैश आदि विशेष रूप से के आधार पर समय में भिन्न हो सकते हैं की जटिलता के बारे में बात करने के लिए समझदार है जहाँ तक है, यह सीधे मूल स्ट्रिंग या सबस्ट्रिंग की लंबाई पर निर्भर नहीं करता है ।

Answer 2

हे (1) क्योंकि मूल स्ट्रिंग की कोई नकल किया जाता है, यह सिर्फ अलग ऑफसेट जानकारी के साथ एक नया आवरण वस्तु बनाता है। निम्नलिखित से खुद के लिए

Answer 3

न्यायाधीश, लेकिन जावा के प्रदर्शन कमियां कहीं और एक स्ट्रिंग की सबस्ट्रिंग में झूठ, यहाँ नहीं। कोड:

public static void main(String[] args) throws IOException { 

     String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + 
       "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + 
       "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; 
     int[] indices = new int[32 * 1024]; 
     int[] lengths = new int[indices.length]; 
     Random r = new Random(); 
     final int minLength = 6; 
     for (int i = 0; i < indices.length; ++i) 
     { 
      indices[i] = r.nextInt(longStr.length() - minLength); 
      lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); 
     } 

     long start = System.nanoTime(); 

     int avoidOptimization = 0; 
     for (int i = 0; i < indices.length; ++i) 
      //avoidOptimization += lengths[i]; //tested - this was cheap 
      avoidOptimization += longStr.substring(indices[i], 
        indices[i] + lengths[i]).length(); 

     long end = System.nanoTime(); 
     System.out.println("substring " + indices.length + " times"); 
     System.out.println("Sum of lengths of splits = " + avoidOptimization); 
     System.out.println("Elapsed " + (end - start)/1.0e6 + " ms"); 
    } 

आउटपुट:

substring 32768 times 
Sum of lengths of splits = 1494414 
Elapsed 2.446679 ms

यदि यह हे है (1) है या नहीं, निर्भर करता है। तुम सिर्फ स्मृति में एक ही स्ट्रिंग संदर्भ है, तो बहुत लंबी स्ट्रिंग की कल्पना, आप स्ट्रिंग बनाने के लिए और लंबे समय से एक को संदर्भित बंद करो। लंबे समय तक स्मृति जारी करने के लिए अच्छा नहीं होगा?

Answer 4

यह जावा के पुराने संस्करणों में ओ (1) था - जैसा कि जॉन ने कहा था, उसने अभी एक ही अंतर्निहित char [], और एक अलग ऑफसेट और लंबाई के साथ एक नया स्ट्रिंग बनाया है।

बहरहाल, यह वास्तव में बदल गया है जावा 7 अद्यतन 6.

के साथ शुरू किया चार [] साझा करने का सफाया कर दिया गया था, और ऑफसेट और लंबाई खेतों हटा दिया गया। सबस्ट्रिंग() अब बस सभी पात्रों को एक नई स्ट्रिंग में कॉपी करता है।

Ergo,-स्ट्रिंग जावा 7 अद्यतन 6

Answer 5

में हे (एन) अब यह रैखिक जटिलता है। यह सबस्ट्रिंग के लिए एक स्मृति रिसाव मुद्दा फिक्सिंग के बाद है।

तो जावा 1.7.0_06 से याद रखें कि String.substring में निरंतर एक की बजाय एक रैखिक जटिलता है।