A Beginner's Guide to Efficient Program Design
h
MrEconomical (383)

this is my first tutorial lul

What is program design?

Program design is the way a program achieves its goal. When you write a program, it's how you want it to work. Most programs are algorithms, which mean they follow a series of steps to reach the end result. The efficiency of these algorithms are important in order to achieve the end goal in a manner that uses the least resources and is as fast as possible.

Why do I care?

Let's say that you have an unordered array of 100,000 integers. You are given 1,000 numbers as search queries, and your goal is to determine whether or not that number exists in the array.

A simple approach to this problem would be a brute force method, simply looping through the entire array to check if the number exists for each query.

Something like this (I'm not very good at pseudocode sorry):

array = [...]
queries = [...]

for (q in queries) {
	found = false

	for (n in array) {
		if (q == n) {
			found = true
		}
	}

	if (found) {
		print(q, "is in the array")
	} else {
		print(q, "is not in the array")
	}
}

Now let's analyze the time complexity of this program, or the amount of time it will take to run. For every query, the program loops through the array. In a worst case scenario, it will have to loop through the entire array before finding the number. Roughly, the program will have to perform 1,000 * 100,000 = 1,000,000,000 operations to complete the task. With a larger set of numbers, the code will take even longer.

A more efficient approach to this problem might be using binary search, which is a search technique that only works on sorted arrays. The basic principle is to halve the size of the array if the target number is greater than or less than the current number. For example, let’s say the target number was 6. If the middle number in the sorted array is 5, then I know if 6 exists, it has to be greater than 5 so the search size was just cut in half. Because of this, binary search takes only log base 2 of the size of the array to find a number. With this method, sorting the array and then performing binary search is much more efficient than the brute force method, only requiring (100,000 * lg(100,000)) + (1,000 * lg(100,000)) = ~1,600,000 operations.

As you can see, a more efficient program can result in a massive optimization and perform the same task significantly faster.

How do I make my code more efficient?

1. Think before coding

When presented with a task, many people will immediately start coding to try to find a way that works, any way. They solve problems on the go and keep trying until their program works. This approach is fine if you just want something that works, but to make something very efficient requires lots of planning and thinking beforehand.

Always keep your end goal in mind, and think of different ways to achieve that goal before starting to code. Plan out how your program is going to work beforehand, and then implement your ideas.

2. Learn some basic algorithms

A giant project can be broken down into many different little parts. For example, if you wanted to make a tic-tac-toe game, you would have to make a user interface, a control system, and the actual game logic. Knowing some efficient algorithms that do specific things can allow you to pull from your previous knowledge to make efficient systems in your project. Some basic ones include binary search, depth-first search and breadth-first search. Many great online resources exist that explain some basic algorithms.

3. Practice

Practice, practice, and more practice. Develop a deeper understanding of algorithms and advanced techniques. Eventually, you will be able to solve some problems based on past experience. Practice gives you a lot of background knowledge that will help you in future endeavors. The more you try to make your programs more efficient, the more efficient they will become.

Conclusion

Efficiency is key to writing great code, whether it be for a website, a server, a database, or a game. Learning to design efficient algorithms is a very important skill to have. Ultimately, the fastest and best programs are those that are the most economical.

You are viewing a single comment. View All
mwilki7 (519)

Recommended after the programs have been written and better algorithms are still desired.