Book Image

Swift Data Structure and Algorithms

By : Mario Eguiluz Alebicto
Book Image

Swift Data Structure and Algorithms

By: Mario Eguiluz Alebicto

Overview of this book

Apple’s Swift language has expressive features that are familiar to those working with modern functional languages, but also provides backward support for Objective-C and Apple’s legacy frameworks. These features are attracting many new developers to start creating applications for OS X and iOS using Swift. Designing an application to scale while processing large amounts of data or provide fast and efficient searching can be complex, especially running on mobile devices with limited memory and bandwidth. Learning about best practices and knowing how to select the best data structure and algorithm in Swift is crucial to the success of your application and will help ensure your application is a success. That’s what this book will teach you. Starting at the beginning, this book will cover the basic data structures and Swift types, and introduce asymptotic analysis. You’ll learn about the standard library collections and bridging between Swift and Objective-C collections. You will see how to implement advanced data structures, sort algorithms, work with trees, advanced searching methods, use graphs, and performance and algorithm efficiency. You’ll also see how to choose the perfect algorithm for your problem.
Table of Contents (15 chapters)
Swift Data Structure and Algorithms
Credits
About the Authors
About the Reviewers
www.PacktPub.com
Preface

Overview of data structures


The following is a table providing an overview of some of the most common and advanced data structures, along with their advantages and disadvantages:

Table 1.2 – Overview of Data Structures

Data Structure

Advantages

Disadvantages

Array

Very fast access to elements if index is known, fast insertion of new elements.

Fixed size, slow deletion, slow search.

Sorted array

Quicker search over non-sorted arrays.

Fixed size, slow insertion, slow deletion.

Queue

Provides FIFO (First In, First Out) access.

Slow access to other elements.

Stack

Provides LIFO (Last In, First Out).

Slow access to other elements.

List

Quick inserts and deletes.

Slow search.

Hash table

Very fast access if key is known, quick inserts.

Slow access if key is unknown, slow deletes, inefficient memory usage.

Heap

Very fast inserts and deletes, fast access to largest or smallest item.

Slow access to other items.

Trie (pronounced Try)

Very fast access, no collisions of different keys, very fast inserts and deletes. Useful for storing a dictionary of strings or doing prefix searches.

Can be slower than hash tables in some cases.

Binary tree

Very fast inserts, deletes, and searching (for balanced trees).

Deletion algorithm can be complex, tree shape depends on the order of inserts and can become degraded.

Red-black tree

Very fast inserts, deletes, and searching, tree always remains balanced.

Complex to implement because of all the operation edge conditions.

R-tree

Good for representing spatial data, can support more than two dimensions.

Does not guarantee good worst-case performance historically.

Graph

Models real-world situations.

Some algorithms are slow and complex.

Overview of algorithms

In studying algorithms, we often concern ourselves with ensuring their stingy use of resources. The time and space needed to solve a problem are the two most common resources we consider.

 

"Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output."

 
 --Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms 3rd Edition (2009)

Specifically, we're interested in the asymptotic behavior of functions describing resource use in terms of some measure of problem size. We'll take a closer look at asymptotic behavior later in this chapter. This behavior is often used as a basis for comparison between methods, where we prefer methods whose resource use grows slowly as a function of the problem size. This means we should be able to solve larger problems quicker.

The algorithms we'll discuss in this book apply directly to specific data structures. For most data structures, we'll need to know how to:

  • Insert new data items

  • Delete data items

  • Find a specific data item(s)

  • Iterate over all data items

  • Perform sorting on data items