27/05/2010
0
Bài viết này trình bày những nghiên cứu và giải pháp của tác giả để tìm kiếm các phần tử không trùng nhau trong một mảng cực lớn với chi phí thời gian là thấp nhất. Giải pháp này được tác giả xem là nhanh nhất và có liên quan đến giải thuật mà chúng ta đã biết "Hash Sieving". Vui lòng vào trang chi tiết để xem thêm.
Nếu thích, bạn có thể xem thêm về Các giải thuật sắp xếp JavaScript, Sắp xếp một chuỗi số, Sắp xếp chữ cái.
- Demo
- Phóng to
- Tải lại
- Cửa sổ mới
Miễn phí web hosting 1 năm đầu tại iPage
Nếu bạn vẫn còn đang tìm kiếm một nhà cung cấp hosting đáng tin cậy, tại sao không dành chút thời gian để thử với iPage, chỉ với không quá 40.000 VNĐ/tháng, nhưng bạn sẽ được khuyến mãi kèm với quà tặng trị giá trên 10.000.0000 VNĐ nếu thanh toán cho 24 tháng ~ 900.000 VNĐ?
Có trên 1 triệu khách hàng hiện tại của iPage đã & đang hài lòng với dịch vụ, tuyệt đối chắc chắn bạn cũng sẽ hài lòng giống họ! Quan trọng hơn, khi đăng ký sử dụng web hosting tại iPage thông qua sự giới thiệu của chúng tôi, bạn sẽ được hoàn trả lại toàn bộ số tiền bạn đã sử dụng để mua web hosting tại iPage. Wow, thật tuyệt vời! Bạn không phải tốn bất kì chi phí nào mà vẫn có thể sử dụng miễn phí web hosting chất lượng cao tại iPage trong 12 tháng đầu tiên. Chỉ cần nói chúng tôi biết tài khoản của bạn sau khi đăng ký.
Nếu muốn tìm hiểu thêm về ưu / nhược điểm của iPage, bạn hãy đọc đánh giá của ChọnHostViệt.com nhé!
When I had the requirement to remove duplicate items from a very large array, I found out that the classic method to be not optimized as it took a pretty long time than desired. So, I devised this new algorithm that can sort a large array in a fraction of the original time.
The fastest method to find unique items in array
This method is kind of cheeky in its implementation. It uses the JavaScript's object to add every item in the array as key. As we all know, objects accepts only unique keys and sure we did capitalize on that.
-
Array.prototype.unique = function() {
-
var o = {}, i, l = this.length, r = [];
-
for(i=0; i<l;i++) o[this[i]] = this[i];
-
for(i in o) r.push(o[i]);
-
return r;
-
};
Some Thoughts On This Algorithm
This is somewhat classified as "Hash Sieving" method and can also be related to a somewhat modified "Hash Sorting Algorithm" where every item in the array is a hash value and a hash function inserts item into a bucket, replacing existing values in case of hash collision. As such, this can be applied to any programming language for faster sieving of very large arrays.
This algorithm has a linear time complexity of O(2n) in worst case scenario. This is way better than what we will observe for the classic method as described below.
About the classic method
The classic (and most popular) method of finding unique items in an array runs two loops in a nested order to compare each element with rest of the elements. Consequently, the time complexity of the classic method to find the unique items in an array is around quadratic O(n²).
This is not a good thing when you have to find unique items within array of 10,000 items.
-
Array.prototype.unique = function() {
-
var a = [], l = this.length;
-
for(var i=0; i<l; i++) {
-
for(var j=i+1; j<l; j++)
-
if (this[i] === this[j]) j = ++i;
-
a.push(this[i]);
-
}
-
return a;
-
};
Comparing the above two algorithms
Test Data: An array of elements having N random integers.
| Sample (N) | Average Case | Best Case | ||
| Classic | New | Classic | New | |
| 50 | 0.43 | 0.25 | 0.01 | 0.02 |
| 100 | 0.60 | 0.30 | 0.09 | 0.16 |
| 500 | 9.57 | 0.87 | 0.1 | 0.2 |
| 1000 | 24.44 | 1.51 | 0.21 | 0.31 |
| 5000 | 584.28 | 7.74 | 0.4 | 1.0 |
| 10000 | 2360.90 | 15.03 | 0.7 | 1.8 |
Conclusion
This method of finding unique items within an array seems to be particularly useful for large arrays that are tending towards the real-life situations. When there are more items in an array that are similar, there is not much of a difference in performance and in fact, the classic algorithm scores better by a small margin. However, as the array gets more random, the runtime of the classic algorithm increases manifold.
More JavaScript Algorithms: Algorithms by JavaScript
bởi Xem- Lượt gửi (0)
- Mới
Save up to 630$ when buy new iPhone 15
GateIO.gomymobi.com
Free Airdrops to Claim, Share Up to $150,000 per Project
https://tooly.win
Open tool hub for free to use by any one for every one with hundreds of tools
chatGPTaz.com, chatGPT4.win, chatGPT2.fun, re-chatGPT.com
Talk to ChatGPT by your mother language
Dall-E-OpenAI.com
Generate creative images automatically with AI
AIVideo-App.com
Render creative video automatically with AI
Cool Domains for Sale!
Tác giả:
Lượt xem:
Lời bình:
Lượt đánh giá:
Lượt gửi:
Kích thước:
Thứ hạng:
Shamasis Bhattacharya [more]
18,110
0
1
0
12.98 KBytes
1 lượt đánh giá / 18,110 lượt xem / 0 lời bình
27/05/2010
Bài viết này trình bày những nghiên cứu và giải pháp của tác giả để tìm kiếm các phần tử ...Giải thuật JavaScript nhanh nhất để tìm phần tử duy nhất trong mảng - Giải thuật JavaScript nhanh nhất để tìm phần tử duy nhất trong mảng - Ngôn ngữ: tiếng Việt
