Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: Pandaa <email@hidden>
- Date: Wed, 28 Jul 2004 11:48:27 +0200
It is my understanding that NSArray's implementation changes between
a more traditional array and a linked list, depending on the number
of elements it contains.
I don't claim to be an expert but that sounds....unlikely. Do you have
some sort of source for this information?
No. There appears to be a "mutable deque"type of CFArray but it is
nothing like a linked list structure.
From CFArray.h :
Computational Complexity
The access time for a value in the array is guaranteed to be at
worst O(lg N) for any implementation, current and future, but will
often be O(1) (constant time). Linear search operations similarly
have a worst case complexity of O(N*lg N), though typically the
bounds will be tighter, and so on. Insertion or deletion operations
will typically be linear in the number of values in the array, but
may be O(N*lg N) clearly in the worst case in some implementations.
There are no favored positions within the array for performance;
that is, it is not necessarily faster to access values with low
indices, or to insert or delete values with high indices, or
whatever.
To the disgrace of most list-readers this thread has been a mess. There
is no linked list class in the Foundation framework, and no array
implementation can take the place of a list because they are
fundamentally different collection types.
I strongly suggest everyone who contributed to this confusion read up
on basic computer science.
Of course, if you find it truly lacking and truly necessary to have
std::list-like semantics, I guess you're always welcome to create your
own
implementation and share it with the world for the betterment of Cocoa
programming worldwide. :-)
It is not about semantics.
There is no NSLinkedList. What would the point of such an object be?
There's already one ordered collection, NSArray.
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.
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!
If that happens, then you can create a custom subclass of NSArray or
NSMutableArray -- and possibly an NSEnumerator subclass to go with
them -- that meets your particular access characteristics and also
interoperates well with the rest of the frameworks.
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.
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.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. email@hidden . . www.synapticpulse.net .
_______________________________________________
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.