w2d4
When learning how to code, we get to spend a lot of time coming up with our own solutions to different puzzles. But there’s more to coding well than merely finding solutions. Learning new syntax is a great way to get more tools for solving different problems, but it’s always exciting to learn certain broader lessons about how to be a better programmer. Today we learned about algorithms and Big O notation, which was like opening a whole new toolbox. Here are some of the things we’ve learned so far about bringing our code to the next level:
Clean Code
When you write code that’s easy to read, it’s not just easier for other programmers to work with, it’s also less confusing, leading to fewer bugs, and easier to modify. Associated chunks of code with unabbreviated descriptive words (referred to as idiomatic code) makes it clear what your code does, and lets you avoid repeating yourself (referred to as DRY or Don’t Repeat Yourself). Breaking code up into small Classes and smaller methods helps your code be readable, clear, and modular.
Class Structure
Writing classes well is sort of an extension of clean code. Using a few principles about how to organize your classes, you can write code that’s easier to read, easier to understand, and easier to read. One of these principles is called “tell don’t ask,” though I think this should be called “ask don’t take”. What the principle is about is instead of grabbing information from another class of object, you should always use one of that class’s methods (and write a method for it, if you need the information).
A related principle is polymorphism, which is the idea that if your program is likely to attempt to ask two different objects the same question (call the same method on them) that method should be defined for both objects to avoid getting an error that crashes your program. For example, if you ask a blank space in Chess “what is your color?” it should respond with “I have no color,” instead of “ERRORKILLPROGRAMDIE.’
Another principle is encapsulation. This is the idea that you should limit each object to containing a minimum amount of information, and have your objects work in tandem to accomplish tasks. This is closely related to avoiding the use of god objects.
Algorithms and Big O Notation
This brings me to what I learned about today! Algorithms and Big O notation. There are usually many ways of solving the same problem, but some algorithms take longer than others. When your code uses your input, different algorithms scale in time at different rates compared to your input. For example, if you have a loop inside a loop and each of them looks at each item you fed the code, your code runs in O(n^2) time. Considering that computers have to handle more and more data going forward, that’s really bad.
If you could find a way to accomplish the same thing without the second loop you could get your program down to O(n) time. If you can split your code up in half each time you iterate through it, you can get yourself down to O(log n) time, which is very nearly as fast as you can get. The ultimate though is O(1) time, which means that your program takes the same amount of time, no matter how much or how big your input is. For example, adding a word to the end of a dictionary would only take O(1) time, no matter how long your dictionary is. But, if you wanted to put it in the right place in the alphabet, that would take O(log n) time if you use an algorithm that searches for where it goes by checking the center item of the dictionary recursively.
Several of the problems we’ve had so far, we learned how to do using much faster algorithms today. I’ll give you an example:
Two Sum
Given a list of numbers, find if any two of them add to a given target.
def bad_two_sum?(array, target) array.each_index do |i| array.each_index do |j| if j > i return true if array[i] + array[j] == target_sum end end end false end
This one takes O(n^2) time. In other words, the time it takes is a function of a square of the size of the array you give it.
def good_two_sum?(array, target_sum) complements = {} array.each do |x| return true if complements[target_sum - x] complements[x] = true end false end
This version takes O(n) time, so the time it takes is a function of the size of the array you give it.
Here’s another one:
Largest Contiguous Sum
Find the largest contiguous sum in a given array.
def largest_contiguous_subsum1(array) subs = [] array.each_index do |idx1| (idx1..array.length - 1).each do |idx2| subs << array[idx1..idx2] end end subs.map { |sub| sub.inject(:+) }.max end
This takes O(n^3) time because not only do I have two loops, but I also loop through again to create a new array to add to subs.
def largest_contiguous_subsum2(array) largest = 0 current = 0 array.each do |el| current += el largest = current if current > largest current = 0 if current < 0 end largest end
This takes O(n) time. I love this solution because not only is it faster, it’s easier to read, and it doesn’t use any tricky objects like hashes, which can be harder for beginners to understand than arrays.
One of my favorite blog posts from AppAcadmey. I love the humble solution to largest contiguous subsum and it’s superior time complexity.













