Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: Steve Checkoway <email@hidden>
- Date: Thu, 29 Jul 2004 02:17:25 -0700
On Jul 28, 2004, at 2:48 AM, Pandaa wrote:
I strongly suggest everyone who contributed to this confusion read up
on basic computer science.
I'm sorry you think I need to brush up on computer science basics (you
are quite wrong). You should not be insulting to people attempting to
help, let alone make assumptions about their programming
ability/knowledge.
Ordered and indexed. A list is ordered and non-indexed. An array has
O(n) insert and remove and O(1) indexed random access. A list has O(1)
insert and remove and O(n) indexed random access.
A list has O(1) remove only if you already have a pointer to the node.
In the best case, it is O(1), in the average and worst cases, it is
Theta(n) since you have to first find the element which takes linear
time.
I'd suggest using NSArray/NSMutableArray for ordered collections, and
only worrying about their access characteristics if use and profiling
of your application point to them as a performance issue.
This is a *very* naive view which may well lead to O(n^2) or worse
implementations of O(1) problems!
Programmers are notorious for optimizing the wrong code. The pervious
point was well made and perfectly valid. Don't waste your time
needlessly optimizing this code unless it is actually a bottleneck.
While writing a doubly linked list is fairly simple, why bother if it
doesn't effect the performance of the application appreciably.
I happen to have a doubly linked list class laying around, if anyone
is interested I can polish it a bit and make it available for anyone
to use. It is such a trivial thing.
Indeed it is.
To get an efficient linked list on a modern computer, it is necessary
to use either a custom memory manager or make nodes carry a small
constant number > 1 of objects. A naive implementation will have poor
iteration performance as every node will probably be on a new cache
line.
It is almost never a good idea for application programmers to concern
themselves with cache characteristics. That's the job of a system
programmer. (Systems programming is also one place where a linked list
is very useful to implement an LRU-like page replacement algorithm.)
Cache characteristics are different for each computer.
On whim, I checked my data structures and algorithms text book. The
index doesn't even mention cache.
- Steve
p.s. Sorry for the slow reply, Mail decided that your mail was Junk.
_______________________________________________
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.