Thread: Need a good method

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    14

    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??

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > 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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    5|-|1+|-|34|) ober's Avatar
    Join Date
    Aug 2001
    Posts
    4,429
    Sounds suspicously like homework to me....

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    14
    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???

  5. #5
    PC Fixer-Upper Waldo2k2's Avatar
    Join Date
    May 2002
    Posts
    2,001
    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?
    PHP and XML
    Let's talk about SAX

  6. #6
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,829
    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.
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  7. #7
    Registered User
    Join Date
    Mar 2005
    Posts
    14
    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.

  8. #8
    ---
    Join Date
    May 2004
    Posts
    1,379
    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.

  9. #9
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,829
    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.
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  10. #10
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    ok, let me get this straight - .................................................. .......

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

    help us help you.
    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
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  11. #11
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    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
    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
    .....

    ??????????
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  12. #12
    PC Fixer-Upper Waldo2k2's Avatar
    Join Date
    May 2002
    Posts
    2,001
    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)?
    PHP and XML
    Let's talk about SAX

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stuck on display method
    By shintaro in forum C++ Programming
    Replies: 2
    Last Post: 02-01-2009, 05:17 PM
  2. Best communication method to thousand childs?
    By Ironic in forum C Programming
    Replies: 8
    Last Post: 11-08-2008, 12:30 AM
  3. C# method
    By siten0308 in forum C# Programming
    Replies: 6
    Last Post: 07-15-2008, 07:01 AM
  4. Overriding a method in C
    By DavidDobson in forum C Programming
    Replies: 1
    Last Post: 07-05-2008, 07:51 AM
  5. In a game Engine...
    By Shamino in forum Game Programming
    Replies: 28
    Last Post: 02-19-2006, 11:30 AM