27/05/2010
0
This JavaScript tutorial shows the author's experiences and solution to find the unique items in a very large JavaScript array for the minimum time. This solution is considered the best by author and it relates to an algorithm that we knew "Hash Sieving". Please go to the full post for more.
If you like sorting array, let try Algorithms by JavaScript, JavaScript Bubble Sort.
- Demo
- Enlarge
- Reload
- New window
Free iPage Web Hosting for First Year NOW
If you're still looking for a reliable web host provider with affordable rates, why you don't take a little of time to try iPage, only with $1.89/month, included $500+ Free Extra Credits for the payment of 24 months ($45)?
Over 1,000,000+ existisng customers can not be wrong, definitely you're not, too! More important, when you register the web hosting at iPage through our link, we're going to be happy for resending a full refund to you. That's awesome! You should try iPage web hosting for FREE now! And contact us for anything you need to know about iPage.
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
by Preview- Sent (0)
- New
Generate your business videos by AI with voice or just text
chatGPTaz.com
Talk to ChatGPT by your mother language
AppAIVideo
Your first FREE AI Video App
Deepfake Video
Deepfake AI Video Maker
Deepfake
Deepfake AI Video Maker
AI Deep Fake
Deepfake AI Video Maker
AIvidio
AI Video Mobile Solutions
AIvideos
AI Video Platform & Solutions
AIvedio
AI Video App Maker
Artificial General Intelligence
Ai and higher level Artificial General Intelligence (AGI)
Artificial General Intelligence
Ai and higher level Artificial General Intelligence (AGI)
Faceswap AI Online
Swap Faces Video, Photo & GIFs Instantly with Powerful AI Tools - Faceswap AI Online FREE
Faceswap AI Online
Swap Faces Video, Photo & GIFs Instantly with Powerful AI Tools - Faceswap AI Online FREE
Faceswap AI Online
Swap Faces Video, Photo & GIFs Instantly with Powerful AI Tools - Faceswap AI Online FREE
Powerful AI Presentation PPT Maker for FREE
Build an impressive presentation with our free online AI presentation app
Your next top AI Assistant
Claude AI, developed by Anthropic
Your next top AI Assistant
Claude AI, developed by Anthropic
Temu Free $500 for New Users
Claim Free Temu $500 Credit via Affiliate & Influencer Program
Free TikTok Ads Credit
Master TikTok Ads for Your Business Marketing
Dall-E-OpenAI.com
Generate creative images automatically with AI
chatGPT4.win
Talk to ChatGPT by your mother language
First AI Product from Elon Musk - Grok/UN.com
Speak to Grok AI Chatbot with Your Language
Tooly.win
Open tool hub for free to use by any one for every one with hundreds of tools
GateIO.gomymobi.com
Free Airdrops to Claim, Share Up to $150,000 per Project
iPhoneKer.com
Save up to 630$ when buy new iPhone 16
Buy Tesla Optimus Robot
Order Your Tesla Bot: Optimus Gen 2 Robot Today for less than $20k
Cool Domains for Sale!
Author:
Previews:
Comment:
Votes:
Sent:
Size:
Rank:
Shamasis Bhattacharya [more]
18,659
0
1
0
12.98 KBytes
1 votes / 18,659 previews / 0 comment
27/05/2010
This JavaScript tutorial shows the author's experiences and solution to find the unique items in a very large JavaScript...JavaScript Fastest Algorithm to Query Unique Items in Array - JID: 2368 - JavaScript Fastest Algorithm to Query Unique Items in Array - Language: English
