Javascript: so sánh hiệu quả hai mảng số nguyên

Question

Tôi có hai mảng số nguyên chứa các giá trị số. Tôi muốn xem qua cả hai danh sách và kiểm tra tính phổ biến (hoặc thiếu) giữa các danh sách. I E. Tôi muốn lặp qua các mảng (s) và tìm thấy các mục xuất hiện trong cả hai danh sách, trong khi trong một chức năng riêng biệt tôi muốn đi qua các mảng và tìm các mục trong lần đầu tiên và không phải trong lần thứ hai.

Cách rõ ràng để làm điều này được lồng cho vòng:

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 
} 

Nhưng với danh sách có thể chứa hàng trăm hoặc hàng ngàn hồ sơ này là khá nhiều itteration và bộ xử lý chuyên sâu. Do đó tôi tự hỏi liệu có cách nào hiệu quả hơn để thực thi mã trên không? Không chỉ tìm kiếm thực tế mà còn hiệu quả hơn một mảng Integer làm vùng chứa cho các giá trị, hoặc không sử dụng lồng nhau cho các vòng lặp để duyệt và so sánh nội dung.

Bất kỳ suy nghĩ nào về các giải pháp hiệu quả hơn hoặc thanh lịch hơn?

Answer 1

Sắp xếp chúng đầu tiên và lượn dọc theo chúng song song.

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

Sắp xếp cả hai mảng, so với vòng chỉ một lần và so sánh:

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]); 
} 

Đây không phải là thử nghiệm vì vậy nếu một cái gì đó là sai xin vui lòng cho tôi biết.
Dù sao điều này sẽ đặt bạn đi đúng hướng vì nó là O (N) ở mức tốt nhất và O (M) ở mức thấp nhất nếu comparedArray.length > arrayToCompareTo.length, hiệu quả hơn nhiều so với O (N^2). Lưu ý rằng sắp xếp có O (N log N).

Answer 3

Khi sử dụng hai vòng lồng nhau, độ phức tạp sẽ là O (n * n). Sắp xếp cả hai mảng có thể được thực hiện theo độ phức tạp O (n log n).

AS Marcelo Cantos đã nói vịt-waddle :) thông qua cả hai trong paralell có phức tạp O (n) dẫn đến một tổng thể phức tạp của O (n log n) + O (n) là O (n log n).

Answer 4

Tôi nghĩ rằng tôi có giải pháp có hiệu quả của O (N) (không loại cần thiết), ở đây nó là:

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; 
} 

Chức năng sẽ trở lại mảng mới với các mục mà tồn tại trong cả hai mảng, và sẽ gán mảng toàn cục với tất cả các mục hiện có trong mảng đầu tiên không tồn tại trong mảng thứ hai.

Mã này dựa trên thực tế cả hai mảng chỉ giữ số nguyên.

Cách sử dụng Ví dụ:

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

Tested với mảng có 100.000 mục: ít hơn một giây. Được thử nghiệm với các mảng có 200.000 mục mỗi: ít hơn 2 giây.

Answer 5

Một khả năng khác có thể đặt hàng các mảng đó khi bạn tạo chúng. Tôi không chắc chắn nếu bạn có thể làm điều đó. Nhưng nếu bạn có thể, nó sẽ tăng một chút sự phức tạp của việc thêm một phần tử vào mảng (O (log n) thay vì O (1)) nhưng nó sẽ làm giảm độ phức tạp của thuật toán so sánh của bạn thành O (n)

Answer 6

Mọi người đều quá phức tạp điều này.Dưới đây là một liner:

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