unique() cho mảng trong javascript

Question

Như mọi người đều biết không có hàm dựng sẵn để loại bỏ các bản sao khỏi một mảng trong javascript. Tôi đã nhận thấy điều này cũng thiếu jQuery (có chức năng duy nhất cho các lựa chọn DOM) và đoạn mã phổ biến nhất mà tôi tìm thấy sẽ kiểm tra toàn bộ mảng và một tập hợp con của nó cho mỗi phần tử (không phải là rất hiệu quả), như :

for (var i = 0; i < arr.length; i++) 
    for (var j = i + 1; j < arr.length; j++) 
     if (arr[i] === arr[j]) 
      //whatever 

vì vậy tôi làm của riêng tôi:

function unique (arr) { 
    var hash = {}, result = []; 
    for (var i = 0; i < arr.length; i++) 
     if (!(arr[i] in hash)) { //it works with objects! in FF, at least 
      hash[arr[i]] = true; 
      result.push(arr[i]); 
     } 
    return result; 
} 

tôi tự hỏi nếu có bất kỳ thuật toán khác được chấp nhận như là tốt nhất cho trường hợp này (hoặc nếu bạn thấy bất kỳ lỗ hổng rõ ràng mà có thể được cố định), hoặc , bạn làm gì khi bạn cần điều này trong javascript (Tôi biết rằng jQuery không phải là khung duy nhất và một số khác có thể có điều này đã được bảo hiểm).

Answer 1

Sử dụng đối tượng theo nghĩa đen là chính xác những gì tôi sẽ làm. Rất nhiều của những người bỏ lỡ kỹ thuật này rất nhiều thời gian, chọn thay vào đó để đi bộ mảng điển hình như mã ban đầu mà bạn đã hiển thị. Tối ưu hóa duy nhất là tránh tra cứu arr.length mỗi lần. Ngoài ra, O (n) là tốt như bạn nhận được cho tính độc đáo và tốt hơn nhiều so với ví dụ O (n^2) ban đầu.

function unique(arr) { 
    var hash = {}, result = []; 
    for (var i = 0, l = arr.length; i < l; ++i) { 
     if (!hash.hasOwnProperty(arr[i])) { //it works with objects! in FF, at least 
      hash[ arr[i] ] = true; 
      result.push(arr[i]); 
     } 
    } 
    return result; 
} 

// * Edited to use hasOwnProperty per comments 

Thời gian phức tạp để tóm tắt

f() | unsorted | sorted | objects | scalar | library 
____________________________________________________________ 
unique | O(n) | O(n) | no | yes | n/a 
original | O(n^2) | O(n^2) | yes | yes | n/a 
uniq  | O(n^2) | O(n) | yes | yes | Prototype 
_.uniq | O(n^2) | O(n) | yes | yes | Underscore 

Như với hầu hết các thuật toán, có offs thương mại. Nếu bạn chỉ phân loại các giá trị vô hướng, bạn đang sửa đổi thuật toán gốc đưa ra giải pháp tối ưu nhất. Tuy nhiên, nếu bạn cần sắp xếp các giá trị không vô hướng, thì việc sử dụng hoặc bắt chước phương thức uniq của một trong hai thư viện được thảo luận sẽ là lựa chọn tốt nhất của bạn.

Answer 2

Tôi nghĩ phiên bản của bạn sẽ không hoạt động khi bạn sẽ có đối tượng hoặc chức năng trong mảng cung cấp biểu diễn dạng chuỗi như [Object object]. Bởi vì bạn chỉ có thể có các chuỗi như các khóa trong các đối tượng (trong đối tượng "băm" ở đây). Bạn sẽ cần phải lặp vào mảng kết quả để tìm xem mục nhập mới đã tồn tại chưa. Nó sẽ vẫn nhanh hơn phương pháp đầu tiên.

JS nguyên mẫu có phương thức "uniq", bạn có thể lấy cảm hứng từ đó.

Answer 3

Tôi không phải là chuyên gia về thuật toán bằng bất kỳ phương tiện nào, nhưng tôi đã theo dõi underscore.js. Họ có điều này như một chức năng gọi là uniq:

http://documentcloud.github.com/underscore/#uniq

Tôi nhìn mã trong thư viện của họ, và sao chép nó vào đây để tham khảo (không mã của tôi, mã này thuộc về underscore.js):

// Produce a duplicate-free version of the array. If the array has already 
// been sorted, you have the option of using a faster algorithm. 
_.uniq = function(array, isSorted) { 
    return _.reduce(array, [], function(memo, el, i) { 
     if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo.push(el); 
     return memo; 
    }); 
}; 

EDIT: Bạn cần phải đi qua phần còn lại của mã underscore.js và tôi gần như đã lấy mã này ra vì nó. Tôi đã để lại đoạn mã chỉ trong trường hợp điều này vẫn hữu ích.

Answer 4

Thật không may các đối tượng JS không nhận dạng được từ ngôn ngữ - như các áp phích khác đã đề cập, sử dụng các đối tượng làm khóa trong từ điển sẽ thất bại khi các đối tượng khác nhau có biểu diễn chuỗi bằng nhau và không có hàm id().

Có một cách để tránh O (n^2) tất cả các cặp kiểm tra số === nếu bạn có thể sửa đổi các đối tượng.Chọn một chuỗi ngẫu nhiên, đi bộ mảng một lần để kiểm tra xem không có đối tượng nào có thuộc tính theo tên đó, sau đó chỉ cần arr[i][randomPropertyName]=1 cho mỗi i. Nếu đối tượng tiếp theo trong mảng đã có thuộc tính đó, thì nó là một bản sao.

Thật không may, phần trên sẽ chỉ hoạt động đối với các đối tượng có thể sửa đổi. Nó không cho các giá trị mảng không cho phép thiết lập tài sản (ví dụ như số nguyên, 42['random']=1 chỉ không hoạt động :()

Answer 5

vui vẻ với niềm vui (ctional)

function uniqueNum(arr) { 
    return Object.keys(arr.reduce(
     function(o, x) {o[x]=1; return o;}, {})).map(Number); 
}