Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: David Blanton <email@hidden>
- Date: Thu, 29 Jul 2004 12:45:56 -0600
I don't claim to be a computer scientist but I can devise awesome data
structures algorithms with the best. Now to my question about this thread:
What is the definition of O(1), O(lg n) and Theta(n).
(If it helps get an answer I do have a math degree from Berkeley so I will
understand the definitions.
I just don't know the functions O() and Theta() )
Thanks for the lesson!
DB
On 7/29/04 3:17 AM, "Steve Checkoway" <email@hidden> wrote:
>
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.
_______________________________________________
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.