tag:code.tutsplus.com,2005:/categories/algorithmsEnvato Tuts+ Code - Algorithms2018-12-14T03:58:31Ztag:code.tutsplus.com,2005:PostPresenter/cms-30003The Binary Search Algorithm in JavaScript<figure class="post_image"><img alt="JavaScript" data-src="https://cms-assets.tutsplus.com/uploads/users/48/posts/30003/image/js-product.png"></figure><p>In this post, I'll compare linear search and binary search algorithms. You'll see pseudocode for each algorithm, along with examples and a step-by-step guide to implementing each.<br></p><h2>Introduction</h2><p>As a programmer, you want to find the best solution to a problem so that your code is not only correct but also efficient. Choosing a suboptimal algorithm could mean a longer completion time, increased code complexity, or worse a program that crashes. </p><p>You may have used a search algorithm to locate items in a collection of data. The JavaScript language has several methods, like <code class="inline">find</code>, to locate items in an array. However, these methods use linear search. A linear search algorithm starts at the beginning of a list and compares each element with the search value until it is found. </p><p>This is fine when you have a small number of elements. But when you are searching large lists that have thousands or millions of elements, you need a better way to locate items. This is when you would use binary search. </p><p>In this tutorial, I will explain how binary search works and how to implement the algorithm in JavaScript. First, we will review the linear search algorithm. </p><h2>Linear Search</h2><p>We will begin by explaining how to implement linear search in JavaScript. We will create a function called <code class="inline">linearSearch</code> that accepts a value that is an integer or string and an array as parameters. The function will search every element in the array for the value and return the position of the value in the array if it is found. If the value is not in the array, it will return -1. For example, calling <code class="inline">linearSearch(1, [3, 4, 2, 1, 5])</code> would return 3, and calling <code class="inline">linearSearch(0, [3, 4, 2, 1, 5])</code> would return -1. </p><p>Here's some pseudocode for our function:</p><pre class="brush: plain noskimlinks noskimwords">Set found to false
Set position to −1
Set index to 0
while found is false and index < number of elements
if list[index] is equal to search value
Set found to true
Set position to index
else Add 1 to index
return position</pre><h3>JavaScript Implementation of Linear Search</h3><p>Here is a JavaScript implementation of the linear search algorithm:</p><pre class="brush: javascript noskimlinks noskimwords">function linearSearch(value, list) {
let found = false;
let position = -1;
let index = 0;
while(!found && index < list.length) {
if(list[index] == value) {
found = true;
position = index;
} else {
index += 1;
}
}
return position;
}</pre><p>It is important to note that the linear search algorithm does not need to use a sorted list. Also, the algorithm can be customized for use in different scenarios like searching for an array of objects by key. If you have an array of customer data that includes keys for the first and last name, you could test if the array has a customer with a specified first name. In that case, instead of checking if <code class="inline">list[index]</code> is equal to our search value, you would check for <code class="inline">list[index].first</code>.</p><p>In the example above, I used the <code class="inline">linearSearch</code> function on an array with five elements. In the worst case, when the search value is not in the list or is at the end of the list, the function would have to make five comparisons. Because our array is so small, there is no need to optimize by using a different algorithm. However, beyond a certain point, it is no longer efficient to use a linear search algorithm, and that is when using a binary search algorithm would be better.</p><h2>Binary Search</h2><p>Imagine you are playing a number guessing game. You are asked to guess a number between 1 and 100. If your number is too high or too low, you will get a hint. </p><p>What would your strategy be? Would you choose numbers randomly? Would you start with 1, then 2, and so on until you guessed correctly? Even if you had unlimited guesses, you want to make the correct guess in as few tries as possible. Therefore, you might start by guessing 50. If the number is higher, you could guess 75. If it is lower, then that means the number is between 50 and 75, and you would choose a number that's in the middle. You would go on like this until you arrived at the correct number. This is similar to how binary search works.</p><p>Unlike linear search, binary search uses a sorted list. To search for a value, you first compare the value to the middle element of the list. If they are equal, the search value has been found. If the search value is greater than the middle element, you search the top half of the data. You then compare the middle element of this section to the search value. Alternatively, if the item is less than the middle element, you search the bottom half of the list and compare its middle value. The list is repeatedly divided in half until the element is found or there are no more items to search.</p><p>To search for 9 in the list:</p><pre class="brush: plain noskimlinks noskimwords">1 2 3 4 5 6 7 8 9 10</pre><p>We first find the middle element. This is the element at position <code class="inline">Math.floor((first + last)/2)</code>, where <code class="inline">first</code> is the first index, and <code class="inline">last</code> is the last index. We choose to round down so that if the result is a fraction, it becomes a whole number. The middle element in this list is 5. Our search value 9 is greater than 5, so we search the list:</p><pre class="brush: plain noskimlinks noskimwords">6 7 8 9 10</pre><p>The middle element of this portion is 8. Nine is greater than 8, so we search the list:</p><pre class="brush: plain noskimlinks noskimwords">9 10</pre><p>The middle element is 9, so we can stop our search here. </p><p>Here's some pseudocode that expresses the above algorithm for binary search: <br></p><pre class="brush: plain noskimlinks noskimwords">Set first to 0
Set last to the last index in the list
Set found to false
Set position to −1
while found is false and first is less than or equal to last
Set middle to the index halfway between first and last
if list[middle] equals the desired value
Set found to true
Set position to middle
else if list[middle] is greater than the desired value
Set last to middle − 1
else
Set first to middle + 1
return position</pre><h3>JavaScript Implementation of Binary Search</h3><p>Now let's code the binary search algorithm in JavaScript! </p><p>We'll create a function, <code class="inline">binarySearch</code>, that accepts a value and an array as parameters. It will return the index where the value occurs in the list if found. If the value is not found, it returns -1. This is our implementation written in JavaScript: </p><pre class="brush: javascript noskimlinks noskimwords">function binarySearch(value, list) {
let first = 0; //left endpoint
let last = list.length - 1; //right endpoint
let position = -1;
let found = false;
let middle;
while (found === false && first <= last) {
middle = Math.floor((first + last)/2);
if (list[middle] == value) {
found = true;
position = middle;
} else if (list[middle] > value) { //if in lower half
last = middle - 1;
} else { //in in upper half
first = middle + 1;
}
}
return position;
}
</pre><h2>Conclusion</h2><p>In this tutorial, we saw how to implement a linear search and a binary search algorithm. The linear search algorithm is simpler and doesn't require a sorted array. However, it is inefficient to use with larger arrays. In the worst case, the algorithm would have to search all elements making n comparisons (where n is the number of elements). </p><p>The binary search algorithm, on the other hand, requires you to sort the array first and is more complicated to implement. However, it is more efficient even when considering the cost of sorting. For example, an array with 10 elements would make at most 4 comparisons for a binary search vs. 10 for a linear search—not such a big improvement. However, for an array with 1,000,000 elements, the worst case in binary search is only 20 comparisons. That's a huge improvement over linear search! </p><p>Knowing how to use binary search isn't just something to practice for an interview question. It's a practical skill that can make your code work much more efficiently.</p>2018-12-14T03:58:31.158Z2018-12-14T03:58:31.158ZAlberta Williamstag:code.tutsplus.com,2005:PostPresenter/cms-30395Using Iterators and Generators in JavaScript to Optimize Code<figure class="post_image"><img alt="" data-src="https://cms-assets.tutsplus.com/uploads/users/48/posts/30395/image/js-product-2.png"></figure><h2>Introduction</h2><p>Have you ever needed to loop through a list, but the operation took a significant amount of time to complete? Have you ever had a program crash because an operation used too much memory? This happened to me when I tried to implement a function that generates prime numbers. </p><p>Generating prime numbers up to a million took far more time than I would have liked. But generating numbers up to 10 million was impossible. My program would crash or just hang. I was already using the sieve of Eratosthenes, which is supposed to be more efficient at generating primes than the brute force approach.</p><p>If you find yourself in a similar situation, you can try using a different algorithm. There are searching and sorting algorithms that work better on larger inputs. The downside is those algorithms may be more difficult to grasp right away. Another option is to use a different programming language. </p><p>A compiled language may be able to process the code significantly quicker. But using another language may not be practical. You may also try using multiple threads. Once again, it may not be practical because your programming language would have to support this.</p><p>Fortunately, with JavaScript, there is another option. If you have a computationally intensive task, you can use iterators and generators to gain some efficiency. Iterators are a property of certain JavaScript collections. </p><p>Iterators improve efficiency by letting you consume the items in a list one at a time as if they were a stream. Generators are a special kind of function that can pause execution. Invoking a generator allows you to produce data one chunk at a time without the need to store it in a list first.</p><h2>Iterators</h2><p>First, let’s review the different ways you can loop through collections in JavaScript. A loop of the form <code class="inline">for (initial; condition; step) { ... }</code> will execute the commands in its body a specific number of times. Similarly, a while loop will execute the commands in its body for as long as its condition is true. </p><p>You can use these loops to traverse a list by incrementing an index variable at each iteration. An iteration is an execution of the body of a loop. These loops do not know about the structure of your list. They act as counters.</p><p>A <code class="inline">for/in</code> loop and a <code class="inline">for/of</code> loop are designed to iterate over specific data structures. Iterating over a data structure means you are stepping through each of its elements. A <code class="inline">for/in</code> loop iterates over the keys in a plain JavaScript object. A <code class="inline">for/of</code> loop iterates over the values of an iterable. What is an iterable? Simply put, an iterable is an object that has an iterator. Examples of iterables are arrays and sets. The iterator is a property of the object that provides a mechanism for traversing the object.</p><p>What makes an iterator special is how it traverses a collection. Other loops need to load the entire collection up front in order to iterate over it, whereas an iterator only needs to know the current position in the collection. </p><p>You access the current item by calling the iterator’s next method. The next method will return the value of the current item and a boolean to indicate when you have reached the end of the collection. The following is an example of creating an iterator from an array.</p><pre class="brush: javascript noskimlinks noskimwords">const alpha = ['a','b','c'];
const it = alpha[Symbol.iterator]();
it.next(); //{ value: 'a', done: false }
it.next(); //{ value: 'b', done: false }
it.next(); //{ value: 'c', done: false }
it.next(); //{ value: undefined, done: true }</pre><p>You can also iterate over the values of the iterator using a <code class="inline">for/of</code> loop. Use this method when you know you want to access all of the items in the object. This is how you would use a loop to iterate through the previous list:</p><pre class="brush: javascript noskimlinks noskimwords">for (const elem of it){
console.log(elem);
}</pre><p>Why would you use an iterator? Using an iterator is beneficial when the computational cost of processing a list is high. If you have a data source that is very large, it may cause problems in your program if you attempt to iterate over it because the entire collection has to be loaded. </p><p>With an iterator, you can load the data in chunks. This is more efficient because you only manipulate the part of the list that you need, without incurring the additional cost of processing the entire list. </p><p>An example could be that you have loaded data from a file or database, and you want to progressively display the information on the screen. You could create an iterator from the data and set up an event handler to grab a few items every time the event occurs. This is an example of what such an implementation might look like:</p><pre class="brush: javascript noskimlinks noskimwords">let posts = load(url);
let it = posts[Symbol.iterator]();
function loadPosts(iterable, count) {
for (let i = 0; i < count; i++) {
display(iterable.next().value);
}
}
document.getElementById('btnNext').onclick = loadPosts(it, 5);</pre><h2>Generators</h2><p>If you want to build a collection, you can do so with a generator. A generator function can return values one at a time by pausing execution at each iteration. When you create an instance of a generator, these items can be accessed using an iterator. This is the general syntax for creating a generator function:</p><pre class="brush: javascript noskimlinks noskimwords">function *genFunc() {
...
yield value;
}</pre><p>The <code class="inline">*</code> signifies that this is a generator function. The <code class="inline">yield</code> keyword pauses our function and supplies the state of the generator at that particular moment. Why would you use a generator? You would use a generator when you want to algorithmically produce a value in a collection. It is particularly useful if you have a very large or infinite collection. Let’s look at an example to understand how this helps us. </p><p>Suppose you have an online pool game you have built, and you want to match players to game rooms. Your objective is to generate all of the ways you can choose two distinct players from your list of 2,000 gamers. The two-player combinations generated from the list <code class="inline">['a', 'b', 'c', 'd']</code> would be <code class="inline">ab, ac, ad, bc, bd, cd</code>. This is a solution using nested loops:</p><pre class="brush: javascript noskimlinks noskimwords">function combos(list) {
const n = list.length;
let result = [];
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
result.push([list[i], list[j]]);
}
}
return result;
}
console.log(combos(['a', 'b', 'c', 'd']));</pre><p>Now try executing the function with a list of 2,000 elements. (You can initialize your list using a for loop that adds the numbers 1 to 2,000 to an array). What happens now when you run your code? </p><p>When I run the code in an <a href="https://repl.it/" target="_self">online editor</a>, the web page crashes. When I try it out in the console in Chrome, I can see the output slowly printing out. However, my computer’s CPU starts to go into overdrive, and I have to force quit Chrome. This is the revised code using a generator function:</p><pre class="brush: javascript noskimlinks noskimwords">function *combos(list) {
const n = list.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
yield [list[i], list[j]];
}
}
}
let it = combos(['a', 'b', 'c', 'd']);
it.next(); </pre><p>Another example is if we wanted to generate the numbers in the Fibonacci sequence up to infinity. Here is one implementation:</p><pre class="brush: javascript noskimlinks noskimwords">function *fibGen() {
let current = 0;
let next = 1;
while(true) {
yield current;
let nextNum = current + next;
current = next;
next = nextNum;
}
}
let it = fibGen();
it.next().value; //0
it.next().value; //1
it.next().value; //1
it.next().value; //2</pre><p>Normally, an infinite loop will crash your program. The <code class="inline">fibGen</code> function is capable of running forever because there is no stopping condition. But since it is a generator, you control when each step is executed.</p><h2>Review</h2><p>Iterators and generators come in handy when you want to process a collection incrementally. You gain efficiency by keeping track of the state of the collection instead of all of the items in the collection. Items in the collection are evaluated one at a time, and the evaluation of the rest of the collection is delayed till later. </p><p>Iterators provide an efficient way to traverse and manipulate large lists. Generators provide an efficient way to build lists. You should try out these techniques when you would otherwise use a complex algorithm or implement parallel programming to optimize your code.</p><p>If you’re looking for additional resources to study or to use in your work, check out what we have available in the <a href="https://codecanyon.net/category/javascript">Envato Market</a>.<br></p><h3>Learn JavaScript: The Complete Guide</h3><p>We’ve built a complete guide to help you <a href="https://code.tutsplus.com/series/learn-javascript-the-complete-guide--cms-1112" target="_self">learn JavaScript</a>, whether you’re just getting started as a web developer or you want to explore more advanced topics.</p><h2>Resources</h2><ul>
<li><a href="https://www.safaribooksonline.com/library/view/design-patterns-elements/0201633612/" target="_self">Design Patterns: Elements of Reusable Object-Oriented Software: Iterator pattern</a></li>
<li><a href="https://tc39.github.io/ecma262/#sec-iteration" target="_self">ECMAScript Specification for Iterators and Generators</a></li>
<li><a href="https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5" target="_self">Structure and Interpretation of Computer Programs - Chapter 3.5: Streams</a></li>
</ul>2018-03-02T12:00:56.000Z2018-03-02T12:00:56.000ZAlberta Williamstag:code.tutsplus.com,2005:PostPresenter/cms-30346Understanding Recursion With JavaScript <figure class="post_image"><img alt="" data-src="https://cms-assets.tutsplus.com/uploads/users/48/posts/30346/image/js-product.png"></figure><h2>Introduction</h2><p>Some problems are more naturally solved using recursion. For example, a sequence like the Fibonacci sequence has a recursive definition. Each number in the sequence is the sum of the previous two numbers in the sequence. Problems that require you to build or traverse a tree-like data structure can also be solved with recursion. Training yourself to think recursively will give you a powerful skill to attack such problems. </p><p>In this tutorial, I will go through several recursive functions step by step to see how they work and show you techniques you can use to systematically define recursive functions.<br></p><h3>
<strong>Contents:</strong><br>
</h3><ul>
<li>What Is Recursion?</li>
<li>Recursion With Numbers</li>
<li>Recursion With Lists</li>
<li>Building Lists</li>
<li>Review</li>
</ul><h2>What Is Recursion?</h2><p>A recursively defined function is a function that is defined in terms of a simpler version of itself. This is a simplified example:</p><pre class="brush: javascript noskimlinks noskimwords">function doA(n) {
...
doA(n-1);
}</pre><p>To understand how recursion works conceptually, we will look at an example that has nothing to do with code. Imagine you are responsible for answering phone calls at work. Since this is a busy company, your phone has multiple phone lines so you can juggle multiple calls at the same time. Each phone line is a button on the receiver, and when there is an incoming call, the button will blink. Today, when you arrive to work and turn the phone on, there are four lines blinking at once. So you get to work answering all of the calls.</p><p>You pick up line one and tell them ‘please hold’. Then you pick up line two and put them on hold. Next, you pick up line three and put them on hold. Finally, the fourth line you answer and speak with the caller. When you are finished with the fourth caller, you hang up and pick up the third call. When you finish with the third call, you hang up and pick up the second call. When you finish with the second call, you hang up and pick up the first call. When you finish that call, you can finally put the phone down.</p><p>Each of the phone calls in this example is like a recursive call in a function. When you get a call, it is put on the call stack (in code speak). If you cannot complete a call right away, you put the call on hold. If you have a function call that can't be evaluated immediately, it stays on the call stack. When you are able to answer a call, it is picked up. When your code is able to evaluate a function call, it is popped off the stack. Keep this analogy in mind as you look over the following code examples.</p><h2>Recursion With Numbers</h2><p>All recursive functions need a base case so they will terminate. However, just adding a base case to our function does not prevent it from running infinitely. The function has to have a step to bring us closer to the base case. Last is the recursive step. In the recursive step, the problem is reduced to a smaller version of the problem.</p><p>Suppose you have a function that will sum the numbers from 1 to n. For example, if n = 4, it will sum 1 + 2 + 3 + 4. </p><p>First, we determine the base case. Finding the base case can also be thought of as finding the case where the problem can be solved without recursion. In this case, it is when n equals zero. Zero has no parts, so our recursion can stop when we reach 0. </p><p>At each step, you will subtract one from the current number. What is the recursive case? The recursive case is the function sum called with the reduced number.</p><pre class="brush: javascript noskimlinks noskimwords">function sum(num){
if (num === 0) {
return 0;
} else {
return num + sum(--num)
}
}
sum(4); //10
</pre><p>This is what is happening at each step:</p><ul>
<li>Go to sum(4).</li>
<li>Is 4 equal to 0? No. Put sum(4) on hold and go to sum(3).</li>
<li>Is 3 equal to 0? No. Put sum(3) on hold and go to sum(2).</li>
<li>Is 2 equal to 0? No. Put sum(2) on hold and go to sum(1).</li>
<li>Is 1 equal to 0? No. Put sum(1) on hold and go to sum(0).</li>
<li>Is 0 equal to 0? Yes. Evaluate sum(0).</li>
<li>Pick up sum(1).</li>
<li>Pick up sum(2).</li>
<li>Pick up sum(3).</li>
<li>Pick up sum(4).</li>
</ul><p>This is another way to view how the function is processing each call:</p><pre class="brush: plain noskimlinks noskimwords">sum(4)
4 + sum(3)
4 + ( 3 + sum(2) )
4 + ( 3 + ( 2 + sum(1) ))
4 + ( 3 + ( 2 + ( 1 + sum(0) )))
4 + ( 3 + ( 2 + ( 1 + 0 ) ))
4 + ( 3 + ( 2 + 1 ) )
4 + ( 3 + 3 )
4 + 6
10</pre><p>The argument should change in the recursive case and bring you closer to the base case. This argument should be tested in the base case. In the previous example, because we are subtracting one in the recursive case, we test if the argument equals zero in our base case.</p><h3>Task</h3><ol>
<li>Implement the sum function using a loop instead of recursion.</li>
<li>Create a function that multiplies two numbers recursively. For example, <code class="inline">multiply(2,4)</code> will return 8. Write what happens at each step for <code class="inline">multiply(2,4)</code>.</li>
</ol><h2>Recursion With Lists</h2><p>Recurring on a list is similar to recurring on a number, except that instead of reducing the number at each step, we are reducing the list at each step until we get to an empty list. </p><p>Consider the sum function that takes a list as input and returns the sum of all of the elements in the list. This is an implementation for the function sum:</p><pre class="brush: javascript noskimlinks noskimwords">function sum(l){
if (empty(l)) {
return 0;
} else {
return car(l) + sum(cdr(l));
}
}</pre><p>The <code class="inline">empty</code> function returns true if the list has no elements. The <code class="inline">car</code> function returns the first element in the list. For example, <code class="inline">car([1,2,3,4])</code> returns 1. The <code class="inline">cdr</code> function returns the list without the first element. For example, <code class="inline">cdr([1,2,3,4])</code> returns [2,3,4]. What happens when we execute <code class="inline">sum([1,2,3,4])</code>?</p><pre class="brush: plain noskimlinks noskimwords">sum([1,2,3,4])
1 + sum([2,3,4])
1 + ( 2 + sum([3,4]) )
1 + ( 2 + ( 3 + sum([4]) ))
1 + ( 2 + ( 3 + ( 4 + sum([]) )))
1 + ( 2 + ( 3 + ( 4 + 0 ) ))
1 + ( 2 + ( 3 + 4 ) )
1 + ( 2 + 7 )
1 + 9
10</pre><p>When recurring on a list, check if it is empty. Otherwise, do the recursive step on a reduced version of the list.</p><h3>Task</h3><ol>
<li>Rewrite this sum function so that it uses a loop to sum each item in the list instead of recursion.</li>
<li>Define a function named length that takes a list as input and returns the number of elements in that list. You should not use JavaScript’s built-in length function. For example, <code class="inline">length(['a', 'b', 'c', 'd'])</code> should return 4. Write what happens at each step.</li>
</ol><h2>Building Lists</h2><p>In the last example, we were returning a number. But suppose we wanted to return a list. That would mean that instead of adding a number to our recursive step, we would need to add a list. Consider the function <code class="inline">remove</code>, which takes an item and list as input and returns the list with the item removed. Only the first found item will be removed.</p><pre class="brush: javascript noskimlinks noskimwords">function remove(item, l){
if (empty(l)) {
return [];
} else if (eq(car(l), item)) {
return cdr(l);
} else {
return cons(car(l), remove(item, cdr(l)));
}
}
remove('c', ['a', 'b', 'c', 'd']) //[‘a’, ‘b’, ‘d’]</pre><p>Here, the <code class="inline">eq</code> function returns true if both inputs are the same. The <code class="inline">cons</code> function takes an element and a list as inputs and returns a new list with the element added to the beginning of it. </p><p>We will be checking if the first item in the list is equal to the item we want to remove. If it is, remove the first element from the list and return the new list. If the first item is not equal to the item we want to remove, we take the first element in the list and add it to the recursive step. The recursive step will contain the list with the first element removed. </p><p>We will keep removing elements until we reach our base case, which is an empty list. An empty list means we have traversed all the items in our list. What does <code class="inline">remove('c', ['a', 'b', 'c', 'd'])</code> do?</p><pre class="brush: plain noskimlinks noskimwords">remove('c', ['a', 'b', 'c', 'd'])
cons( ‘a’, remove(‘c’, [‘b’, ‘c’, ‘d’]) )
cons( ‘a’ , cons( ‘b’, remove(‘c’, [‘c’, ‘d’]) ))
cons( ‘a’, cons( ‘b’, [‘d’] )
cons( ‘a’, [‘b’, ‘d’])
[‘a’, ‘b’, ‘d’]</pre><p>In a situation when we need to build a list, we take the first element and add it to the recursive part of our list.</p><h3>Task</h3><ol>
<li>Rewrite the remove function so that it uses loops instead of recursion to remove an element from a list.</li>
<li>Alter the remove function so that it removes all occurrences of an item from a list. For example, <code class="inline">remove(‘c’, [‘a’, ‘b’, ‘c’, ‘d’, ‘c’]</code> returns [‘a’, ‘b’, ‘d’]. Write what happens step by step.</li>
</ol><h2>Review</h2><p>There are three parts to a recursive function. The first is the base case, which is the terminating condition. The second is the step to get us closer to our base case. The third is the recursive step, where the function calls itself with the reduced input. </p><p>Recursion is like iteration. Any function that you can define recursively can also be defined using loops. Other things to consider when using recursion are recurring on nested lists and optimizing your recursive calls. </p><p>A great resource to continue learning about recursion is the book <a href="https://mitpress.mit.edu/books/little-schemer">The Little Schemer</a>. It teaches you how to think recursively using a question and answer format.</p>2018-02-22T12:00:40.000Z2018-02-22T12:00:40.000ZAlberta Williamstag:code.tutsplus.com,2005:PostPresenter/cms-21677Understanding Base-36 Math<p>My name is 13 characters long. There are lots of DeWolfes, lots of Shawns, a few Shawn DeWolfes. My 13 character name doesn’t mean anything unique. Even my nine-digit social insurance number only goes so far. In my country, Canada, it defines me specifically, but any other nation with a nine digit social insurance number system will likely have a member with a number the same as my own.</p><p>What if one number could address every person alive, be shorter than a name and shorter than a social insurance number? You can’t do it with Base-10 numbers, but with Base-36, it’s a breeze.</p><p>We use base ten so much that we discount the utility of going up by orders of ten with each digit we add to a number. With two digits we can go from 0 to 99. Hexadecimal takes it further: with two hexadecimal digits, we can get to 255 - from 0 to FF. </p><p>Hexadecimal numbers get above the ten digit mark without having to invent new numbers. It does this by using A, B, C, D, E and F to reference the 11th through 16th digitals. Base-36 takes that one step further and uses all of the conventionally available characters we are familiar with. Base-36 uses numbers to handle the first ten digits. Digits 11 through 36 are referenced with the alphabet from A to Z. We know the order of numbers from 0 to 9, and we know the alphabet, so we can anticipate the progression.</p><br><p>By using the base-36 number, massively bigger numbers can be referenced with an economy of size. While a two digit number gets you to 99; ZZ, a two digit Base-36 expression gets to 1295. Z,ZZZ,ZZZ is the base ten equivalent of 78,364,164,095. </p><p>With that seven digit number under base-36, you can reference every person alive and almost every person who was ever alive with their own unique 7-digit number. </p><p>When you get to eight digits, you could have the Internet of things covered. Eight digits at base-36 counts to above two trillion (2,821,109,907,455 to be exact).</p><p>Base-36 is a good practical ceiling to work with in lieu of base ten or a hexadecimal sequences. PHP and MySQL have conversion functions that can convert numbers to and from base-36. The functionality is there. It allows for the storage of more compact data. </p><p>From the human perspective, it has been said that many people can remember a list of 5 things plus or minus two. Many can recall important phone numbers. And just as most people can recall a seven digit phone number, so it can be argued that they can retain a seven character string representation of something big - instead of a 1-in-a-million phone number, a seven character base-36 figure will represent one of 78 billion references. </p><h2>Why Are Big Numbers Important?</h2><p>As shown above above, big numbers can be handy to addressing large masses of data. Facebook stores their posts with ID numbers that are spiralling upwards. </p><p>A post I just pulled has the ID number of 902352183124757. Fifteen digits - 902 trillion. If they’re at 902 trillion, and a guy like me throws in a crazy amount of posts per day and a tens of millions do as I do, that post odometer is going to roll over soon. </p><p>Were the posts formatted to be 10 base-36 digits, the database would have more leg room (eg. almost 4 quadrillion (3,656,158,440,062,980) references available). If Facebook got to this point through exponential growth and that exponential growth is leveling out, then 2+ quadrillion posts should give that database the room it needs to reference new posts without going to a googolplex value. </p><h3>Aren’t Base-36 Numbers Processing Intensive?</h3><p>Yes and no. Inside of a database, integers are the most economical way to store data. Base-36 numerals would be considered strings and strings are more expensive storage. </p><p>Likewise, auto-increment in MySQL will only increment integers. You can format strings to be consistent. For example, all 10 characters could be used with zeroes to the left of the number so that 0000000008 would be eight while 00000000ZZ would be 1295. When sorted alphabetically, the progression would look like a numerical progression. While auto-incrementation is built into MySQL and most other relational databases, it’s not the only game in town. You can create new auto generated base-36 numbers by associating a trigger to a table (which we'll discuss momentarily) to introduce new, orderly values when new records are inserted. </p><h2>Where Base-36 Can Be Used</h2><p>The goal of base-36 is compaction and relevance. Instead of 10 digits to reference the people on Earth, seven characters will address them all. Instead of 16 digits to address all of the Facebook’s status updates ever, 10 characters can be used. When it comes to relevance, the sequence can be both an incrementing value and some of the value can be set aside to declare additional qualities in what is being defined. </p><p>Base-36 can be used to reference these sorts of items:</p><ul>
<li>
<b>People.</b> A seven digit base-36 number can reference 78 billion people. If you convert a user’s reference into 7 characters.</li>
<li>
<b>Country Codes.</b> Country codes are already two character representations. There are 193 recognized countries (by writing that, I just know some country is going to split into two by the time I get to the close bracket). The <a href="http://www.iso.org/iso/country_codes.htm" rel="external" target="_blank">ISO-3166 standard</a> is a list of two digit country codes. With two alphabetical characters, 676 specific countries can be referenced, country codes are good at using just two characters. Using the ISO-3166 standard leaves over 400 references unused, but it still provides a common and recognizable reference.</li>
<li>
<b>Cities.</b> China, with its one billion people, has over 1020 cities. Those communities could be referenced inside of two base-36 digits. Many countries will have fewer than 1000 communities. Let’s say that community references get really particular and to satisfy all of the references, three digits can associate 46,655 communities inside of one country.</li>
<li>
<b>Devices.</b> The Internet of Things is coming, I’m sure. I have three devices with their own wireless needs. Some tech-friendly people could have many more wired devices. If this were 36 devices per person, then one digit could cover off all of those devices. Two digits to reference devices and things covers off 1295 possibilities.</li>
</ul><h3>Amalgamated Serial Numbers</h3><p>These strings can be combined to make unique by amalgamating the characters in an orderly sequence. In the following example, you can make a reference to people, their location and their devices. The whole string can be unique while elements therein repeat.</p><p>For example: US001200GHK4 could actually mean:</p><ul>
<li>US - country code</li>
<li>001 - Manhattan</li>
<li>200GHK4 - A person’s unique code. </li>
</ul><br><p>Maybe their devices get added to the identification process. Let’s say the laptop is their primary device. When their cellphone is put into the figuring it is the second device that is associated with the user: US001200GHK42. The “2” stands for that second device.</p><p>If that is how the base-36 were worked into creating some identification, the length of the string will speak to what it associates. </p><ul>
<li>Two digits long = country using the ISO-3166 standard codes</li>
<li>Five digits long = community in a country</li>
<li>Twelve digits long = a person as they reside in a country</li>
<li>Thirteen digits long = a reference to an IP addressable device owned by a user in a particular community and country.</li>
</ul><p>With 13 digits, a MySQL search for “US%” for will return all US citizens. “US001%” will return all of the people in Manhattan. “US001%1” will reveal the primary / preferred device used by all of those Manhattan residents. With a logic like that, communication can be routed to a preferred chunk of a network.</p><p>Of course, there are a lot of what if:<br></p><ul>
<li>What if they change cities? The third to fifth characters change.</li>
<li>What if they hop to another country? The first five digits change to reflect new digs.</li>
<li>What if they own more than 36 devices? If that happens, then the last two digits can represent their device instead of solely the last-- a fourteen digit ID# would say, “this dude has a lot of gadgets.”</li>
</ul><h2>Storage in a Database</h2><p>The main purpose of creating these large numbers and storing them as base-36 references is to practice a sort of economy. These need to be sequential like index keys, but you do not have to do any particular math with them.</p><p>In MySQL, base-36 strings stored as <code class="inline">VARCHAR</code> data types behave like integers. The strings can be compared through aggregate functions like <code class="inline">MAX()</code> and <code class="inline">MIN()</code> to get the highest and lowest available numbers, respectively. </p><p>You can also fetch a base-36 string by sorting in descending order to get the highest number first. Unlike integers, base-36 strings can be filtered with <code class="inline">LIKE</code> statements should the strings be a combination of amalgamated series and incrementing values. </p><h3>Using Values in MySQL</h3><p>In MySQL there is the <code class="inline">CONV()</code> function that can convert from anything from a base-2 through to a base-36 number. To get a base-36 to its base 10 equivalent, do <code class="inline">CONV(‘ZA’, 36, 10)</code>. To get it from a base 10 over to a base-36 you can go the other way. <code class="inline">CONV(‘1294’, 10, 36)</code>. You can nest these functions to create something that increments: <code class="inline">CONV(CONV('ZA', 36, 10) + 1, 10, 36)</code> will output ‘ZB.’</p><h3>Incrementing Base-36 Keys in MySQL</h3><p>This can be put into a custom procedure and that procedure can be triggered when new records are inserted into a database table. In the example below, the trigger is added to the <code class="inline">base_example</code> table to execute and create a base-36 key when a new record is added to the base_example table.</p><pre class="brush: sql noskimlinks noskimwords">CREATE TABLE IF NOT EXISTS `base_example` (
`bkey` varchar(12) NOT NULL,
`info` text NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
CREATE TRIGGER `b36_incr` BEFORE INSERT ON `base_example` FOR EACH ROW
BEGIN
DECLARE old_bkey VARCHAR(12);
DECLARE rowcount INT;
SELECT COUNT(*), bkey into rowcount, old_bkey FROM `base_example` GROUP BY bkey ORDER BY bkey DESC LIMIT 1;
IF (1 <= rowcount) AND (old_bkey IS NOT NULL) THEN
SET new.bkey = LPAD(CONV(CONV(old_bkey, 36, 10) + 1, 10, 36), 12, '0');
ELSE
SET new.bkey = LPAD('0', 12, '0');
END IF;
END</pre><p>Figure 1. A triggered procedure to create and incrementing value.</p><p>In this example, there are two assumptions added to the mix. First, the <code class="inline">VARCHAR</code> field is to be 12 characters long. Second, the values in the <code class="inline">VARCHAR</code> field are left-padded with zeros so that all of the output look consistent and can be sorted in a predictable fashion.</p><h2>Math With Base-36</h2><p>Base-36 is cool, but most languages still reference things in base 10 and binary. PHP can do base conversions however and it is clever enough to extrapolate the the letters A through Z cover the 11th through 36th digits. </p><p>With a simple function, base-36 numerals can be passed a function (which we'll see momentarily) for conversion, calculation, and a return value. It does this by pulling the 0-9A-Z characters from the formula, carrying out a base-36 calculation and then converting the output back to base-36.</p><pre class="brush: php noskimlinks noskimwords">$bthreesix = "ZZ"; // the base 10 equivalent of 1295
$zz = base_convert($bthreesix,36,10);
$zz++; // ZZ becomes 100
$bthreesix = base_convert($zz,10,36);
echo $bthreesix;</pre><h3>Doing Base-36 Formulas in PHP</h3><p>There is a limit to how complex the math is, but I wrote an example function <code class="inline">b36math()</code> that converts a base-36 formula into a base-36 result.</p><pre class="brush: php noskimlinks noskimwords"><?php
print b36math("ZY++");
print "<br/>";
print b36math("ZW + 9");
print "<br/>";
function b36math($formula = "") {
$out = preg_replace_callback(
"/([\w]+)/",
"b36convert",
$formula);
// incr / decr don't work as advertised
$out = str_replace("++", " + 1", $out);
$out = str_replace("--", " - 1", $out);
eval('$outer = '.$out.';');
return strtoupper(base_convert($outer, 10, 36));
}
function b36convert($matches) {
$digits = "";
array_shift($matches);
foreach ($matches as $key => $match) {
$digits .= $match;
}
$new_number = base_convert($digits, 36, 10);
return intval($new_number);
}
?></pre><p>Figure 2. The b36math conversion function to execute functions executed with base-36 numbers.</p><h2>Conclusion</h2><p>Our world is data hungry. That data has to be well referenced. In the crunch to access bigger bodies of data, using references stored as base-36 numbers is a way to store bigger numbers in less space. </p><p>There is a foot race to what is a valuable commodity: processing speed, bandwidth, or storage. When one is in generous supply, you can spend it compensating for the other. If you have a lot of available cycles for processing, you can do store data in a cumbersome format and use processing to make it useable. </p><p>While there is a cap of how many digits can be referenced in an integer, <code class="inline">varchar</code> fields can go to 255 characters, and text fields are open-ended. Very large base-36 numbers can be stored to reference individual elements in very large bodies of data.</p>2014-08-20T13:00:41.000Z2014-08-20T13:00:41.000ZShawn DeWolfetag:code.tutsplus.com,2005:PostPresenter/cms-20437Algorithms and Data Structures<p>I assume you are a computer programmer. Perhaps you are a new student of computer science or maybe you are an experienced software engineer. Regardless of where you are on that spectrum, algorithms and data structures matter. Not just as theoretical concepts, but as building blocks used to create solutions to business problems.</p>
<p>Sure, you may know how to use the C# <code>List</code> or <code>Stack</code> class, but do you understand what is going on under the covers? If not, are you really making the best decisions about which algorithms and data structures you are using?</p>
<p>Meaningful understanding of algorithms and data structures starts with having a way to express and compare their relative costs.</p>
<h2>Asymptotic Analysis</h2>
<p>When we talk about measuring the cost or complexity of an algorithm, what we are really talking about is performing an analysis of the algorithm when the input sets are very large. Analyzing what happens as the number of inputs becomes very large is referred to as asymptotic analysis. How does the complexity of the algorithm change when applied to ten, or one thousand, or ten million items? If an algorithm runs in five milliseconds with one thousand items, what can we say about what will happen when it runs with one million? Will it take five seconds or five years? Wouldn't you rather figure this out before your customer?</p>
<p>This stuff matters!</p>
<h3>Rate of Growth</h3>
<p>Rate of growth describes how an algorithm's complexity changes as the input size grows. This is commonly represented using Big-O notation. Big-O notation uses a capital O ("order") and a formula that expresses the complexity of the algorithm. The formula may have a variable, n, which represents the size of the input. The following are some common order functions we will see in this book but this list is by no means complete.</p>
<h4>Constant - O(1)</h4>
<p>An O(1) algorithm is one whose complexity is constant regardless of how large the input size is. The "1" does not mean that there is only one operation or that the operation takes a small amount of time. It might take one microsecond or it might take one hour. The point is that the size of the input does not influence the time the operation takes.
</p>
<pre class="brush: cpp noskimlinks noskimwords">public int GetCount(int[] items)
{
return items.Length;
}
</pre>
<h4>Linear - O(n)</h4>
<p>An O(n) algorithm is one whose complexity grows linearly with the size of the input. It is reasonable to expect that if an input size of one takes five milliseconds, an input with one thousand items will take five seconds.</p>
<p>You can often recognize an O(n) algorithm by looking for a looping mechanism that accesses each member.</p>
<pre class="brush: cpp noskimlinks noskimwords">public long GetSum(int[] items)
{
long sum = 0;
foreach (int i in items)
{
sum += i;
}
return sum;
}
</pre>
<h4>Logarithmic - O(log n)</h4>
<p>An O(log n) algorithm is one whose complexity is logarithmic to its size. Many divide and conquer algorithms fall into this bucket. The binary search tree <code>Contains</code> method implements an O(log n) algorithm.</p>
<h4>Linearithmic - O(n log n)</h4>
<p>A linearithmic algorithm, or loglinear, is an algorithm that has a complexity of O(n log n). Some divide and conquer algorithms fall into this bucket. We will see two examples when we look at merge sort and quick sort.</p>
<h4>Quadratic - O(n^2)</h4>
<p>An O(n^2) algorithm is one whose complexity is quadratic to its size. While not always avoidable, using a quadratic algorithm is a potential sign that you need to reconsider your algorithm or data structure choice. Quadratic algorithms do not scale well as the input size grows. For example, an array with 1000 integers would require 1,000,000 operations to complete. An input with one million items would take one trillion (1,000,000,000,000) operations. To put this into perspective, if each operation takes one millisecond to complete, an O(n^2) algorithm that receives an input of one million items will take nearly 32 years to complete. Making that algorithm 100 times faster would still take 84 days.
</p>
<p>We will see an example of a quadratic algorithm when we look at bubble sort.</p>
<h3>Best, Average, and Worst Case</h3>
<p>When we say an algorithm is O(n), what are we really saying? Are we saying that the algorithm is O(n) on average? Or are we describing the best or worst case scenario?</p>
<p>We typically mean the worst case scenario unless the common case and worst case are vastly different. For example, we will see examples in this book where an algorithm is O(1) on average, but periodically becomes O(n) (see <code>ArrayList.Add</code>). In these cases I will describe the algorithm as O(1) on average and then explain when the complexity changes.</p>
<p>The key point is that saying O(n) does not mean that it is always n operations. It might be less, but it should not be more.</p>
<h3>What Are We Measuring?</h3>
<p>When we are measuring algorithms and data structures, we are usually talking about one of two things: the amount of time the operation takes to complete (operational complexity), or the amount of resources (memory) an algorithm uses (resource complexity).</p>
<p>An algorithm that runs ten times faster but uses ten times as much memory might be perfectly acceptable in a server environment with vast amounts of available memory, but may not be appropriate in an embedded environment where available memory is severely limited.</p>
<p>In this book I will focus primarily on operational complexity, but in the Sorting Algorithms section we will see some examples of resource complexity.</p>
<p>Some specific examples of things we might measure include:</p>
<ul>
<li>Comparison operations (greater than, less than, equal to).</li>
<li>Assignments and data swapping.</li>
<li>Memory allocations.</li>
</ul>
<p>The context of the operation being performed will typically tell you what type of measurement is being made.</p>
<p>For example, when discussing the complexity of an algorithm that searches for an item within a data structure, we are almost certainly talking about comparison operations. Search is generally a read-only operation so there should not be any need to perform assignments or allocate memory.</p>
<p>However, when we are talking about data sorting it might be logical to assume that we could be talking about comparisons, assignments, or allocations. In cases where there may be ambiguity, I will indicate which type of measurement the complexity is actually referring to.</p>
<h2>Next Up</h2>
<p>This completes the first part about algorithms and data structures. Next up, we'll move on to the linked list. </p>2014-02-22T05:13:52.618Z2014-02-22T05:13:52.618ZRobert Horvicktag:code.tutsplus.com,2005:PostPresenter/net-26561Understanding the Principles of Algorithm Design<p>This article will dive into the principles of algorithm design. If you haven't a clue what I'm referring to, read on!</p>
<p><!--more--></p>
<p>When you hear the word "algorithm," you probably respond in one of three ways:</p>
<ol>
<li>You immediately know and understand what we're talking about because you studied computer science.</li>
<li>You know that algorithms are the workhorses of companies like Google and Facebook, but you aren't really sure what the word means.</li>
<li>You run and hide in fear because everything you know about algorithms reminds you of high-school Calculus nightmares.</li>
</ol>
<p>If you are one of the second two, this article is for you.</p>
<hr>
<h2>What is an Algorithm, Exactly?</h2>
<blockquote class="pullquote"><p>Algorithms are not a special type of operation, necessarily. They are conceptual, a set of steps that you take in code to reach a specific goal.</p></blockquote>
<p>Algorithms have been commonly defined in simple terms as "instructions for completing a task". They've also been called "recipes". In <em>The Social Network</em>, an algorithm is what Zuckerberg needed to make Facemash work. If you saw the movie, you probably remember seeing what looked like a scribbly equation on a window in Mark's dorm room. But what does that scribbly algebra have to do with Mark's simple "hot or not" site?</p>
<p>Algorithms are indeed instructions. Perhaps a more accurate description would be that algorithms are patterns for completing a task in an efficient way. Zuckerberg's Facemash was a voting site to determine someone's attractiveness relative to a whole group of people, but the user would only be given options between two people. Mark Zuckerberg needed an algorithm that decided which people to match up to one another, and how to value a vote relative to that person's previous history and previous contenders. This required more intuition than simply counting votes for each person.</p>
<p>For instance, let's say you wanted to create an algorithm for adding 1 to any negative number, and subtracting 1 from any positive number, and doing nothing to 0. You might do something like this (in JavaScript-esque pseudo code):</p>
<pre class="brush: js noskimlinks noskimwords">function addOrSubtractOne(number){
if (number < 0) {
return number + 1
} else if (number < 0) {
return number - 1
} else if (number == 0) {
return 0;
}
}</pre>
<p>You may be saying to yourself, "That's a function." And you're right. Algorithms are not a special type of operation, necessarily. They are conceptual - a set of steps that you take in code to reach a specific goal.</p>
<blockquote><p>So why are they a big deal? Clearly, adding or subtracting 1 to a number is a fairly simple thing to do.</p></blockquote>
<p>But let's talk for a second about searching. To search for a number in an array of numbers, how would you think to do it? A naive approach would be to iterate the number, checking each number against the one you're searching for. But this isn't an efficient solution, and has a very wide range of possible completion times, making it an erratic and unreliable search method when scaled to large search sets.</p>
<pre class="brush: js noskimlinks noskimwords">function naiveSearch(needle, haystack){
for (var i = 0; i < haystack.length; i++){
if (haystack[i] == needle) { return needle; }
}
return false;
}</pre>
<p>Fortunately, we can do better than this for search.</p>
<h3>Why is it Inefficient?</h3>
<blockquote class="pullquote"><p>There is no better way to become a better algorithm designer than to have a deep understanding and appreciation for algorithms.</p></blockquote>
<p>Let's say your array has 50,000 entries, and you brute-force search (that is, search by iterating the full array). The entry you are searching for, in the best case scenario, will be the first entry in the 50,000-entry array. In the worst case scenario, however, the algorithm will take 50,000 times longer to complete than in the best case scenario.</p>
<h3>So what's Better?</h3>
<p>Instead, you would search using binary search. This involves sorting the array (which I will let you learn about on your own) and subsequently dividing the array in half, and checking to see if the search number is greater or less than the halfway mark in the array. If it is greater than the halfway mark of a sorted array, then we know that the first half can be discarded, as the searched number isn't a part of the array. We can also cut out a lot of work by defining the outer bounds of the array and checking to see if the searched number exists outside of those bounds, and if so, we have taken what would have been a multiple-iteration operation and turned it into a single iteration operation (which in the brute-force algorithm would have taken 50,000 operations).</p>
<pre class="brush: js noskimlinks noskimwords">sortedHaystack = recursiveSort(haystack);
function bSearch(needle, sortedHaystack, firstIteration){
if (firstIteration){
if (needle > sortedHaystack.last || needle < sortedHaystack.first){
return false;
}
}
if (haystack.length == 2){
if (needle == haystack[0]) {
return haystack[0];
} else {
return haystack[1];
}
}
if (needle < haystack[haystack.length/2]){
bSearch(needle, haystack[0..haystack.length/2 -1], false);
} else {
bSearch(needle, haystack[haystack.length/2..haystack.length], false);
}
}</pre>
<h3>Sounds Fairly Complicated</h3>
<p>Take the seemingly complicated nature of a single binary search algorithm, and apply it to billions of possible links (as searching through Google). Beyond that, let's apply some sort of ranking system to those linked searches to give an order of response pages. Better yet, apply some kind of seemingly randomized "suggestion" system based on artificial intelligence social models designed to identify who you might want to add as a friend.</p>
<p>This gives us a much clearer understanding of why algorithms are more than just a fancy name for functions. At their finest, they are clever, efficient ways of doing something that requires a higher level of intuition than the most apparent solution. They can take what might would require a supercomputer years to do and turn it into a task that finishes in seconds on a mobile phone.</p>
<h3>How do Algorithms Apply to Me?</h3>
<p>For most of us as developers, we aren't designing high-level abstracted algorithms on a daily basis.</p>
<blockquote><p>Luckily, we stand on the shoulders of the developers who came before us, who wrote native sort functions and allow us to search strings for substrings with indexOf in an efficient manner. </p></blockquote>
<p>But we DO, however, deal with algorithms of our own. We create <code>for</code> loops and write functions every day; so how can good algorithm design principles inform the writing of these functions?</p>
<h3>Know Your Input</h3>
<p>One of the main principles of algorithmic design is to, if possible, build your algorithm in such a way that the input itself does some of the work for you. For instance, if you know that your input is always going to be numbers, you do not need to have exceptions/checks for strings, or coerce your values into numbers. If you know that your DOM element is the same every time in a <code>for</code> loop in JavaScript, you shouldn't be querying for that element in every iteration. On the same token, in your <code>for</code> loops, you shouldn't use convenience functions with overhead if you can accomplish the same thing using (closer to) simple operations.</p>
<pre class="brush: js noskimlinks noskimwords">// don't do this:
for (var i = 1000; i > 0; i--){
$("#foo").append("<span>bar</span>");
}
// do this instead
var foo = $("#foo");
var s = "";
for(var i = 1000; i > 0; i--){
s += "<span>bar</span>";
}
foo.append(s);</pre>
<p>If you are a JavaScript developer (and you use jQuery) and you don't know what the above functions are doing and how they are significantly different, the next point is for you.</p>
<h3>Understand Your Tools</h3>
<blockquote class="pullquote"><p>At their finest, [algorithms] are clever, efficient ways of doing something that requires a higher level of intuition than the most apparent solution.</p></blockquote>
<p>It is easy to think that this goes without saying. However, there is a difference between "knowing how to write jQuery" and "understanding jQuery". Understanding your tools means that you understand what each line of code does, both immediately (the return value of a function or the effect of a method) and implicitly (how much overhead is associated with running a library function, or which is the most efficient method for concatenating a string). To write great algorithms, it is important to know the performance of lower-level functions or utilities, not just the name and implementation of them.</p>
<h3>Understand the Environment</h3>
<p>Designing efficient algorithms is a full-engagement undertaking. Beyond understanding your tools as a standalone piece, you must also understand the way that they interact with the larger system at hand. For instance, to understand JavaScript in a specific application entirely, it is important to understand the DOM and performance of JavaScript in cross browser scenarios, how available memory affects rendering speeds, the structure of servers (and their responses) you may be interacting with, as well as a myriad of other considerations that are intangible, such as usage scenarios.</p>
<hr>
<h2>Reducing the Workload</h2>
<p>In general, the goal of algorithm design is to complete a job in fewer steps. (There are some exceptions, such as Bcrypt hashing.) When you write your code, take into consideration <em>all</em> of the simple operations the computer is taking to reach the goal. Here is a simple checklist to get started on a path to more efficient algorithm design:</p>
<ul>
<li>Use language features to reduce operations (variable caching, chaining, etc).</li>
<li>Reduce iterative loop nesting as much as possible.</li>
<li>Define variables outside of loops when possible.</li>
<li>Use automatic loop indexing (if available) instead of manual indexing.</li>
<li>Use clever reduction techniques, such as recursive divide and conquer and query optimization, to minimize the size of recursive processes.</li>
</ul>
<hr>
<h2>Study Advanced Techniques</h2>
<p>There is no better way to become a better algorithm designer than to have a deep understanding and appreciation for algorithms.</p>
<ul>
<li>Take an hour or two every week and read <a href="http://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043">The Art of Computer Programming</a>.
</li>
<li>Try a <a href="https://facebook.interviewstreet.com/recruit/challenges">Facebook Programming Challenge</a> or a <a href="http://code.google.com/codejam">Google Codejam</a>.
</li>
<li>Learn to solve the same problem with different algorithmic techniques.
</li>
<li>Challenge yourself by implementing built in functions of a language, like <code>.sort()</code>, with lower level operations.
</li>
</ul>
<hr>
<h2>Conclusion</h2>
<p>If you didn't know what an algorithm was at the start of this article, hopefully, now, you have a more concrete understanding of the somewhat elusive term. As professional developers, it is important that we understand that the code we write can be analyzed and optimized, and it is important that we take the time to do this analysis of the performance of our code.</p>
<p>Any fun algorithm practice problems you've found? Perhaps a dynamic programming "knapsack problem", or "drunken walk"? Or maybe you know of some best practices of recursion in Ruby that differ from the same functions implemented in Python. Share them in the comments!</p>
2012-10-05T22:28:42.000Z2012-10-05T22:28:42.000ZJonathan Cutrell