On Thursday, December 30, 2004, at 08:57 AM, Matthew wrote:
<snip>
If you go with 3), check into red/black trees. AFAIK algorithms based
on red/black tree methods are presently the fastest way to access huge
data volumes.
(If they are not, someone give a faster one. I'm interested too.)
Algorithmically, sure, red-black trees are pretty close to fastest.
However, if you want to make the simplifying assumption that all your
data will reside in "memory" (relying on the VM system heavily), then
you're probably better with skip lists. I know it sounds silly that a
linked-list variant would beat any sort of sophisticated tree approach,
but when you factor in locality of reference, and the general data
access pattern for searching, you wind up trashing your caches (both
on-chip and in the VM system) with trees and therefore do much, much
better with skip lists. Besides, they're a lot easier to program
anyway.
Brendan Younger
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/email@hidden
