Diving into Java (with strong JavaScript and Python background) Part 4(Algorithms)

Welcome back to my journey to learn and become proficient in Java. To recap, my plan of action is as follows:

1. √ Load most common environment
2. √ Research naming conventions
3. √ Hello World app to confirm environment set up properly
4. √ Review and practice basic data types and available methods in Java
5. √ Review and practice equivalents to arrays/lists and objects/dictionaries in Java
6. Algorithm practice
7. Sample projects with the above knowledge
8. Learn Spring framework
9. Sample projects with Spring with REST API and WebSockets or Socket.IO

In my previous article, I explored the different data structures that build upon the primitive data types and how they relate to the data structures utilized in JavaScript and Python. So let’s apply this knowledge by implementing some basic algorithms.

When practicing algorithms, I like to implement them without using other libraries or external functions (including those from a language’s standard library). Part of the practicing algorithms is 1) to better understand how commonly used methods work under the hood, and 2) to learn concepts that can be applied to solving your own problems in writing code.

In Wordle Clash, a recent group project with two other classmates at DigitalCrafts, I was responsible for implementing the entirety of the game logic via Socket.IO. One of the tasks in this project, determining which letters were in the word and which letters were in the correct spot, seemed simple at first glance. However, there were some cases that needed to be addressed that added some complexity to handle properly — what if the player entered the same letter twice? Does that letter appear twice in the word? What if that letter was only in the word once, and the second instance of the letter in the guess was the in the correct position? The answers to these questions necessitated that if a letter is in the word, I would need to find all instances of the letter within the word and the guess and determine which instances to mark as correct and which ones to mark as incorrect. This in turn introduces another computational problem: if say the letter “e” was guessed for spots 2 and 5, do I really need to run that series of steps to determine how to mark each “e” a second time?

I solved this problem in a similar way to what I saw with an optimal algorithm for determining if a given number is a prime number or not: the trick is to determine if you really need to do a computational heavy operation before you let that operation start. The trick to making any algorithm efficient (especially at larger sample sizes) is to find ways to drastically reduce the sample size to perform the heavy lifting on. In this article, I will explore how to complete a few algorithms the syntactically Java way.

Sorting

A common problem the appears while creating software is the need to take a list of data and sort the items into particular order. While writing the code, we can only compare two values at the same time — we won’t be able to visually group together multiple numbers to move around at the same time as you might do if you were physically sorting index cards. There are several different sorting strategies and solutions available. I will look at a couple of the simple sort algorithms and a couple more efficient algorithms. Before I jump into it, I need to set up a few couple utility functions:

The first two functions are helpers to decide where two elements should be in relation to each other. The first is utilized for algorithms that sort by swapping elements sequentially until in the proper positions. Using a ternary operator allows for a simple flag to switch between sort directions. The second is used for the divide and conquer strategies that place elements into the proper positions. The final function is used to simplify the process of swapping two elements in an array within the algorithm code.

Bubble Sort

Bubble sort is a simple sorting algorithm that loops through the entire array several times swapping adjacent elements as needed until we have a sorted array. Some of the shortcomings with this approach is for each item in the array, we loop through every item in the array. Going through the entirety of an array multiple times is very costly in terms of CPU cycles, the electricity to perform those cycles, or vCPU hours on Amazon Web Services. On large data sets, this can potentially cost hundreds, if not thousands, of times more if the algorithm isn’t efficient. One thing to note on the implementation above: what if the array is already sorted or becomes sorted early in the process? As is, it is running the comparison loops on every item multiple times even if it’s sorted. One way to improve this algorithm for best case scenario is to add some code before, during, and after the inner loop to indicate whether the inner loop results in any swaps:

Insertion Sort

The idea behind insertion sort is that as you go from left to right, every time you find a number out of position, you place that item in the correct position in relation to the already sorted numbers on the left. Some features about the insertion sort is that the inner loop length shrinks for each iteration of the outer loop, and there is potential that the inner loop may not even need to run on some of the iterations of the outer loop due to the if condition the gates access to the inner loop.

Merge Sort

Merge sorts utilize a divide and conquer strategy. The basic idea is we’re cutting the sample size into half and sorting those halves, then rebuilding the array so that the elements are in order. This is also the first algorithm we explored that utilizes the concept of recursion — the concept of a function calling itself and making a new instance of itself. For each call of the function, we call itself on the left half, then the right half, then merge the halves together. The merging makes an extra copy of both halves in memory, so this algorithm pays the cost of extra memory in order to reduce CPU cycles. The first time merge actually gets called is when the two halves are single element arrays, then each time merge is subsequently called, halves are longer but already sorted.

Quick Sort

The idea behind quick sort is every time an element is processed, it is in the proper position. An element is selected, called the pivot, then every element smaller than that is placed on the left side of it, and every element larger than it is placed on the right side (reverse if sorting in descending order). At the end of each step, we know the pivot is place in the correct location. It’s overall a pretty efficient method to sort a list of items. A couple scenarios that produce efficiency decline with quick sort is when the pivot element is the highest or lowest value of the entire list. This can be mitigated in a couple ways: select the middle element as the pivot for each step, or pick a random element. There are several more sorting algorithms available that can handle some of these worst-case scenarios more effectively. I’ll explore and learn more of these outside of article writing, so let’s move on to a couple of searching algorithms.

Searching

Another common problem that appears while developing software is the need to be able to retrieve a specific item within a list of data. Like sorting, we aren’t able to just scan over multiple items at a time while writing code. We need to read one item at a time, then see if it’s the item we need. There are numerous strategies using different data types to accomplish this task. Today, I will look at two.

Linear Search

The first basic search method is the linear search. The idea behind this method is to start from the beginning then checking one by one for the correct element. It’s common to return the index (position number) of the correct element or -1 if the element is not found. As you can imagine with this approach, if the element you need is the last item of the list, you have to traverse the entirety of the list before you get to the desired element. The longer the list is, the longer it is to find an item on the last slot. Let’s look at a method that will allow us to find items faster.

Binary Search

The other search method I’ll explore in this article is the binary search. The beauty of this algorithm is that it can find matches in just a few steps. The big caveat with this algorithm is that the array has to be already sorted for this to work. How it works is we compare if the middle element in our target first. If it isn’t, we then determine if the target is higher or lower than the middle element. If it is higher, we can toss out all the elements before the middle element, as well as the middle element itself in one step. By drastically reducing our sample space during each step, we can find our target element extremely fast. Just for reference on the power and scale of exponents and logarithms, given a one thousand element list, it only takes 10 steps to reduce the sample size to 1. For one million — 20 steps to reduce to one. One billion? Only 30 steps to reduce the sample size to 1!

2³⁰ is over 1 billion!

I mentioned earlier that binary search can only be used for lists that are already sorted. This is because if it wasn’t, we would not have the confidence to toss out half the list at a time on each step. Does this mean whenever we need to perform a search we should just sort the list, then perform a binary search? Not necessarily either. If the goal is to just get the target element without the need to use the sorted list for anything else, it would be more efficient to just use the linear search since every element is going to be accessed anyways in order to perform a search. There are some data structures available that sorts a list as elements are added, at the expense of extra cycles to insert new data at the savings of several cycles to perform a binary search. There’s going to be a lot of trade offs in terms of gaining significant time or space in one area at the expense increased time or space elsewhere. The ideal solution is going to be dependent on the goal and scope of a particular application and the data that application consumes.

Math Algorithms

Math algorithms are fun. Solving and understanding implementations of certain math problems and concepts is good practice for utilizing domain (industry specific) knowledge to solve problems efficiently. For example, if I was building software that bundles together questions to help determine what coverage types of health insurance a biological male was eligible for, I know that I don’t need to access the question bank that determines someone’s eligibility for prenatal care. Programming is so much more than just taking a set of input data and spitting out results. It’s about being built with a specific user base in mind. It’s building with the knowledge that can not be gained or optimized by just using the proper algorithm or data type. It’s knowledge that can take an optimized, general-purpose algorithm and optimize it even further to fit that industry’s use case. We’ll see how using some extra knowledge beyond the code itself can optimize determining if a given integer is a prime number or not.

Finding the Square Root of a Number

Something I took for granted while studying algebra and tutoring it many many years ago was how much work the calculator actually saves you from having to do square roots by hand if it doesn’t get cancelled out by a square. I was curious with how exactly a square root is calculated and I stumbled upon the Babylonian method. The formula version can look rather daunting, but here’s the idea behind it:

1) Start with an initial guess.
2) Divide the base number by the guess.
3) Average the guess and the result
4) Compare the difference of the number and the average squared.
5) If the difference is within an acceptable range, the average is the square root.
6) Repeat steps 2–5 with the average becoming the next guess until within an acceptable range.

Each step of the process gets you closer and closer to the exact square root, which could probably become millions of places past the decimal if calculated to its entirety. We don’t know how many steps it will take to get to an acceptable range when we start, so a do-while loop is utilized to average the guess and result, then use that as the next guess. The precision, or how many places we want past the decimal point, determines if the average we have is accurate enough for our purposes and serves to break out of the do-while loop by returning out of the function.

Prime Numbers

A prime number is any positive integer greater than 1 that can only be divided evenly by itself and 1. With only this knowledge, an initial attempt at crafting this algorithm might look like this:

This implementation can tell you whether or not a number is a prime number…on a large number like 600,851,475,143, it can take awhile depending on the machine, especially if you’re trying to do something like find the largest prime number that’s also a multiple of a large number. So let’s look at some math properties that help reduce the sample size of the loop. The primary optimization relies on this bit of knowledge: if a number to test is divisible by a lesser number, then we don’t need to test it during the loop. The two numbers that we’ll use for this test are 2 and 3 — if start off by testing these two numbers specifically, there’s a 66% chance we won’t even need to enter the loop:

For the first application of this knowledge, I start by first testing if the number is 2 or 3 since the next test will fail them as being prime numbers. Let’s work on optimizing the loop itself. The second test will fail 66% of the numbers for us before we enter the loop, but if it doesn’t, the loop is still testing numbers we’ve effectively eliminated. Now for the other reason 2 and 3 are used on the other test: we can represent every integer in the following format — 6x+n. For this scenario, if we think in terms of a number as an offset of a multiple of six, we will observe the following patterns:

1) 6x+0: (6, 12, 18, 24) — Divisible by 2 and 3; do not need to test.
2) 6x+1 -or- 6x-5 (7, 13, 19, 25) — Potential primes; DO need to test.
3) 6x+2 -or- 6x-4 (8, 14, 20, 26) — Divisible by 2; do not need to test.
4) 6x+3 -or- 6x-3 (9, 15, 21, 27) — Divisible by 3; do not need to test.
5) 6x+4 -or- 6x-2 (4, 10, 16, 22) — Divisible by 2; do not need to test.
6) 6x+5 -or- 6x-1 (5, 11, 17, 23) — Potential primes; DO need to test.

We see from the the list above, 4 out of the 6 numbers are in every group of 6 are automatically tested by checking if a number is divisible by 2 or 3. So I only really need to test numbers expressed by the following formula: 6x ± 1. So in my for loop, I can increment the index by 6 for each iteration and save a ton of CPU cycles while testing larger numbers. The starting value for the loop will be 5. We have explicitly tested for negative numbers, 0, 1, 2, and 3 prior to the loop. 4 is divisible by two, so starting on 4 is a wasted iteration. Starting the index on 5 lets us test in terms of number / i and number / (i + 2) to capture the 6x ± 1 during each iteration:

There is one more optimization we can do with this algorithm. On the initial implementation, the stopping point for the loop was the half of the input number. This actually results in duplicate comparisons. Let’s explore the different ways you can multiply two numbers together to get 16:

1) 1 x 16
2) 2 x 8
3) 4 x 4 (square root of 16)
4) 8 x 2 (reverse order of #2)
5) 16 x 1 (reverse order of #1)

The pattern to observe here is that once we pass the square root of the number, any other potential factors beyond that have been implicitly tested by its pair. What this means is we can change the exit condition of our for loop to i * i ≤ num, giving us this final result:

This algorithm is a super fun example of utilizing domain knowledge to greatly reduce the sample size and as a result make an algorithm perform more efficiently. While this particular scenario this algorithm solves may not be used in day-to-day programming, the thought processes that took us from the initial implementation to the final, optimized implementation is a crucial skill to developing highly performant applications, no matter the platform and domain.

In this article, we tackled quite a few algorithms across 3 categories. In the next article, I will recreate one of my earlier console-based projects from DigitalCrafts in Java!