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.

>>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;
}

---

Faking it won't work. Here is a sample test file he gave us and you'll see what I mean by huge files.

>>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. :-)

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?

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?

Quote:

---

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.

could you explain more clearly what you are trying to find

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.

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

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.