Do you really need to use loop operation? Think it over!
As a programmer, the first instinct of searching for something in a collection of objects will be looping through it! It is a straight solution and often times very fast, if, and only if the collection is small. However, once the size of collection goes big, it can hurt your program's performance a lot. So when you need to search for a large array, what do you do?
1) Binary search. BS is always a fast and effective way to search if the array is sorted. Regular looping through an array, aka linear search, takes O(n), but binary search takes O(logn), which is much faster. To make it into perspective, please refer to the below chart. As you can see, when the n is very small, linear search might be a little bit faster than binary search, because binary search has to do a little bit more work than a linear search method. However, when n is large, binary search is way faster than linear search.
Binary search is also very easy to code up. Let us use a simple Python code to demonstrate below:
2) What if the array is not sorted?! Bang! It is certainly not a good position to be. If you can control how the array is generated, and you know it will grow large, make it sorted. Well, if the array is not controlled by you and it is not sorted, you still can do something to make it faster. Even though the complexity will be O(n), you can divide the array into several chunks, and use multi-process to search them in parallel. In this case, the initial prep-up might take some time, but once it is done, your searching will use much less time than a normal brutal force linear search. You also can make your code asynchronously, so latter program does not need to wait for the searching to be done.
1) Binary search. BS is always a fast and effective way to search if the array is sorted. Regular looping through an array, aka linear search, takes O(n), but binary search takes O(logn), which is much faster. To make it into perspective, please refer to the below chart. As you can see, when the n is very small, linear search might be a little bit faster than binary search, because binary search has to do a little bit more work than a linear search method. However, when n is large, binary search is way faster than linear search.
Binary search is also very easy to code up. Let us use a simple Python code to demonstrate below:
2) What if the array is not sorted?! Bang! It is certainly not a good position to be. If you can control how the array is generated, and you know it will grow large, make it sorted. Well, if the array is not controlled by you and it is not sorted, you still can do something to make it faster. Even though the complexity will be O(n), you can divide the array into several chunks, and use multi-process to search them in parallel. In this case, the initial prep-up might take some time, but once it is done, your searching will use much less time than a normal brutal force linear search. You also can make your code asynchronously, so latter program does not need to wait for the searching to be done.
Comments
Post a Comment