224.srt

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:00:00.506 --> 00:00:09.566 A:middle
[ Silence ]

00:00:10.066 --> 00:00:10.996 A:middle
>> Good morning and welcome.

00:00:11.326 --> 00:00:12.336 A:middle
Thank you.

00:00:13.516 --> 00:00:15.546 A:middle
[ Applause ]

00:00:16.046 --> 00:00:16.456 A:middle
Thank you.

00:00:17.076 --> 00:00:19.666 A:middle
My name is Quinn Taylor, I'm an
Internal Applications Engineer

00:00:19.666 --> 00:00:21.586 A:middle
at Apple and I'm excited
to be talking today

00:00:21.586 --> 00:00:23.436 A:middle
about Designing Code
for Performance.

00:00:23.436 --> 00:00:26.016 A:middle
It's great to see such a
big crowd here, obviously,

00:00:26.016 --> 00:00:27.086 A:middle
you're all interested
in performance

00:00:27.086 --> 00:00:28.196 A:middle
as well and that's fantastic.

00:00:28.196 --> 00:00:30.636 A:middle
So, to start off, I want
to give you a little bit

00:00:30.636 --> 00:00:31.746 A:middle
of introduction, the motivation

00:00:31.746 --> 00:00:33.806 A:middle
for this talk, why
it came to be.

00:00:33.806 --> 00:00:37.926 A:middle
It's no secret that the raging
success of the App Store has led

00:00:37.926 --> 00:00:40.376 A:middle
to a huge influx of new
developers to the platform.

00:00:40.996 --> 00:00:42.306 A:middle
As you've heard Tim
say on Tues--

00:00:42.306 --> 00:00:46.156 A:middle
on Monday, about two-thirds of
you are here for this conference

00:00:46.156 --> 00:00:47.606 A:middle
for the first time,
that's fantastic.

00:00:47.816 --> 00:00:50.906 A:middle
Many of you are in fact new to
programming in the recent past.

00:00:50.946 --> 00:00:53.486 A:middle
You come from a diverse
array of backgrounds

00:00:53.486 --> 00:00:55.476 A:middle
and experience levels
and that's great.

00:00:55.476 --> 00:00:57.976 A:middle
You have a lot of different
kinds of wonderful apps

00:00:57.976 --> 00:00:59.226 A:middle
that you can contribute
for our customers

00:00:59.226 --> 00:01:00.176 A:middle
in the App Store that they love.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:00:59.226 --> 00:01:00.176 A:middle
in the App Store that they love.

00:01:01.136 --> 00:01:03.126 A:middle
However, across all these
domains and different types

00:01:03.126 --> 00:01:05.236 A:middle
of applications, one
thing that's constant is

00:01:05.236 --> 00:01:07.566 A:middle
that everyone uses data
structures and it's common

00:01:07.566 --> 00:01:08.686 A:middle
to have performance issues.

00:01:08.986 --> 00:01:11.096 A:middle
No matter what your app does,
you're going to be using arrays

00:01:11.096 --> 00:01:13.516 A:middle
and dictionaries and so on and
it's important to understand how

00:01:13.516 --> 00:01:15.036 A:middle
that can affect your
application.

00:01:15.286 --> 00:01:16.426 A:middle
When you have issues like this,

00:01:16.426 --> 00:01:19.646 A:middle
often they're puzzling unless
you have some knowledge

00:01:19.646 --> 00:01:22.336 A:middle
of what's going on under the
hood and what's happening

00:01:22.486 --> 00:01:24.856 A:middle
so you can evaluate
your app and improve.

00:01:25.526 --> 00:01:29.416 A:middle
So, the goal of this session is
really to teach you how to fish.

00:01:29.416 --> 00:01:30.966 A:middle
I'm not here to give
you a one half tip

00:01:30.966 --> 00:01:32.636 A:middle
about how you can fix
this specific problem,

00:01:32.636 --> 00:01:34.806 A:middle
but really to look at the
grand scheme of things,

00:01:34.806 --> 00:01:36.846 A:middle
understand when it comes
to data structures,

00:01:37.056 --> 00:01:39.336 A:middle
how can I make my app
perform the best possible.

00:01:40.126 --> 00:01:42.776 A:middle
OK. So the things we're going
to cover today, first off,

00:01:42.776 --> 00:01:44.396 A:middle
when to focus on performance,

00:01:45.226 --> 00:01:47.846 A:middle
how to evaluate what we call
computational complexity,

00:01:48.676 --> 00:01:51.306 A:middle
how to choose and use data
structures in your application,

00:01:51.596 --> 00:01:53.756 A:middle
and last, how to design
your code for performance.

00:01:53.756 --> 00:01:54.886 A:middle
We'll give some concrete
examples.

00:01:55.076 --> 00:01:58.636 A:middle
So to start off, when to focus
on performance, and you think,

00:01:58.956 --> 00:02:01.086 A:middle
is it a trick question, the
answer is always, right?

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:01:58.956 --> 00:02:01.086 A:middle
is it a trick question, the
answer is always, right?

00:02:01.086 --> 00:02:03.286 A:middle
That's true to certain extent

00:02:03.286 --> 00:02:04.836 A:middle
and we will talk
about that in detail.

00:02:05.006 --> 00:02:06.626 A:middle
To start off with a quote,
I have this on my wall,

00:02:06.626 --> 00:02:09.145 A:middle
this is form Steve Jobs,
"We don't get a chance to do

00:02:09.145 --> 00:02:11.996 A:middle
that many things, and everyone
should be really excellent.

00:02:12.336 --> 00:02:14.136 A:middle
We've all chosen to do
this with our lives.

00:02:14.366 --> 00:02:15.726 A:middle
So it better be damn good.

00:02:15.876 --> 00:02:16.956 A:middle
It better be worth it."

00:02:17.506 --> 00:02:19.016 A:middle
I love this quote
because it motivates me

00:02:19.016 --> 00:02:21.836 A:middle
to make my applications the
best that I possibly can and try

00:02:21.836 --> 00:02:23.396 A:middle
to eek performance
out of every angle.

00:02:23.986 --> 00:02:24.916 A:middle
Have you noticed that he says,

00:02:24.916 --> 00:02:26.526 A:middle
"Everyone should be
really excellent,"

00:02:26.766 --> 00:02:28.036 A:middle
it's not necessarily perfect.

00:02:28.036 --> 00:02:30.776 A:middle
We as developers know that
our applications have flaws.

00:02:30.776 --> 00:02:33.496 A:middle
We do the best that we can
to make them as polished

00:02:33.496 --> 00:02:35.026 A:middle
as possible before
we hand them over,

00:02:35.286 --> 00:02:36.786 A:middle
but we have a limited
amount of time.

00:02:37.166 --> 00:02:39.086 A:middle
Steve also said, "You
have to pick carefully.

00:02:39.406 --> 00:02:41.856 A:middle
Innovation is saying
no to 1,000 things."

00:02:41.956 --> 00:02:43.556 A:middle
So how do we strike
the balance here

00:02:43.556 --> 00:02:45.376 A:middle
when it comes to performance?

00:02:45.426 --> 00:02:47.026 A:middle
You may have seen a
quote from Donald Knuth,

00:02:47.026 --> 00:02:48.976 A:middle
a famous computer
scientist where he says,

00:02:48.976 --> 00:02:51.076 A:middle
"Premature optimization
is the root of all evil."

00:02:51.456 --> 00:02:53.346 A:middle
People tend to throw this
around at developer forums

00:02:53.776 --> 00:02:55.656 A:middle
and some people will use
this almost an excuse to say,

00:02:55.656 --> 00:02:57.616 A:middle
"You don't need to worry about
performance at all, right?

00:02:57.616 --> 00:02:58.716 A:middle
It's not going to
be a big deal."

00:02:59.106 --> 00:03:00.286 A:middle
Sometimes that's the case.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:02:59.106 --> 00:03:00.286 A:middle
Sometimes that's the case.

00:03:00.686 --> 00:03:03.166 A:middle
But unfortunately, we usually
only see this middle sentence

00:03:03.166 --> 00:03:03.576 A:middle
of the quote.

00:03:03.716 --> 00:03:05.736 A:middle
But he said a lot more,
he said, "We should forget

00:03:05.736 --> 00:03:09.136 A:middle
about small efficiencies
about 97 percent of the time.

00:03:09.596 --> 00:03:11.906 A:middle
Yet we should not pass
up our opportunities

00:03:11.906 --> 00:03:13.316 A:middle
in that critical 3 percent.

00:03:13.736 --> 00:03:15.226 A:middle
So there comes a
time when focusing

00:03:15.226 --> 00:03:17.586 A:middle
on performance is really
important for your application.

00:03:18.256 --> 00:03:20.716 A:middle
I like to summarize this by
saying, "Optimize performance

00:03:20.886 --> 00:03:22.666 A:middle
when it will make a
meaningful difference."

00:03:22.666 --> 00:03:24.246 A:middle
That's what we're going
to be talking about today,

00:03:24.476 --> 00:03:26.196 A:middle
is how I can choose to see--

00:03:26.196 --> 00:03:28.086 A:middle
is this going to make a
difference for my application?

00:03:28.726 --> 00:03:32.136 A:middle
So, to talk about that, there's
a principle called Amdahl's Law

00:03:32.136 --> 00:03:34.196 A:middle
which is really about
helping you pick your battles

00:03:34.196 --> 00:03:34.896 A:middle
in performance.

00:03:34.896 --> 00:03:38.086 A:middle
So this law was proposed
by Gene Amdahl,

00:03:38.086 --> 00:03:40.566 A:middle
a very famous computer
architect, and basically,

00:03:40.566 --> 00:03:43.046 A:middle
it has to do with predicting
the maximum improvement

00:03:43.046 --> 00:03:45.476 A:middle
that you can expect by speeding
up some portion of your code.

00:03:46.096 --> 00:03:48.266 A:middle
This depends obviously on
what percentage of time

00:03:48.266 --> 00:03:50.846 A:middle
that code is taking to
begin with to see what kind

00:03:50.846 --> 00:03:51.816 A:middle
of speed that you can achieve.

00:03:52.176 --> 00:03:54.896 A:middle
And the payoff is much larger
for the dominant piece of code,

00:03:54.896 --> 00:03:56.056 A:middle
the thing that's
taking the most time,

00:03:56.416 --> 00:03:57.666 A:middle
this appear fairly obvious.

00:03:58.336 --> 00:03:59.946 A:middle
So the question is,
will the payoff

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:04:00.166 --> 00:04:01.816 A:middle
of improving the
performance of this of piece

00:04:01.866 --> 00:04:03.916 A:middle
of code be worth the effort,
the time that it's going

00:04:03.916 --> 00:04:04.786 A:middle
to take me to do that?

00:04:05.126 --> 00:04:06.996 A:middle
And this applies
directly to concurrency.

00:04:06.996 --> 00:04:09.656 A:middle
In fact, as this law was
originally stated, it had to do

00:04:09.656 --> 00:04:12.046 A:middle
with multi-core processing
and breaking your code

00:04:12.046 --> 00:04:15.056 A:middle
up into multiple pieces, and
that has great tie ends as well

00:04:15.056 --> 00:04:17.036 A:middle
to Grand Central
Dispatch and using blocks.

00:04:17.146 --> 00:04:19.555 A:middle
So let me give you an
example of Amdahl's Law.

00:04:19.966 --> 00:04:22.866 A:middle
Say that you have a process
that has two segments A and B

00:04:23.036 --> 00:04:25.836 A:middle
and one takes 80 seconds and
one takes 20 seconds, all right.

00:04:25.936 --> 00:04:28.396 A:middle
So we have a certain
amount of time.

00:04:28.426 --> 00:04:32.116 A:middle
Now, if you can spend a
bit of time and optimize

00:04:32.116 --> 00:04:36.066 A:middle
and cut the time spent by
process B-- segment B in half,

00:04:36.066 --> 00:04:36.866 A:middle
then you have a great win.

00:04:36.866 --> 00:04:38.916 A:middle
Now you're 90 percent of
your previous performance.

00:04:39.206 --> 00:04:41.906 A:middle
However, if you can apply
the same effort to speed

00:04:41.906 --> 00:04:43.546 A:middle
up process A and cut
that time in half,

00:04:43.696 --> 00:04:44.906 A:middle
now you've gone to 60 percent.

00:04:45.186 --> 00:04:47.506 A:middle
This is a much bigger win
and this is what we talk

00:04:47.506 --> 00:04:49.246 A:middle
about when we say
identifying bottlenecks,

00:04:49.246 --> 00:04:51.216 A:middle
looking at the actual
problems in your code.

00:04:51.616 --> 00:04:53.596 A:middle
So that's where you really
want to focus on performance.

00:04:53.876 --> 00:04:56.616 A:middle
You know, it's great to have
a performance win in segment B

00:04:56.856 --> 00:04:58.306 A:middle
but everyone has things
that they have to do.

00:04:58.306 --> 00:04:59.846 A:middle
So you got to choose
wisely what you work on.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:05:00.346 --> 00:05:01.696 A:middle
So back to Donald Knuth,

00:05:01.696 --> 00:05:03.326 A:middle
he talked about premature
optimization.

00:05:04.006 --> 00:05:06.756 A:middle
Now, premature optimization,
generally leads

00:05:07.026 --> 00:05:09.376 A:middle
to unnecessary complexity
in your code.

00:05:09.666 --> 00:05:11.256 A:middle
You take something
that's simple and to try

00:05:11.256 --> 00:05:14.186 A:middle
to get more performance out of
it, you change and tweak things

00:05:14.186 --> 00:05:15.766 A:middle
and make it more
complex and clever.

00:05:16.096 --> 00:05:17.046 A:middle
Sometimes that's great.

00:05:17.306 --> 00:05:19.176 A:middle
But if it ain't broke,
don't fix it.

00:05:19.586 --> 00:05:21.766 A:middle
You don't have to fix something
that's not necessarily a problem

00:05:21.766 --> 00:05:22.296 A:middle
for your code.

00:05:22.536 --> 00:05:24.806 A:middle
You have a ton of features
that you need to implement

00:05:24.806 --> 00:05:27.366 A:middle
for your app and polishing it
to make it great for you users.

00:05:27.466 --> 00:05:30.576 A:middle
So I'd like to focus on
something I call informed design

00:05:30.576 --> 00:05:32.266 A:middle
which leads to elegant
and efficient code.

00:05:32.926 --> 00:05:34.716 A:middle
Informed design is all

00:05:34.716 --> 00:05:36.866 A:middle
about considering your
performance early on,

00:05:37.226 --> 00:05:38.616 A:middle
even during the design phase.

00:05:38.616 --> 00:05:41.016 A:middle
You can do that before you
even write a line of code.

00:05:41.426 --> 00:05:44.026 A:middle
And it helps to intelligently
avoid problems

00:05:44.026 --> 00:05:45.636 A:middle
that you can actually
face in the real world,

00:05:45.666 --> 00:05:47.146 A:middle
rather than premature
optimization

00:05:47.146 --> 00:05:48.896 A:middle
and fixing your problem
that may not be

00:05:48.896 --> 00:05:50.056 A:middle
such a big problem after all.

00:05:51.096 --> 00:05:53.736 A:middle
And this is useful because it
can help you avoid designing

00:05:53.736 --> 00:05:56.196 A:middle
slowness into your application
only to fix it later.

00:05:56.506 --> 00:05:58.606 A:middle
So if you can think about
it upfront, it's a big win.

00:05:58.606 --> 00:06:01.256 A:middle
OK. So now let's move
to talking about how

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:05:58.606 --> 00:06:01.256 A:middle
OK. So now let's move
to talking about how

00:06:01.256 --> 00:06:02.406 A:middle
to design for performance.

00:06:02.596 --> 00:06:04.536 A:middle
If you have a performance
issue that you've identified

00:06:04.536 --> 00:06:07.006 A:middle
in your code, there's
three broad ways

00:06:07.006 --> 00:06:08.346 A:middle
that you can resolve that.

00:06:08.346 --> 00:06:10.106 A:middle
The first is, don't do it.

00:06:10.486 --> 00:06:11.596 A:middle
If there's unnecessary work,

00:06:11.596 --> 00:06:12.636 A:middle
then you can completely
cut it out.

00:06:12.636 --> 00:06:15.876 A:middle
The second is do it as rarely as
possible, and the third is do it

00:06:15.876 --> 00:06:17.056 A:middle
as efficiently as possible.

00:06:17.846 --> 00:06:20.296 A:middle
Now, these are generally in
increasing order of difficulty.

00:06:20.296 --> 00:06:22.986 A:middle
It's very easy to just remove
code that you no longer need,

00:06:22.986 --> 00:06:24.586 A:middle
but getting something to
be more efficient can be

00:06:24.586 --> 00:06:25.286 A:middle
really difficult.

00:06:25.716 --> 00:06:27.246 A:middle
In order to answer these
questions and choose

00:06:27.246 --> 00:06:28.916 A:middle
which approach works
for your scenario,

00:06:29.236 --> 00:06:30.526 A:middle
you really have to
have some context.

00:06:30.796 --> 00:06:31.916 A:middle
Is the work necessary?

00:06:31.976 --> 00:06:33.806 A:middle
If not, I may be
able to remove it.

00:06:33.966 --> 00:06:35.716 A:middle
Is redundant work being done?

00:06:35.816 --> 00:06:37.146 A:middle
Doing the same thing
over and over again,

00:06:37.146 --> 00:06:38.546 A:middle
I may be able to
reuse that work.

00:06:38.866 --> 00:06:40.296 A:middle
Or is there a more
efficient way?

00:06:40.686 --> 00:06:42.486 A:middle
And that last question is
really the most tricky.

00:06:42.976 --> 00:06:46.106 A:middle
How do I know if I can do better
than what I'm doing right now?

00:06:46.976 --> 00:06:49.536 A:middle
So, to answer that question,
we're going to the next portion

00:06:49.536 --> 00:06:50.136 A:middle
of the talk-- where we talk

00:06:50.136 --> 00:06:52.926 A:middle
about computational
complexity and cost.

00:06:52.926 --> 00:06:54.956 A:middle
Now, these are some big words
so I'll explain out for you

00:06:55.546 --> 00:06:57.346 A:middle
in kind of broad terms.

00:06:57.346 --> 00:06:59.716 A:middle
So we're talking about the
cost of code, and by this,

00:06:59.716 --> 00:07:01.906 A:middle
I don't mean how much you
pay for an app in the store

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:06:59.716 --> 00:07:01.906 A:middle
I don't mean how much you
pay for an app in the store

00:07:02.146 --> 00:07:05.506 A:middle
or how much it cost to you
to have people develop it.

00:07:05.636 --> 00:07:08.396 A:middle
Every piece of code takes
some amount of time to run

00:07:08.396 --> 00:07:10.656 A:middle
because there's work being
done, and it's obvious

00:07:10.656 --> 00:07:12.306 A:middle
that more work takes more time.

00:07:13.096 --> 00:07:14.536 A:middle
However, it's not
necessarily obvious

00:07:14.536 --> 00:07:16.406 A:middle
that sometimes you can
have really short code

00:07:16.406 --> 00:07:19.526 A:middle
that does a lot of work and it
can hide some complexity, right?

00:07:19.526 --> 00:07:22.076 A:middle
There's a cost associated
with a particular code,

00:07:22.346 --> 00:07:24.566 A:middle
perhaps an API Caller, so on,
or you're using a library.

00:07:25.106 --> 00:07:29.246 A:middle
Now, the effects of data
growth can vary quite a bit

00:07:29.246 --> 00:07:31.166 A:middle
when you're choosing
an algorithm

00:07:31.256 --> 00:07:33.426 A:middle
and it can really impact you
performance, particularly

00:07:33.426 --> 00:07:34.676 A:middle
as your data size grows.

00:07:35.216 --> 00:07:37.266 A:middle
It may be disproportional
affect the number

00:07:37.266 --> 00:07:38.536 A:middle
of objects that you add.

00:07:38.996 --> 00:07:40.966 A:middle
And consequently, small
tests often won't turn

00:07:40.966 --> 00:07:42.056 A:middle
up this kind of problems.

00:07:42.316 --> 00:07:43.746 A:middle
We do-- we try to
do as much testing

00:07:43.746 --> 00:07:45.856 A:middle
as we can before we send
our app out into the world,

00:07:46.216 --> 00:07:47.496 A:middle
but you've probably
all experienced

00:07:47.496 --> 00:07:49.966 A:middle
that your customers will use
you app in new and exciting

00:07:49.966 --> 00:07:52.746 A:middle
and sometimes terrifying ways
and throw a lot of data added

00:07:52.746 --> 00:07:54.116 A:middle
in ways that you
didn't anticipate.

00:07:54.486 --> 00:07:56.316 A:middle
And sometimes these
performance issues will crap

00:07:56.316 --> 00:07:59.476 A:middle
out where you least
want them to.

00:07:59.986 --> 00:08:02.856 A:middle
OK. Fortunately, this kind of
complexity can often be analyzed

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:07:59.986 --> 00:08:02.856 A:middle
OK. Fortunately, this kind of
complexity can often be analyzed

00:08:03.016 --> 00:08:04.036 A:middle
without even running the code.

00:08:04.036 --> 00:08:06.046 A:middle
Much like the Xcode static
analyzer can do that.

00:08:06.576 --> 00:08:09.016 A:middle
And the key to this is
understanding the complexity

00:08:09.016 --> 00:08:11.016 A:middle
of the code that you're running
and how much work is being done.

00:08:11.286 --> 00:08:14.786 A:middle
Now, Computer Science has entire
semester courses devoted to this

00:08:14.786 --> 00:08:17.186 A:middle
that leaves sophomore
students really puzzled.

00:08:17.486 --> 00:08:19.466 A:middle
We don't the have time to
get into entire semester

00:08:19.466 --> 00:08:21.306 A:middle
but I'm going to give you
kind of a crash course

00:08:21.526 --> 00:08:24.126 A:middle
and help you have a framework
for understanding complexity

00:08:24.316 --> 00:08:25.216 A:middle
and analyzing your code.

00:08:25.216 --> 00:08:27.186 A:middle
So, in Computer Science, we talk

00:08:27.186 --> 00:08:29.096 A:middle
about something called
"Big O" notation.

00:08:29.096 --> 00:08:32.416 A:middle
So this is a way by ranking
algorithms by efficiency,

00:08:32.416 --> 00:08:34.096 A:middle
generally, by their
time efficiency,

00:08:34.096 --> 00:08:35.546 A:middle
or memory efficiency, or so on.

00:08:35.546 --> 00:08:38.576 A:middle
And the letter O stands for
the order, the order of growth

00:08:38.576 --> 00:08:39.966 A:middle
of this and we'll talk
about this in detail.

00:08:40.525 --> 00:08:43.586 A:middle
And it really relates to how the
performance changes as the scale

00:08:43.586 --> 00:08:46.646 A:middle
of the work that you're doing
when you increase the number

00:08:46.646 --> 00:08:48.116 A:middle
of objects you're
working with for example.

00:08:48.666 --> 00:08:53.196 A:middle
So, with Big O notation,
what we're really seeking

00:08:53.196 --> 00:08:55.816 A:middle
to do is approximate the worst
case behavior for an algorithm,

00:08:56.086 --> 00:08:57.896 A:middle
the most work that you
might ever have to do.

00:08:58.156 --> 00:09:00.696 A:middle
Ideally with an algorithm, you
may be able to skip out early

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:08:58.156 --> 00:09:00.696 A:middle
Ideally with an algorithm, you
may be able to skip out early

00:09:00.956 --> 00:09:03.406 A:middle
and so on if you're doing
searches and that type of thing.

00:09:03.626 --> 00:09:06.976 A:middle
But Big O is concerned with
how bad could this possibly be?

00:09:06.976 --> 00:09:09.586 A:middle
So then that's my absolute
worst case of performance.

00:09:09.656 --> 00:09:11.606 A:middle
And in general, we
ignore coefficients

00:09:11.606 --> 00:09:13.566 A:middle
and lower order terms
and logarithmic bases

00:09:13.566 --> 00:09:15.636 A:middle
because what we really
care about is the order.

00:09:15.636 --> 00:09:17.726 A:middle
Whether it's n or n
squared as we'll go

00:09:17.726 --> 00:09:18.706 A:middle
into detail in just a moment.

00:09:19.726 --> 00:09:21.866 A:middle
Now, for any given task,
it's important to realize

00:09:21.866 --> 00:09:23.236 A:middle
that there are inherent limits.

00:09:23.626 --> 00:09:25.266 A:middle
There are some things
that just take time.

00:09:25.266 --> 00:09:26.636 A:middle
We'd like to do everything
instantly

00:09:26.636 --> 00:09:28.016 A:middle
but that's not always possible.

00:09:28.356 --> 00:09:30.116 A:middle
A perfect example of
this, Fred Brooks,

00:09:30.116 --> 00:09:31.546 A:middle
a famous software engineer,

00:09:31.956 --> 00:09:34.506 A:middle
"Nine women can't make
a baby in one moth."

00:09:34.506 --> 00:09:35.596 A:middle
As many women you assign to it,

00:09:35.596 --> 00:09:36.796 A:middle
you'd like to do
it concurrently,

00:09:36.796 --> 00:09:38.226 A:middle
it will be much more
convenient for them

00:09:38.476 --> 00:09:39.696 A:middle
but it's simply not possible.

00:09:39.696 --> 00:09:40.936 A:middle
There's a hard limit
on this, right?

00:09:41.016 --> 00:09:43.586 A:middle
So we're going to talk
about Big O complexity.

00:09:43.586 --> 00:09:45.376 A:middle
And I want to identify
for you a few key

00:09:45.436 --> 00:09:46.766 A:middle
and common order functions.

00:09:46.846 --> 00:09:49.426 A:middle
So I have a table here, in
the first column, notation,

00:09:49.426 --> 00:09:51.616 A:middle
you'll see how you
might see it written

00:09:51.616 --> 00:09:54.346 A:middle
and these are pronounced
Big O of 1 or order 1,

00:09:54.536 --> 00:09:57.346 A:middle
order log n, order n and so on.

00:09:57.426 --> 00:10:00.266 A:middle
You might also hear it referred
to by the name constant time,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:09:57.426 --> 00:10:00.266 A:middle
You might also hear it referred
to by the name constant time,

00:10:00.266 --> 00:10:02.396 A:middle
logarithmic time, linear
time, quadratic time,

00:10:02.396 --> 00:10:03.906 A:middle
and so on 'cause
they're interchangeable.

00:10:04.236 --> 00:10:06.436 A:middle
And then provided in the
third column some examples

00:10:06.436 --> 00:10:08.556 A:middle
of common algorithms
or tasks that fall

00:10:08.556 --> 00:10:09.696 A:middle
into these different categories.

00:10:10.006 --> 00:10:11.996 A:middle
I won't go into them in
detail here on this slide

00:10:12.306 --> 00:10:14.916 A:middle
but this is great for
reference to come back and see

00:10:14.916 --> 00:10:16.716 A:middle
where my task actually fit.

00:10:16.716 --> 00:10:19.446 A:middle
And we'll talk a little bit
more in detail about identifying

00:10:19.446 --> 00:10:20.876 A:middle
which of these your
task belongs to.

00:10:20.876 --> 00:10:22.906 A:middle
Now, a few of these
are most common.

00:10:22.906 --> 00:10:25.566 A:middle
You'll see this all over the
place and they're very common

00:10:25.566 --> 00:10:27.226 A:middle
for algorithms that
you'll be working with.

00:10:27.356 --> 00:10:28.586 A:middle
So I'll talk about
these in detail.

00:10:30.766 --> 00:10:34.156 A:middle
So the first, before I get
into some specific details,

00:10:34.156 --> 00:10:36.116 A:middle
let me show you a comparison
of these order functions.

00:10:36.116 --> 00:10:37.596 A:middle
So it's easy to see
them in a table

00:10:37.836 --> 00:10:39.696 A:middle
but maybe it doesn't hit
home why this is important.

00:10:39.696 --> 00:10:43.096 A:middle
First off, this is what order n
squared complexity looks like,

00:10:43.386 --> 00:10:49.096 A:middle
like a parabola, order n
log n, order n, order log n,

00:10:49.986 --> 00:10:51.306 A:middle
and order 1 or constant time.

00:10:51.836 --> 00:10:53.926 A:middle
Now, the first thing that
you can see is these diverged

00:10:54.066 --> 00:10:54.986 A:middle
really rapidly.

00:10:55.266 --> 00:10:57.146 A:middle
When you get to a
large number of items

00:10:57.146 --> 00:10:59.896 A:middle
across the bottom scale,
you have some of this

00:10:59.896 --> 00:11:01.206 A:middle
that it gets really complex

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:10:59.896 --> 00:11:01.206 A:middle
that it gets really complex

00:11:01.206 --> 00:11:02.426 A:middle
and shoots its way
up towards the top.

00:11:02.426 --> 00:11:04.096 A:middle
That means your performance
is going to be bad.

00:11:04.096 --> 00:11:05.816 A:middle
You're doing that
much more work, right?

00:11:06.106 --> 00:11:07.266 A:middle
The other thing to
notice is that down

00:11:07.266 --> 00:11:09.706 A:middle
at the bottom left corner,
they're really close together.

00:11:09.866 --> 00:11:12.406 A:middle
So for small scale, it
may not be necessary

00:11:12.406 --> 00:11:14.056 A:middle
to find a really
optimal algorithm.

00:11:14.246 --> 00:11:15.636 A:middle
This would be arranged
where you want to watch

00:11:15.636 --> 00:11:17.096 A:middle
out for premature optimization.

00:11:17.326 --> 00:11:18.516 A:middle
Am I really going to
have an issue here,

00:11:18.516 --> 00:11:20.676 A:middle
because they're all
pretty close together.

00:11:20.676 --> 00:11:22.196 A:middle
So those are some
things to be aware off.

00:11:22.906 --> 00:11:27.766 A:middle
So, I'm going to go through some
examples of a few sample pieces

00:11:27.766 --> 00:11:31.146 A:middle
of code that have
somebody's complexities.

00:11:31.146 --> 00:11:33.216 A:middle
And remember, the key for this
is, is that we want to look

00:11:33.216 --> 00:11:36.056 A:middle
of the growth-- at the growth of
the amount of work as the size

00:11:36.056 --> 00:11:36.966 A:middle
of variant [inaudible]
increases.

00:11:37.036 --> 00:11:38.576 A:middle
So first is a very simple one.

00:11:38.576 --> 00:11:40.166 A:middle
Let's say that we have
an array of integers

00:11:40.366 --> 00:11:42.526 A:middle
and I have a function where
I pass in an integer value

00:11:42.686 --> 00:11:44.106 A:middle
and an index, and I simply want

00:11:44.106 --> 00:11:46.856 A:middle
to know does this value
appear at that index.

00:11:46.856 --> 00:11:48.596 A:middle
Now you could see we're
only doing one operation

00:11:48.876 --> 00:11:52.056 A:middle
and you may know that indexing
into an array is extremely fast.

00:11:52.286 --> 00:11:54.896 A:middle
So, in this case, it's
order 1 regardless

00:11:54.896 --> 00:11:56.006 A:middle
of what index I choose,

00:11:56.006 --> 00:11:57.426 A:middle
it's going to return
nearly instantly.

00:11:57.516 --> 00:12:01.146 A:middle
So if we have a sample array,
you can see I'm in query 1 index

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:11:57.516 --> 00:12:01.146 A:middle
So if we have a sample array,
you can see I'm in query 1 index

00:12:01.146 --> 00:12:02.776 A:middle
and say that that
value is not there.

00:12:03.026 --> 00:12:04.716 A:middle
Here I found it,
and there I've not.

00:12:04.976 --> 00:12:06.366 A:middle
So I don't have to
look at anything else

00:12:06.366 --> 00:12:07.556 A:middle
in the array, just one spot.

00:12:07.746 --> 00:12:08.956 A:middle
So that makes this order 1.

00:12:09.626 --> 00:12:11.736 A:middle
If we change this
up just slightly,

00:12:12.746 --> 00:12:14.206 A:middle
now we have an order
and algorithm.

00:12:14.496 --> 00:12:16.256 A:middle
So, now I'm interested in seeing

00:12:16.426 --> 00:12:18.806 A:middle
if a particular value
appears anywhere in an array,

00:12:18.946 --> 00:12:20.416 A:middle
not just at given index.

00:12:20.416 --> 00:12:22.106 A:middle
In order to do that,
because I don't know

00:12:22.106 --> 00:12:24.426 A:middle
where it would appear, if it's
there at all, I have to look

00:12:24.426 --> 00:12:25.676 A:middle
through each index in the array.

00:12:26.006 --> 00:12:27.846 A:middle
So we have a for loop when
we start at the beginning

00:12:27.846 --> 00:12:28.596 A:middle
and we go towards the end

00:12:28.596 --> 00:12:30.316 A:middle
and then we test to
see if it's there.

00:12:30.316 --> 00:12:32.406 A:middle
If at any point I
find it, I return yes.

00:12:32.606 --> 00:12:35.826 A:middle
But the worst case is that it's
not there in the array at all.

00:12:35.826 --> 00:12:37.866 A:middle
And I have to check
thought every single index

00:12:37.866 --> 00:12:38.896 A:middle
in order to determine that.

00:12:38.896 --> 00:12:41.906 A:middle
So, if you could see here,
I have to march one by one

00:12:42.046 --> 00:12:43.826 A:middle
down the array until
I find the object

00:12:44.316 --> 00:12:45.366 A:middle
or determine that
it's not there.

00:12:45.876 --> 00:12:47.226 A:middle
So in worst case, order n.

00:12:47.426 --> 00:12:51.206 A:middle
For order n squared, let's
say we have a similar array,

00:12:51.286 --> 00:12:53.866 A:middle
I give it a value and I want
to say, does this value appear

00:12:53.866 --> 00:12:55.576 A:middle
at least twice anywhere
in this array?

00:12:55.576 --> 00:12:57.606 A:middle
In order to do that, I have

00:12:57.606 --> 00:13:01.016 A:middle
to compare every two possible
pairings of indexes in the array

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:12:57.606 --> 00:13:01.016 A:middle
to compare every two possible
pairings of indexes in the array

00:13:01.016 --> 00:13:01.896 A:middle
to see if they're equal.

00:13:02.266 --> 00:13:04.106 A:middle
So what that means is that
I have to do two for loops.

00:13:04.106 --> 00:13:06.636 A:middle
I have an outer for loop and
an inner for loop and each

00:13:06.636 --> 00:13:09.696 A:middle
of this is an order n algorithm.

00:13:10.866 --> 00:13:13.566 A:middle
And inside this for loop once
I get to comparing two indexes,

00:13:13.816 --> 00:13:16.816 A:middle
you see, I compare each of these
two to see if they're equal

00:13:16.816 --> 00:13:20.916 A:middle
and if at any point I find them,
I can bail out and say yes.

00:13:20.966 --> 00:13:22.736 A:middle
And you can see that we're
doing a lot more work here.

00:13:22.736 --> 00:13:26.226 A:middle
J is moving back and forth like
a mad man and I is just trying

00:13:26.226 --> 00:13:27.976 A:middle
to keep up, and finally
here at the end,

00:13:28.116 --> 00:13:30.006 A:middle
we find those two
matching values.

00:13:30.216 --> 00:13:32.416 A:middle
Now in the worst case, there
may be no values at all.

00:13:32.416 --> 00:13:35.626 A:middle
These two values may not
be present in the array

00:13:35.626 --> 00:13:37.916 A:middle
or the value may not be present
twice in the array but we have

00:13:37.916 --> 00:13:40.046 A:middle
to go to the very
end to find that out.

00:13:40.046 --> 00:13:41.046 A:middle
Now, some of you
may look at this

00:13:41.046 --> 00:13:43.036 A:middle
and realize this is a
rather naive implementation.

00:13:43.286 --> 00:13:45.216 A:middle
I'm starting the j loop
at zero every time.

00:13:45.656 --> 00:13:48.946 A:middle
So, for example, when I get
to the very end of the array

00:13:48.946 --> 00:13:51.436 A:middle
and j starts at the beginning,
I've already compared that one,

00:13:51.506 --> 00:13:53.496 A:middle
I was at the beginning
and j was at the end.

00:13:53.876 --> 00:13:55.616 A:middle
So that's kind of silly
they have to do that.

00:13:55.766 --> 00:13:58.186 A:middle
So instead you could choose
to start the inner for loop

00:13:58.186 --> 00:14:00.746 A:middle
at i plus 1 for example
and you eliminate half

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:13:58.186 --> 00:14:00.746 A:middle
at i plus 1 for example
and you eliminate half

00:14:00.746 --> 00:14:01.606 A:middle
of your comparisons.

00:14:01.846 --> 00:14:02.786 A:middle
That's great, that's
a great win.

00:14:02.786 --> 00:14:04.466 A:middle
So now we're in the
n squared over 2,

00:14:05.076 --> 00:14:06.226 A:middle
but it still ends for a growth.

00:14:06.226 --> 00:14:09.116 A:middle
So the key to this is
although it's now much faster

00:14:09.266 --> 00:14:11.106 A:middle
for a given input
size, it's still going

00:14:11.106 --> 00:14:12.646 A:middle
to have the same
growth properties

00:14:12.646 --> 00:14:15.436 A:middle
as you add one more object or
one more item to the array,

00:14:15.726 --> 00:14:17.466 A:middle
you're going to add
n comparisons.

00:14:17.666 --> 00:14:19.566 A:middle
That's the important thing
from this, so order n squared.

00:14:20.256 --> 00:14:22.526 A:middle
OK. So, calculating complexity.

00:14:22.936 --> 00:14:25.196 A:middle
We've seen that you can
combine this order functions.

00:14:25.196 --> 00:14:28.086 A:middle
For the n squared example I just
showed, we have two for loops

00:14:28.256 --> 00:14:30.856 A:middle
and each of those has order n
and we have nested complexities,

00:14:30.856 --> 00:14:33.276 A:middle
we multiply those together,
n times n, we get n squared.

00:14:33.656 --> 00:14:35.186 A:middle
When you have sequential
complexities,

00:14:35.186 --> 00:14:37.616 A:middle
we add those together and
then we take the largest term.

00:14:37.616 --> 00:14:40.236 A:middle
So for example, this function
were introduced to n squared.

00:14:40.586 --> 00:14:43.296 A:middle
We have one n squared
call and two n and three

00:14:43.296 --> 00:14:46.016 A:middle
that are constant time but all
we care about it the n squared,

00:14:46.156 --> 00:14:48.226 A:middle
nothing else, because that's
the growth of this function.

00:14:48.416 --> 00:14:50.446 A:middle
OK. So you see that
was source code.

00:14:50.786 --> 00:14:52.996 A:middle
However, sometimes you may not
have access to the source code

00:14:52.996 --> 00:14:56.476 A:middle
or not be aware of what work
it's doing, and in such cases,

00:14:56.476 --> 00:14:57.456 A:middle
you can often estimate.

00:14:58.026 --> 00:14:59.726 A:middle
You can consider what the
code would have to do,

00:14:59.726 --> 00:15:01.396 A:middle
what kind of work it's
trying to accomplish,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:14:59.726 --> 00:15:01.396 A:middle
what kind of work it's
trying to accomplish,

00:15:01.586 --> 00:15:03.086 A:middle
and another complimentary
alternative is

00:15:03.086 --> 00:15:04.596 A:middle
to profile with instruments.

00:15:04.716 --> 00:15:07.516 A:middle
This can be a great way to find
performance issues in your code.

00:15:07.516 --> 00:15:09.056 A:middle
There are many sessions
from previous years

00:15:09.056 --> 00:15:11.036 A:middle
about using instruments
and in fact,

00:15:11.036 --> 00:15:15.266 A:middle
Xcode 5 as you saw earlier this
week introduces new debug gauges

00:15:15.266 --> 00:15:17.306 A:middle
including memory and CPU
is that it can help you

00:15:17.526 --> 00:15:18.866 A:middle
with identifying
this kind of issues.

00:15:19.886 --> 00:15:22.296 A:middle
Now, some APIs may
appear to be very similar

00:15:22.296 --> 00:15:23.916 A:middle
but it's important
not to confuse them

00:15:23.916 --> 00:15:25.636 A:middle
when you're estimating, just
look at the name and say, "Oh,

00:15:25.636 --> 00:15:27.106 A:middle
I know what that is"
because of the name.

00:15:27.106 --> 00:15:29.426 A:middle
For example, we have
a containsObject API

00:15:29.426 --> 00:15:31.256 A:middle
on both NSArray and NSSet.

00:15:31.506 --> 00:15:33.556 A:middle
But it would be folly to
assume that they're the same.

00:15:33.636 --> 00:15:35.636 A:middle
So let's look at NSArray first.

00:15:35.636 --> 00:15:37.336 A:middle
At the containsObject,
we want to see

00:15:37.336 --> 00:15:39.276 A:middle
if a given object appears
anywhere in the array.

00:15:39.926 --> 00:15:40.796 A:middle
What work does it do?

00:15:41.296 --> 00:15:42.116 A:middle
Well, in this case,

00:15:42.116 --> 00:15:44.246 A:middle
the documentation actually
tells us explicitly

00:15:44.486 --> 00:15:47.246 A:middle
that it sends the isEqual
message to each object

00:15:47.246 --> 00:15:49.506 A:middle
in the array until one
of them returns true

00:15:49.626 --> 00:15:51.016 A:middle
or which is the end
of the array.

00:15:51.506 --> 00:15:52.746 A:middle
OK. So it goes to each object.

00:15:52.746 --> 00:15:54.696 A:middle
That certainly sounds
like order n complexity

00:15:54.896 --> 00:15:56.366 A:middle
and that's certainly
a valid assumption.

00:15:56.366 --> 00:15:57.846 A:middle
I think that that's
pretty reasonable.

00:15:58.376 --> 00:15:59.906 A:middle
Now, we may think, well, what

00:15:59.906 --> 00:16:01.696 A:middle
if I can enumerate
these concurrently

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:15:59.906 --> 00:16:01.696 A:middle
if I can enumerate
these concurrently

00:16:01.696 --> 00:16:02.616 A:middle
and compare the objects?

00:16:02.616 --> 00:16:04.036 A:middle
That would be sort of a win.

00:16:04.346 --> 00:16:07.036 A:middle
And it would, it would reduce
it by a constant factor

00:16:07.036 --> 00:16:09.236 A:middle
but it would still
be a linear operation

00:16:09.396 --> 00:16:10.116 A:middle
with the size of the array.

00:16:10.926 --> 00:16:13.096 A:middle
OK. So let's see NSSet.

00:16:13.696 --> 00:16:16.446 A:middle
NSSet also has containsObject,
it has the same object.

00:16:16.446 --> 00:16:17.936 A:middle
I give it an object,
it does the same thing.

00:16:17.936 --> 00:16:19.506 A:middle
It tells me whether it's
in the collection or not.

00:16:20.206 --> 00:16:22.276 A:middle
It looks just like the one
that we just saw in NSArray.

00:16:22.736 --> 00:16:23.816 A:middle
Is it also order n?

00:16:23.986 --> 00:16:24.926 A:middle
You might assume
that it would be.

00:16:25.586 --> 00:16:28.186 A:middle
However, it's actually order
1, it's a constant time.

00:16:28.256 --> 00:16:29.626 A:middle
Regardless of the
size of the set,

00:16:29.626 --> 00:16:32.736 A:middle
containsObject is always
really fast, that's great.

00:16:33.576 --> 00:16:35.896 A:middle
There's a caveat, please don't
go start replacing NSArray

00:16:35.896 --> 00:16:38.406 A:middle
with NSSet anywhere in your
code because it's fast.

00:16:38.406 --> 00:16:40.186 A:middle
There's context to
understand about why is this

00:16:40.186 --> 00:16:41.206 A:middle
and if it will work for you.

00:16:41.206 --> 00:16:45.246 A:middle
So, the reason that it's faster
is it must be doing less work.

00:16:45.566 --> 00:16:48.266 A:middle
It's doing the same amount
of work, roughly speaking,

00:16:48.266 --> 00:16:50.126 A:middle
regardless of how
large my collection is.

00:16:50.306 --> 00:16:51.066 A:middle
So talk about that.

00:16:51.336 --> 00:16:53.356 A:middle
The reason that this is is
something called hashing.

00:16:53.446 --> 00:16:55.536 A:middle
We'll talk about
hash-based organization.

00:16:55.636 --> 00:17:00.756 A:middle
So, NSSet uses a hash table for
storage as this NSDictionary.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:16:55.636 --> 00:17:00.756 A:middle
So, NSSet uses a hash table for
storage as this NSDictionary.

00:17:02.156 --> 00:17:04.586 A:middle
Every object has a
deterministic hash value.

00:17:04.586 --> 00:17:06.256 A:middle
You may have seen
the hash method.

00:17:06.256 --> 00:17:08.656 A:middle
This is defined on NSObject
we'll talk about in detail.

00:17:09.336 --> 00:17:12.096 A:middle
And it returns an unsigned
integer value that you could use

00:17:12.156 --> 00:17:13.675 A:middle
to store this object
in a hash table.

00:17:14.306 --> 00:17:16.646 A:middle
And equal objects should
always have the same hash.

00:17:16.776 --> 00:17:20.246 A:middle
We'll talk about this in more
detail and give examples.

00:17:20.246 --> 00:17:22.945 A:middle
When in a hash table, objects
are grouped into "buckets",

00:17:23.136 --> 00:17:26.906 A:middle
parts of the array based on
the hash that they provide.

00:17:27.256 --> 00:17:30.596 A:middle
And the structure has a hash
function that takes a hash

00:17:30.596 --> 00:17:31.866 A:middle
and maps it to a given bucket.

00:17:32.056 --> 00:17:34.536 A:middle
It can decide that this range of
hashes goes first in the bucket,

00:17:34.536 --> 00:17:36.556 A:middle
and this one and so on,
and it can divide this up.

00:17:36.556 --> 00:17:38.326 A:middle
And the goal of this
hash function is

00:17:38.326 --> 00:17:40.716 A:middle
to achieve uniform
distribution so that you have

00:17:40.716 --> 00:17:42.046 A:middle
about the same number of objects

00:17:42.046 --> 00:17:43.396 A:middle
in all the buckets
in the hash table.

00:17:44.596 --> 00:17:48.096 A:middle
When you achieve this lookup in
a hash table, it really only has

00:17:48.126 --> 00:17:50.206 A:middle
to consider the objects that
are in a particular bucket.

00:17:50.206 --> 00:17:52.246 A:middle
It knows if an object is
going to be there it will be

00:17:52.246 --> 00:17:55.516 A:middle
in this bucket and it can check
isEqual on only a few objects

00:17:55.566 --> 00:17:56.976 A:middle
or none at all if there's
none in the bucket.

00:17:57.176 --> 00:17:58.076 A:middle
This is an obvious win.

00:17:58.076 --> 00:18:00.566 A:middle
If you have an array that's a
thousand objects, you may have

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:17:58.076 --> 00:18:00.566 A:middle
If you have an array that's a
thousand objects, you may have

00:18:00.566 --> 00:18:03.266 A:middle
to check up to a thousand items
in order to see if it's there.

00:18:03.266 --> 00:18:05.526 A:middle
But with the set, you may
have to check only a handful.

00:18:05.526 --> 00:18:06.176 A:middle
This is great.

00:18:06.316 --> 00:18:09.166 A:middle
So let me give you a concrete
example with an animation here.

00:18:09.166 --> 00:18:11.766 A:middle
Say we have a hash function and
we have a hash table we're going

00:18:11.766 --> 00:18:12.666 A:middle
to store some objects in.

00:18:13.056 --> 00:18:14.936 A:middle
Let's say that we want
to store the names

00:18:14.936 --> 00:18:17.396 A:middle
of all Apple CEOs
past and present.

00:18:17.396 --> 00:18:19.086 A:middle
So let's start off
with Tim Cook.

00:18:19.086 --> 00:18:21.436 A:middle
We ran this through our hash
function and it determines

00:18:21.436 --> 00:18:24.026 A:middle
that Tim Cook by the hash
belongs in bucket 2, great.

00:18:24.026 --> 00:18:24.616 A:middle
So we set him there.

00:18:25.316 --> 00:18:27.346 A:middle
We have Steve Jobs and
that gets determined to go

00:18:27.346 --> 00:18:29.006 A:middle
in bucket 0, great, no problem.

00:18:29.746 --> 00:18:31.486 A:middle
OK. Now we're going
to add Gil Amelio

00:18:31.836 --> 00:18:33.986 A:middle
and our hash function
decides that it goes

00:18:33.986 --> 00:18:35.306 A:middle
in the same bucket
as Steve Jobs.

00:18:35.306 --> 00:18:36.746 A:middle
We have a collision
in our hash table,

00:18:37.086 --> 00:18:38.546 A:middle
rather unfortunate
and somewhat awkward.

00:18:38.546 --> 00:18:43.276 A:middle
[laughter] In order to see if
we should insert this object,

00:18:43.486 --> 00:18:45.146 A:middle
we have to compare
so we check isEqual.

00:18:45.146 --> 00:18:47.776 A:middle
And in fact, we see that
Steve Jobs is not equal

00:18:47.776 --> 00:18:49.346 A:middle
to Gil Amelio, thank goodness.

00:18:50.156 --> 00:18:53.076 A:middle
And so what happens
is we move one aside

00:18:53.076 --> 00:18:53.956 A:middle
and we chain this together,

00:18:53.956 --> 00:18:56.316 A:middle
they both occupy the
same bucket, great.

00:18:56.876 --> 00:18:57.976 A:middle
Now we have Michael Spindler,

00:18:58.096 --> 00:18:59.926 A:middle
no collision here,
goes into bucket 5.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:19:00.266 --> 00:19:02.536 A:middle
We have John Sculley, and
once again we get a hash

00:19:02.536 --> 00:19:03.256 A:middle
table collision.

00:19:03.256 --> 00:19:05.976 A:middle
So the hash function decides
it goes in the same place.

00:19:05.976 --> 00:19:07.746 A:middle
So once again, we compare
each of these objects

00:19:07.746 --> 00:19:09.016 A:middle
to see if this is equal.

00:19:09.016 --> 00:19:11.736 A:middle
They are there not equal so we
move them aside and we stick

00:19:11.736 --> 00:19:12.516 A:middle
that in the same bucket.

00:19:12.796 --> 00:19:14.746 A:middle
So, this is all well and
good except you'll notice

00:19:14.796 --> 00:19:17.476 A:middle
that now the majority of my
objects are all in one bucket

00:19:17.476 --> 00:19:20.646 A:middle
in the hash table and half of my
hash table is completely empty.

00:19:20.646 --> 00:19:21.336 A:middle
I'm not using it.

00:19:21.576 --> 00:19:23.226 A:middle
This is obviously not optimal.

00:19:23.426 --> 00:19:25.456 A:middle
If I have some sort of simple
query to see if someone is

00:19:25.456 --> 00:19:28.206 A:middle
in the list for example,
and my hash function happens

00:19:28.206 --> 00:19:30.876 A:middle
to navigate to the same bucket,
I now have to check through each

00:19:30.876 --> 00:19:33.446 A:middle
of those objects to see if
they're equal to Bill Gates

00:19:33.446 --> 00:19:34.796 A:middle
to determine no he's
not in the table.

00:19:34.796 --> 00:19:37.106 A:middle
All right, so this is
definitely not optimal.

00:19:37.106 --> 00:19:39.706 A:middle
Fortunately, something
like NSSet can choose

00:19:39.896 --> 00:19:41.636 A:middle
to optimize the hash
function on the fly.

00:19:41.636 --> 00:19:43.686 A:middle
If it realizes that your
performance is not as good

00:19:43.686 --> 00:19:46.206 A:middle
as you could expect it
reserves the right to be able

00:19:46.206 --> 00:19:48.866 A:middle
to move objects around, to
change the hash function

00:19:48.866 --> 00:19:50.016 A:middle
and redistribute them evenly.

00:19:50.256 --> 00:19:51.726 A:middle
So here we're in a
much better situation

00:19:51.846 --> 00:19:54.096 A:middle
and our lookups are restored
to being really fast.

00:19:54.546 --> 00:19:55.616 A:middle
OK, great.

00:19:56.326 --> 00:19:58.246 A:middle
So how can you participate
in this?

00:19:58.246 --> 00:20:01.636 A:middle
Defining your identity for your
object is how you take part

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:19:58.246 --> 00:20:01.636 A:middle
Defining your identity for your
object is how you take part

00:20:01.636 --> 00:20:03.416 A:middle
of this hash-based identity.

00:20:04.046 --> 00:20:06.726 A:middle
So NSObject as I mentioned
defines an isEqual method

00:20:06.726 --> 00:20:09.006 A:middle
and a hash method and they're
functionally equivalent

00:20:09.006 --> 00:20:11.506 A:middle
to comparing the pointers,
the object addresses

00:20:11.506 --> 00:20:12.916 A:middle
for these two objects,

00:20:12.916 --> 00:20:14.696 A:middle
and returning just
the address itself.

00:20:15.906 --> 00:20:17.866 A:middle
Now, Apple-provided subclasses

00:20:17.866 --> 00:20:19.796 A:middle
of NSObject will override
this as necessary.

00:20:19.846 --> 00:20:23.006 A:middle
For example, NSString has its
own hash, NSDate, NSNumber

00:20:23.006 --> 00:20:26.916 A:middle
and so on, there's a variety
that do this, and in fact,

00:20:26.916 --> 00:20:29.856 A:middle
arrays, NSSets themselves also
have their own hash and isEqual.

00:20:30.606 --> 00:20:33.256 A:middle
Custom objects that you
create should choose

00:20:33.256 --> 00:20:34.166 A:middle
to override these methods

00:20:34.166 --> 00:20:36.676 A:middle
if pointer quality is not
sufficient for your needs.

00:20:36.676 --> 00:20:39.026 A:middle
For example, say that you
have two person objects

00:20:39.026 --> 00:20:40.466 A:middle
and you want them to
be considered equal

00:20:40.466 --> 00:20:43.366 A:middle
if the Social Security Number
is the same for both of them,

00:20:43.366 --> 00:20:44.196 A:middle
something to that effect.

00:20:44.596 --> 00:20:45.766 A:middle
And you can learn a
lot more about this.

00:20:45.766 --> 00:20:48.546 A:middle
This will be in the slides
for reference afterward

00:20:48.796 --> 00:20:51.626 A:middle
about objects comparison and
implementing these methods.

00:20:52.006 --> 00:20:54.266 A:middle
OK. There are a few rules
of the road if you're going

00:20:54.266 --> 00:20:55.716 A:middle
to implement these
on your own object.

00:20:56.326 --> 00:20:59.296 A:middle
If isEqual returns
true for two objects,

00:20:59.516 --> 00:21:01.946 A:middle
then the hash must be the
same for both of these.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:20:59.516 --> 00:21:01.946 A:middle
then the hash must be the
same for both of these.

00:21:02.386 --> 00:21:04.226 A:middle
This is critical because
if you have two objects

00:21:04.226 --> 00:21:05.976 A:middle
that should be the same but
have two different hashes,

00:21:06.236 --> 00:21:08.326 A:middle
they could get put in
different places in a hash table

00:21:08.536 --> 00:21:09.596 A:middle
and you won't be
able to find them

00:21:09.596 --> 00:21:10.306 A:middle
when you're looking for them.

00:21:10.306 --> 00:21:11.776 A:middle
You'll get incorrect results.

00:21:12.066 --> 00:21:14.696 A:middle
However, the same hash value
does not necessarily imply

00:21:14.956 --> 00:21:16.096 A:middle
that isEqual must be true.

00:21:16.636 --> 00:21:18.456 A:middle
You can have two objects
that have the same hash value

00:21:18.456 --> 00:21:20.346 A:middle
but isEqual will
be the tie breaker.

00:21:21.046 --> 00:21:23.336 A:middle
If you decide to
implement isEqual,

00:21:23.656 --> 00:21:26.266 A:middle
you really should also define
hash for this very reason

00:21:26.436 --> 00:21:28.536 A:middle
so that you can guarantee
that they are the same.

00:21:28.736 --> 00:21:30.756 A:middle
Now, a good hash as you're
implementing one should

00:21:30.756 --> 00:21:31.886 A:middle
minimize collisions.

00:21:32.226 --> 00:21:34.936 A:middle
A poor hash will really cause
your performance to tank.

00:21:35.276 --> 00:21:36.556 A:middle
All right, for example,
in the worst case,

00:21:36.556 --> 00:21:38.006 A:middle
let's say that you're
like, "I don't know

00:21:38.006 --> 00:21:39.996 A:middle
about this hash thing, I'm
just going to return one

00:21:39.996 --> 00:21:41.266 A:middle
for all of my objects."

00:21:41.576 --> 00:21:43.496 A:middle
They all have the same hash
which means they're all going

00:21:43.496 --> 00:21:45.196 A:middle
to go to the same
bucket in the hash table

00:21:45.446 --> 00:21:47.756 A:middle
which means you've now turned
an NSSet into an NSArray

00:21:48.016 --> 00:21:49.126 A:middle
and killed your performance.

00:21:50.296 --> 00:21:51.496 A:middle
That's the opposite
of what we want.

00:21:51.496 --> 00:21:54.606 A:middle
So we want to be careful
about that and we'll talk

00:21:54.606 --> 00:21:57.056 A:middle
about that in just a moment.

00:21:57.286 --> 00:22:00.336 A:middle
One other key important thing is
that when you have hash lookup,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:21:57.286 --> 00:22:00.336 A:middle
One other key important thing is
that when you have hash lookup,

00:22:00.336 --> 00:22:02.356 A:middle
your hashes really should
be stable and predictable.

00:22:02.566 --> 00:22:04.666 A:middle
If your hash tends
to change while it's

00:22:04.666 --> 00:22:06.096 A:middle
in the collection,
it's really bad.

00:22:06.096 --> 00:22:07.936 A:middle
You're not going to
be able to find it.

00:22:07.936 --> 00:22:08.996 A:middle
So there are two options really.

00:22:08.996 --> 00:22:11.256 A:middle
The first is not to modify
and object in a collection.

00:22:11.296 --> 00:22:14.446 A:middle
If you have a mutable string
and you've put it in as the key

00:22:14.446 --> 00:22:17.596 A:middle
or an object in a set, for
example, and you change

00:22:17.596 --> 00:22:19.366 A:middle
that string and the hash
will change and you're going

00:22:19.366 --> 00:22:21.916 A:middle
to have all sorts of hilarity
and hair-pulling that ensues.

00:22:22.366 --> 00:22:25.496 A:middle
The second option is to not
base your hash on mutable state.

00:22:25.636 --> 00:22:27.386 A:middle
This may be an option for you
'cause that's something they

00:22:27.386 --> 00:22:28.026 A:middle
consider as well.

00:22:28.136 --> 00:22:30.136 A:middle
So let me show you
sample implementation.

00:22:30.386 --> 00:22:32.946 A:middle
You all have the WWDC app
on your phones and iPads

00:22:33.226 --> 00:22:34.576 A:middle
and there is a news object,

00:22:34.856 --> 00:22:36.656 A:middle
as you see in the news
update throughout the week,

00:22:36.656 --> 00:22:38.196 A:middle
we have these news
objects to represent that.

00:22:38.196 --> 00:22:39.646 A:middle
This is a simplified
representation.

00:22:39.646 --> 00:22:41.786 A:middle
Here we're just looking as
the title and the time stamp.

00:22:41.866 --> 00:22:44.256 A:middle
So I want to focus on
these two implementations.

00:22:44.256 --> 00:22:47.026 A:middle
Now, for hash, you see that we
need to return some hash value

00:22:47.026 --> 00:22:49.696 A:middle
and we're just returning the
hash that NSString provides us

00:22:49.696 --> 00:22:50.576 A:middle
from this title property.

00:22:51.316 --> 00:22:53.966 A:middle
However, if we have
two news items

00:22:53.966 --> 00:22:56.206 A:middle
that may have the same title
and thus have the same hash,

00:22:56.446 --> 00:22:58.466 A:middle
we can break the tie
by calling isEqual

00:22:58.746 --> 00:23:00.976 A:middle
and compare both the
title and the time stamp.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:22:58.746 --> 00:23:00.976 A:middle
and compare both the
title and the time stamp.

00:23:01.086 --> 00:23:02.716 A:middle
Let me also check to see
if it's the same object.

00:23:02.806 --> 00:23:05.806 A:middle
So, there are a lot of
examples of things like this

00:23:05.806 --> 00:23:08.776 A:middle
in the documentation
that I encourage you

00:23:09.506 --> 00:23:12.646 A:middle
to check out afterward.

00:23:12.726 --> 00:23:14.166 A:middle
OK. So next I want
to talk to you

00:23:14.246 --> 00:23:15.746 A:middle
about data structures
performance,

00:23:15.806 --> 00:23:16.866 A:middle
kind of applying
what we've learned.

00:23:17.026 --> 00:23:18.406 A:middle
We've got the map view
part out of the way

00:23:18.406 --> 00:23:20.446 A:middle
about Big O complexity
and hashes and so on.

00:23:20.446 --> 00:23:21.636 A:middle
So I'm going to talk
to you a little

00:23:21.636 --> 00:23:23.116 A:middle
but about choosing
data structures

00:23:23.116 --> 00:23:24.126 A:middle
and choosing data structures

00:23:24.126 --> 00:23:25.306 A:middle
and the performance
characteristics about them.

00:23:25.306 --> 00:23:26.516 A:middle
So let's start with an analogy.

00:23:26.516 --> 00:23:28.566 A:middle
Say that you have books
that you need to organize.

00:23:28.946 --> 00:23:29.926 A:middle
There's a lot of different ways

00:23:29.926 --> 00:23:31.466 A:middle
that you could choose
to organize books.

00:23:32.416 --> 00:23:34.496 A:middle
Say you could sort them
by topic or author,

00:23:34.716 --> 00:23:35.996 A:middle
title, even size or color.

00:23:35.996 --> 00:23:37.956 A:middle
You can choose an arbitrary
characteristic and choose

00:23:37.956 --> 00:23:38.766 A:middle
to sort them that way.

00:23:39.046 --> 00:23:40.896 A:middle
Everyone does this with
their CD collections

00:23:41.016 --> 00:23:42.696 A:middle
and the iTunes have
solved that problem now.

00:23:43.286 --> 00:23:44.716 A:middle
But everyone has their
own preferred way

00:23:44.886 --> 00:23:46.096 A:middle
to sort things and
organize them.

00:23:46.836 --> 00:23:49.446 A:middle
However, each of these options
makes some things really easy

00:23:49.766 --> 00:23:50.656 A:middle
and others difficult.

00:23:50.656 --> 00:23:52.616 A:middle
Say that you've chosen to
organize alphabetically

00:23:52.616 --> 00:23:54.336 A:middle
by author and then
later you want

00:23:54.336 --> 00:23:56.376 A:middle
to find all the New York
Times' best sellers,

00:23:56.566 --> 00:23:58.816 A:middle
or you want to find children's
books, those are scattered all

00:23:58.816 --> 00:24:01.326 A:middle
over in your collection and
it's not easy to look them

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:23:58.816 --> 00:24:01.326 A:middle
over in your collection and
it's not easy to look them

00:24:01.326 --> 00:24:02.336 A:middle
up when they're sorted
by author.

00:24:02.396 --> 00:24:03.456 A:middle
So this is something
to be aware of.

00:24:03.456 --> 00:24:06.386 A:middle
It's also important to plan
for scale when appropriate

00:24:06.386 --> 00:24:07.576 A:middle
as you're choosing
your data structures.

00:24:07.576 --> 00:24:10.216 A:middle
For example, it's a
completely different thing

00:24:10.216 --> 00:24:12.536 A:middle
to organize a small bookshelf
here where you can say,

00:24:12.536 --> 00:24:13.856 A:middle
"Go find the small green book"

00:24:13.856 --> 00:24:16.026 A:middle
and instantly you've all
found it because it's small

00:24:16.706 --> 00:24:18.696 A:middle
versus organizing a
really large library.

00:24:18.926 --> 00:24:21.206 A:middle
Things that will work at small
scale may not necessarily

00:24:21.206 --> 00:24:22.736 A:middle
when you get to large
amounts of data.

00:24:23.376 --> 00:24:25.356 A:middle
You have to have a
more intelligent way

00:24:25.356 --> 00:24:26.116 A:middle
to organize things.

00:24:26.226 --> 00:24:27.996 A:middle
So, choosing a strategy,

00:24:28.296 --> 00:24:30.306 A:middle
every data structure
has some tradeoffs.

00:24:30.306 --> 00:24:31.786 A:middle
It has things that
it's best at and things

00:24:31.786 --> 00:24:32.966 A:middle
that is not as well suited for.

00:24:33.336 --> 00:24:35.166 A:middle
And you want to use the one
that best fits your needs.

00:24:35.586 --> 00:24:37.796 A:middle
When you choose a data structure
that's not the best fit,

00:24:37.796 --> 00:24:40.086 A:middle
it really hurts your
performance, for example,

00:24:40.086 --> 00:24:41.616 A:middle
using a hammer to
drive in a screw,

00:24:41.846 --> 00:24:43.596 A:middle
not the ideal tool
for the situation.

00:24:43.946 --> 00:24:45.256 A:middle
Even if you have the right tool,

00:24:45.466 --> 00:24:46.846 A:middle
you may not be using
it optimally.

00:24:46.986 --> 00:24:49.186 A:middle
And if you have a hammer with
the nail and you just pressed

00:24:49.186 --> 00:24:53.086 A:middle
down really hardly as hard as
you can, it's not going to be

00:24:53.086 --> 00:24:55.026 A:middle
as effective as whacking
that really hard, right?

00:24:55.026 --> 00:24:56.956 A:middle
So, it's really important
to choose the right thing

00:24:56.956 --> 00:24:58.646 A:middle
for your needs and
use it correctly.

00:24:58.646 --> 00:25:01.236 A:middle
And we encourage
you to always prefer

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:24:58.646 --> 00:25:01.236 A:middle
And we encourage
you to always prefer

00:25:01.236 --> 00:25:03.236 A:middle
to use the built-in
API whenever possible.

00:25:03.566 --> 00:25:04.846 A:middle
The collections that
are available

00:25:04.846 --> 00:25:06.936 A:middle
on the foundation framework
are extensively tested.

00:25:06.936 --> 00:25:08.246 A:middle
They've been around for years.

00:25:08.596 --> 00:25:10.656 A:middle
We use them just as much
as you do and we want them

00:25:10.656 --> 00:25:14.206 A:middle
to be really, really fast
just as much as you do.

00:25:14.206 --> 00:25:17.586 A:middle
This also-- using the built-in
frameworks also guarantees

00:25:17.796 --> 00:25:20.066 A:middle
that in the future when we have
improvements such as you'll see

00:25:20.066 --> 00:25:21.746 A:middle
in OS X Mavericks and in iOS 7,

00:25:21.746 --> 00:25:24.806 A:middle
that you will also get
those improvements for free.

00:25:25.046 --> 00:25:27.706 A:middle
Your apps will suddenly
become faster which is great.

00:25:28.766 --> 00:25:31.516 A:middle
So, getting down to actually
choosing a data structure,

00:25:31.516 --> 00:25:33.586 A:middle
there's a few things you
have to know for context.

00:25:33.586 --> 00:25:35.176 A:middle
The first is knowing
what you need.

00:25:36.076 --> 00:25:37.906 A:middle
Is it important that my
object have an order?

00:25:38.366 --> 00:25:39.956 A:middle
Will I have duplicates
in my collection?

00:25:40.296 --> 00:25:42.656 A:middle
Do I have to be able to add or
remove objects, have it mutable?

00:25:43.276 --> 00:25:44.496 A:middle
What operations are
most critical

00:25:44.496 --> 00:25:45.746 A:middle
for me to be really fast?

00:25:45.746 --> 00:25:47.156 A:middle
What am I going to be
doing with my structure?

00:25:47.396 --> 00:25:50.096 A:middle
And even where my data come
from and go to, for example,

00:25:50.096 --> 00:25:52.116 A:middle
you may choose differently
if your data will come

00:25:52.116 --> 00:25:55.416 A:middle
from user input or from a
property list file or Core Data

00:25:55.706 --> 00:25:57.166 A:middle
or JSON over the web or so on.

00:25:57.486 --> 00:25:59.306 A:middle
There's certain things that
may change your decision.

00:25:59.306 --> 00:26:01.706 A:middle
And the second thing is
to know what to expect

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:25:59.306 --> 00:26:01.706 A:middle
And the second thing is
to know what to expect

00:26:01.876 --> 00:26:03.606 A:middle
from your collection, which
we'll go into in detail.

00:26:03.606 --> 00:26:05.056 A:middle
There are certain
things that are broadly

00:26:05.056 --> 00:26:06.316 A:middle
to across all of
our collections.

00:26:06.366 --> 00:26:08.026 A:middle
For example, getting
the count of items

00:26:08.026 --> 00:26:09.976 A:middle
in a collection is
always really fast.

00:26:09.976 --> 00:26:10.816 A:middle
It's constant time.

00:26:10.816 --> 00:26:12.756 A:middle
We cache that for you because
that's a common operation.

00:26:13.296 --> 00:26:14.686 A:middle
Enumerating through
all the objects

00:26:14.686 --> 00:26:17.346 A:middle
in a collection is generally
linear time because you have

00:26:17.346 --> 00:26:18.746 A:middle
to visit each of the objects.

00:26:18.896 --> 00:26:21.346 A:middle
Even if you have a set or
dictionary, look up this fast

00:26:21.496 --> 00:26:22.436 A:middle
but going through
each on this going

00:26:22.436 --> 00:26:23.296 A:middle
to take the same out of time.

00:26:23.646 --> 00:26:25.996 A:middle
And other operations will
vary by the collection.

00:26:25.996 --> 00:26:28.786 A:middle
So, before we go over
individual data structures,

00:26:28.786 --> 00:26:30.796 A:middle
I want to share this and
note about mutability.

00:26:31.106 --> 00:26:33.166 A:middle
The best guideline with
mutability, we got a lot

00:26:33.166 --> 00:26:35.746 A:middle
of questions about this, is
to use it when you need it,

00:26:35.816 --> 00:26:37.646 A:middle
when it's semantically
correct, when you're adding

00:26:37.646 --> 00:26:39.126 A:middle
and removing objects
from a collection.

00:26:39.766 --> 00:26:41.566 A:middle
And mutable collections
do have benefits.

00:26:41.596 --> 00:26:44.366 A:middle
If you don't need mutability,
it can be to your benefit

00:26:44.366 --> 00:26:45.966 A:middle
to use an immutable
collection instead.

00:26:46.356 --> 00:26:50.876 A:middle
Most foremost among these
benefits is thread safety.

00:26:51.116 --> 00:26:54.186 A:middle
If a collection is
immutable such as an NSArray,

00:26:54.186 --> 00:26:56.386 A:middle
you know that no other thread
can add or remove objects

00:26:56.566 --> 00:26:58.696 A:middle
and you don't have to worry
about exceptions or crashes.

00:26:59.556 --> 00:27:01.996 A:middle
Also, there are memory and speed
optimizations that are possible

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:26:59.556 --> 00:27:01.996 A:middle
Also, there are memory and speed
optimizations that are possible

00:27:02.146 --> 00:27:03.276 A:middle
with immutable collections

00:27:03.276 --> 00:27:04.966 A:middle
because we know they're not
going to change in size.

00:27:05.186 --> 00:27:07.406 A:middle
We can allocate just the
exact right amount of memory

00:27:07.406 --> 00:27:08.886 A:middle
for the objects that
you've provided.

00:27:10.446 --> 00:27:14.716 A:middle
Now, another option is to make a
collection immutable afterwards.

00:27:15.166 --> 00:27:17.836 A:middle
Make a copy of it that you
can use for quick reference

00:27:17.836 --> 00:27:19.836 A:middle
and get those benefits
but still be able to build

00:27:19.836 --> 00:27:21.796 A:middle
up your collection
without a remove.

00:27:22.346 --> 00:27:26.066 A:middle
And lastly, if you do use
immutability, it's often great

00:27:26.066 --> 00:27:27.346 A:middle
if you can help us to help you.

00:27:27.666 --> 00:27:29.506 A:middle
You know how your
collection is being used.

00:27:29.606 --> 00:27:32.366 A:middle
We design it for a broad
range of different uses

00:27:32.576 --> 00:27:34.356 A:middle
and you know specifically where
you're going to do with it.

00:27:34.476 --> 00:27:36.606 A:middle
And there's times that you can
provide hence help us get you

00:27:36.606 --> 00:27:37.766 A:middle
the best performance.

00:27:37.766 --> 00:27:39.626 A:middle
One example is initializing
a collection

00:27:39.626 --> 00:27:40.796 A:middle
with initWithCapacity.

00:27:41.306 --> 00:27:43.136 A:middle
Now, what this does is
gives us kind of a hint

00:27:43.366 --> 00:27:45.446 A:middle
about how many objects
you're likely to store

00:27:45.666 --> 00:27:46.506 A:middle
in a given collection.

00:27:46.926 --> 00:27:49.556 A:middle
So for example, if you say "I'm
only going to store three items

00:27:49.556 --> 00:27:51.226 A:middle
in this mutable array
and add and remove them",

00:27:51.446 --> 00:27:53.076 A:middle
you can provide that
capacity upfront

00:27:53.266 --> 00:27:54.506 A:middle
and we can optimize
it accordingly.

00:27:55.196 --> 00:27:57.936 A:middle
Now, don't-- It's not wise to
try to outsmart the collections

00:27:57.936 --> 00:28:00.016 A:middle
and ask for a really
large capacity.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:27:57.936 --> 00:28:00.016 A:middle
and ask for a really
large capacity.

00:28:00.266 --> 00:28:01.836 A:middle
The collections are
really finally tuned

00:28:01.836 --> 00:28:03.356 A:middle
and optimized to
take care of that.

00:28:03.636 --> 00:28:05.806 A:middle
And even if you do provide
the capacity hint upfront,

00:28:06.016 --> 00:28:07.966 A:middle
the collection can
dynamically grow and shrink

00:28:07.966 --> 00:28:09.566 A:middle
as objects were added
and removed.

00:28:09.666 --> 00:28:11.646 A:middle
So this just provides us an
upfront way to kind of get

00:28:11.646 --> 00:28:12.786 A:middle
in the ballpark of
what you need.

00:28:12.826 --> 00:28:15.976 A:middle
OK. So I'm going to go
on a quick tour of some

00:28:15.976 --> 00:28:20.196 A:middle
of the data structures
in foundations

00:28:20.196 --> 00:28:21.346 A:middle
in the most valuable players.

00:28:21.506 --> 00:28:22.666 A:middle
Give you a brief
overview and talk

00:28:22.666 --> 00:28:24.736 A:middle
about their performance
characteristics.

00:28:24.736 --> 00:28:26.406 A:middle
First, NSArray and MutableArray.

00:28:26.656 --> 00:28:27.526 A:middle
You're all familiar with this.

00:28:27.526 --> 00:28:29.506 A:middle
It's a work host of
the Cocoa library.

00:28:30.436 --> 00:28:31.806 A:middle
It's an order collection.

00:28:32.106 --> 00:28:34.876 A:middle
It always indexed access and
you can have duplicate objects

00:28:34.876 --> 00:28:35.256 A:middle
in an array.

00:28:36.366 --> 00:28:38.346 A:middle
Operations that are
really fast are anything

00:28:38.346 --> 00:28:40.656 A:middle
that includes indexing:
objectAtIndex,

00:28:40.956 --> 00:28:42.396 A:middle
the firstObject and lastObject.

00:28:42.686 --> 00:28:45.006 A:middle
Adding and removing
at either end

00:28:45.006 --> 00:28:47.246 A:middle
of a mutable array is
actually really fast as well.

00:28:47.436 --> 00:28:49.196 A:middle
This may come as
a surprise adding

00:28:49.196 --> 00:28:50.986 A:middle
at the end would seem really
fast but you may think

00:28:50.986 --> 00:28:52.046 A:middle
that if you had at the
beginning you'd have

00:28:52.046 --> 00:28:53.136 A:middle
to shift everything over.

00:28:53.456 --> 00:28:55.716 A:middle
However, that tends to
be a common use case

00:28:55.716 --> 00:28:56.906 A:middle
for a lot of our developers.

00:28:57.096 --> 00:28:58.806 A:middle
So we've optimized
that and we've--

00:28:58.806 --> 00:29:00.666 A:middle
even the guarantee that
inserting at the front,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:28:58.806 --> 00:29:00.666 A:middle
even the guarantee that
inserting at the front,

00:29:00.816 --> 00:29:02.966 A:middle
the very front of a mutable
array is also really fast.

00:29:02.966 --> 00:29:04.496 A:middle
It's such a great thing
to be aware of as well,

00:29:04.496 --> 00:29:05.856 A:middle
to not be afraid to
insert in the front.

00:29:06.546 --> 00:29:09.446 A:middle
Slower operations include
anything that involves search

00:29:09.446 --> 00:29:10.926 A:middle
and looking through
any of these indexes

00:29:10.926 --> 00:29:12.126 A:middle
as we've already
mentioned before.

00:29:12.406 --> 00:29:15.296 A:middle
Also, adding and removing at
an arbitrary index somewhere

00:29:15.426 --> 00:29:17.346 A:middle
in the middle of the array,
not either of the ends,

00:29:17.496 --> 00:29:19.416 A:middle
would tend to be a
little bit slower.

00:29:19.416 --> 00:29:22.346 A:middle
One specialty operation I'd
like to call is binary search.

00:29:22.586 --> 00:29:23.626 A:middle
If you're not familiar
with this,

00:29:23.626 --> 00:29:26.836 A:middle
binary search is a quick way
to narrow down your search.

00:29:27.146 --> 00:29:28.196 A:middle
There are a couple
pre-conditions.

00:29:28.196 --> 00:29:30.536 A:middle
You have to have some
sorted range of data.

00:29:30.536 --> 00:29:33.776 A:middle
So if I know that my array is
already sorted in ascending

00:29:33.776 --> 00:29:37.406 A:middle
or descending order, I could use
binary search to quickly narrow

00:29:37.406 --> 00:29:40.436 A:middle
down and cut out half of
the objects each time.

00:29:40.786 --> 00:29:44.536 A:middle
And this is a great win because
this is an order login operation

00:29:44.536 --> 00:29:45.486 A:middle
as compared to order in.

00:29:45.486 --> 00:29:48.076 A:middle
if you remember from the graph,
order in was a line that goes

00:29:48.076 --> 00:29:49.396 A:middle
up at a 45-degree angle

00:29:49.516 --> 00:29:52.656 A:middle
and order login stays
really close to the bottom.

00:29:52.656 --> 00:29:57.976 A:middle
It's got great performance
as your objects has a scale.

00:29:58.046 --> 00:29:59.736 A:middle
Next is NSSet and NSMutableSet.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:30:00.526 --> 00:30:03.616 A:middle
This is an unordered collection,
it does not allow duplicates,

00:30:03.616 --> 00:30:05.926 A:middle
and it has hash-based lookup
as we discussed previously.

00:30:07.086 --> 00:30:09.486 A:middle
In sense, adding,
removing and searching

00:30:09.486 --> 00:30:10.916 A:middle
for objects are really fast,

00:30:11.006 --> 00:30:12.516 A:middle
precisely because of
the hash-based lookup.

00:30:13.116 --> 00:30:14.496 A:middle
Now, there are some
specialty operations

00:30:14.496 --> 00:30:16.006 A:middle
that are really convenient
on NSSet.

00:30:16.256 --> 00:30:18.216 A:middle
For example, set arithmetic.

00:30:18.216 --> 00:30:20.376 A:middle
If you think of a Venn diagram
where you've got two circles

00:30:20.376 --> 00:30:22.516 A:middle
that overlap, you can find
the intersection between them,

00:30:22.736 --> 00:30:24.666 A:middle
you can see who one is
completely containing the other

00:30:24.666 --> 00:30:25.056 A:middle
and so on.

00:30:25.306 --> 00:30:27.546 A:middle
And if you have mutable
sets, you can extend this

00:30:27.766 --> 00:30:31.116 A:middle
and intersect the set
and modify one set

00:30:31.476 --> 00:30:33.506 A:middle
to only contain the objects
that also appear in another set

00:30:33.646 --> 00:30:35.476 A:middle
or minus set or union
set and so on.

00:30:35.476 --> 00:30:36.936 A:middle
This can be really
convenient for merging

00:30:36.936 --> 00:30:39.176 A:middle
and separating different
collections of objects.

00:30:39.266 --> 00:30:39.996 A:middle
Good thing to be aware of.

00:30:40.666 --> 00:30:43.676 A:middle
Caveats with NSSet, when
you convert from an array

00:30:43.676 --> 00:30:47.166 A:middle
to an NSSet, you can do that
but you do lose your ordering

00:30:47.316 --> 00:30:49.556 A:middle
of the array and you
lose any duplicates

00:30:49.556 --> 00:30:50.756 A:middle
that may appear in the array.

00:30:50.916 --> 00:30:52.206 A:middle
Those will be stripped
out with the set.

00:30:52.456 --> 00:30:55.446 A:middle
If you convert back to an array,
you may get a smaller array

00:30:55.446 --> 00:30:57.566 A:middle
and you almost certainly get
one that's in a different order

00:30:57.736 --> 00:30:58.746 A:middle
that the one you passed in.

00:30:59.546 --> 00:31:02.126 A:middle
Related to this is that you
can't store a set directly

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:30:59.546 --> 00:31:02.126 A:middle
Related to this is that you
can't store a set directly

00:31:02.126 --> 00:31:04.216 A:middle
in a property list or
in JSON as we'll talk

00:31:04.216 --> 00:31:06.306 A:middle
about in a little bit.

00:31:06.546 --> 00:31:10.086 A:middle
You can convert to an array and
back as you're reading them out,

00:31:10.246 --> 00:31:11.706 A:middle
but these are caveats
to be aware of.

00:31:12.196 --> 00:31:14.336 A:middle
OK. A brief of note
on NSCountedSet.

00:31:14.336 --> 00:31:16.356 A:middle
This is really a handy one
that many people are not aware.

00:31:16.866 --> 00:31:18.626 A:middle
It's also unordered
just a like a set,

00:31:18.626 --> 00:31:19.976 A:middle
no duplicates and hash lookup.

00:31:20.476 --> 00:31:22.096 A:middle
It's a subclass of NSMutableSet

00:31:22.096 --> 00:31:23.546 A:middle
so it has all the
same operations

00:31:23.546 --> 00:31:25.076 A:middle
and the same characteristics.

00:31:25.076 --> 00:31:27.996 A:middle
Its big trick though is it
attracts the net insertion count

00:31:27.996 --> 00:31:28.806 A:middle
of each object.

00:31:29.106 --> 00:31:32.266 A:middle
So, object still only appear
once in a count of set, however,

00:31:32.266 --> 00:31:33.846 A:middle
if you insert the
same object again,

00:31:33.846 --> 00:31:36.116 A:middle
the count for that object will
increase to two and so on.

00:31:36.116 --> 00:31:37.606 A:middle
If you remove that
object, it decreases

00:31:37.806 --> 00:31:39.036 A:middle
and if it's removed it set 0.

00:31:39.406 --> 00:31:41.236 A:middle
This can be really convenient
if you're trying to count

00:31:41.236 --> 00:31:43.166 A:middle
up occurrences of a
particular object.

00:31:43.166 --> 00:31:45.756 A:middle
It may be words and text
or something like that.

00:31:46.436 --> 00:31:48.696 A:middle
It's kind of a histogram
binning type of thing,

00:31:48.936 --> 00:31:49.856 A:middle
so great thing to be aware of.

00:31:50.566 --> 00:31:52.586 A:middle
Next is NSDictionary
and NSMutableDictionary.

00:31:52.836 --> 00:31:54.096 A:middle
This you're also
very familiar with.

00:31:54.476 --> 00:31:57.626 A:middle
It's an unordered collection,
it has key value entries

00:31:57.816 --> 00:31:59.176 A:middle
to store those associated
together,

00:31:59.656 --> 00:32:01.146 A:middle
it has unique key values,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:31:59.656 --> 00:32:01.146 A:middle
it has unique key values,

00:32:01.226 --> 00:32:03.066 A:middle
and it uses hash lookup
just a like a set.

00:32:03.206 --> 00:32:07.506 A:middle
So, adding, removing and
searching are also really fast

00:32:07.506 --> 00:32:09.276 A:middle
in the dictionary, anything
where you're looking

00:32:09.606 --> 00:32:12.136 A:middle
for an object by the key, adding
or removing and searching.

00:32:12.956 --> 00:32:15.526 A:middle
Specialty operations, one thing
that's convenient is it has some

00:32:15.726 --> 00:32:17.636 A:middle
handy API for reading
and writing directly

00:32:17.636 --> 00:32:18.796 A:middle
from a property list file.

00:32:19.416 --> 00:32:21.516 A:middle
And also one other thing
that was added in 10.8

00:32:21.516 --> 00:32:22.956 A:middle
in iOS 6 is really handy.

00:32:23.496 --> 00:32:26.326 A:middle
If you have a mutable
array and you know upfront

00:32:26.326 --> 00:32:29.386 A:middle
which keys will ever appear in
this mutable dictionary, sorry,

00:32:29.386 --> 00:32:32.266 A:middle
mutable dictionary, you can
provide a key set in array

00:32:32.266 --> 00:32:33.396 A:middle
of those keys upfront.

00:32:33.706 --> 00:32:35.326 A:middle
And there's a class
method on the NSDictionary.

00:32:35.546 --> 00:32:36.526 A:middle
You give it an array of keys,

00:32:36.526 --> 00:32:38.716 A:middle
it will give you a
sharedKeySet object.

00:32:39.026 --> 00:32:41.816 A:middle
If you provide that one
creating an NSMutableDictionary,

00:32:42.246 --> 00:32:44.976 A:middle
it can create a really
optimal hash algorithm

00:32:44.976 --> 00:32:47.636 A:middle
for organizing those
particular keys.

00:32:47.636 --> 00:32:49.356 A:middle
It knows upfront what's
likely to be there.

00:32:49.536 --> 00:32:52.016 A:middle
And it can be a great
situation if you need mutability

00:32:52.016 --> 00:32:54.056 A:middle
but you want speed and you
know the keys you're going

00:32:54.056 --> 00:32:54.566 A:middle
to have upfront.

00:32:55.326 --> 00:32:58.256 A:middle
Caveats of NSDictionary, you're
probably familiar with the fact

00:32:58.396 --> 00:32:59.556 A:middle
that any keys that you provide

00:32:59.556 --> 00:33:01.926 A:middle
to NSDictionary are
going to be copied in.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:32:59.556 --> 00:33:01.926 A:middle
to NSDictionary are
going to be copied in.

00:33:02.306 --> 00:33:05.556 A:middle
They have to conform to
the NSCopying Protocol.

00:33:06.156 --> 00:33:09.016 A:middle
And you should never mutate an
object that is a dictionary key.

00:33:09.336 --> 00:33:12.116 A:middle
The hash will change very likely
and you probably won't be able

00:33:12.116 --> 00:33:13.726 A:middle
to find it and you'll
get incorrect results.

00:33:13.726 --> 00:33:16.756 A:middle
This is a major thing
to be aware of.

00:33:16.756 --> 00:33:17.486 A:middle
NSOrderedSet

00:33:17.486 --> 00:33:21.366 A:middle
and NSMutableOrderedSet
are an ordered collection,

00:33:21.366 --> 00:33:23.896 A:middle
similar to arrays, they don't
allow duplicates like I said,

00:33:23.896 --> 00:33:26.306 A:middle
and they support both
index and hash-base lookup.

00:33:26.646 --> 00:33:31.356 A:middle
This class was introduced in
iOS 7-- iOS 5 and OS X 10.7.

00:33:31.356 --> 00:33:34.446 A:middle
And it's effectively across
between a set and array.

00:33:34.936 --> 00:33:37.486 A:middle
It's not a subclass of either
one although you can get an

00:33:37.486 --> 00:33:40.506 A:middle
array or set representation
that one convenient thing

00:33:40.506 --> 00:33:42.066 A:middle
about this are their
live-updating.

00:33:42.316 --> 00:33:44.446 A:middle
So as objects are added or
remove to the mutable set,

00:33:44.446 --> 00:33:46.786 A:middle
those array and set
representations will be updated

00:33:46.786 --> 00:33:47.186 A:middle
as well.

00:33:47.976 --> 00:33:49.666 A:middle
Now, a caveat of this
is that you're going

00:33:49.666 --> 00:33:50.816 A:middle
to have increased memory usage.

00:33:50.816 --> 00:33:53.496 A:middle
You can't get the best of both
worlds with as a free launch.

00:33:53.756 --> 00:33:55.646 A:middle
So because we're
maintaining ordering,

00:33:55.836 --> 00:33:56.866 A:middle
we have an array internally.

00:33:56.866 --> 00:33:59.556 A:middle
And because we're
guaranteeing uniqueness

00:33:59.556 --> 00:34:01.336 A:middle
and no difficult objects,
we also have a set.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:33:59.556 --> 00:34:01.336 A:middle
and no difficult objects,
we also have a set.

00:34:01.596 --> 00:34:03.086 A:middle
So roughly double memory usage.

00:34:03.436 --> 00:34:06.256 A:middle
And also when you-- If you
want to store an ordered set

00:34:06.256 --> 00:34:08.235 A:middle
in a property list, you'd
have to convert it to an array

00:34:08.485 --> 00:34:11.585 A:middle
and then back as
you bring it out.

00:34:11.585 --> 00:34:13.456 A:middle
NSIndexSet and NSMutableIndexSet
differ

00:34:13.456 --> 00:34:15.826 A:middle
because they don't store
objects, they store indexes,

00:34:16.096 --> 00:34:18.985 A:middle
integer values, so it's a
collection of unique indexes

00:34:19.335 --> 00:34:22.376 A:middle
and these are really handy
for referencing some subset

00:34:22.376 --> 00:34:23.966 A:middle
of object in an NSArray.

00:34:24.565 --> 00:34:26.116 A:middle
And it's really handy especially

00:34:26.116 --> 00:34:28.795 A:middle
because you can avoid the
memory overhead of making a copy

00:34:28.795 --> 00:34:31.186 A:middle
or saying objects at indexes,
you can give it an index set

00:34:31.186 --> 00:34:33.806 A:middle
and it gives you a new
auto released array

00:34:34.136 --> 00:34:35.176 A:middle
with those objects in it.

00:34:35.346 --> 00:34:37.926 A:middle
If you want to avoid that
overhead, you can just enumerate

00:34:37.926 --> 00:34:39.585 A:middle
through the objects
at particular indexes

00:34:39.585 --> 00:34:41.656 A:middle
without creating a new array
and it's really handy for that.

00:34:42.136 --> 00:34:44.045 A:middle
Index set has really
efficient storage

00:34:44.045 --> 00:34:45.806 A:middle
and coalescing of indexes.

00:34:45.996 --> 00:34:48.646 A:middle
So if you have a mutable index
set and you add the indexes 1

00:34:48.646 --> 00:34:50.126 A:middle
and 3, it will store
those separately.

00:34:50.416 --> 00:34:53.246 A:middle
If you add 2 as well, it's
intelligent enough to coalesce

00:34:53.246 --> 00:34:55.076 A:middle
and say, "I'm going to
store the range 1 to 3."

00:34:55.376 --> 00:34:57.606 A:middle
And if you add more indexes
that are consecutive,

00:34:57.686 --> 00:34:58.936 A:middle
it will group those altogether.

00:34:58.936 --> 00:35:00.316 A:middle
So it's really efficient
with storage.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:34:58.936 --> 00:35:00.316 A:middle
So it's really efficient
with storage.

00:35:00.876 --> 00:35:03.906 A:middle
It also supports set arithmetic
such as intersection, subset,

00:35:03.906 --> 00:35:06.326 A:middle
and difference like we
saw with mutable sets.

00:35:06.326 --> 00:35:09.066 A:middle
One caveat of this is when
you're using index set

00:35:09.066 --> 00:35:10.946 A:middle
and you apply it to
an NSMutableArray,

00:35:11.176 --> 00:35:13.906 A:middle
if that array changes after
you've obtain the index set,

00:35:13.906 --> 00:35:15.446 A:middle
you can have all
sorts of bad results.

00:35:15.446 --> 00:35:19.216 A:middle
For example, you have a mutable
array, you've gotten a group

00:35:19.216 --> 00:35:21.976 A:middle
of indexes, and then you
remove all the objects

00:35:21.976 --> 00:35:22.806 A:middle
or some of them in the array.

00:35:22.836 --> 00:35:24.316 A:middle
If you try to get
objects as indexes,

00:35:24.446 --> 00:35:25.656 A:middle
you can easily get
a range exception

00:35:25.656 --> 00:35:27.376 A:middle
because that index no
longer exists in array.

00:35:27.376 --> 00:35:29.916 A:middle
So this is something
to be aware of.

00:35:29.916 --> 00:35:31.956 A:middle
NSMapTable and NSHashTable
are very interesting.

00:35:32.116 --> 00:35:32.816 A:middle
They are very similar

00:35:32.816 --> 00:35:35.156 A:middle
to NSMutableDictionary
and NSMutablSet.

00:35:35.916 --> 00:35:38.026 A:middle
There's a couple
of key differences.

00:35:38.266 --> 00:35:40.146 A:middle
They offer a lot more
flexibility with some

00:35:40.146 --> 00:35:41.316 A:middle
of these additional options.

00:35:41.526 --> 00:35:43.606 A:middle
You can use pointer
identity rather than choosing

00:35:43.606 --> 00:35:45.686 A:middle
to use isEqual as you would
in these other collections.

00:35:46.016 --> 00:35:48.746 A:middle
It can contain any kind of
pointer not just in an object.

00:35:48.746 --> 00:35:50.186 A:middle
It could be a void
star or any kind

00:35:50.236 --> 00:35:51.286 A:middle
of pointer you can
store in here.

00:35:51.766 --> 00:35:54.726 A:middle
You can optionally say that you
want weak references so that

00:35:54.726 --> 00:35:57.166 A:middle
if all the strong references
to an object stored as a key

00:35:57.166 --> 00:35:58.776 A:middle
or value in a map table

00:35:58.776 --> 00:36:00.446 A:middle
for example should
those go away then

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:35:58.776 --> 00:36:00.446 A:middle
for example should
those go away then

00:36:00.446 --> 00:36:02.226 A:middle
that entry would automatically
be removed for you.

00:36:02.436 --> 00:36:05.246 A:middle
And this works under ARC as
well with zeroing references.

00:36:05.836 --> 00:36:08.446 A:middle
And you can optionally say that
you don't want to copy on insert

00:36:08.676 --> 00:36:12.046 A:middle
as you add an object to
a map table, for example,

00:36:12.046 --> 00:36:12.966 A:middle
it won't copy the key.

00:36:12.966 --> 00:36:14.856 A:middle
You can specify that.

00:36:15.226 --> 00:36:18.976 A:middle
Now, you can't convert a
map table or a hash table

00:36:18.976 --> 00:36:21.186 A:middle
that contains these
raw C pointers directly

00:36:21.186 --> 00:36:24.826 A:middle
to their counterpart,
mutable dictionary or so on,

00:36:25.106 --> 00:36:28.666 A:middle
because they don't translate
over well, and also a caution

00:36:28.666 --> 00:36:30.026 A:middle
to be aware of premature
optimization.

00:36:30.026 --> 00:36:31.706 A:middle
This is one of the situations
that where you think,

00:36:31.706 --> 00:36:35.306 A:middle
this is going to be just what I
need, but you'll sacrifice some

00:36:35.306 --> 00:36:38.786 A:middle
of your compatibility with APIs
that require an NSDictionary.

00:36:38.946 --> 00:36:41.246 A:middle
And for most cases, it's
probably not necessary.

00:36:41.246 --> 00:36:44.206 A:middle
It's a great tool to be aware
of but it's not something

00:36:44.206 --> 00:36:45.046 A:middle
that you're generally going.

00:36:45.046 --> 00:36:47.266 A:middle
This was also introduced
in OS X 10.5

00:36:47.596 --> 00:36:49.606 A:middle
and of course binding iOS
release you should be able

00:36:49.606 --> 00:36:51.976 A:middle
to use this broadly
throughout your applications.

00:36:52.116 --> 00:36:52.976 A:middle
And last is NSCache.

00:36:53.366 --> 00:36:55.186 A:middle
This is also similar
to NSMutableDictionary

00:36:55.456 --> 00:36:57.136 A:middle
and it's a great
tool to have as well.

00:36:57.726 --> 00:37:00.696 A:middle
Primarily, there's
a few big benefits.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:36:57.726 --> 00:37:00.696 A:middle
Primarily, there's
a few big benefits.

00:37:00.696 --> 00:37:03.446 A:middle
First and foremost is that
its thread safe unlike

00:37:03.446 --> 00:37:04.196 A:middle
in mutable dictionary.

00:37:04.426 --> 00:37:06.846 A:middle
It doesn't copy your keys
unlike in mutable dictionary

00:37:07.146 --> 00:37:09.446 A:middle
and it supports auto-removal
under memory pressure.

00:37:09.716 --> 00:37:11.166 A:middle
So when the OS needs
to reclaim memory,

00:37:11.166 --> 00:37:13.896 A:middle
it can automatically boot
out entries from this cache.

00:37:13.926 --> 00:37:15.956 A:middle
This is ideal for objects
that you can regenerate

00:37:15.956 --> 00:37:17.266 A:middle
or obtain again easily.

00:37:17.266 --> 00:37:18.526 A:middle
For more detail on this,

00:37:18.526 --> 00:37:21.036 A:middle
I highly recommend the talk
Building Efficient OS X apps.

00:37:21.276 --> 00:37:23.206 A:middle
A lot of this also
applies to iOS as well.

00:37:23.206 --> 00:37:26.736 A:middle
It focuses a lot on memory usage
and this [inaudible] and energy.

00:37:26.966 --> 00:37:28.996 A:middle
And it will go into match
more depth about NSCache

00:37:28.996 --> 00:37:31.906 A:middle
and purgeable table data and
what you can do to work well

00:37:31.906 --> 00:37:34.586 A:middle
and be a good citizen when
memory pressure comes to bear.

00:37:35.466 --> 00:37:37.506 A:middle
So, wrapping up these
data structures,

00:37:37.506 --> 00:37:39.866 A:middle
I have just two brief
asides as it relates

00:37:39.866 --> 00:37:41.396 A:middle
to data structures
and storing them.

00:37:41.446 --> 00:37:42.786 A:middle
So first property list.

00:37:42.786 --> 00:37:45.396 A:middle
You're all familiar with them
that you can store hierarchies

00:37:45.396 --> 00:37:47.676 A:middle
of data, XML or binary format.

00:37:47.826 --> 00:37:50.066 A:middle
Each of you at least has an
info.plist in your application

00:37:50.066 --> 00:37:51.636 A:middle
and may use them
in other places.

00:37:52.016 --> 00:37:53.786 A:middle
They support property
list objects.

00:37:53.786 --> 00:37:57.396 A:middle
It's a set of six objects in
foundation, arrays, data, date,

00:37:57.396 --> 00:37:58.896 A:middle
dictionary, number, and string.

00:37:59.446 --> 00:38:02.276 A:middle
Any others that you can, for
example, convert to a string,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:37:59.446 --> 00:38:02.276 A:middle
Any others that you can, for
example, convert to a string,

00:38:02.536 --> 00:38:05.146 A:middle
you would have to use NSCoding
and archive it into an NSData

00:38:05.146 --> 00:38:06.746 A:middle
and store it in the
property list.

00:38:07.866 --> 00:38:09.176 A:middle
So you do have flexibility
there.

00:38:09.426 --> 00:38:10.226 A:middle
It's good to be aware though

00:38:10.226 --> 00:38:11.676 A:middle
that mutability is
not preserved.

00:38:11.676 --> 00:38:13.846 A:middle
If I build up mutable
dictionaries and arrays

00:38:13.846 --> 00:38:16.246 A:middle
in a hierarchy that I like and
then store it to property list

00:38:16.556 --> 00:38:18.546 A:middle
and read it back out,
they're no longer mutable.

00:38:18.546 --> 00:38:20.246 A:middle
I'll get the immutable
variance to those.

00:38:20.336 --> 00:38:21.156 A:middle
That's important to know.

00:38:22.546 --> 00:38:24.676 A:middle
Property lists are generally
not efficient for lots

00:38:24.676 --> 00:38:27.006 A:middle
of binary data like
encoding things into NSData

00:38:27.006 --> 00:38:30.086 A:middle
and stick them in there, or for
really large files, particularly

00:38:30.086 --> 00:38:31.666 A:middle
if you're using and XML format.

00:38:32.106 --> 00:38:35.056 A:middle
There may be better
alternatives to look into.

00:38:35.176 --> 00:38:38.426 A:middle
You'll see property list
commonly with NSUserDefaults

00:38:38.426 --> 00:38:40.386 A:middle
for storing user preferences
for your application,

00:38:40.386 --> 00:38:42.116 A:middle
it's a common way
to interact with it.

00:38:42.516 --> 00:38:45.686 A:middle
NSPropertyListSerialization is
also a really handy way to deal

00:38:45.686 --> 00:38:48.776 A:middle
with this for input and
output of property list.

00:38:49.406 --> 00:38:51.956 A:middle
And I encourage you to
look at NSKeyedArchiver

00:38:51.956 --> 00:38:54.166 A:middle
and NSKeyedUnarchiver
if you have needs

00:38:54.166 --> 00:38:56.296 A:middle
to store other data
in a property list.

00:38:56.406 --> 00:38:57.716 A:middle
The second aside is on JSON.

00:38:58.136 --> 00:39:00.556 A:middle
This is JavaScript Object
Notation and originated

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:38:58.136 --> 00:39:00.556 A:middle
This is JavaScript Object
Notation and originated

00:39:00.556 --> 00:39:01.886 A:middle
in JavaScript but it's supported

00:39:01.886 --> 00:39:03.806 A:middle
across a broad variety
of platforms.

00:39:04.296 --> 00:39:06.926 A:middle
It's a lightweight data
interchange format that's human

00:39:06.926 --> 00:39:09.166 A:middle
readable and it's really
handy, and it's commonly used

00:39:09.166 --> 00:39:11.146 A:middle
for things like web
services or sending things

00:39:11.146 --> 00:39:12.296 A:middle
between different platforms.

00:39:12.626 --> 00:39:14.676 A:middle
And it works with a
few Foundation classes.

00:39:14.676 --> 00:39:16.026 A:middle
Some of them are
similar to property list.

00:39:16.026 --> 00:39:18.426 A:middle
You'll see array,
dictionary, number and string,

00:39:18.426 --> 00:39:19.606 A:middle
but there's also NSNull.

00:39:19.896 --> 00:39:22.086 A:middle
If you're not familiar with
this, this is null place holder.

00:39:22.316 --> 00:39:25.106 A:middle
Collections in Cocoa don't
allow you to store nil inside

00:39:25.106 --> 00:39:27.946 A:middle
of a collection, but JSON
does allow null objects,

00:39:27.946 --> 00:39:31.056 A:middle
and you'll see those transfer
across NSNull place folders.

00:39:31.486 --> 00:39:33.666 A:middle
And there are also
some restrictions

00:39:33.666 --> 00:39:37.156 A:middle
such as the top level object in
JSON needs to be a dictionary

00:39:37.156 --> 00:39:39.866 A:middle
and you can only use strings
for the keys in your dictionary.

00:39:39.866 --> 00:39:41.186 A:middle
You can't use numbers
or other things.

00:39:42.026 --> 00:39:45.666 A:middle
OK. And you should definitely
be aware of NSJSONSerialization.

00:39:45.666 --> 00:39:47.286 A:middle
This was introduced
a few releases ago

00:39:47.546 --> 00:39:51.646 A:middle
and it's a really convenient
way to deal with JSON.

00:39:51.966 --> 00:39:53.366 A:middle
It supports reading and writing.

00:39:53.366 --> 00:39:56.476 A:middle
You can even pass an object and
see if it will form valid JSON.

00:39:56.476 --> 00:39:59.266 A:middle
You can also specify
whether you want mutability

00:39:59.266 --> 00:40:01.206 A:middle
when you read objects
out of JSON

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:39:59.266 --> 00:40:01.206 A:middle
when you read objects
out of JSON

00:40:01.206 --> 00:40:02.896 A:middle
which is different
from property list.

00:40:03.056 --> 00:40:08.136 A:middle
And this class has been improved
and iterated a lot over time.

00:40:08.136 --> 00:40:10.126 A:middle
It's fast and it's built-in,
you don't have to link

00:40:10.126 --> 00:40:13.206 A:middle
in a static library,
for example, on iOS.

00:40:13.386 --> 00:40:16.666 A:middle
You can count on the
improvements to efficiency

00:40:16.666 --> 00:40:17.826 A:middle
and performance over time.

00:40:18.026 --> 00:40:19.336 A:middle
And you'll see even
more improvements

00:40:19.536 --> 00:40:22.746 A:middle
in iOS 7 and in Mavericks.

00:40:22.866 --> 00:40:25.326 A:middle
OK. So that wraps up about
data structure and performance.

00:40:25.646 --> 00:40:26.586 A:middle
That's a lot of information.

00:40:26.586 --> 00:40:29.426 A:middle
For our final section, I'm going
to kind of tie this all together

00:40:29.426 --> 00:40:31.086 A:middle
and talk about real
world applications.

00:40:31.086 --> 00:40:33.916 A:middle
How we can take all this about
"Big O" complexity and talking

00:40:33.916 --> 00:40:35.106 A:middle
about data structures
performance

00:40:35.106 --> 00:40:37.846 A:middle
and how fast they are and
apply that to my actual code.

00:40:37.846 --> 00:40:39.706 A:middle
So I'm going to give you
example again from our code.

00:40:39.706 --> 00:40:42.556 A:middle
From the WWDC App, we
refresh the sessions.

00:40:42.556 --> 00:40:43.796 A:middle
You all saw this on Monday.

00:40:43.996 --> 00:40:46.196 A:middle
You're anxiously waiting
for those TBAs to disappear

00:40:46.196 --> 00:40:47.676 A:middle
and see what the
sessions were going to be.

00:40:48.076 --> 00:40:49.896 A:middle
And we have this
functionality to refresh those.

00:40:49.926 --> 00:40:53.456 A:middle
So the data is stored and
Core Data on the application,

00:40:53.496 --> 00:40:55.516 A:middle
on your device, and we
periodically fetch updates

00:40:55.516 --> 00:40:57.486 A:middle
from the server to check
if there's new information.

00:40:58.016 --> 00:40:59.566 A:middle
Now, we did notice some
performances issues

00:40:59.566 --> 00:41:00.996 A:middle
in early versions
of the applications.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:40:59.566 --> 00:41:00.996 A:middle
in early versions
of the applications.

00:41:01.216 --> 00:41:02.506 A:middle
At first we were
getting great speed,

00:41:02.736 --> 00:41:05.456 A:middle
but as the conference
became more fleshed out

00:41:05.456 --> 00:41:06.456 A:middle
and more sessions were added,

00:41:06.576 --> 00:41:08.336 A:middle
the speed got progressively
slower

00:41:09.046 --> 00:41:11.176 A:middle
and noticeably slower
not just a little bit

00:41:11.176 --> 00:41:12.426 A:middle
but a lot more over time.

00:41:12.756 --> 00:41:13.946 A:middle
And it became kind
of unbearable.

00:41:14.226 --> 00:41:15.846 A:middle
And when we profile that
we found that's there was

00:41:15.846 --> 00:41:16.476 A:middle
non-linear growth.

00:41:16.476 --> 00:41:17.546 A:middle
We obviously had some sort

00:41:17.546 --> 00:41:19.186 A:middle
of complexity problem
doing too much work.

00:41:19.276 --> 00:41:21.296 A:middle
So I'm going to walk you
through a simple example here.

00:41:21.296 --> 00:41:23.276 A:middle
So this is what we did at first.

00:41:23.386 --> 00:41:26.126 A:middle
We have an array of sessions
that we get from the server,

00:41:26.156 --> 00:41:28.706 A:middle
we just fetched, and then we
iterate through each of those,

00:41:28.706 --> 00:41:31.066 A:middle
so we want to handle each
of these refreshed sessions

00:41:31.066 --> 00:41:32.906 A:middle
so we have a for loop
that's order and complexity.

00:41:33.406 --> 00:41:34.806 A:middle
And then we do a core data fetch

00:41:34.806 --> 00:41:37.096 A:middle
to see what we have
locally on our device.

00:41:37.236 --> 00:41:41.046 A:middle
We look for a session with that
particular ID and then we see

00:41:41.076 --> 00:41:42.466 A:middle
if I had a session with
that then I'm going

00:41:42.466 --> 00:41:43.166 A:middle
to merge them together.

00:41:43.166 --> 00:41:44.086 A:middle
If this is a new session,

00:41:44.086 --> 00:41:45.346 A:middle
I'm going to insert
it in the Core Data.

00:41:45.746 --> 00:41:47.266 A:middle
So we were seeing
non-linear performance.

00:41:47.466 --> 00:41:50.706 A:middle
And probably the suspicion
is this may be n squared.

00:41:51.036 --> 00:41:54.186 A:middle
Well, the for loop has to
be there and that the part

00:41:54.186 --> 00:41:55.906 A:middle
at the end about merging
sessions looks pretty simple.

00:41:55.906 --> 00:41:57.416 A:middle
So the work must be
somewhere in between,

00:41:57.746 --> 00:41:58.946 A:middle
right here in the
core data fetch.

00:41:59.066 --> 00:42:00.946 A:middle
And let's think about
what work it has to do.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:41:59.066 --> 00:42:00.946 A:middle
And let's think about
what work it has to do.

00:42:01.676 --> 00:42:04.146 A:middle
Well, we're forming a predicate
to search where we say,

00:42:04.656 --> 00:42:07.736 A:middle
"Find me a WWDC session
objection with the session ID

00:42:07.736 --> 00:42:09.566 A:middle
as equal to this
session I just gave you.

00:42:10.066 --> 00:42:11.716 A:middle
So when I tell core data
to do that, we think,

00:42:11.846 --> 00:42:12.856 A:middle
what would they have to do?

00:42:13.416 --> 00:42:16.486 A:middle
Well, because it may not have
ordering on the other side,

00:42:16.486 --> 00:42:18.216 A:middle
probably what it's doing
is it's going through each

00:42:18.216 --> 00:42:20.486 A:middle
of the sessions and seeing
if that session ID matches

00:42:20.906 --> 00:42:22.856 A:middle
which is an order
n algorithm, right?

00:42:22.856 --> 00:42:24.286 A:middle
So there we have
our hidden work.

00:42:24.286 --> 00:42:25.786 A:middle
We have an order
n loop and order n

00:42:25.786 --> 00:42:28.146 A:middle
for finding the session
as core data fetch.

00:42:28.546 --> 00:42:29.406 A:middle
That's where n squared is.

00:42:29.616 --> 00:42:32.006 A:middle
So, let's just hoist that right
out, let take the core data out,

00:42:32.006 --> 00:42:33.746 A:middle
we'll optimize that
a little bit.

00:42:33.746 --> 00:42:35.496 A:middle
Let's say that we now
change it so that instead

00:42:35.496 --> 00:42:37.946 A:middle
of fetching one session
at a time, we get the list

00:42:37.946 --> 00:42:40.356 A:middle
of session ideas that we've
just gotten and we fetch all

00:42:40.356 --> 00:42:41.246 A:middle
of those at the same time.

00:42:41.586 --> 00:42:43.696 A:middle
Now we have them all in
one array and that's great.

00:42:43.696 --> 00:42:44.326 A:middle
We should see order

00:42:44.326 --> 00:42:46.306 A:middle
and performance now,
except we don't.

00:42:47.036 --> 00:42:47.746 A:middle
If you have keen eyes,

00:42:47.746 --> 00:42:49.756 A:middle
you'll notice there's still
some work left inside the loop.

00:42:50.206 --> 00:42:52.656 A:middle
Now, although we know
what session it is

00:42:52.656 --> 00:42:54.006 A:middle
and we've just moved
the session--

00:42:54.006 --> 00:42:56.916 A:middle
the problem or the work
out of core data of finding

00:42:56.916 --> 00:42:58.176 A:middle
that session, we'd
moved into a line

00:42:58.176 --> 00:42:59.906 A:middle
where we're calling
index of object.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:43:00.016 --> 00:43:01.296 A:middle
Now we have an array
of all these sessions

00:43:01.296 --> 00:43:02.836 A:middle
but we're still doing
a linear search.

00:43:03.026 --> 00:43:04.646 A:middle
We're stepping through each
of these until we find the one

00:43:04.646 --> 00:43:05.436 A:middle
with the right session.

00:43:05.846 --> 00:43:07.456 A:middle
So, we haven't really
eliminated the problem.

00:43:08.146 --> 00:43:09.246 A:middle
But there is a great
way around it.

00:43:09.586 --> 00:43:12.526 A:middle
Since we're using session IDs
that are unique across these,

00:43:13.076 --> 00:43:14.426 A:middle
do a slight modification,

00:43:14.426 --> 00:43:16.136 A:middle
and after we've gotten all
those sessions upfront,

00:43:16.136 --> 00:43:18.706 A:middle
we create a dictionary where
the objects are the sessions

00:43:18.706 --> 00:43:20.616 A:middle
themselves and we key
them by the session ID.

00:43:20.916 --> 00:43:21.836 A:middle
This is going to be unique.

00:43:21.986 --> 00:43:24.876 A:middle
And now, inside the loop, you
can see that we just have look

00:43:24.876 --> 00:43:26.716 A:middle
at that dictionary
and find the one--

00:43:27.026 --> 00:43:28.936 A:middle
the session has that
particular session ID,

00:43:29.256 --> 00:43:32.236 A:middle
and look up in a dictionary is
order 1, it's no longer order n.

00:43:32.416 --> 00:43:33.336 A:middle
So we just solved our problem.

00:43:33.336 --> 00:43:35.906 A:middle
We've taken this algorithm from
order n squared to order n,

00:43:36.086 --> 00:43:39.216 A:middle
and now all of you can get your
session updates really quickly.

00:43:39.216 --> 00:43:40.996 A:middle
There's not 5,000 of
you waiting forever

00:43:40.996 --> 00:43:42.106 A:middle
for all those sessions
to reload.

00:43:42.176 --> 00:43:44.746 A:middle
So that's a real world example
from our own application.

00:43:45.786 --> 00:43:49.156 A:middle
So, I want to also
give a couple of tips

00:43:49.156 --> 00:43:50.446 A:middle
about eliminating extra work.

00:43:52.136 --> 00:43:54.306 A:middle
Really what you want to
do is minimize redundancy

00:43:54.366 --> 00:43:56.056 A:middle
and in particular
expensive code.

00:43:56.366 --> 00:43:58.346 A:middle
So what we just saw in the
previous example was each time

00:43:58.346 --> 00:43:59.496 A:middle
to the for loop we
we're searching

00:43:59.496 --> 00:44:01.886 A:middle
through the same array just
for a different session ID.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:43:59.496 --> 00:44:01.886 A:middle
through the same array just
for a different session ID.

00:44:02.536 --> 00:44:05.206 A:middle
If there's a way that we can
get that out of a loop and do

00:44:05.206 --> 00:44:08.156 A:middle
that work just once, do it less
frequently, that's a big one.

00:44:08.836 --> 00:44:11.476 A:middle
Also, take advantage of
faster lookup when possible

00:44:11.506 --> 00:44:12.776 A:middle
like we did at the NSDictionary.

00:44:12.856 --> 00:44:15.396 A:middle
Sets can also be useful for
this one, that's appropriate.

00:44:16.616 --> 00:44:18.306 A:middle
Using mutable collections
and strings

00:44:18.516 --> 00:44:21.486 A:middle
when it makes sense can also
be a big performance win.

00:44:21.486 --> 00:44:23.756 A:middle
And I'll show you an example
of that in just a moment.

00:44:23.756 --> 00:44:25.916 A:middle
And also streamline how
you access your data.

00:44:26.036 --> 00:44:28.536 A:middle
Don't make it hard for yourself
to get to the data that you need

00:44:28.676 --> 00:44:29.746 A:middle
as quickly as possible.

00:44:30.036 --> 00:44:31.596 A:middle
You can organize your
data in such a way

00:44:31.596 --> 00:44:33.106 A:middle
that it's structured
intelligently

00:44:33.106 --> 00:44:34.646 A:middle
and your lookup will
be really fast.

00:44:35.016 --> 00:44:38.126 A:middle
And again, try not to
reinvent the wheel.

00:44:38.246 --> 00:44:39.546 A:middle
There's times where you
need to write your own code

00:44:39.546 --> 00:44:42.806 A:middle
but there are situation, for
example, joining an array

00:44:42.806 --> 00:44:43.746 A:middle
of components with strings.

00:44:43.746 --> 00:44:45.966 A:middle
You may have a group of strings
that you want to comma separate.

00:44:46.386 --> 00:44:49.006 A:middle
You could write your own code to
do that and append into a string

00:44:49.006 --> 00:44:50.966 A:middle
and so on but there's already
API where you can give an array

00:44:50.966 --> 00:44:53.076 A:middle
of objects and give it
some string that you want

00:44:53.276 --> 00:44:55.076 A:middle
as the delimiter and it can
join them together for you.

00:44:55.156 --> 00:44:59.456 A:middle
So wherever possible,
use those as your benefit

00:44:59.456 --> 00:45:02.496 A:middle
from the optimizations and
eliminate extra work, you know,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:44:59.456 --> 00:45:02.496 A:middle
from the optimizations and
eliminate extra work, you know,

00:45:02.496 --> 00:45:04.026 A:middle
that we're doing as fast
as we can think to do it.

00:45:04.156 --> 00:45:07.176 A:middle
So, an example on
eliminating this extra work,

00:45:07.886 --> 00:45:10.896 A:middle
let's say that you have a method
that takes an array and I want

00:45:10.896 --> 00:45:12.866 A:middle
to scan through that and do
something with these objects

00:45:12.866 --> 00:45:15.336 A:middle
and if the result is not nil,
I want to add it to a new array

00:45:15.336 --> 00:45:16.496 A:middle
and I'm going to
return that back

00:45:16.496 --> 00:45:19.366 A:middle
from this function,
from this method.

00:45:19.366 --> 00:45:22.326 A:middle
The big problem here is really
each time we're creating a new

00:45:22.326 --> 00:45:23.916 A:middle
immutable copy of an array.

00:45:23.916 --> 00:45:26.496 A:middle
This is an obvious no-no
and we can avoid this.

00:45:26.786 --> 00:45:29.606 A:middle
Instead of doing that, you can
create a mutable array upfront

00:45:29.836 --> 00:45:31.466 A:middle
and add the objects to
the array which is going

00:45:31.466 --> 00:45:33.626 A:middle
to be really fast, and at
the end when we're done,

00:45:33.836 --> 00:45:36.656 A:middle
we can call copy which gives
us back an immutable NSArray

00:45:36.786 --> 00:45:37.646 A:middle
and we can return that.

00:45:37.646 --> 00:45:39.516 A:middle
So we take a full
advantage of the mutability

00:45:39.516 --> 00:45:42.006 A:middle
when it make sense for us and
we still fulfill the contract

00:45:42.006 --> 00:45:44.506 A:middle
of our method by saying we'll
return an actual NSArray.

00:45:44.876 --> 00:45:47.586 A:middle
And you could do some other
things with appending to it,

00:45:47.586 --> 00:45:50.316 A:middle
NSMutableString or
NSMutableData and so on.

00:45:50.936 --> 00:45:53.926 A:middle
The key takeaway from this whole
section and I'd like to say,

00:45:53.976 --> 00:45:55.436 A:middle
don't leave performance
on the table.

00:45:55.796 --> 00:45:58.216 A:middle
If there's performance there
just waiting for you to take it

00:45:58.216 --> 00:46:00.316 A:middle
and be faster, don't
leave it there.

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:45:58.216 --> 00:46:00.316 A:middle
and be faster, don't
leave it there.

00:46:00.846 --> 00:46:01.726 A:middle
Take advantage of it.

00:46:01.906 --> 00:46:04.506 A:middle
You know, if I could be using
an NSDictionary for this rather

00:46:04.506 --> 00:46:07.406 A:middle
than an NSArray, I might
as well do that, you know.

00:46:07.476 --> 00:46:10.176 A:middle
You have to weigh the
benefits, the pros and cons

00:46:10.726 --> 00:46:12.226 A:middle
of choosing either way.

00:46:12.786 --> 00:46:15.336 A:middle
But I really encourage
you to think deeply

00:46:15.586 --> 00:46:17.716 A:middle
about the performance that
you're going to expect to see

00:46:17.716 --> 00:46:18.786 A:middle
with your data structures.

00:46:19.636 --> 00:46:21.166 A:middle
And so, a lot more
information that you can found

00:46:21.166 --> 00:46:23.746 A:middle
out is Dave DeLong is our
App Frameworks Evangelist

00:46:23.746 --> 00:46:26.306 A:middle
and he'll be a great point
man for any questions you have

00:46:26.306 --> 00:46:28.826 A:middle
on this and also on the Cocoa
Labs, in Developer Forums,

00:46:28.826 --> 00:46:30.296 A:middle
and then I have three
documentation links

00:46:30.296 --> 00:46:33.086 A:middle
that are really useful for
more in-depth understanding

00:46:33.086 --> 00:46:34.676 A:middle
of collections, property lists,

00:46:34.676 --> 00:46:35.956 A:middle
and archive sand
serializations and so on.

00:46:36.296 --> 00:46:37.886 A:middle
There's two related
sessions, I mentioned the one

00:46:37.886 --> 00:46:41.336 A:middle
on Building Efficient OS X
Apps and Hidden Gems in Cocoa

00:46:41.336 --> 00:46:43.256 A:middle
and Cocoa Touch is immediately
following in this room.

00:46:43.506 --> 00:46:44.756 A:middle
This is a great overview
of a lot

00:46:44.756 --> 00:46:46.676 A:middle
of things you may not be
familiar with or even aware

00:46:46.676 --> 00:46:49.496 A:middle
of throughout the Cocoa
and Cocoa Touch frameworks,

00:46:49.496 --> 00:46:52.176 A:middle
also in XCode and
different things like that.

00:46:52.206 --> 00:46:53.966 A:middle
So just to summarize, I
have a few key takeaways

00:46:53.966 --> 00:46:55.606 A:middle
that I want you to remember if
nothing else from the session.

00:46:56.006 --> 00:46:59.076 A:middle
The first is that complexity
kills large-scale performance.

00:46:59.406 --> 00:47:02.286 A:middle
If you have a lot of work and
your complexity grows over time,

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:46:59.406 --> 00:47:02.286 A:middle
If you have a lot of work and
your complexity grows over time,

00:47:02.526 --> 00:47:03.856 A:middle
when you get to large
amounts of data,

00:47:04.096 --> 00:47:05.126 A:middle
your performance will tank.

00:47:05.516 --> 00:47:06.406 A:middle
You need to be aware of that.

00:47:06.626 --> 00:47:09.856 A:middle
Second, know how much
work your code is doing.

00:47:10.186 --> 00:47:11.796 A:middle
Know what it's actually
trying to accomplish,

00:47:11.796 --> 00:47:13.666 A:middle
that's where a lot of the
hidden complexity lies.

00:47:14.326 --> 00:47:16.606 A:middle
Avoid redundancy and
strive for efficiency,

00:47:16.606 --> 00:47:19.306 A:middle
it's the last two points of
how you can resolve this kind

00:47:19.306 --> 00:47:20.296 A:middle
of performance issues.

00:47:20.776 --> 00:47:22.336 A:middle
If you're doing something
over and over again,

00:47:22.596 --> 00:47:23.426 A:middle
take it out of a loop.

00:47:23.426 --> 00:47:24.236 A:middle
Do it just once.

00:47:24.506 --> 00:47:26.416 A:middle
If you're doing something
in an inefficient way,

00:47:26.416 --> 00:47:27.576 A:middle
try to find a better algorithm.

00:47:28.406 --> 00:47:30.926 A:middle
Focus on the biggest
performance wins first

00:47:30.926 --> 00:47:32.196 A:middle
as we talked about Andahl's Law.

00:47:32.196 --> 00:47:34.066 A:middle
Find the bottlenecks and
eliminate them first.

00:47:34.066 --> 00:47:35.446 A:middle
Don't prematurely optimize.

00:47:36.186 --> 00:47:37.636 A:middle
Prefer to use the
built-in collections

00:47:37.636 --> 00:47:41.046 A:middle
and API wherever possible so you
can benefit from optimizations

00:47:41.046 --> 00:47:42.046 A:middle
and improvements over time.

00:47:42.796 --> 00:47:45.246 A:middle
Design according to
your particular needs.

00:47:45.576 --> 00:47:48.386 A:middle
Choose a data structure that
fits how you need to access it.

00:47:49.296 --> 00:47:51.686 A:middle
Something that will make
it really fast to the tasks

00:47:51.686 --> 00:47:53.676 A:middle
that you need to do and
it's going to be convenient.

00:47:54.486 --> 00:47:56.566 A:middle
And last, think about
performance early.

00:47:56.976 --> 00:47:59.136 A:middle
There's a difference between
premature optimization

00:47:59.406 --> 00:48:00.886 A:middle
and being-- having common sense

WEBVTT
X-TIMESTAMP-MAP=MPEGTS:181083,LOCAL:00:00:00.000

00:47:59.406 --> 00:48:00.886 A:middle
and being-- having common sense

00:48:01.056 --> 00:48:02.696 A:middle
about the performance
of your application.

00:48:02.986 --> 00:48:04.286 A:middle
When you use some
of this knowledge

00:48:04.286 --> 00:48:06.376 A:middle
about understanding how
complexity can affect

00:48:06.376 --> 00:48:08.516 A:middle
performance, it enables you to
make great decisions upfront

00:48:08.806 --> 00:48:12.086 A:middle
about how to store your data so
that you can access it quickly,

00:48:12.416 --> 00:48:14.656 A:middle
you'll be happy, and your
users will be delighted

00:48:14.656 --> 00:48:16.066 A:middle
with the performance
of your application.

00:48:16.496 --> 00:48:16.836 A:middle
Thank you.

00:48:17.516 --> 00:48:20.500 A:middle
[ Applause ]