Re: Where is NSList? [off-topic]
Re: Where is NSList? [off-topic]
- Subject: Re: Where is NSList? [off-topic]
- From: Pandaa <email@hidden>
- Date: Thu, 29 Jul 2004 12:23:28 +0200
Flamebait taken.
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.
I'm sorry if you feel insulted, that was never my intention.
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.
Indeed it was a point well made, had the topic been that of code
optimization. Now, however, it was about algorithm selection/design.
When you know that your application will need to scale well with regard
to some input size, it's a waste of time to first create and implement
a design that you know will have problems.
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.
This is absolutely obvious. Why is there a need to make a whole point
out of this in a thread where we know nothing about the application the
original poster was working on?
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.
That depends completely upon the application. In many cases it is an
excellent idea for the application programmer to concern him or herself
with cache characteristics. Audio processing comes to mind, and it is
true in many computationally heavy applications.
(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.
Yes they are, but some basics will hold true on most computers. Enough
to make a difference.
On whim, I checked my data structures and algorithms text book. The
index doesn't even mention cache.
Did you expect otherwise?
Time complexity analysis of operations on data structures is usually
done in a very abstracted way precisely because the intricate details
will vary from computer to computer (and because they are
mathematically more difficult to handle). This does not mean that these
issues are irrelevant to data structure implementation. In cases where
it matters, quite the opposite is true.
In cases where it doesn't matter, why obviously it doesn't!
p.s. Sorry for the slow reply, Mail decided that your mail was Junk.
Thank you.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. 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.