• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: storing, searching, and displaying variable-sized data sets
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: storing, searching, and displaying variable-sized data sets


  • Subject: Re: storing, searching, and displaying variable-sized data sets
  • From: Brendan Younger <email@hidden>
  • Date: Fri, 31 Dec 2004 00:13:30 -0600


On Dec 30, 2004, at 6:45 PM, Tim Ramsey wrote:

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:
This email sent to email@hidden


  • Follow-Ups:
    • Re: storing, searching, and displaying variable-sized data sets
      • From: Matthew <email@hidden>
References: 
 >Re: storing, searching, and displaying variable-sized data sets (From: Tim Ramsey <email@hidden>)

  • Prev by Date: Re: Is it possible to draw text to an offscreen view that has no window?
  • Next by Date: Re: Subclass Import Issues
  • Previous by thread: Re: storing, searching, and displaying variable-sized data sets
  • Next by thread: Re: storing, searching, and displaying variable-sized data sets
  • Index(es):
    • Date
    • Thread