Chapter 9. Choosing the Perfect Algorithm

In this chapter, we are going to describe some problems/applications that exist nowadays and how to solve them with algorithms and data structures. We have been preparing ourselves during the last eight chapters, learning the basic and advanced concepts of data structures and algorithms and their corresponding implementations in Swift. Now we are going to describe scenarios that exist in the real world and we are going to solve them by applying the concepts that we have learned throughout this book.

Have you ever attached a URL link in any social network status with a limited count of characters? Have you ever noticed how some Internet applications change long and redundant URLs to tiny, shorter ones? They do it in order to save space and memory, but with an additional benefit for the user, that is, to save you some characters and to allow you to write more content. This is one of the example scenarios that we are going to explain in this chapter...

URL shortener

The first task we are going to address is to build a URL shortener library. But before anything else...what is a URL shortener, and how does it work?

Problems with long URL

A URL is a unique address that identifies a webpage (or domain) on the Internet (the pretty and readable version of an IP Address). URLs such as www.google.com or www.apple.com seem to be easy, short, and straightforward to remember and use. However, the Internet today is full of content (more than we can even imagine) and each webpage needs its own unique URL. Moreover, we apply some organization to make URLs more structured and easy to use with the use of slashes, /, the slugs from blog posts, the date included in the URL, and so on. All of this information makes URLs longer, so it is not complicated to find URLs such as www.domain.com/category/subcategory/year/month/day/long-blog-post-slug-or-title.

And this is the most common pattern for blog sites, for example, which are one of the most shared content...

Searching in a huge amount of data

In this section, we are going to develop a new feature for our URL shortener. This feature will need to search for data in a huge table, which, as you can guess, could delay the response of the system. Let's see the feature we are going to add and the solutions that we are going to implement.

The huge blacklist problem

Now, imagine that our URL shortener is very successful. We want to offer a premium service for our users, We will have a new feature, when a user clicks one of our short URLs http://shor.ty/4324, we guarantee that the final website http://www.blog.com/category/page/1 is safe for the user.

In order to achieve a secure service like this, we are going to call a web service from an Internet provider that has over 1 million blacklisted URLs in a table. So when we transform a short URL into the original one, we can check the blacklist table to see if the URL is secure or not and act upon it. The process is described in the following figure:

Method...

Summary

In this chapter, we have learned how to deal with problems that require algorithms and data structures by:

1. Creating a high-level approach of the solution.

2. Writing and describing the Swift implementation.

3. Calculating Big-O complexities of our solution to check if the algorithm behaves properly for a real-world situation.

4. Measuring and detecting bottlenecks.

5. Modifying them to achieve a better performance with an alternative solution.

Moreover, and in order to learn this, we have seen what a Bloom filter is and how to display graphs in the playground to analyze results more easily.

We have created two solutions for two problems, and after a Big-O analysis and with the help of algorithms and data structures, we have improved our solutions a lot and we have made our code more efficient. That was the goal of this chapter, and of the entire book itself. Congratulations!

Epilogue

After nine chapters, you have learned about Swift, data structures, and algorithms. Now it is time for you to put all these concepts in practice in real-world scenarios. When facing a complex task, remember the cons and benefits of the different data structures, take into account the time and space complexity of each algorithm, and measure your first solution in order to improve it as needed. You have learned the basic concepts to start making great solutions to complex problems with the help of data structures and algorithms in Swift. Now it's your turn!