A k-d tree isn't directly applicable here - the problem is that
the input data isn't normalized, so you can't just drop people
into a 2d grid consisting of one axis being height, and the other
axis being hair length. You need to 'normalize' the heights and
lengths into ranks first, *then* insert them, and normalizing the
lengths -> ranks is an NlogN process to begin with. Constructing
a k-d tree isn't free either - you either have to pre-sort your
inputs, or sort-as-you-go, which works out to NlogN as well.
On Friday, 27 January 2012 at 20:07:44 UTC, sclytrack wrote:
On 01/27/2012 08:36 PM, Andrei Alexandrescu wrote:
Here's a multikey sorting problem that's bothering me; I think
it's well
researched but I can't find the right keywords.
Say we have a collection of people with height and hair length
information. We want to get people who are "tall and
long-haired". More
precisely, we want to order people by rank(p.height) +
rank(p.hairlength), where rank(p.k) is the function that
returns the
rank of person p if ordered by key k.
The brute force approach would essentially compute the two
ranks and
then sort by their sum. That's three sorts and at least one
temporary
array. But I think things can be done considerably better. Any
ideas?
Thanks,
Andrei
http://en.wikipedia.org/wiki/K-d_tree
Sclytrack
