A few weeks ago I finished reading “Automate the boring stuff with Python” from Al Sweigart, In this review, I’ll try to make a good review of the book and talk about the main chapters.
It’s a book recommended for novices, for me, it’s a good book for beginners, but for people who already know how to program in other dynamic and interpreted programming language, I think is not necessary to read this book, go ahead and read something more advanced.
TL;DR: If you know how to program in another interpreted programming language like Ruby, go ahead and read something more advanced, if you are a beginner, start with this book, it’s a very good book to start coding.
And much more, I think every experienced programmer knows nostarch very well because they have a lot of famous and good books, if you are a beginner, you can trust them.
I didn’t have the physical edition of this book, I’ve read the digital edition on my Kindle Paperwhite, read technical books on digital readers is always it’s always a fear because some books don’t look good at the small screens, especially the code snippets, but this was not the problem of this book, I think large publishers like nostarch or O’Reilly you’ll never going to have this problem.
The physical edition I think should be excellent too, because I have other books from nostarch and no one disappointed me.
Content
The book is divided into two parts, the first one talks about all the basic things of any programming language like variables, loops, ifs/else and etc. This part is good to understand the basic of python. This part covers all between variables and manipulates text.
The second part and the most interesting show you how to automate boring stuff with python in a simple way, at this part you develop a lot of applications, for example reading Excel documents. This part has eleven chapters, talking about a lot of things, this is the best part of my opinion, the author shows you how to do a lot of cool things like web scraping 🙂
Final Conclusions
The most interesting is the second part when you create a lot of applications to automate the boring stuff, but the first part is good to understand and knows the python basic. One thing that I loved in this book is the fact that it has a lot of exercises (with answers) to you train what you learned in the chapter, if you do all the exercises your read will be funnier and you’ll learn much more.
The only bad thing on this book is that this is a simple book for people that already know how to program, but this is not a problem because the book doesn’t say that is something advanced, but even for who already knows how to program, the second part with practical projects can be very good.
Final thoughts
This is my first book review and I’ll try to get better on the next review posts, I’ll try to review every technical book that I read.
Some weeks ago I was reading Pat Shaughnessy, Ruby Under a Microscope that is an excellent book about all the engineering behinds Ruby language, and when reading, sometimes I was feeling lost with myself when reading some C codes from Ruby implementation then I decided to stop reading the book and start a little review about C programming language because the last time that I wrote some C code that wasn’t on Arduino was ~3 years ago at my university. When I was at my first university, I clearly remember how some students feel lost and some students feel delighted with the theory and concept of pointers, and for me, it was fascinating.
In this post, I’ll try to explain in a simple and practical way all the theory behind C pointers, for on the next posts I write about topics like Static and Dynamic memory allocation and function pointers.
It’s easy to create programs impossible to read and alter if you don’t give the appropriate attention to the pointers that you’re creating.
This post talks about
What are pointers
How to use pointers
Strings and Arrays
Pass by reference and pass by value
The computer memory
To understand pointers correctly, first, we need to understand from a top-level view of how the computer memory works.
The computer memory is like an array, is a block of consecutively memory cells order by their addresses, that memory can be manipulated alone or in groups.
When you create an integer for example:
int counter = 0;
The C Lang picks 4 consecutive memory cells (bytes) from the memory and stores the value that you assigned to the variable.
And remember each memory cells that you requested to store your integer have a memory address that can be referenced by hexadecimal.
This address will vary on each execution of the program.
To see this address of a variable in C we can use the ampersand operator:
int counter = 0;
printf("Variable Address: %p\n", &counter);
Variable Address: 0x7ffeccd5f0d4
The %p is the correct specifier to an output the memory address.
Another good experiment to do is to create two variables and see the address of each one:
int counter = 0;
int age = 0;
printf("Variable Address: %p\n", &counter);
printf("Variable Address: %p\n", &age);
Pay attention to how C allocates the variable age exactly 4 bytes after the first one, this is because the integer needs 4 bytes to be stored.
The memory address is very interesting and it would be good that we can store it at variables and make nice operations this, and that’s is what pointers consist.
Pointers
Follow my blog to get notified every new post:
Pointers in computer science is an object (usually a variable) that stores the memory address of another value. In C you can declare a pointer using an asterisk before the name of the variable and store an address of a variable of the same type of the pointer.
int counter = 0;
int *pointerCounter = &counter;
Note: Pointers always point to a specific data type, we have one exception on type void.
In C we can see the value stored at the address of pointed memory too, for this, use the asterisk before the name of the pointer:
printf("Pointer value of the pointed memory: %i\n", *pointerCounter);
When a pointer is pointing to a value, the pointer only stores the address of the first byte of this value, when asked, C uses the data type of the pointer to walk over the next `n` bytes to see the full pointed value.
For example, if we’re pointing to an integer and the first byte of this integer is located on 0x7ffe3bc5e164 (see the previus image), the pointer will only store the 0x7ffe3bc5e164 and when asked for the vallue will know to walk +4 right because integer is a datatype of 4 bytes.
To understand better, is nice to examine and run the fallowing example:
int counter = 10;
int *pointerCounter = &counter;
printf("Variable counter address: %p\n", &counter);
printf("Pointer value: %p\n", pointerCounter);
printf("Pointer address: %p\n", &pointerCounter);
printf("Pointer vale of the pointed memory: %i\n", *pointerCounter);
Variable counter address: 0x7ffe19cd26fc
Pointer value: 0x7ffe19cd26fc
Pointer address: 0x7ffe19cd2700
Pointer vale of the pointed memory: 10
It is nice to note that the address of a counter variable is exactly the value pointed by the pointer.
You can do arithmetic and logic operations with pointers too, on this example I sum 10 to the value pointed by pointerCounter.
int counter = 10;
int *pointerCounter = &counter;
*pointerCounter = *pointerCounter + 10;
printf("Pointer vale of the pointed memory: %i\n", *pointerCounter);
printf("Pointer vale of the pointed memory: %i\n", counter);
Pointer vale of the pointed memory: 20
Pointer vale of the pointed memory: 20
“Ok, this is so cool but what can I do with that? I’m only storing the address of some value into one kind of variable.”
With pointers we can do a lot of things, one of the main things is pass values by reference to functions.
Pass by reference and pass by value
When you pass a something to a function in C and make changes to it, that changes won’t exist outside of that function scope, what its means?
void sum(int counter, int age) {
counter = counter + age;
printf("counter value: %i\n", counter);
}
int main() {
int counter = 10;
int age = 5;
sum(counter, age);
printf("response value: %i\n", counter);
}
counter value: 15
response value: 10
On this example, we send the counter variable to the void function sum that stores at counter the sum of counter and age, after this, we print the value of counter inside the function an we see the value 15 printed, but on the printf outside the function at main, we got 10, why? This is what we call pass by value and C passes arguments to function by value, almost all languages pass by value (Java, C#, Ruby, Python), and there isn’t a direct way for the called function to alter a variable in the calling function.
But in C we can do what we call pass by reference, we call the function passing variable address and receiving as a pointer, doing this you’re saying to function “Hey, that’s the value memory address, pick this and alter as you want”.
void sum(int *counter, int age) {
*counter = *counter + age;
printf("counter value: %i\n", *counter);
}
int main() {
int counter = 10;
int age = 5;
sum(&counter, age);
printf("response value: %i\n", counter);
}
If you run this code you’ll realize that on the last printf the counter is 15, that’s why we’ve passed the counter address to sum function, and at the function, we do the operation directly on the counter address on memory. This is what we call pass by reference, we aren’t passing the value to function but it’s a reference at the memory.
What’s next?
On this post we talked about all the basics behind pointers in C, it’s not a simple topic and if you don’t understand keep trying and run the examples of this post on your own machine, you can also read the sections 5.1 and 5.2 of the legendary K&R C Programming Language that’s, in my opinion, is the best book of ANSI C.
On next three posts I’ll talk more about pointers, I will write about pointers in arrays and strings, dynamic and static memory allocation and function pointers.
Feel free to ask any questions at my twitter, email or comment on this post.
Tell, don’t ask is a useful key concept when talking about object-oriented programming, it consists in to send messages to object (whenever possible) telling objects what you want and that we shouldn’t ask questions to it about its state and make decisions for him, it bypasses encapsulation.
In a more abstract mindset, every object needs to trust that other objects can make decisions alone, without his help.
In a more abstract mindset, every object needs to trust that other objects can make decisions alone, without his help.
If you’re treating objects like structs you’re wrong, the key difference between they is that structs stores only data and was made to represent a record, and this is one of the key difference betwween procedural and object oriented code, objects have behavior.
Defining a simple People struct in C lang and asking for its name if not empty:
struct People {
int age;
int weight;
char name[50];
};
struct People ronald = { name: "", age: 42, weight: 140};
if (strcmp(ronald.name, "") != 0) {
printf("Person Name: %s\n", ronald.name);
}
This C code in Ruby will look something like this in Ruby:
class People
attr_reader :name
def initialize(age:, weight:, name:)
@age = age
@weight = weight
@name = name
end
end
people = People.new(age: 45, weight: 140, name: "Ronald")
puts "People name: #{people.name}" unless people.name.empty?
The error is treating only like a record, objects have behavior too.
class People
def initialize(age:, weight:, name:)
@age = age
@weight = weight
@name = name
end
def name
"People name: #{@name}" unless @name.empty?
end
end
people = People.new(age: 42, weight: 140, name: "Ronald")
puts people.name
Ok… This is just a mediocre example, we only extracted a simple logic, but it was good to see the difference between structs (only data) and objects (behavior/state).
Another Example
Related Posts
Ok, let’s go to another example more real, let’s imagine a simple system that has Books and Stock and we want to store books at stock and print every book of stock:
class Book
attr_reader :name, :author, :year
def initialize(name, author, year)
@name = name
@author = author
@year = year
end
end
class Stock
attr_reader :capacity, :maximum_capacity
attr_accessor :books
def initialize(books: [], capacity: 0, maximum_capacity: 10)
@books = books
@capacity = capacity
@maximum_capacity = maximum_capacity
end
end
def add_books(book, stock)
if stock.capacity < stock.maximum_capacity
stock.books << book
end
end
def print_books(stock)
stock.books.each do |book|
puts "Name: #{book.name}, Author: #{book.author}"
end
end
book1 = Book.new("Practical Object-Oriented Design in Ruby","Sandi Metz","2012")
book2 = Book.new("Ruby Under a Microscope","Pat Shaughnessy","2013")
stock = Stock.new
add_books(book1, stock)
add_books(book2, stock)
print_books(stock)
This code works good but what’s the problem? This code is so procedural, let’s refactor to become more OOP.
Starting from add_books, it’s asking a lot of information about object(stock) state for making decisions, this is wrong and the logic or add books to stock and check about stock capacity needs to belong to a stock object, with Tell don’t ask thinking this logic would be written like this:
class Stock
attr_reader :quantity, :maximum_quantity
attr_accessor :books
def initialize(books: [], quantity: 0, maximum_quantity: 10)
@books = books
@quantity = quantity
@maximum_quantity = maximum_quantity
end
def <<(book)
books << book unless crowded
end
def crowded
quantity == maximum_quantity
end
end
Now if we need to one book to stock we just need to write:
stock << book1
We don’t need to ask questions about state and then add, all this logic is encapsulated at an object, much better right?
print_books need to be refactored too, let’s make this logic more OOP, first of all, we can create a method at Stock to print all books and their information.
class Stock
...
def print_books
books.each do |book|
puts "Name: #{book.name}, Author: #{book.author}"
end
end
end
class Book
...
def full_description
"Name: #{name}, Author: #{author}, Year: #{year}"
end
end
Now we refactor again our print_books for just call full_description on each book.
class Stock
...
def print_books
books.each do |book|
puts book.full_description
end
end
end
Much better our code now, right? If you got lost you can check full code here, or ask me on twitter/email.
Comparing two codes
On the first version of the code, objects was asking for state like this image:
Now our objects are telling what want:
Luckily on internet we’ve hundreds of examples in many languages, you should search for it after read this post.
“The distinction between a message that asks for what the sender wants and a message that tells the receiver how to behave may seem subtle but the consequences are significant. Understanding this difference is a key part of creating reusable classes with well-defined public interfaces”
Final thoughts
This isn’t easy get started thinking like this and correcting your errors, but you need to get used to not ask your object about his state and tell him what you want every that is possible, at the beginning will be hard to think like this (it’s have been difficult for me), but with time you’ll master this skill.
When you’re starting with ruby programming, a lot of people (and me too), usually have questions about the difference between ruby .map, .select, .collect, .each and many others enumerables.
Each
Each executes for each element the logic passed in block.
For example, if you want to print each element of one array using what we usually do in another languages with for loops, it will look like this:
places = ["restaurant", "mall", "park", "theater"]
for i in 0..places.size
puts places[i]
end
# => restaurant
# => mall
# => park
# => theater
Ok, this works but is not readable, it’s not a natural language, and in ruby, we love to prioritize it, with .each it will be much more lovely.
places.each do |place|
puts place
end
# => restaurant
# => mall
# => park
# => theater
Or if you want or are working on IRB you can use inline syntax.
Also Known As "Filter" in other languagens, select executes the passed expression for each element of array, if is true, it adds to the final response array, for example:
On this code we use select to return an array with all numbers greater than 3.
And for being a module, you can include it on your class and have access to this collection of powerful methods. But, how to include it? It’s not just add include Enumerable to your class, you need to create an each method in your class that yields every element of collection.
As described in ruby documentation: "The class must provide a method each, which yields successive members of the collection."
Let’s use a simple example to apply this, a class named OddNumbers.
The class have a each method that yields three odd numbers.
class OddNumbers
include Enumerable
def each
yield 1
yield 3
yield 5
end
end
After do that, you already can see all Enumerable methods in your class.
A lot of people when are starting with ruby programming think all these methods it’s all the same (and it’s normal!) but they aren’t, when you understand each one, not only each/select/map but a lot of others of Enumerable module, you have great power in your fingers, obviously nobody will memorize all methods of this module, but you can search on documentation when you need something that smeels like an Enumerable method.
Big O notation is a famous topic in computer science, but this topic still afraid of a lot of people. Some programmers don’t have a complete cs degree and never studied this, and those who have studied almost always didn’t understand very well.
In this text I will explain what really is Big O, and what you really need to know.
I’ll explain all the basics of Big O notation with examples written in Ruby.
This is not a complete guide of Big O notation if you want to know everything about, at the end of this post I give north of where to continue your study.
Introducing
This text is not recommended for:
People who have solid knowledge of Big O notation.
People who want to know advanced topics of Big O
What I’ll explain on this post:
What is Big O
The most common notations
Simple examples
Simple Benchmarks
First of all, what is Big O notation?
Big O notation is the language and metric we use when talking about growth rates and the efficiency of algorithms. It can be used to describe the behavior of an algorithm in terms of the growth in the number of operations as the number of elements processed increases, with this technique we can evaluate how our code will behave with a lot of data or operations.
If you want a long explanation you can read the big o article on Wikipediahere.
Why is it important? I’ll never use it.
A lot of methods or data structures of every programming language are described using Big O, like binary search that in Ruby can be called Array#bsearch.
First of all, if you always work with small sizes of data and operations, maybe you’ll never use it. But it’s good to understand the basic concepts of algorithms, because it can help you to make better design decisions and construct better algorithms.
Nowadays on the big data century, tons of data and operations are reality. You’ll probably need to design an algorithm thinking on his time or space complexity.
Nowadays on the big data century, tons of data and operations are reality. You’ll probably need to design an algorithm thinking on his time or space complexity.
It’s better to know because a lot of methods of your favorite programming language have different times, with Big O you can understand better the performance of each one.
And remember, a lot of big tech companies like Google, Facebook and Amazon asks for big o answers on their interview process, this is very common that is discussed on the legendary book Cracking the Code Interview.
Understanding
Visualizing the complexity
On Big O notation we have a lot of possibilities of notations, and we don’t have a fixed list of runtimes but the most common is:
Notation
Short Description
Denomination
O(1)
The best solution possible
Constant
O(log n)
Almost good, binary search is the most famous algorith O(log n)
Logarithmic
O(N)
When you walk through each data. "ok" solution
Linear
O(n log n)
Not bad solution. Most famous algorithm is Merge Sort.
nlogn
O(N^2)
Horrible, you can see the example bellow
Quadratic
O(2^n)
Horrible, most famous algorithm is quicksort
Exponential
O(N!)
The most horrible solution, factorial is when you test each possible solution
Factorial
Time or Space?
We can use Big O to describe both time or space, but what it means? Simple, one algorithm that uses O(N) runtime, will use O(N) space too, but it’s not that easy, some algorithms can be O(N) in time complexity but O(N^2) in space.
Time for What?
Data structures or algorithms can have multiple Big O times for multiple actions, for example An Array has O(1) time to access, but O(n) to search (depending on which algorithm you use), all depends on the scope of our code.
The Pragmatic Programmer is a legendary and timeless book, full of wisdom. This is not only a review, but a recommendation of a book.
Presenting our problem
On your life you never thought that some actions of your day spend a lot of time to be done, and you can make simple actions to reduce the time spent? Let’s use a simple example, dictionary(physical edittion, not google), how much time do you need to find a word? Depend of the way you search.
“The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use and 47,156 obsolete words. To this may be added around 9,500 derivative words included as subentries.”
This is a lot of data right? Let’s imagine that we’re building an algorithm to search for a word.
Code
For learning purpose on all examples I’ll use an array of numbers not strings.
Let’s create the array that I’ll use on all the next examples. This array will be our dictionary, but instead of words(strings), we’ll use numbers. The word “zoo”, will be the last word of our dictionary and will be represented as number 1000000. As you can see below:
dictionary = []
0.upto(1000000) do |number|
dictionary << number
end
Now, we have an array with one million numbers. Let’s assume that this array of numbers is our dictionary and the 1000000 on the last slot it’s our word “zoo”.
First Solution O(N)
Considering that this dicionary is in alphabetical order, how much time you’ll spend to find the word “zoo” (our 1000000) if you go through each word?
Yes, to find “zoo” you’ll spend a lot of time because you’ll need to go through all the words. These scenarios when we walk through each data, on Big O notation we call O(n), because our algorithm will take N times to find the word, where N is the number of words. Let’s see the code.
Code
Now let’s assume that we’re going though each word until we find the word.
def o_n(dictionary)
dictionary.each do |word|
word if word == 1000000
end
end
o_n(dictionary)
This is a very common and as I described previously, is not a bad solution, but not good to. In terms of difficulty to understand is not hard too, a lot of algorithm O(n) we have iterators on lists.
Second Solution O(1)
Let’s assume that now you already knows what is the location of word zoo on dictionary, every time that you need to search for it you only need to open the dictionary on the page and just read. You don’t need to find for the word, you already knows its location.
Code
O(1) is a algorithm that is idependent of the input size it will always take the same time to execute, the time is constant. The best example of it, it’s access an array:
def o_one(dictionary)
dictionary[1000000]
end
o_one(dictionary)
O(1) is always the best solution, and you probably use it every day, the most commond usage of it is with Hashes.
I think everybody here knows, but Ruby already have Hash implemented.
hash = {
color: "red"
}
hash[:color]
# => "red"
Third Solution O(log n)
Follow my blog to get notified every new post:
Some people have a lot of difficult to understand the concept of O(log N) algorithm, but I hope that this example with dictionary can help you undersand:
Let’s assume that you don’t know where the word is located, but you know that if you search each word O(N) will spend a lot of time, and you don’t know where the word is located, what will you do? You could start opening the dictionary on a random page and search if the words of this page come before or after the word that you’re looking for if is after you open on another page after this page, and look again… and repeat it until you find the word that you’re searching for.
If you already studied algorithms you probably noted that I described one of the most famous algorithms of all time, the binary search and that is the most famous example of O(log n) algorithm.
Let’s see the code.
Code
For this example, I’ll use a simple binary_search implementation (Not recursive).
def binary_search(dictionary, number)
length = dictionary.length - 1
low = 0
while low <= length
mid = (low + length) / 2
return dictionary[mid] if dictionary[mid] == number
if dictionary[mid] < number
low = mid + 1
else
length = mid - 1
end
end
"Number/Word not found"
end
puts binary_search(dictionary, 1000000)
To identify an algorithm that is O(log n) you can follow two simple steps:
The choice of the next element on which to perform some action is one of several possibilities, and only one will need to be chosen.
The elements on which the action is performed are digits of n
If you think that it’s not enough at you can find better references at the given links, I’ll not explain a lot of maths because it’s a text for beginners.
Fourth Solution O(N^2)
Imagine that you’re searching word by word like on O(N) but for some reason you need to make your search again, this is the O(N^2). This example applied to our history of the dictionary is hard to understand but with code is more easily.
The trick is basically to think that O(N^2) is when we pass through N, N times, so we’ll have N*N that is O(N^2), the most common example is a loop inside a loop.
Code
def o_n2(dictionary)
dictionary.each do |word|
dictionary.each do |word2|
word if word == 1000000
end
end
end
o_n2(dictionary)
Don’t worry, this is a very common case too, almost every person already hasdone something like that, especially when we’re starting to code that we use the famous quicksort that is a nice example of O(N^2), but this code won’t have a good performance for large data. The best way is think if you can reduce this algorithm to O(log n), some times an O(N^2) can be reduced to O(log n).
Fifth Solution O(n log n)
This is the most hard definition for me, and I admit that I spend hours searching on internet because the definitions that I’ve found didn’t satisfy me (And don’t have much answers on internet).
The simplest explanation that I’ve found is:
O(n log n) is basically you running N times an action that costs O(log n).
O(n log n) is basically you running N times an action that costs O(log n).
In the binary tree, inserting one node (in a balanced tree) is O(log n) time. Inserting a list of N elements into that tree will be O(n log n) time.
O(n log n) code can be often the result of an otimization of quadratic algorithm. The most famous example of this type is the merge sort algorithm.
For this definition won’t have short history, I definitely didn’t think in anything that makes sense on our history with dictionary.
If you think that this is not enough at references you find links to better understand, I’ll not explain a lot of maths because it’s a text for beginners.
Sixth Solution O(2^N)
Exponencial runtime, this is a very hard definition, like O(n log n). This type of problem is when the number of instructions growth exponentially, it’s common to found it on recursive algorithms, or some search algorithms.
"When you have a recursive function that makes multiple calls, the run time will be O(2^n)"
If you search on internet you’ll probably see a lot of people talking that Fibonacci recursive solution is a good example:
def fibonacci(number)
return number if number <= 1
fibonacci(number - 2) + fibonacci(number - 1)
end
puts fibonacci(10)
For find a O(2^N) you can start following one simple rules:
O(2^N) denotes an algorithm whose growth doubles with each additon to the input data set. (Exponential growth)
For this definition won’t have short history, too, sorry guys.
Seventh Solution O(N!)
The factorial solution, is very horrible. But I think there’s no example in our history of finding words in dictionary, and I don’t want to dive inside a lot of math in this beginners guide.
O(N!) is every time that you calculate all permutation of a given array of size N.
The most common example of this notation is that solving salesman problem via brute-force(testing every solution possible). (A lot of sites such as wikpedia uses this example).
Code
In Ruby we have a method that returns all permutations of a given array.
Let’s examine some benchmark of algorithms of each example and compare, for better understanding and understand that Big O really exists.
On this section I’ll use the same implementations of algorithms from previus chapter but using Ruby Benchmarking module to compare the execution times.
4.1 O(1) vs O(N)
For this example we’ll use the same dictionary array created on previus chapter with one million of data.
0.upto(1000000) do |number|
dictionary << number
end
So if we run the algorithms created in th above chapter:
Benchmark.bm { |bench| bench.report("o(1)") { o_one(dictionary) } }
Benchmark.bm { |bench| bench.report("o(n)") { o_n(dictionary) } }
# user system total real
# o(1) 0.000000 0.000000 0.000000 ( 0.000005)
# user system total real
# o(n) 0.060000 0.000000 0.060000 ( 0.052239)
A very low difference, and that’s is why O(N) on the graph of complexity is not very bad, with one million of data he just needed 0.052239s, but and if we growth your dataset to almost 15 million, the O(N) solution will be good? Let’s see:
# user system total real
# o(1) 0.000000 0.000000 0.000000 ( 0.000004)
# user system total real
# o(n) 0.750000 0.000000 0.750000 ( 0.741515)
The time of O(N) solution increased 12.5x more than the array of one million while the O(1) solution stay constant at ~0.000004s, and that’s is very wrong if we’re talking about scalable systems on the big data century.
O(N) vs O(N^2)
First of all, let’s create again an array but this time with lil bit less data:
data = []
0.upto(20000) do |number|
data << number
end
Yes, twenty thousand is good enought to this example, because O(N^2) is very bad, and if you growth you data, you’ll problaby get 100% cpu usage on Ruby process and it will be killed by OS.
Let’s examine the runtime of previus O(N) and O(N^2) algorithms of our dictionary example using benchmark module and the data array created:
Benchmark.bm { |bench| bench.report("o(n)") { o_n(data) } }
Benchmark.bm { |bench| bench.report("o(n^2)") { o_n2(data) } }
# user system total real
# o(n) 0.010000 0.000000 0.010000 ( 0.000963)
# user system total real
# o(n^2) 19.550000 0.000000 19.550000 ( 19.560149)
Obviusly that this number will vary
This difference is pretty high, and that is where Big O came. Remember, on Big O we’re talking about the "behavior of an algorithm in terms of the growth in the number of operations as the number of elements" as I talked on previus chapter.
Ok, twenty thousand of data is pretty high from some people, and if we try an array of five thousand, is it enought?
user system total real
o(n) 0.000000 0.000000 0.000000 ( 0.000252)
user system total real
o(n^2) 1.330000 0.000000 1.330000 ( 1.329480)
If you’re thinking: “The difference is so much smaller, I don’t need to optimize this code.”
You’re pretty wrong depending of your situation, because if we get the difference between an execution of each algorithm we have 1.329228s of difference, and it can be an eternity for your costumer if you consider that your client wait for 1.329228s three times each day, we’re stealing 27.9s per week of your costumer, and we’re only working with five thousands of data, I’m sure that a lot of people work with a lot of more.
So, in this case of an O(n^2) I pretty recomend that you try to reduce this for an O(n log n)
O(N!)
This is a nice test because if we use one million of numbers the algorithm will take more than 10 hours to execute on my machine, and if I use five thousand of data (like on the previous example) it will take a nice time too, so to show the O(N!) in action I’ll need to use only 500 numbers.
On this example I’ll use the Array#permutation, method of Ruby.
dictionary = []
0.upto(500) do |number|
dictionary << number
end
Benchmark.bm { |bench| bench.report("o(!n)") { dictionary.permutation(3).to_a } }
And the final output is weird:
# user system total real
# o(!n) 25.530000 1.650000 27.180000 ( 28.155015)
28.1s with 500 numbers.
Finishing
I’ll not benchmark all algorithms and data structures, but I pretty recommend that you study and test others one. Specially the O(log n)
What’s Next?
If you want to be a rockstar at *Big O* just keep studying, reading a lot.
This last books, have one chapter 100% dedicated to Big O notation, and I pretty recommend for those who wants to study more deep.
You can fallow the reference links bellow and study by yourself.
Final thoughts
It was a very long post, and I know it, but I think that a good understand of the big o principles is important for a lot of software engineers, to the daily work or for coding interviews.
If you have any question that I can help you, please ask! Send an email (otaviopvaladares@gmail.com), pm me on my Twitter or comment on this post!
.png)
.png)
O. Valadares' Blog 