# Need a good method

• 04-02-2005
Asagohan
Need a good method
I have a problem. I have a large number of intergers in a file. After that, i have an even larger number of paris. The number of pairs are almost the square of the number of integers. And the pairs are between 0 and whatever number of integers there are
-1.
for example the file might contain: INTS: 4 7 8 49 2 30 1...
PAIRS: (0, 3) (4,5) (1,2) (0,2)...
So when (0,3) is read it will find the largest number between positions 0 and 3 of the integers and return the index (in this case 3). The pairs have to be read in sequence but the integers will probably be in an array.

Does this program require the use of dynamic programming to get the fastest possible algorithm? If so i was thinking of using a 2d array to store the answer to the first pair in the array, then fill in the rest of the array using this answer and use the array to obtain the answers.
(The array will be made up of all the ints going vertically and horizontally representing all the possible pairs. And only half of the array is required because you cant have a pair where the first number is larger than the second).

Does anyone have a better (faster) algorithm??
• 04-02-2005
Salem
> Does this program require the use of dynamic programming to get the fastest possible algorithm?
What algorithm?
The only thing you've got going on at the moment is reading files, which can't really be optimised. The real trick is what you intend to do with the array once you've built it.

> I have a large number of intergers in a file
What do you call large - 1000? 1000000?
• 04-03-2005
ober
Sounds suspicously like homework to me....
• 04-05-2005
Asagohan
It's not quite homework, more like a project I've been working on... The main point is to make it run as fast as possible, due to the huge data set I'll have to work with. The number of ints will be about 10,000 and the number of pairs will be around 100,000,000.
I think if i made a 2d array that big, it wouldn't fit into RAM and i would be working with virtual memory which will slow it down. But my algorithm was:

Fill the 2d array by checking the current index with the previous index for each number.

If a pair is made of the same number (e.g (3,3) then the largest index will be that number(3).

I also noted that if (2, 8) has a largest number of 3, then all positions up to (2, 3) will also be 3. And that if (0,8) is 3 then all positions until (3, 8) will be 3. Therefore position numbers between (0,3) and (3,8) do not need to be known.

I was thinking of using these ideas to reduce the size of my array by using just the first line,but then there will be other problems for positions after (3, 8) ie(4,8) (5,8) etc.

Does anyone have any suggstions???
• 04-06-2005
Waldo2k2
well if you're worried about having so many int variables (which take 4 bytes for each) why not dump the largest possible value of the pairs into a single character array(one byte per integer). That gets you down to about 488mb in that array...which is still huge...I'd like to help more but I'm still kind of confused on what exactly it is you're looking to accomplish here...could you possibly provide a more visual representation?
• 04-06-2005
So you read 10,000 integers into an array. 40k, no big deal.

You read the first pair, scan from x to y, get the biggest number in that interval, and do whatever you want to do with it. Why do you need to store the pairs?

This is presumably some graphics manipulation.
• 04-07-2005
Asagohan
The reason why the pairs are in a huge 2d array is becuase there will be so many, so if i keep searching linearly through the 1d array I will take ages if i have 100,000 pairs to go through.

"I'd like to help more but I'm still kind of confused on what exactly it is you're looking to accomplish here..."

My question is, how can I get the 100,000 pairs that i might have in only a few seconds, without storing them in a giant 2d array. I definately must do some pre processing of the integers before hand. I want to use results from previous to aid in getting the result for the current pair.

For example... my integers might be: 2 7 4 3 9 10 302 73 1
and i have to find pairs (0,3) (1,7)(2,5)(6,7)(3,8)(7,8)(0,8)

I find that (0,3) has the largest number in index 1.
So when i do the second pair (1,7) i already know that (0,3)=1, so i only need to check (1,4)(1,5)(1,6)(1,7) right?

An what i found was that if (0,4) = 2 then (1,4)(2,4)(3,4)(4,4) will all be 2 aswell. and so if it was in a 2d array, there would be a big block between (2,2) - (2,4) which would all be 4. So if i could utilise this information, i dont have to compare so much and waste time and space.

Do u need any more explanation?? I am really lost.
• 04-07-2005
sand_man
Quote:

The reason why the pairs are in a huge 2d array is becuase there will be so many, so if i keep searching linearly through the 1d array I will take ages if i have 100,000 pairs to go through.
It wont make a bit of difference in speed.
• 04-08-2005
With the examples you are giving, I suspect looking to see if your interval x,y is already covered by parts of other intervals and then checking the values that are not covered by such a pre-existing result will require more computation then simply scanning the interval.

I thought I had some idea what it was you were doing, but the more you say, the more cryptic you are making it.
• 04-08-2005
misplaced
ok, let me get this straight - .................................................. .......

.................................................. ..........

define each variable:
(x, y) = n

now, how does (x,y) equal in n ?
what operation takes place?

given this data
2 7 4 3 9 10 302 73 1
you say
"I find that (0,3) has the largest number in index 1."

to me, when you say 'index 1', i'm guessing you mean the second integer in your data, which is 7. i don't see, mathematically, how................

...............nevermind
• 04-08-2005
misplaced
Quote:

for example the file might contain: INTS: 4 7 8 49 2 30 1...
PAIRS: (0, 3) (4,5) (1,2) (0,2)...
So when (0,3) is read it will find the largest number between positions 0 and 3 of the integers and return the index (in this case 3). The pairs have to be read in sequence but the integers will probably be in an array.
(0, 3) - 3
(4,5) - 30
(1,2) - 7
(0, 2) - 8

and
Quote:

For example... my integers might be: 2 7 4 3 9 10 302 73 1
and i have to find pairs (0,3) (1,7)(2,5)(6,7)(3,8)(7,8)(0,8)
0,3 - 7
1,7 - 302
2,5 - 10
.....

??????????
• 04-08-2005
Waldo2k2
yeah, could you maybe come up with a good stretch of pseudo code so we can figure out what's really going on? I get what you're trying to do, but for what purpose? What do these integers represent, are they becoming part of this array? If so is it random? Why are you making pairs? How are you arriving at n when you have (x,y)?