Thread: Efficient Algorithm

  1. #1
    Registered User purple's Avatar
    Join Date
    Mar 2002
    Posts
    28

    Efficient Algorithm

    I have a program that I need an efficient algorithm for and I was hoping someone could lend some insight. This program will eventually be written in Java for my Advanced Data Structures class, so I'm more concerned with an efficient algorithm as opposed to actual working code at this point.

    Here is what the program must do efficiently. Read in a SUPER HUGE file of positive numbers, then determine:
    a) The maximum value of a[j] + a[i], for j >= i
    b) The maximum value of a[j] - a[i], for j >= i
    c) The maximum value of a[j] * a[i], for j >= i
    d) The maximum value of a[j] / a[i], for j >= i

    The key here is to have something efficient because the files the grader will be using are huge. Thanx in advance.

  2. #2
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>The key here is to have something efficient because the files the grader will be using are huge.
    If you know the format of the file and it's consistent then you can fake indexed access and get great performance by treating i and j as offsets. For example, in a file like this
    Code:
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    You could add each of those numbers like this :-)
    Code:
    #include <stdio.h>
    
    int main(void)
    {
      FILE *fp;
      int a = 0, b = 0;
      long i = 2L, j = 3L; /* Test values */
    
      if ((fp = fopen("input.txt", "rb")) == 0)
      {
        return 1;
      }
    
      if (fseek(fp, i * 2, SEEK_SET) != 0 || fscanf(fp, "%d", &a) != 1)
      {
        return 1;
      }
    
      if (fseek(fp, j * 2, SEEK_SET) != 0 || fscanf(fp, "%d", &b) != 1)
      {
        return 1;
      }
    
      printf("%d + %d == %d\n", a, b, a + b);
    
      fclose(fp);
    
      return 0;
    }
    *Cela*

  3. #3
    Registered User purple's Avatar
    Join Date
    Mar 2002
    Posts
    28
    Faking it won't work. Here is a sample test file he gave us and you'll see what I mean by huge files.

  4. #4
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>Faking it won't work.
    On the contrary, using offsets will work perfectly for this file. The format is consistent, so no matter what size the file is, you can index into it very efficiently in both speed and memory usage with some sort of file seek like I used above. :-)
    *Cela*

  5. #5
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    If i'm reading this correctly, the problem is to find either ``maximum'' or ``minimum'' values in the array multiple times (the j > i restriction changes this slightly, but not by too much). Since you have to do this multiple times, it might be worth loading the entire file into memory and then sorting it. That test file is huge, but i think speed for size is worth it here - unless your professor disagrees

    edit:

    actually, collect the first maximum and second maximum and then the first minimum after both of these and in one pass you should probably have all the information you need. what was i thinking?
    Last edited by ggs; 02-02-2003 at 06:17 PM.
    .sect signature

  6. #6
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Wink

    I have given and had to do a similar program in college. Look at file processing techniques and do you also have to show the actual big Oh efficiency for this algorithm?
    Mr. C: Author and Instructor

  7. #7
    Registered User purple's Avatar
    Join Date
    Mar 2002
    Posts
    28
    Originally posted by Mister C
    Do you also have to show the actual big Oh efficiency for this algorithm?
    No we don't have to show big O, but efficiency is key here. From friends of mine that are previous students of his, supposedly the teacher is a real jerk off and will actually halt processing early if he feels it is taking too long.

    I will probably try and come up with something along the lines of what ggs has suggested above in his edit.

    Any more input is greatly appreciated.
    Last edited by purple; 02-02-2003 at 07:48 PM.

  8. #8
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    could you explain more clearly what you are trying to find

  9. #9
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    although i'm not really clear on what you are tyring to find
    but the way i read it is that you have to choose an a[j] and an a[i] for each of these which results in the largest possible value for the expression.

    one thing to note about this is that a[j] and a[i] for a and c will be the same so you only have to choose those values once, and simmilarly, a[j] and a[i] for b and d will be the same.

  10. #10
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    I am not sure wheather this is appropriate.. but you can use B trees which will bring down the search time drastically.. Even big Databases use this technique.. Some ven use a b+ Tree... THis necessaraly does not need to be implemented into the memory but can be done on the disk itself... But for effeciency this will have to be done while writing to the file itself...

  11. #11
    Registered User purple's Avatar
    Join Date
    Mar 2002
    Posts
    28
    Sorting will just cause more problems because of the restriction "for j >= i."

    If I sort then I will have no way to tell if the ith value preceeds the jth value. Also the overhead involved in sorting files of this size will probably be more of a detriment than an aid.
    Last edited by purple; 02-05-2003 at 03:04 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Efficient Sorting Algorithm
    By GCNDoug in forum C++ Programming
    Replies: 10
    Last Post: 11-13-2008, 09:06 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. efficient compression algorithm pls
    By gooddevil in forum C Programming
    Replies: 7
    Last Post: 05-08-2004, 03:33 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM