OT: Algorithm to speed up vector range search

[Sims]

Hi,

I hope you guys can help me solve a problem that i am having with speeding
my system.
I also hope i can explain myself

Here goes,
I have a set of columns that i numbered from 0 to x.
Each row contains objects that can span over many columns.

so for example i can have col:

0-1-2-3-4-5-6
AAAA
BBBBB
CC

As you can see row 'A' ranges between 1- 3, 'B' between 2 and 5, 'C' ranges
between 0 and 1.

So if i was looking for rows that range between 0 and 1 i should return A
and C, (partial items are OK).

I could loop thru all the rows but that does not seem like a very efficient
way of doing what i want.

so if i had a structure like

struct _MYDATA{
int max; // the max col
int min; // the min col
int data; // the number that i am after.
};

What would be the best way to retrieve the number that range between x-y?

Many thanks for your help.
Sims

 

[Harald Grossauer]

Hi,

I hope you guys can help me solve a problem that i am having with speeding
my system.
I also hope i can explain myself

Here goes,
I have a set of columns that i numbered from 0 to x.
Each row contains objects that can span over many columns.

so for example i can have col:

0-1-2-3-4-5-6
AAAA
BBBBB
CC

As you can see row 'A' ranges between 1- 3, 'B' between 2 and 5, 'C'
ranges between 0 and 1.

Maybe it does in your newsreader, but it does not on mine. Well, never mind.

So if i was looking for rows that range between 0 and 1 i should return A
and C, (partial items are OK).

I could loop thru all the rows but that does not seem like a very
efficient way of doing what i want.

Why not? You only have to check two conditions per line. It won't get any
faster unless you store additional per-column information.

 

[Sims]

Maybe it does in your newsreader, but it does not on mine. Well, never

mind.

Sorry, i didn't quite think of that.

Why not? You only have to check two conditions per line. It won't get any
faster unless you store additional per-column information.

No, there must be a faster way, (i think).
In the example above i could have an array of columns.

col[0] = {C}
col[1] = {C, A}
col[2] = {A}
col[3] = {A, B}

and so on...

So if i was looking for items in column 0 to column 2 i would simply loop
thru the array above from item 0 to 2, rather than looping thru the whole
lot.
But the problem is now i have, (in my example above), 'C' is repeated twice
and so is 'A'.
Someone suggested that i did a union of the set but i am not sure how to do
that really in C++.

Regards,

Sims

 

[Karl Heinz Buchegger]

Hi,

I hope you guys can help me solve a problem that i am having with speeding
my system.
I also hope i can explain myself

Here goes,
I have a set of columns that i numbered from 0 to x.
Each row contains objects that can span over many columns.

so for example i can have col:

0-1-2-3-4-5-6
AAAA
BBBBB
CC

As you can see row 'A' ranges between 1- 3, 'B' between 2 and 5, 'C' ranges
between 0 and 1.

So if i was looking for rows that range between 0 and 1 i should return A
and C, (partial items are OK).

I could loop thru all the rows but that does not seem like a very efficient
way of doing what i want.

so if i had a structure like

struct _MYDATA{
int max; // the max col
int min; // the min col
int data; // the number that i am after.
};

What would be the best way to retrieve the number that range between x-y?

Depends. If your data don't change often, you could sort the
data according to min (and of course keep the sorted data around for the
next search).
Then, when scanning through the sorted data *and* reaching an entry, which
has a min value greater then the max value of your range, you know that
all following entries will also be completely to the right of your range
and thus cannot fit.
You can do the same in the other direction (sort according to max, compare
with the min of your range, thus quickly discarding all data to the left
of your range).

There is even a clever technique to combine both methods into one.
I read about this technique in an article written by Jim Blinn and
he calls it "Triage Tables"