Re: Creating a dictionary who's objects are also linked or indexed?
Re: Creating a dictionary who's objects are also linked or indexed?
- Subject: Re: Creating a dictionary who's objects are also linked or indexed?
- From: Wagner Truppel <email@hidden>
- Date: Sat, 12 Aug 2006 14:41:06 -0700
What you're attempting to do falls under the name of "rectangular
range searches", the one-dimensional version of which is: given a
keyed set of items with a well-defined ordering relation among their
keys, and given two keys into the set, select the items which fall
between those keys.
This is a well-studied problem in computational geometry and has a
simple and efficient solution in the form of a data structure called
a "range tree". The one-dimensional range search problem uses a
balanced binary search tree to return all items within the query
range. The tree can be built in O(n log n) time and uses O(n log n)
storage, and queries can be performed in O(k + log n) time, where n
is the total number of items in the set and k is the number of items
found within the query range. In other words, the time to answer a
query is essentially linear in the number of items returned.
For details, try googling for "range tree". Also, take a look at
chapter 5 of the excellent book:
Computational Geometry
http://www.amazon.com/gp/product/3540656200/sr=8-1/qid=1155417398/
ref=sr_1_1/103-2373405-0892656?ie=UTF8
Wagner
============
The difference between an auto mechanic and a quantum mechanic is
that the quantum mechanic can get the car inside the garage without
opening the door.
I'm curious if there is a better Cocoa solution than I've found to
the following problem: I often have a list of items (strings,
numbers, or dates) where I know the values of the first and last
items and need to iterate over the inclusive set of items that fall
between the first and last items. I can accomplish this by
effectively implementing the lookup capability of a dictionary in
an object contained in an array or by adding an index to an object
in a dictionary. It can also be handled using Core Data which seems
a lot like using a sledgehammer to swat a fly.
For example, I have a list of names and want to enumerate over the
set of items from a given item to a given item. My code determines
that "Ball" is the first value of interest and "Smith" is the last
value, and given these, I need to return the inclusive set of items
that fall between (simple alpha comparison) these values in the
parent set.
It seems like a fairly common problem and am wondering if Cocoa
provides a simpler solution that I'm not seeing?
_______________________________________________
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