DEV Community: Eben Eleazer

OOP Polymorphism aka "All Dogs Don't Bark the Same"

Eben Eleazer — Sat, 27 Aug 2022 22:43:00 +0000

The final major concept that make the "four pillars" of Object Oriented Programming, is Polymorphism. In order to fully understand polymorphism, I recommend being comfortable with the other 3 pillars (encapsulation, abstraction and inheritance), first.

Generational Differences

Just like the Fresh Prince said, "Parents just don't understand". Just because child classes (aka sub-classes) inherit properties and behaviors from their parent classes (aka super-classes), that doesn't mean they do things the exact same way. I mean, you don't act exactly like your parents. do you? (it's okay if you do).

the point is, while parents and children may have many of the same attributes and behaviors, they don't have to be one for one exactly. And, especially when it comes to behaviors, children don't always perform those behaviors the same way.

Every Dog Has His Day

As an example, lets make some classes about different dogs.

Here is our dog class:

class Dog
    def initialize(breed)
        @breed = breed
        @number_of_legs = 4
    end

    def bark
        puts "Bark, Bark"
    end
end

Let's also say that our program is going to let us differentiate between small dogs and big dogs, and so we will need a class for both small dogs and big dogs.

Since we already have a Dog class, we can have Small Dog and Big Dog inherit from the Dog super class. This makes sense because a Small Dog is a Dog, and a Big Dog is also still a Dog.

class SmallDog < Dog
end

class BigDog < Dog
end

Sweet, now SmallDog and BigDog can be initialized with a breed, they both will have a number_of_legs set to 4, and they both have a bark method. Thanks inheritance!

The problem is, though, we want to make sure there's a difference between small dogs and big dogs. Right now, they both do everything exactly the same as their superclass (a generic dog), and therefore exactly the same as each other.

Specifically, it make more sense for small dogs to say "yap, yap" and big dogs to say "ruff, ruff" when they bark.

By invoking the OOP principle of polymorphism, we can do that!

class SmallDog < Dog
    def bark
        puts "yap, yap"
    end
end

class BigDog < Dog
    def bark
        puts "RUFF, RUFF"
    end
end

By giving our subclasses a method with the same name as its super class, our program will prefer to use the subclass implementation when the method is called (on an instance of that subclass). This is called method overriding and is they key to polymorphism.

What that means is that, now, Dog.bark will print "Bark, Bark", SmallDog.bark will print out "yap, yap" and BigDog.bark will output "RUFF, RUFF".

All dogs bark, but the way they bark can change depending on the exact class of Dog (aka subclass)

All the Pillars

With that, we have gone over all 4 of the major concepts in Object Oriented Programming (also known as the 4 pillars of OOP).

As a quick recap:

Encapsulation - bunding properties and behaviors into an object/class
Abstraction - Ignoring unnecessary details and properties
Inheritance - Using super and sub classes to share behaviors and properties with related classes
Polymorphism - letting sub classes implement their methods differently than their super class

This concludes the series on OOP concepts. If you have any comments or questions, feel free to respond below!

Thanks, see you next time.

OOP Inheritance aka "It's About Family"

Eben Eleazer — Sun, 14 Aug 2022 20:12:11 +0000

I wish I had a rich uncle, but unfortunately we're not talking about that kind of inheritance.

We are talking about family, though.

Specifically, Inhertiance is talked about in terms of parent classes and child classes.

Super classes

How can one class be a parent of another? It's not like our classes are out here giving birth. In fact, some people prefer to call them "super" classes instead, and personally, I think that makes more sense.

So if a class consists of common properties and behaviors of other objects (or instances) then what do you think a super class would be?

Exactly, It has properties that are common to other classes!

When we say super, or parent, what we're actually saying is "more general".

All Squares are Rectangles

Let's look at an example that you're likely familiar with. I'm sure you remember from geometry what a rectangle and a square are.

You'll also likely remember that all squares are also rectangles, but all rectangles are not necessarily squares. A square has all the properties of a rectangle (4 sides, 4 right angles), but it also has additional properties (all sides are equal length).

If we make a class for rectangles:

class Rectangle
    @sides = 4
    @all_right_angles = true
end

and squares:

class Square
    @sides = 4
    @all_right_angles = true
    @all_sides_equal = true
end

we'll see that all the things in the rectangle class are in the square class.

Since the whole point of a class is to be more abstract, and more general, the more general class is the "super" class. In this case the rectangle is the super or parent class. The square class would be considered a subclass or child class.

Grandparent Classes and other relations

A rectangle is the parent of a square, because a square has all the properties and behaviors of a rectangle.

But, aren't all rectangles also parallelograms? (If you forgot geometry, the answer is yes.)

And, aren't all parallelograms also quadrilaterals? And aren't all quadrilaterals also polygons? And aren't all... you get the idea.

Just like the parents of your parents, we can call these classes grandparent classes. Further relations can be considered decedents or ancestor classes, but it's not very common.

** Square < Rectangle < Parallelogram < Quadrilateral < Polygon **

There are also "sibling" classes that share the same parent but are otherwise unrelated.

A rhombus class for example, would be a sibling of the rectangle class, because they are both children of the parallelogram class!

Inheritance in Code

Now that we have the concept down, let's look at what it means for our coding.

look at our square and rectangle classes from before:

class Rectangle
    @sides = 4
    @all_right_angles = true
end

class Square
    @sides = 4
    @all_right_angles = true
    @all_sides_equal = true
end

Since squares have all the properties and behaviors of rectangles, we can set up our square class as a child or subclass of rectangles. In ruby we do this using a '<' in the class declaration.

class Rectangle
    @sides = 4
    @all_right_angles = true
end

class Square < Rectangle
    @all_sides_equal = true
end

Now the square class will * inherit * everything in the rectangle class, and we don't have to type it all out again!

OOP Abstraction aka All You Need Are Stick Figures

Eben Eleazer — Sun, 07 Aug 2022 18:12:49 +0000

I'm going to be honest, I still use stick figures 99% of the time I draw people.

It's not because I'm particularly bad at drawing (I've taken an art class or two), but for most of the diagrams or figures in which I need to represent a person, it's just not worth the effort trying to create a photorealistic person. As long as the audience understands it's a person, that's usually good enough.

2 legs, 2 arms, a torso and a head, and that's generally enough to get the idea of a "person" across. I may add extra details to specify gender or something, but only if I really have to.

Sure, I could worry about hairstyles, what the face looks like, hopes, dreams etc., but we don't need those things to visually understand an object is a person. We just need those few lines and a circle, arranged in a specific way.

Now I know this is supposed to be a technical post about Object Oriented Programming, not an art blog, but this is actually a perfect example of our next core concept in OOP: Abstraction!

The Devil is in the Details

The dictionary defines abstraction as:

abstraction
[ ab-strak-shuhn ]
noun
the act of considering something as a general quality or characteristic, apart from concrete realities, specific objects, or actual instances.

*note this is actually the second definition on dictioary.com, but it's the useful one

In other words, we ignore all the details that makes up an individual, and focus only on the common properties and behaviors.

This should already sound familiar if you read the first two posts in this series, because that is exactly how we figure out what to include in our classes!

But abstraction goes even deeper than that. Or should I say shallower?

You see, since we're dealing with code, we're probably not going to be dealing with the objects visually. So even the details of what the object looks like, are probably unnecessary.

The only details. and therefore the only properties and behaviors, that we need to worry about are the ones that we're actually going to use!

For example, let's imagine we are going to use person objects in a program. These person objects are probably going to represent users, so let's abstract a person/user that might be used in a program.

We're probably not going to be looking at the person, so we can leave out anything related to the appearance of a person (number of legs, size, hair color, etc.)

Unless it's like a counseling program or something, we can probably leave out anything related to a person's internal state as well.

Actually, it'll be faster just to think about what details we do need, that all of our person/user objects will have in common.

One thing property that people have is a name. And it might be useful for our program so we can tell people apart.

class Person
    def initialize(name)
        @name = name
    end
end

Also, all the people in our program are going to do want to do something in our program, so that's a behavior detail they'll need.

class Person
    def initialize(name)
        @name = name
    end

    def do_something
        # does something in the program
    end

end

And you know what, I think that's it.

Just like with stick figures, we can add more stuff if we decide we need it, but as far as our app is concerned, a person can be as simple as "a thing, with a name, that does something".

Now that's abstract!

Conclusion

When it comes to coding, less is more. By abstracting away all the useless details from the real world, we can model just the things that are actually useful.

OOP Encapsulation aka Wrap it Up

Eben Eleazer — Sun, 31 Jul 2022 18:32:00 +0000

Last time when we talked about objects, I mentioned that an object can be considered as a bundle of properties and behaviors. This time, we're going to take that idea even further and look at the concept of encapsulation.

Encapsulation

When we think of an object, real or imaginary, physical or code. The first thing we need to do is separate it from the rest of existence. What I mean, is that in order to create the concept of an object, let's just say a smartphone, you simultaneously create the concept of "not a smartphone". There is a distinction made between the objects that have the properties and behaviors of smartphones, and basically everything else.

This is just another way of saying that and object is a group of properties and behaviors, but the focus is in the grouping process.

The non-computer definition in the dictionary for Encapsulation is, "the action of enclosing something in or as if in a capsule". Obviously, that's not exactly what we want, but if you think about it, it's a lot closer than you might think. We might not be using a capsule per say, but we are definitely enclosing things.

In this case, the "capsule" is the idea of the object itself. You can think of the object as a capsule containing properties and behaviors. Which properties and behaviors are encapsulated are what define the object.

Hiding Data

When it comes to the properties of objects, usually it's considered poor design to interact with property values directly. It may not be obvious, but this is also a part of the concept of encapsulation.

For example, let's take a tree as our object. A tree has properties such as species, height, age, etc. Now, while a tree definitely has those properties, how can we, as people (aka separate objects) access those properties? We don't get to just know those things, we have to do something (look, measure, etc.) in order to gain access to those properties.

Also, remember that doing something is more like a behavior, or in the case of code, a method. So, we have to use methods in order to read or change the values of object properties.


class Tree

   def initialize( tree_params ) #tree_params is a hash
      @height = tree_params[:height]
      @species = tree_params[:height]
      @age = tree_params[:height]
   end


end

This makes sense in the real world, too. You don't get to just know the information in a book, you have to read it. You don't get to automatically know what color a car is, you have to look at it!

Getters and Setters

In the real world, we have lots of complex behaviors and actions that we can take when interacting with objects. If we want to know the age of the tree from earlier, for example, we might have to cut it down and count the rings. Or, we could measure the trunk diameter and do some science.

While methods in code can also be very complex, when it comes to accessing properties of other objects, we have much more power than in the physical world.

We can simply ask an object about a property, or tell it to change. It would be like going up to the tree, asking it's age, and then knowing it's 116 years old. Or, it would be like telling the tree to become a palm tree.


class Tree

   def initialize( tree_params ) #tree_params is a hash
      @height = tree_params[:height]
      @species = tree_params[:height]
      @age = tree_params[:height]
   end

   def get_age
     return @age
   end

   def set_age(age)
      @age = age
   end

   def set_species(species)
     @species = species
   end


# I used get_ and set_ in the method declarations to help
# illustrate getters v setters. 

end

In code, these methods are extremely common and are an important part of encapsulation. Methods that asking an object about it's properties are called "getters" (because they get the value from the object) and methods that tell that value to change (usually by directly giving a replacement value) are called "setters"

Encapsulation Conclusion

By restricting access to properties (and internal behaviors as well) through getters and setters, and by combing them into more complex behaviors, we are able to create object models that are useful and behave predictably.

From there, the fun can start

Thinking Objectively: OOP Basics

Eben Eleazer — Sun, 24 Jul 2022 22:24:35 +0000

After the last series on Big-O notation, I decided to do another series covering some of the basics of programming.

This time, we'll be exploring the 4 key concepts of Object Oriented Programming. Also known as the 4 "pillars", these concepts form the foundation of OOP. These concepts should help you think about coding in a way that can be very intuitive.

What are Objects?

It's self explanatory, but Object Oriented Programming (OOP) is going to be focused around the idea of objects. So, the first point of order is to understand what an object is in programming.

A Thought Experiment

In order to understand the idea of an object, let's do a thought experiment.

Think of an object. It can be anything you can imagine. Now, think about how you would describe your thing to someone else, without using its name.

...

Depending on your object, it was probably pretty simple. In fact, it's basically just charades on easy mode.

(It is small, I has a tail, It says "quack", it can swim, it has a bill, etc...)

Each of these descriptors can be thought of as either a property, or a behavior. Properties are things that describe what the object is, and behaviors describe what it does. Once you have enough of these descriptors, you can easily imagine the object (or something close enough).

In other words, an object can be thought of as a group of properties and behaviors.

We're going to come back to these properties and behaviors, but for now the big revelation is that they have to be thought of as a group!

Think about it, if I just say color: brown or can fly, individually they don't mean much. But when you group the properties and behaviors together you get the full picture:


   size = "small"
   tail = true
   quack = (do something)
   swim = (do something)
   mouth_type = "bill"
   color = "brown"
   fly = (do something)

When written this way, it's easy to see how we can use this view of objects to start to model them using code.

Keeping it Classy

Let's make a small program about ducks. We'll start with two ducks:


duck_1 = "Cleopatra"
duck_2 = "Mr. Whiskers"

That's cool, but let's say we want to tell the color of the ducks:

duck_1_name = "Cleopatra"
duck_1_color = "brown"
duck_2_name = "Mr. Whiskers"
duck_2_color = "mallard"

We should also tell the age and gender of the ducks, and whether or not they're "available":

duck_1_name = "Cleopatra"
duck_1_color = "brown"
duck_1_age = 2
duck_1_gender = "Male"
duck_1_available = true

duck_2_name = "Mr. Whiskers"
duck_2_color = "mallard"
duck_2_age = 2
duck_2_gender = "Prefer not to say"
duck_2_available = true

Now imagine, we have 10 more ducks sign up for our dating app (did I not mention what we were making?). We would have to write out those 5 variables for each one.

Not only that, but even though the values are different, all the ducks have a variable for name, color, age, gender and available. Since I know I need these variables for every duck, and I have a good idea what the possible values will be, It would be cool if I could just tell the program to make a "duck".

Classes allow us to do just that!

class Duck 

 attr_accessor :name
 attr_accessor :color
 attr_accessor :age
 attr_accessor :gender
 attr_accessor :available

end

Duck.new(name: 'Cleopatra', color: 'brown', age: 2, gender: 'male', available: true)

#etc...

It might help to think of a class as a template or a prototype for individual objects.

Object Orientation

With objects and classes we can represent real world (or imaginary) objects in code. By building onto, extending and connecting these objects and classes of objects to each other, we can build incredibly complex programs and model any number of situations.

Big O: Series Finale

Eben Eleazer — Sat, 16 Jul 2022 22:57:43 +0000

If you've been following along with the series so far, you should be familiar with the overall concept of Big O notation, as well as being able to recognize constant, linear, logarithmic and polynomial time complexities.

For this last entry, we'll wrap up with some of the less common "common complexities", and a little bit about space complexity.

O(2^n) Exponential Time

While O(n^2) is sometimes mistakenly referred to as exponential time (it's actually called polynomial time), true exponential time is another thing entirely. Exponential time refers to functions that grow at a rate of O(2^n).

This is actually much more complex than polynomial time, and can result in unacceptably long runtimes. For every single increase in input size, the entire number of operations doubles!

At input size 1, number of operations is 2.
At input size 2, number of operations is 4.
At input size 10, number of operations is 1,024.
At input size 11, number of operations is 2,048!

Here is a direct comparison to the other common complexities we've gone over:

n = 11

Constant time/O(1): 1 operation
Logarithmic time/O(log n): around 4 operations
Linear time/O(n): 11 operations
Polynomial time/O(n^2): 121 operations

Exponential time/O(2^n): 2,048 operations

As you can see, things can get out of hand very quickly.

Some kinds of recursion can lead to algorithms with O(2^n) time complexity, so it's worth watching out for. But, if you're using the proper data structures and techniques, exponential time algorithms should be avoidable or optimizable to a more efficient solution.

O(n!) Factorial Time

Now if you thought O(2^n) was bad, you don't want to know about O(n!).

Thinking through factorial time, we can see that increasing the input by 1, doesn't just double the number of operations, it multiplies them by whatever our new value is. In other words, the 11th input, will take 11 times as many operations as the 10th.

Let's look at some sample values like before:

At input size 1, number of operations is 1. (not bad)
At input size 2, number of operations is 2. (wait this is actually less)
At input size 3, number of operations is 6. (hmmmmm )
At input size 4, number of operations is 24. (that's a pretty big jump)
At input size 10, number of operations is 3,628,800. (pretty wild)
At input size 11, number of operations is 39,916,800!

Obviously, algorithms in factorial time quickly become too complex to be very useful. However, there is a famous example of a factorial algorithm called "the travelling salesman" which shows at least one use case. It's pretty interesting, and you can go really deep into computational complexity, if you're up for it.

Space Complexity

So far, for this whole series, we've only been talking about Big-O notation in regards to time complexity.

But, as you probably already know, there is another aspect to algorithms called space complexity. Space complexity is also expressed using big-o, and goes hand in hand with time complexity. In fact, you already know everything you need to understand space complexity. All we have to do is change our perspective a bit.

Space complexity describes how much more space in memory an algorithm uses as the input size increases.

Pretty familiar, right. All we need to do is look at memory use instead of number of operations. In other words, instead of focusing on what we "do", we'll look at what we "make".

Take, for example, a basic factorial method


def factorial(n)
   if n < 1
      return 0
   elsif n == 1
      return 1
   else
      return n * factorial(n-1)
   end
end

We can calculate that our time complexity is O(n). The conditional will be constant time, but since we will have to call our function recursively on all numbers up to n, we can see that it runs in linear time.

Now let's look at the space complexity. To do this, we'll change our perspective from "do" to "make".

Is there any place in our code where we create a new value? Yes, There is. When we do our recursive call we need to make the value "n - 1". This will require a new space to record the value of "n-1". So, we can say that as our n increases the amount of space it requires will increase.

In this case, an input of 10 will make 10 new values, and an input of 100 will make 100 new values (0-99). If we apply our big-O notation logic, it's easy to see that the space complexity will be O(n), or linear space complexity.

Just remember that space complexity follows the same logic, we're just applying it to a different aspect of the algorithm.

Conclusion

If you've followed through from the beginning, hopefully you now know enough about big-o notation and complexity theory to confidently identify common complexities. If not, I hope that I at least encouraged you to investigate further and gave a decent enough intro to the subject.

O(log n): Logging time

Eben Eleazer — Sat, 09 Jul 2022 14:30:52 +0000

If you're following this series, we've already covered constant, linear and exponential time. Now it's time to get logarithmic!

If you don't remember what the logarithm is from high school, that's perfectly fine. I'm not the best at them either. In fact, in math class you probably dealt with logs with a base 10 (since most math uses the decimal system as default), but I'm going to be talking about base 2 (for other that will make sense in a bit).

A good compromise for our catering company

After all that work teaching the haters a lesson, It's time for our algorithmic catering company to get back to catering.

The problem is, making our O(n) individual meals was too hard, and our O(1) soup got complaints for being too boring. We need something in the middle; something less complex than linear time, but that solves a problem that can't be solved in constant time.

What about a buffet?

Instead of making individual meals for every person, or making one big meal for everyone, we could do our events buffet style. That way, people could get the individual meals they want, but we wouldn't have to make a meal for everyone, just several big trays.

It would probably be a good idea to increase the variety of foods, depending on the size of the event. The more people, the more likely someone will complain that we didn't have what they want. We also charge more money for larger events, so we need to give them their money's worth.

At the same time, if we add a new dish for every person, that would defeat the point. What we could do, is add a new dish every time the number of guests doubles!

Think about it, for a party of 10 people (assuming we start with one dish for one person) we would make 4 dishes*. That seems like a good amount for 10 people, and once we get 16 we'll make a 5th dish. Those are reasonable numbers, and still less work than individual meals.

What about 1,000 guests? If you work it out, we'd only have to make 11 dishes! That's way less work, and I doubt anyone would complain with over 10 options on the menu.

Great!

Putting some Logarithm in our Algorithm

In order for our plan to work, we'll need to find a way to increase our dishes by one whenever our total doubles. Another way to think of it, is that we need to find the number of times the number of guests can be divided in half until you get to one. This is also the exponent that 2 would be raised to to get to our number of guests.

If it hasn't come back to you yet, this is exactly what logarithm is for! Specifically, we need to use log base 2 because our doubling/multiplying by 2 means that 2 is the number with the exponent.

With all that in mind, let's make some pseudocode for our new catering algorithm:

# n = number of guests

def cater_party_buffet_style(n)

   number_of_dishes = 1 #set a default number of dishes

   if n == 0
      # if no one shows up, we don't have to cook
      number_of_dishes = 0
   elsif n < 4
      # if we have less than 4 guests (but at least one)
      # we should just make 2 dishes.
      number_of_dishes = 2
   else
      # We use log base 2 to get our exact number of dishes
      # And we use `ceil` to round up 

      number_of_dishes = Math.log(n, 2).ceil
   end

   number_of_dishes.times do 
      cook_something(entrée, side, dessert, etc)
   end
end

O(log n) complexity

Looking at our algorithm, it's pretty easy to see how the number of operations grows. Since it clearly increases with the logarithm (base 2) of the input, we say it is O(log n) or logarithmic time.

Probably the most famous example of a O(log n) time complexity algorithm is binary search. I'm not going to go over it, because it's been done to death, but here's a good resource.

The key to logarithmic time is that as the input size increases, the number of operations increases at an increasingly smaller rate.

When we look at logarithmic time curve on a chart, we can see that at low values it's relatively similar to linear time. But as our input size increases, it is actually causes actually gets closer to constant time.

Final Notes

If the giveaway for linear time is "iterating over the input", and for exponential time it's "nested iteration", then what's the giveaway for logarithmic time?

We could say: "removing a fractional part of the data set with each iteration". Binary search, a popular O(log n) function, works by dividing the search range in half, and then recursing until the item is found. In our buffet style catering algorithm, each additional guest only contributes half as much to unlocking a new dish, as the previous guest. (You may recognize this pattern from RPG leveling)

Theoretically, in our catering algorithm we could wait until the guests triple, which would still be logarithmic time, only the base would be 3. But working with 2 parts is more natural, and it works better with Booleans, so most of the time the base of your logarithmic algorithms will be 2. That's why if you see O(log n) you can assume it to be base 2.

*1 dish at 1 guest, 2 dishes at 2 guests, 3 dishes at 4 guests, 4 dishes at 8 guests

O(n ) : Don't be a Square

Eben Eleazer — Sat, 02 Jul 2022 18:31:37 +0000

Getting more complex

So far we've covered O(1) aka Constant Time, and O(n) aka linear time.

While constant time is the most efficient, linear time is also not bad when it comes to algorithm complexity. O(n²), however, is pretty bad. We'll see just how quickly the operations get out of hand by going back to our catering company...

Our Catering Company is in Trouble

The company that we've been working with were happy with our first event, but they have gotten tons of complaints about our last catering job. Apparently, the guests thought our ingenious Constant Time Soup was lazy and they wanted more food options.

We could try to find a compromise between the two, to deliver a nice experience at better than linear time...

Or we could be super vindictive and hatch a ridiculously contrived revenge plot!

A "Catering Company" Company

If those guests knew how hard it was to run a catering company, they would understand why we wanted to use Constant Time Soup. If they had to make all those meals, they'd recognize our ingenuity.

So we're going to run a new company that teaches people the difference between doing the event each way! That'll teach 'em!

Just like before, let's make some pseudocode to map this out:

# n = number of people aka haters

def teach_those_haters_a_lesson (n)

   # we have to teach each hater 
   n.each do |hater|  # O(n)

     # First we have to get each hater to cater a party
     # for all the other haters, using the individual meal method

     idnv_meal_cater_party(all_the_other_haters) # O(n)

     # After that, we let them do the soup way
     # so they can see why it's better!

     soup_cater_party (all_the_other_haters) # O(1)

   end
end

If that plan sounds like an overly impractical and overly complex plan, you're absolutely right. Not only are we going to have to cater a party with individual meals, we're going to have to do that for every guest! A WHOLE SEPERATE PARTY FOR EVERY GUEST!

Yeah we'll have to also do a soup party, and technically we don't have to make a meal for our revenge victim while they are cooking with us, but those are trifles compared to the extra work we'll do (and remember what happens to constants in big O notation) .

The simplest way to think of it, is that For every guest, we have to make a meal for [almost] every guest. In other words, perform an O(n) complexity algorithm (make meals) O(n) times. Since it's O(n) X O(n), we get O(n²).

Identifying O(n²)

An easy way to spot an O(n²) time complexity are nested loops. Specifically, if a data set is being iterated over within another iteration.

That being said, not every nested iteration results in O(n²) time. The nested loop doesn't have to be correlated with the original input size. For example, if we consider each character in an array of strings, in one case we are looking at the size of the array (how many strings) and in the other we are looking at each string's length (which could be anything).

Since those two inputs aren't necessarily the same, they'll need separate variables, and our big-O function will end up being O(nk) where k represents the size of the other input (in the example case, it would be the max length of an individual string)

If k is constant (or has a maximum value that is constant) then our nested loop would technically simplify to linear time O(n). But, the smaller the size of the input, the more effect it will have. Just because k may become negligible as n reaches infinity, it can still make a big difference at the sizes you're actually inputting.

Next Time

We're almost done with the common complexities. Next time we'll look at logarithmic time O(log n), and it's cousin O(n log n)

Till then...

O(1): Constantly Efficient

Eben Eleazer — Sun, 26 Jun 2022 17:41:28 +0000

In the last post, we broke down O(n) aka linear time, because (in my opinion) it is the most straightforward common complexity to understand. As n (number/size of input) grows O (number of operations) grows at a similar rate.

The truth is, there's an even simpler common complexity. Not only that, it's also by far the most efficient.

Of course, i'm talking about O(1) or Constant Time.

Back to the Catering Company

If you'll remember from last time, we had a catering company who was hired to do an event. We decided to make an individual plate for everyone, and we therefore calculated our catering algorithm to be O(n).

But, what if we didn't have to make an individual plate for everyone?

What if instead just made one big pot of soup!

Then we wouldn't have to do anything all day! We could just make one giant pot of soup and make sure it's big enough for all the guests.

Just like before, let's pseudocode this up:

# n = number of guests

def cater_party (n)
   # make 1 big pot of soup
end

So how does our number of operations grown in relation to our input size?

If there's 1 guest, we make 1 pot of soup.
If there're 100 guests, we make 1 pot of soup.
If there're 1,000,000,000 guests, we make 1 pot of soup.

Looking at our algorithm, and thinking about it logically, no matter how many people attend our event, we're still only going to make 1 pot of soup.

The number of operations, in our case, is constant. Our algo simply doesn't increase in complexity based on the input.

Remember, we can simplify constant values to 1 for the sake of simplifying our big-o notation (since the effects of constant values on complexity decrease to negligible at higher n values). No matter how many operations it actually takes, if it doesn't grow along with our input size, we might as well just consider it one big operation.

And so we get O(1).

The most efficient complexity

O(1) algorithms, because they are constant time, they are easily the most efficient complexity. A truly constant time algo, will process an infinite amount of data, in the same time it would take to do just 1.

A code example, that you've probably used, would be accessing an array element by index. In this case, since you know the index, it doesn't matter how large the array is because the program knows exactly where the element is.

There are other plenty of other algorithms with a complexity of O(1), and many other complex algorithms use them. In fact, you could probably think of most basic operations as algorithms with O(1) complexity.

Next time

Now that we've gone through O(n) and O(1) were going to start getting more complex

O(n) our way

Eben Eleazer — Sat, 18 Jun 2022 15:40:54 +0000

Now that we have a basic overview of Big-O notation, I think the best way to build understanding will be to learn by going through each of the most common complexities.

Part 2: O(n)

The first big-o function we're going go look at is O(n), also known as linear time.

Hypothetical Catering Company

Lets pretend you own your own catering company. You recently scored a contract with a local business to provide food for all their corporate meetings and events!

But, you're not just a caterer. You're also a coder! So before we do anything, we're going to map out our algorithm so make our meal as efficient as possible.

Let's write some pseudocode (in ruby cause I like it most)

# n = number_of_people

def cater_party (n)
   # whatever we're going to do
end

There are a couple of ways you could handle this event, but let's say you decide to make a meal for every person in attendance.

Lets update our pseudocode

# n = number_of_people

def cater_party (n)
   n.each do |person_at_party|
      # plate some chicken
      # plate some side dishes
      # etc
      return full_meal
   end
end

If 1 person shows up, you make 1 plate
If 10 people show up, you'll need to make ten plates
If 10,000 people show up, you'll have to cook and prepare 10,000 separate meals!

We can see that as the number of people who are come to the event increases, the plates we need to make also increases by a constant amount. In this case 1 more person means 1 more meal to make.

Intuitively, it's pretty easy to see how our workload grows related to the number of people. Our workload increases by a constant amount for every new person.

This is the relationship expressed by O(n).

Constants

If we think about our catering meals example, there was a lot of extra work we left out. What about all the set-up? What about providing the drinks? What if we had to make a dinner and a desert plate?

Really our catering pseudocode might look more like this:

# n = number_of_people

def cater_party (n)

   # cook all the food
   # drive to the venue
   # set up 

   n.each do |person_at_party|
      # plate some chicken
      # plate some side dishes
      # do it again for desert
      # get them a drink
      # etc
      return full_meal
   end
end

Shouldn't we take those things into account?

First, remember that we're talking about big-o, and big-o only describes how the complexity grows as the input size increases.

Does the number of people affect how much set-up we have to do? Not really.

Does it affect our drinks? No, we'll just put out a dispenser.

Is doing 2 plates per person affected by the number of people? This one is tricky, and you may be tempted to say yes, but really think about it. Yes, creating a full course for each person is twice as hard, but we still expect the same increase in work per person. If you consider both dinner and dessert as one "meal", then we're right back to a 1 to 1 increase.

All these extra things are constants. Since they stay the same relative to our input size, we can mostly ignore them when determining the basic big-o complexity for a given algorithm.
Sure, you can add them in to be more precise, but just know that as "n" gets bigger, the effect of constants shrinks.

More about O(n)

I mentioned in the beginning that O(n) is also called linear time. That's because if you plot O(n) on a graph with number of items (n) on one axis, and number of operations (O) on another, you'll get a straight line like below:

Next Time

O(n) is a the baseline when it comes to complexity (overall, not just tin coding). It's probably the most intuitive, and one of the easiest big-o functions to understand.

Next time, we'll look at the notation for the least complex algorithms.

BIG-O for BIGinners

Eben Eleazer — Sat, 11 Jun 2022 19:01:14 +0000

Just like Sunrise in the 90s, I've decided to do a series on "Big O" (if you don't get that reference, look it up; decent show)

Part 1: Overview

Diving into algorithms and data structures, you most likely will have seen Big O notation, or at least seen some references to it.

But, what does it mean? How can it be calculated? And what is it useful for?

In this series, I will try to break down Big O notation in a way that is easy to understand and allows you to feel confident when dealing with Big O notation in the future.

So, let's get into Part 1:

What is Big-O notation?

Before we get started with what Big O is and what is does, I think that I should take a second to clear up a common misconception.

Big-O does not describe how much time (or space) an algorithm takes to run

If you think about it, there's really no way to actually know how long an algorithm or function is going to take to evaluate beforehand. System specs, programming language used, details about the input, all of these things will affect our function at runtime.

For example, Going through a sorted data structure using Linear search (checking every element) is usually less efficient than a binary search (targeting the center and dividing the search space in half).

But, what if the element we're searching for is the leading element?

In that case, the linear search will finish almost immediately while the binary search will go through the maximum number of iterations.

So, Big-O notation will not give an absolute description of the complexity, but rather describes the worst case scenario.

(if you're interested look up Big Theta and Big Omega, for average and best case scenario noatation)

What is Big-O, though

Big O notation, in the simplest terms I can think of, is a mathematical function that describes how algorithm complexity grows as the number of elements increases and in the worst case scenario

I already explained the worst case scenario part, but the "as the number of elements increase" part is key.

If you look at the chart, you'll see different ways that the number of operations(complexity) increases as a function of the number of items (size). We'll go into each of the different functions shown later.

"n"

Even though it's called "Big O" notation, the key to understanding it lies in the n variable.

The "n" variable represents the size of the input, usually the number of elements that the algorithm has to work on. This is the main variable we will be looking at.

Next Time

That's a basic overview of big-O notation, what it means and how to read it. This will be a series, so the next article will tackle how to figure out big-O for your own algorithms.

If you have any comments, questions or corrections, Feel free to leave a comment!

See you next time...

Testing, 1, 2 : Basic Testing in Rails

Eben Eleazer — Sat, 04 Jun 2022 23:28:07 +0000

When creating a new Rails app or API using rails new, we get a lot of files and directories set up for us. Until now, I'd been avoiding one folder in particular.

Test

It's time to tackle (1) why you would write tests and (2) how to write basic tests in Ruby on Rails.

See, it wasn't just a joke

1. Why Write Tests

You may be thinking, "why would I write a test, when I already know how to pass it", or something like that. Especially for personal projects or when you're the only person working on a particular codebase, writing tests may seem tedious or unnecessary.

But, I'm going to give you a few reasons why Test Driven Development can be helpful, even for personal projects.

Helps Application Design

By writing tests first it forces you to think of the outcome of your code. You decide what is expected, then you write code to achieve it. No matter if the test is behavior driven or directly checks for a specific return value, the fact that you are forced to make these decisions beforehand, can keep you from developing unnecessary code.

Makes Refactoring Painless

When you have tests, you can refactor your code without worrying (too much) about unaffected side effects. Since you wrote tests for all the important functionality, then as long as the tests still pass you should be good.

2. How to Write Tests

Okay, so now that you've decided it's worthwhile, let's write some tests!

The Test folder

In the root of your Rails app (generated with rails new) a "test" folder will be created. When you inspect this folder you'll see a similar set of subfolders to our "app" folder.

There are a couple key differences between the test and app directories, but for the most part our test files, and thier paths within the "test" folder will correspond directly with thier counterparts in our "app" folder.

More concisely, the file at "/test/models/model_test.rb" will contain the test for "/app/models/model.rb"

In fact, when you use rails generators or rails g [model or whatever], a test class will also be generated and placed in the corresponding test folder.

Test Syntax

A test contains at least one assertation. An assertation evaluates an object or expression for expected results. There are quite a few different assertations you can use, depending on what you are trying to test, and a full list is available here.

Here is the most basic test case:

test "the truth" do
  assert true
end

Which is technically the same as this:

def test_the_truth
  assert true
end

But it doesn't look as cool (plus the first syntax makes it clear it is a testing method), so don't use the second version.

Here is an example of a test for a model validation on email address

 test 'does not accept bad email addresses' do
    user = User.new(email: "not an email address", password_digest: 'password')
    user_2 = User.new(email: "notanemailaddress", password_digest: 'password')
    user_3 = User.new(email: "anemail@addr.ess", password_digest: 'password')

    assert_not user.save, "email should not allow spaces"
    assert_not user_2.save, "email should have an @ and a ."
    assert user_3.save
  end

Notice that a single test can contain multiple assertations. The test will not pass until all assertations are successful.

More about tests

What I've talked about are the basics of testing. I may do a future piece on different types of test (Model, System, Integreation, Functional) but for now, I hope I've given a general overview of testing in rails