This content originally appeared on Level Up Coding - Medium and was authored by Mohamed Hijazi
The important part of any project development in Unity is project analysis to check for performance issues and optimization. At the heart of optimization lies Big O.
Big O notation is a method that expresses the relationship between many steps an algorithm will require related to the size of input data, in other words how complex the algorithm is.
Understanding Big O notation in Unity
Big O notation is a way to measure an algorithm’s efficiency. It allows us to understand space time complexity of our code.
The best example to understand Big O is when you have a big list of items and you want to find an item in the list. Using a for /foreach loop is quick for very small list, but when the list grows, this is when your performance will start taking a hit.
O of N
This is known as O of N, where N is the amount of data you had to filter. The best case scenario is O of 1, where 1 is the 1st item you want in the list. The worst case scenario is where N is the last item in the list. So if you have 100 items, and the item you need is in the 90th slot, using a for loop would have taken you 90 iterations until you find the item you need, which very inefficient. This is called linear search.
Big O Binary Search
Binary search is the solution for big lists, it is an efficient algorithm for finding your item in a big list. It is also known as half-interval search or a binary chop.
Simply put, the algorithm will half your list, and continue halving it until it finds the item you need using O of 1 (best case scenario) instead of O of N.
A very important step is to first sort your list.
Example
int[] ages = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};As you see the list is already sorted, and let’s say we need to find the int 4.
Using the binary search, first we half the array:
//length of array (10) / 2 = 5
So the middle of the array is 5, so we check is 4 is greater than 5 which no, so the half on the right side of 5 will not be used anymore and we will use the left side of 5.
so new list is:
1, 2, 3, 4, 5
We go again and half the new list again, and we check 4 is on which side. Here it is on the right side, so we half the list again and we will remain with a new array:
4, 5
Now in this final list, 4 is our 1st item in the list, which is O of 1.
When our list is big, doing this algorithm is way more efficient that doing a normal for loop to find our item. So the time complexity for binary search where we halving the array each time, is way less complex than a normal loop. DIVIDE AND CONQUER.
This algorithm is also known as O(Log n): halving a list.
In the next article, we will dive a little deeper into the BIG O.
Big O Unity Optimization was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Mohamed Hijazi
Mohamed Hijazi | Sciencx (2021-08-16T15:58:06+00:00) Big O Unity Optimization. Retrieved from https://www.scien.cx/2021/08/16/big-o-unity-optimization/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.