जावास्क्रिप्ट: कुशलतापूर्वक दो पूर्णांक सरणी की तुलना करें

Question

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

ऐसा करने का स्पष्ट तरीका छोरों के लिए नीडिंत है:

var containedInFirst = false; 
for (var primaryID = 0; primaryID < PrimaryArray.length; primaryID++) { 
     containedInFirst = false; 
     for (var secondaryID = 0; secondaryID < SecondaryArray.length; secondaryID++) { 
      if (PrimaryArray [primaryID] === SecondaryArray[secondaryID]) { 
       containedInFirst = true; 
       break; 
      } 
     } 

//Do some more stuff based on the value of containedInFirst here 
} 

लेकिन दिया सूचियों सैकड़ों या रिकॉर्ड के हजारों हो सकता है यह काफी itteration और प्रोसेसर गहन का एक सा है। इसलिए मैं सोच रहा था कि उपरोक्त कोड को निष्पादित करने का एक और अधिक प्रभावी तरीका है? न केवल वास्तविक खोज, बल्कि मूल्यों के कंटेनर के रूप में एक इंटीजर सरणी से कुछ अधिक कुशल, या सामग्री को पार करने और तुलना करने के लिए लूप के लिए नेस्टेड का उपयोग न करें।

अधिक कुशल या सुरुचिपूर्ण समाधानों पर कोई विचार?

Answer 1

उन्हें समानांतर में पहले और बतख-वेडल को क्रमबद्ध करें।

a.sort(); 
b.sort(); 

left = []; both = []; right = []; 
i = 0; j = 0; 
while (i < a.length && j < b.length) { 
    if (a[i] < b[j]) { 
     left.push(a[i]); 
     ++i; 
    } else if (b[j] < a[i]) { 
     right.push(b[j]); 
     ++j; 
    } else { 
     both.push(a[i]); 
     ++i; ++j; 
    } 
} 
while (i < a.length) { 
    left.push(a[i]); 
    ++i; 
} 
while (j < b.length) { 
    right.push(b[j]); 
    ++j; 
} 

Answer 2

क्रमबद्ध दोनों सरणियों, पाश से सिर्फ एक बार और तुलना करें:

function diff(arrayToCompareTo, comparedArray) 
{ 
    Sort(arrayToCompareTo); 
    Sort(comparedArray); 

    var difference = [], same = []; 
    for(var i = 0; i < arrayToCompareTo.length; ++i) 
    { 
    if (arrayToCompareTo[i] != comparedArray[i]) 
     difference.push(comparedArray[i]); 
    else 
     same.push(comparedArray[i]); 
    } 

    if (comparedArray.length > arrayToCompareTo.length) 
    for(var i = arrayToCompareTo.length; i < comparedArray.length; ++i) 
     difference.push(comparedArray[i]); 
} 

यह परीक्षण नहीं किया है, इसलिए यदि कुछ गलत है तो कृपया मुझे बताएं।
वैसे भी यह आपको सही दिशा में सेट कर देना चाहिए क्योंकि यह ओ (एन) सर्वोत्तम है और ओ (एम) comparedArray.length > arrayToCompareTo.length पर सबसे खराब है, यह ओ (एन^2) से अधिक कुशल है। ध्यान दें कि सॉर्टिंग ओ (एन लॉग एन) लेता है।

Answer 3

दो नेस्टेड लूप का उपयोग करते समय जटिलता ओ (एन * एन) होगी। दोनों सरणी को सॉर्ट करना जटिलता ओ (एन लॉग एन) में किया जा सकता है।

के रूप में मार्सेलो Cantos समानांतर में दोनों के माध्यम से बतख-waddle :) कहा जटिलता हे (एन) हे की एक समग्र जटिलता के लिए अग्रणी (एन एन लॉग इन करें) + O (एन) जो हे है (एन एन लॉग इन करें) है।

Answer 4

मैं मैं हे (एन) की दक्षता के साथ समाधान (कोई तरह की जरूरत है) लगता है, यहाँ यह है:

var firstNotSecond; 
function CompareIntArrays(arr1, arr2) 
{ 
    firstNotSecond = new Array(); 

    var arr3 = new Array(); //appear in both 
    var arrTemp = new Array(); //used for firstNotSecond 
    var usedNumbers = new Array(); 

    for (var i = 0; i < arr1.length; i++) 
    { 
     var key = arr1[i]; 
     usedNumbers[key] = true; 
     arrTemp[key + ""] = true; 
    } 

    for (var i = 0; i < arr2.length; i++) 
    { 
     var key = arr2[i]; 
     if (usedNumbers[key]) 
     { 
      arr3[arr3.length] = key; 
      arrTemp[key] = false; 
     } 
    } 

    for (var key in arrTemp) 
     if (arrTemp[key]) 
      firstNotSecond[firstNotSecond.length] = parseInt(key); 

    return arr3; 
} 

समारोह आइटम है कि दोनों सरणियों में मौजूद साथ नई सरणी वापस आ जाएगी, और होगा पहले सरणी में मौजूद सभी आइटमों के साथ वैश्विक सरणी असाइन करें जो कि दूसरी सरणी में मौजूद नहीं है।

यह कोड इस तथ्य पर भरोसा कर रहा है कि दोनों सरणी केवल पूर्णांक संख्याएं हैं।

प्रयोग उदाहरण: एक सेकंड से भी कम:

alert(CompareIntArrays([15, 551, 25, 910, 11], [25, 11, 785, 880, 15])); 
alert(firstNotSecond); 

सरणियों 100,000 आइटम होने के साथ परीक्षण किया गया। प्रत्येक 200,000 आइटम वाले सरणी के साथ परीक्षण: 2 सेकंड से कम।

Answer 5

एक और संभावना उन एरे को ऑर्डर करने के दौरान ऑर्डर कर सकती है। मुझे यकीन नहीं है कि आप ऐसा कर सकते हैं। लेकिन यदि आप कर सकते हैं, तो यह ओ (1) के बजाय सरणी (ओ (लॉग एन) में तत्व जोड़ने की पूर्णता को बढ़ाएगा) लेकिन यह आपकी तुलना एल्गोरिदम की जटिलता को ओ (एन)

Answer 6

पर कम करेगा

हर कोई इस पर अत्यधिक जटिल है।"सुंदर" भाग के लिए

var isEqual = (JSON.stringify(arr1.sort()) === JSON.stringify(arr2.sort()));