Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: David Blanton <email@hidden>
- Date: Thu, 29 Jul 2004 17:25:21 -0600
Thanks for the lesson!
On 7/29/04 12:45 PM, "David Blanton" <email@hidden> wrote:
>
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.