Re: [OT] Time complexity (was: Where is NSList?)
Re: [OT] Time complexity (was: Where is NSList?)
- Subject: Re: [OT] Time complexity (was: Where is NSList?)
- From: Marcel Weiher <email@hidden>
- Date: Thu, 29 Jul 2004 23:44:44 +0100
On 29 Jul 2004, at 22:59, Allan Odgaard wrote:
O(n^2) can often occur in simple applications, like e.g. iTunes,
assume we have all songs in an array, we have another array with
selected artists, now we need to construct the array of all songs by
the selected artists. A naive implementation would iterate over the
array of selected artists, and for each, iterate over all the songs
and copy those which match.
If iTunes were written in Objective-C, this could look something like
the following:
for (i=0;i<[songs count]; i++) {
id song = [songs objectAtIndex:i];
if ( [selectedArtists containsObject:[song artist]] ) {
[selectedSongs addObject:song];
}
}
Interestingly enough, the second 'n' that makes this run n^2 (or
rather N*M ), is hidden inside -containsObject:
Imagine I have 10,000 songs all by different artist, and select all
the artists, that's 10,000 x 10,000 iterations = 100,000,000 -- even
on my G4, that is an operation I can feel, and I am quite sure that a
lot of programs work like this ;)
Yep. And when and if we see that happening, we can make a trivial
change:
NSSet *artistCheck = [NSSet setWithArray:selectedArtists];
for (i=0;i<[songs count]; i++) {
id song = [songs objectAtIndex:i];
if ( [artistCheck member:[song artist]] ) {
[selectedSongs addObject:song];
}
}
And our algorithm is well-behaved again (if it ever was a problem in
the first place, because M tends to be quite a bit lower than N). So,
we can easily fix this problem when and where it occurs, if it occurs
(and we've identified it as a REAL vs. an imagined problem), there is
no need for premature optimizations...
<obligatory_HOM_plug>
Or we could even make more compact, if we've added a category to
NSObject called -isMemberOf:
selectedSongs = [[songs select] isMemberOf:[NSSet
setWithArray:selectedArtists]];
</obligatory_HOM_plug>
Marcel
--
Marcel Weiher Metaobject Software Technologies
email@hidden www.metaobject.com
Metaprogramming for the Graphic Arts. HOM, IDEAs, MetaAd etc.
1d480c25f397c4786386135f8e8938e4
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.