Swift Data Structure and Algorithms

图书信息

作者	Erik Azar
出版社	Packt Publishing
ISBN	9781785884658
出版时间	2016-11-01
字数	197.9万
分类	进口书,外文原版书,电脑,网络

读书简介

Master the most common algorithms and data structures, and learn how to implement them efficiently using the most up-to-date features of Swift 3 About This Book Develop a deep understanding of the collections in the Swift Standard Library with this step-by-step guide Develop native Swift data structures and algorithms for use in mobile, desktop, and server-based applications Learn about performance efficiency between different data structures and algorithms Who This Book Is For This book is for developers who want to learn how to implement and use common data structures and algorithms natively in Swift. Whether you are a self-taught developer without a formal technical background or you have a degree in Computer Science, this book will provide with the knowledge you need to develop advanced data structures and algorithms in Swift using the latest language features. What You Will Learn Get to know about the basic data structures and how to use the Swift REPL Use the Swift Standard Library collections bridging to Objective-C collections, and find out about protocol-oriented programming Find out about Swift generators and sequences, and see how to use them to implement advanced data structures such as Stack, StackList, Queue, and LinkedList Implement sorting algorithms such as Insertion Sort, Merge Sort, and Quick Sort and understand the performance trade-offs between them See how to implement various binary trees, B-Tree, and Splay Trees Perform advanced searching methods using Red-Black trees, AVL trees, and Trie trees, and take a look at several substring search algorithms Get to know about the data structures used in graphs and how to implement graphs such as depth-first search, breadth-first search, directed graphs, spanning tree, and shortest path Explore algorithm efficiency and see how to measure it In Detail 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. Style and approach This easy-to-follow yet comprehensive guide can either be read from beginning to end, or depending on your current knowledge level, you can jump to the specific chapter that interests you. Each chapter topic starts with an introduction to the topic and algorithm before moving on to the hands-on implementation and analysis.

目录

Swift Data Structure and Algorithms

Swift Data Structure and Algorithms

Credits

About the Authors

About the Reviewers

www.PacktPub.com

Why subscribe?

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Downloading the example code

Downloading the color images of this book

Errata

Piracy

Questions

1. Walking Across the Playground

What is the importance of data structures?

Data structures + algorithms = programs

Interactive Playgrounds

The Swift REPL

Fundamental data structures

Contiguous data structures

Arrays

Declaring an array

Retrieving elements

Adding elements

Removing elements

Linked data structures

Singly linked list

Overview of data structures

Overview of algorithms

Data types in Swift

Value types and reference types

Named and compound types

Type aliases

Collection types in the Swift standard library

Asymptotic analysis

Order of growth

Summary

2. Working with Commonly Used Data Structures

Using the Swift standard library

Why structures?

Declaring arrays in Swift

Initializing array

Adding and updating elements in an array

Retrieving and removing elements from an array

Retrieving and initializing dictionaries

Initializing a dictionary

Adding/modifying/removing a key-value pair

Retrieving values from a dictionary

Declaring sets

Initializing a set

Modifying and retrieving elements of a set

Set operations

Comparison operations

Membership and equality operations

Characteristics of tuples

Unnamed tuples

Named tuples

Implementing subscripting

Subscript syntax

Subscript options

Understanding mutability and immutability

Mutability of collections

Interoperability between Swift and Objective-C

Initialization

Swift type compatibility

Bridging collection classes

NSArray to Array

NSSet to set

NSDictionary to dictionary

Swift protocol-oriented programming

Dispatching

Protocol syntax

Protocols as types

Protocol extensions

Examining protocols for use in collections

Array literal syntax

Making an array enumerable

Sequence/IteratorProtocol

Summary

3. Standing on the Shoulders of Giants

Iterators, sequences, and collections

Iterators

Sequences

Collections

Stack

Applications

Implementation

Protocols

Queue

Applications

Implementation

Protocols

Circular buffer

Applications

Implementation

Protocols

Priority queue

Applications

Implementation

Protocols

StackList

Applications

Implementation

Protocols

Summary

4. Sorting Algorithms

The insertion sort

The algorithm

Analysis of the insertion sort

Use cases of the insertion sort

Optimizations

Merge sort

The algorithm for array-based merge sort

Analysis of merge sort

The algorithm and analysis for linked list-based merge sort

Performance comparison

Quick sort

The algorithm – Lomuto's implementation

Analysis of Lomuto's partitioning scheme

The algorithm – Hoare's implementation

Analysis of Hoare's partitioning scheme

Choice of pivot

The wrong way – first or last element

The wrong way – select random element

The right way

Improved pivot selection for quick sort algorithm

Optimizations

Summary

5. Seeing the Forest through the Tree

Tree – definition and properties

Overview of different types of tree

Binary tree

Binary search tree

B-tree

Splay tree

Red-black tree

Binary trees

Types and variations

Code

Binary search trees

Inserting a node

Tree walks (traversals)

Inorder tree walk

Preorder tree walk

Postorder tree walk

Searching

Deletion

B-trees,

Splay trees

Splay operation

Simple rotation or zig

Zig-Zig or Zag-Zag

Zig-Zag

Summary

6. Advanced Searching Methods

Red-black trees

Red-black tree node implementation

Rotations

Right rotation

Left rotation

Insertion

AVL trees

AVL tree node implementation

AVL tree rotations

Simple rotation left

Simple rotation right

Double rotation – right-left

Double rotation – left-right

Search

Insertion

Trie tree

Radix tree

A look at several substring search algorithms

Substring search algorithm examples

Naive (brute force) algorithm

The Rabin-Karp algorithm

Summary

7. Graph Algorithms

Graph theory

Types of graphs

Undirected graph

Directed graph

Weighted graph

Graph representations

Object-oriented approach – structs/classes

Adjacency list

Adjacency matrix

Incidence matrix

Data structures

Vertex

Edge

Adjacency list

Depth first search

Breadth first search

Spanning tree

Minimum spanning tree

Prim algorithm

Shortest path

Dijkstra algorithm

SwiftGraph

Summary

8. Performance and Algorithm Efficiency

Algorithm efficiency

Best, worst, and average cases

Measuring efficiency and the Big-O notation

Asymptotic analysis

How to calculate complexities

Orders of common functions

O(1)

O(log(n))

O(n)

O(nlog(n))

O(n^2)

O(2^n)

Graphic comparison

Evaluating runtime complexity

Summary

9. Choosing the Perfect Algorithm

URL shortener

Problems with long URL

URL shortener solution approach

URL shortener Swift implementation

Method 1 - searching for the correct tuple

Method 2 – accessing the correct array position by index

Searching in a huge amount of data

The huge blacklist problem

The huge blacklist solution approach

The huge blacklist Swift implementation

Method 2 – the Bloom filter solution

Summary

Epilogue