स्ट्रिंग तुलना की तुलना में संख्या तुलना तेजी से है?

Question

मैंने सुना है कि हैशिंग (यानी एक स्ट्रिंग या ऑब्जेक्ट को किसी संख्या में परिवर्तित करना) तारों के लिए उपयोग किया जाता है और ऐसा इसलिए है क्योंकि तारों की तुलना में संख्याओं की तुलना करना आसान है। यदि सही है, तो इसका क्या कारण है?

Answer 1

की आवश्यकता है यह आवश्यक रूप से मामला है, लेकिन शायद मामले समय के सबसे अधिक नहीं है।

मैं तुलना करने के लिए स्ट्रिंग "सेब" बनाम "संतरे" हैं:

निम्नलिखित स्थिति पर विचार करें। अगर मैं केवल "सेब" == "संतरे" निर्धारित करना चाहता हूं, तो मुझे केवल प्रत्येक स्ट्रिंग के पहले अक्षर की तुलना करने की आवश्यकता है: 'ए'! = 'ओ' => "सेब"! = "संतरे"। यदि मैं स्ट्रिंग हैश करता हूं और फिर तुलना करता हूं, तो यह काफी धीमा है क्योंकि मुझे दोनों स्ट्रिंग्स को पार्स करना होगा और परिणामस्वरूप पूर्णांक की तुलना करने से पहले उन्हें हैशिंग एल्गोरिदम में फ़ीड करना होगा।

यदि, हालांकि, मुझे यह तुलना कई बार करने की ज़रूरत है, और शायद मैं "संतरे" की तुलना "ऑरंगुटान" से कर रहा हूं, तो अगर मैं एक बार सभी तारों को हश करता हूं और कई बार पूर्णांक की तुलना करता हूं, यह तेजी से काम करेगा। यह सिद्धांत है कि हैश नक्शा पर आधारित है।

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

Answer 2

हाँ, पर कि हैशिंग कोई लेना देना नहीं है।

तुलना संख्या सरल हार्डवेयर निर्देश है कि बिट्स तुलना शामिल है।

तारों की तुलना में (ए) दोनों स्ट्रिंग्स के माध्यम से पुनरावृत्त होता है जब तक आप अलग-अलग वर्ण नहीं पाते (संख्याओं के विपरीत, जो निश्चित आकार होते हैं) और (बी) यूनिकोड जादू के बहुत सारे (अलग-अलग लंबाई के विभिन्न तार वास्तव में बराबर हो सकते हैं, और अलग-अलग होते हैं विभिन्न कोड ब्लॉक में वर्ण अलग-अलग तुलना करते हैं)।

---

हैशिंग आमतौर पर एक स्ट्रिंग को सरणी अनुक्रमणिका में परिवर्तित करने के लिए उपयोग किया जाता है।

Answer 3

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

Answer 4

दो नंबर तुलना परिमाण दो तार (एक ही संख्या का प्रतिनिधित्व) की तुलना की तुलना में तेजी है। मुकाबले दो नंबर बस अलग-अलग बिट्स की तुलना की आवश्यकता होती है और सुपर तेजी से किसी और का उपयोग कर, XOR, 2 के पूरक, आदि

दो तार की तुलना करना बहुत धीमी और महंगी है किया जा सकता है। अधिकांश एल्गोरिदम को संपूर्ण स्ट्रिंग के माध्यम से पुनरावृत्ति की आवश्यकता होती है और प्रत्येक वर्ण से मिलान होता है।

उदाहरण के लिए मान लीजिए कि हम साथ 12 (गलत) 9 की तुलना करना चाहते हैं। संख्यात्मक तुलना के लिए, आइए मान लें कि एल्गोरिदम व्यक्तिगत बिट की तुलना करता है। 9 = 1001 12 = 1100

यहाँ, सबसे खराब स्थिति एल्गोरिथ्म 4 बिट्स की तुलना करेंगे।

अब अगर हम तारों के रूप में "9" और "12" का प्रतिनिधित्व करते हैं, तो उन्हें स्मृति में 16 बिट्स के रूप में संग्रहीत किया जाएगा (याद रखें: जावा स्मृति में स्ट्रिंग का प्रतिनिधित्व करने के लिए यूटीएफ -16 का उपयोग करता है) और स्ट्रिंग को पास करना होगा तुलना एल्गोरिदम। वास्तव में, जावा के वास्तविक स्ट्रिंग तुलना समारोह के नीचे है:

public boolean equals(Object anObject) { 
    if (this == anObject) { 
     return true; 
    } 
    if (anObject instanceof String) { 
     String anotherString = (String)anObject; 
     int n = count; 
     if (n == anotherString.count) { 
      char v1[] = value; 
      char v2[] = anotherString.value; 
      int i = offset; 
      int j = anotherString.offset; 
      while (n-- != 0) { 
       if (v1[i++] != v2[j++]) 
        return false; 
      } 
      return true; 
     } 
    } 
    return false; 
} 

आप देख सकते हैं, वहाँ एक बहुत अधिक स्ट्रिंग तुलना के लिए चारों ओर जा रहा है।

Answer 5

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

जावा में

उदाहरण के लिए एक स्ट्रिंग मूल रूप से

 /** The value is used for character storage. */ 
    private final char value[]; 

    /** The offset is the first index of the storage that is used. */ 
    private final int offset; 

    /** The count is the number of characters in the String. */ 
    private final int count; 

और बराबरी के तरीके के रूप में प्रस्तुत किया जाता है है

if (this == anObject) { 
    return true; 
} 
if (anObject instanceof String) { 
    String anotherString = (String)anObject; 
    int n = count; 
    if (n == anotherString.count) { 
     char v1[] = value; 
     char v2[] = anotherString.value; 
     int i = offset; 
     int j = anotherString.offset; 
     while (n-- != 0) { 
      if (v1[i++] != v2[j++]) 
       return false; 
     } 
     return true; 
    } 
} 
return false; 

के बराबर होती है विधि दोनों इस == anObject और n == anotherString करता है .count, अनिवार्य रूप से पूर्णांक तुलना दोनों, वर्णों की तुलना करना शुरू करने से पहले भी।यह एक अनुदेश कि एक पूर्णांक की तुलना से अधिक समय एक बहुत ले जा रहा है

---

सी स्ट्रिंग तुलनासरल है/तेजी से जावा से बराबर लेकिन यह पाश और कई निर्देश के कुछ प्रकार में शामिल होंगे लेता है लूप के माध्यम से प्रत्येक पास के लिए।

यह एक अनुदेश कि एक पूर्णांक की तुलना से अधिक समय लग जाएगा