Algorithms, Data Structures, and Design Patterns for Self-Taught Developers

rendering

One of the comparisons I see of developers that have gone to school and that have not is a variety of less orthodox lessons that magically help in the real world. I usually say “Learn it as you go” but these lessons are so fundamental that unless you pick a super-specific field, you won’t learn and that will make you a lesser dev.

In the spirit of this, I decided dive deep down, read through Quora questions, Reddit discussions, and other news sources to compile a full list of knowledge that a programmer of any kind lacks if they had not attended school.

A recently made Quora question compiled some of the answers:

  • algortihms, data structures, and design patterns
  • compilers (implementations)
  • programming languages (implementations)
  • machine learning (implementations
  • finite state machines
  • code-as-data
  • functional programming
  • object composition
  • recursion
  • lambda calculus
  • pointers
  • type systems, category theory
  • search
  • numerical methods
  • common vocabulary, jargon, conventions
  • concurrency
  • artificial intelligence
  • operating systems

And while this is not a complete list it gives us an interesting starting point. Some of these need extra clarifications while some of these can be dismissed. So let’s dive into these one by one.

Today, I will cover the first bullet point. Algorithms, Data Structures, and Design Patterns.

Resource:

Algorithms, Data Structures, and Design Patterns

All of three of these basically compile to this: knowledge of efficient code placement and efficient execution of code to achieve the best possible result in the shortest amount of time. What a mouthful. Of course, that’s not the official definition but that’s totally fine. An algorithm, then, is basically a step-by-step procedure for calculations/execution. Data structure is a particular way of storing and organizing data (efficiently). A design pattern is basically a solution to a specific design problem. Design not meaning graphic design, but rather code structure and setup.

So, how can you learn these without taking courses? And why are they important?

Well, the biggest deal with these things is efficiency. How will these help you become more efficient with your coding? Computer programs are basically algorithms strung together coupled with data storage.

Algorithms

The deal with algorithms is that you’ll tie efficient mathematics to increase the efficiency of your programs without increasing the size of your programs exponentially. I’ve found a great website with a list of such algorithms.

Algorithms allow you to significantly cut down on processing time with some algorithms cutting your processing time from several years to several seconds when you deal with a great deal of data.

Just to illustrate with some examples, I’ll use PHP to create an array-searching algorithm. It will seem counter-intuitive , mainly because we already have an array-search algorithm in PHP, but this is how things get started, even in PHP. You start with a simple inefficient algorithm and move on up. Okay, here we go:

<?php
function searchArray($array, $term){
    $found = FALSE;
    $position = 0;
    foreach($array as $key => $value){
        if($value == $term){
            $found = true;
            $position = $key;
            return $key;
        }
    }
    if($found == FALSE){
        return 'Not found';
    }
}

$fruits = array('oranges', 'apples', 'bananas');
$watermelon = searchArray($fruits, 'watermelon');
echo $watermelon;
?>

The foreach part is like an “algorithm”. It may look more familiar if it was rewritten in a “for” statement rather than “foreach” but you get the idea. Can you think of a faster way to search an array? The problem here is that the more terms you have, the longer it will take to find the position of our element. Which sucks. Well, what if we ordered the array first or kept a self-ordering array (described below)? You could potentially use a binary search then which basically works by “guessing” and finding the answer. It picks the middle of your array and tries to figure out if it should look toward the top or bottom half. Then it hits the middle of that half and so on until it finds the right result.

Where to learn it:

Data Structures

You probably know the basics of this. You have your arrays, integers, booleans, strings, as well as combination. A study of this can really help you understand how data operates and what makes your programming more efficient, rather what data type. For example, a string is actually an array of characters (basically speaking) so you should know that costly array functions will be just as costly for your strings.

The great thing about data structures is that using the correct structure can improve what you’re doing. I would say that this is one of the reasons why more seasoned programmers prefer strong statically-typed languages (languages that require a declaration of what type of a variable it is). So what is a data structure?

A data structure is a data-type (like int, array, etc.) with various functions that allow it to grow, be smaller, and definitions on how it should be treated. Let’s create a special self-ordering array, basically a slightly extended array.

<?php

class SelfOrderingArray{
    protected $arr = array();
    protected $type = '';

    public function __construct($type = 'NUMERIC', $defaultArr = array()){
        $this->type = $type;
        $this->arr = $defaultArr;

    }

    private function innerSort(){
    if($this->type == 'NUMERIC'){
        sort($this->arr, SORT_NUMERIC);
    }
    elseif($this->type == 'STRING'){
        sort($this->arr, SORT_STRING);
    }
    else{
        sort($this->arr, SORT_REGULAR);
    }
    return true;
    }

    public function addElement($el){
       array_push($this->arr, $el);
        $this->innerSort();
         return true;
    }
    public function rmElement($el){
        if(isset($this->arr[$el])){
            unset($this->arr[$el]);
            $this->innerSort();
        }
        return true;
    }
    public function getArray(){
        return $this->arr;
    }

}

$newArr = new SelfOrderingArray('STRING', array('orange', 'apple', 'watermelon'));
$newArr->addElement('pear');
print_r($newArr->getArray());

?>

We’ve created a (inefficient) data structure that orders itself whenever an element is added or removed. This can be useful for number of reasons. But outside of that, this is pretty much how new data structures are made. Of course, we’d normally also create a more efficient “Add” system that would not require a resort of the entire array but rather the only parts of the array that require it. But that’s part of programming. You try to make things more efficient by just thinking about it and testing. What if we split the array whenever we added an element, added the element to the end/beginning between the split and added the arrays together? Would that be more efficient? Idk, but that’s part of learning about data structures and algorithms!

Recently, dynamic arrays have made it to some languages. What are those? Well, if you only coded in PHP, you’ve never had to experience regular arrays that require you to declare array size right away, and you can’t change it either. The array takes up a certain amount of space and will not grow. Dynamic arrays (in a similar way as our “self-ordering array”) adds several functions that allow it to grow by being duplicated and having their size expanded.

Resources:

Design Patterns

A directly applicable concept, design patterns are simply “solutions” to existing problems. Think about it this way, you’re presented with a challenge. “How do you most efficiently do X?” A design pattern is a pre-established and tested solution on how to do X. It helps not only with communication among developers but obviously for your application.

The pattern I hear most about, for example, is the Singleton Pattern. It’s a pattern essential when you require exactly one instance of a class. Part of this design is to make sure that there IS only one instance and if there isn’t one, one is created. Some examples include Logger classes, Config classes, and other similar classes. I will be using a Singleton class that I found on PHPBuilder.

<?php

class SingletonClass
{
    private static $_instance = null;
    private function __construct() { }
    public function __clone() {
        trigger_error( "Cannot clone instance of Singleton pattern ...", E_USER_ERROR );
    }
    public function __wakeup() {
        trigger_error('Cannot deserialize instance of Singleton pattern ...', E_USER_ERROR );
    }
    public static function getInstance()
    {
        if( !is_object(self::$_instance) )
            self::$_instance = new self;

        return self::$_instance;
    }
}

$configs = SingletonClass::getInstance();
?>

Without getting too deep into it, let me explain. Similar to constructors, PHP allows __clone which basically tells PHP what to do when someone tries to clone your class/object. Anyways, so what this class does is it makes sure it exists only once. Whenever you want to retrieve the class’s functions or variables, you use the static called SingletonClass::getInstance() which first checks if an instance of the object exists and if it doesn’t, create an instance of the object.

Think about it, this is really smart. You can use this for database connections to make sure you don’t create 10 different database connections throughout your app. And every time you want to access the class and its functions/variables, you can just use the static caller for ::getInstance. You’ll still be accessing the same object just under a different variable.

Resources:

Where will this get you?

Well the positive of learning all of these things, as I’ve said, is efficiency. But beyond that, there’s communication with other developers, better understanding of code and frameworks and so on.

Algorithms can propel you forward and give you better insight as to what kind of function to use to sort more efficiently, or how to use it correctly. By learning basic algorithms you’ll also have an easier time going through framework basecode and how they handle data and some of their additional functions.

Data Structures and how they work also help you pick what’s best. You learn what operations are expensive in terms of processing and memory. You can also learn how to create your own data structures, sort of. If you think about it, all data structures (the “collection” type) are classes that congregate primary data structures together and find efficient ways of accessing/storing/using data via, wait for it, algorithms.

Design Patterns, the last part, I feel like are the most immediate because they help you setup your structure in conventional, tested, and proven ways. You’ll also recognize these, again, in frameworks, libraries, extensions and that will give you a better insight as to how those work, how you can improve them, and how you can create your own.

Good luck on learning about these! And make sure you sign up for updates for the next topic!

NOTE: Any and all criticism regarding the article and what’s in it is appreciated. 

Comments

  1. Patrik Fuhrmann says:

    Very nice tutorial. If only I could join defense company and write software for rovers on PHP. I understand it was just example but this machines are running languages such as C++, Ada, Fortran and most of the code is actually generated by machine (mainly tests).

    • Antonin Januska says:

      Totally fine. Which is why I reference resources. Most of my visitors are web developers, just like me, so I tried to give examples in PHP, the bread-n-butter of a developer.

      If you have any great examples in other languages, I’m all for referencing them in my article! :)

  2. Under data structures, you said “strong-typed languages (languages that require a declaration of what type of a variable it is)”. I could be wrong but I think you meant statically typed languages.

    • Antonin Januska says:

      I had to actually look this one up. I think you’re right. I’ll go ahead and change that.

    • danhatch says:

      statically typed = code needs to be compiled before being run
      strongly typed = all objects have their own types and cannot be swapped
      strongly typed languages have different variable declaration rules/standards.
      weak inference = variable types need to be declared
      strong inference = most variable types are inferred based on their context, ex Haskell

  3. Great, great, great,great!

    Excellent to understand, simple language!

    It’s getting favorited.

  4. Alex Bonel says:

    I want to mention that in the beginning list of this post, the really one statement which should be highlighted among others is common vocabulary, jargon, conventions as this statement makes great influence on understanding all of the concepts in any kind of informational technologies.

  5. danhatch says:

    Some consider the Singleton pattern as a very poor design decision. Here is a really good overview with some alternatives you can use found here: http://gameprogrammingpatterns.com/singleton.html Basically, it’s about minimizing global state and having finer control over the initialization of your objects.

  6. Ronald Chaplin says:

    Excellent read! Very clear and easy to understand.

Add Your Comment