Manfred Nowak wrote:
> Population and sweep would each be linear in time.
The sweep is linear in time only, if the populatable points of the area
are bount by O(n), which is not neccessary the case.
Therefore, I don't see to find in the generell case a solution faster
than
O( n + k*log( k))
On 1/28/12 10:29 AM, H. S. Teoh wrote:
Actually, the reason I chose hypercubes was because I was hoping that
the convex hull with hypercubes in the original features' space would be
equivalent (or easily massaged to be equivalent) to using simplexes in
rank space. (Although the part about the (1
Andrei Alexandrescu wrote:
> we have multiple predicates, p1, p2, ..., pk. We want to sort
> elements in increasing order of rank(a, p1) + ... + rank(a, pk).
Got it. Thinking ocasionally.
-manfred
On Sat, Jan 28, 2012 at 08:12:52AM -0600, Andrei Alexandrescu wrote:
> On 1/27/12 11:02 PM, H. S. Teoh wrote:
> >If you treat the attributes as components of an n-dimensional vector,
> >then you could recast the problem as the convex hull of k hypercuboids,
> >where each hypercuboid lies between (0
On 1/28/12 9:10 AM, Manfred Nowak wrote:
Andrei Alexandrescu wrote:
[ About ranks]
Actually they need to be computed.
Then the problem is still too unclear.
It's very simple and clear in formulation actually.
Given a range r of elements, define rank(a, p) as the position that
object a wou
Andrei Alexandrescu wrote:
[ About ranks]
> Actually they need to be computed.
Then the problem is still too unclear.
> I think it's possible to find cases where
>rank(a, k1) + rank(a, k2) < rank(b, k1) + rank(b, k2)
> but
>alpha * a.k1 + beta * a.k2 > alpha * b.k1 + beta.k2.
Of course.
On 1/28/12 1:08 AM, Manfred Nowak wrote:
Andrei Alexandrescu wrote:
generally what one wants is a selection of "best of breed" stocks
that are among the top ones in a variety of categories. (Relative
importance could be assigned to each category.)
This is quite different and easier than the p
On 1/27/12 11:02 PM, H. S. Teoh wrote:
If you treat the attributes as components of an n-dimensional vector,
then you could recast the problem as the convex hull of k hypercuboids,
where each hypercuboid lies between (0,0,0,...) and (x1,x2,x3,...). The
points on the convex hull then are the high-
Andrei Alexandrescu wrote:
> generally what one wants is a selection of "best of breed" stocks
> that are among the top ones in a variety of categories. (Relative
> importance could be assigned to each category.)
This is quite different and easier than the problem initially
stated, because ranks
On Fri, Jan 27, 2012 at 09:22:26PM -0500, Andrei Alexandrescu wrote:
[...]
> I wasn't thinking necessarily of the standard library, but it is
> something that is often needed even if not perceived as such. For
> example, the stock screeners offered by financial sites are crappy -
> they allow you t
Andrei Alexandrescu wrote:
Andrei Alexandrescu wrote:
> generally what one wants is a selection of "best of breed" stocks
> that are among the top ones in a variety of categories. (Relative
> importance could be assigned to each category.)
This is quite different and easier than the problem ini
Andrei Alexandrescu wrote:
> generally what one wants is a selection of "best of breed" stocks
> that are among the top ones in a variety of categories. (Relative
> importance could be assigned to each category.)
This is quite different and easier than the problem initially stated,
because rank
On 1/27/12 8:33 PM, Peter Alexander wrote:
On Friday, 27 January 2012 at 19:36:49 UTC, Andrei Alexandrescu wrote:
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 consi
On 1/27/12 8:26 PM, Manfred Nowak wrote:
Andrei Alexandrescu wrote:
That's three sorts and at least one temporary array.
If a temporary array is allowed, the ranks and the sum of the ranks
might be computed by a diogonal sweep over the area defined by the two
dimensions and populated by the e
On Friday, 27 January 2012 at 19:36:49 UTC, Andrei Alexandrescu
wrote:
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?
Can you defin
Andrei Alexandrescu wrote:
> That's three sorts and at least one temporary array.
If a temporary array is allowed, the ranks and the sum of the ranks
might be computed by a diogonal sweep over the area defined by the two
dimensions and populated by the elements.
Population and sweep would each
On Fri, 27 Jan 2012 16:45:41 -0600, Andrei Alexandrescu
wrote:
On 1/27/12 5:35 PM, Christof Schardt wrote:
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
I think, you are mixing two problem levels:
L
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* inser
On Friday, 27 January 2012 at 19:36:49 UTC, 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
On 1/27/12 5:35 PM, Christof Schardt wrote:
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
I think, you are mixing two problem levels:
Level one (theory):
How are the two properties weighted against eac
>>> 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
I think, you are mixing two problem levels:
Level one (theory):
How are the two properties weighted against each other
and can be combined to a total
On 1/27/12 5:27 PM, Derek wrote:
On Sat, 28 Jan 2012 06:36:49 +1100, 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.
On Sat, 28 Jan 2012 06:36:49 +1100, 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 ar
On 1/27/12 3:07 PM, 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
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-hai
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
26 matches
Mail list logo
