reduce time cost, need help
I have a following problem:
I receive M N-array of integers. Then for each array, I'll read the entire array element by element. For each element's value, an appropriate function will be called. More detail:
n1 -> call function f1();
n2 -> call function f2();
.....
nN -> call function fN();
I could use a switch to do that job as below:
for all array in M array
for all i from 1 to N
switch(array)
case n1: call f1();
case n2: call f2(); ....
However, the cost will be MxN^2/2. Knowing that the M N-arrays have exactly the same values (X(i) = Y(i) for all pair X array and Y array in N-arrays and for all i from 1 to N), how I could make the algorithms better?
Note: A human being could easily to reduce the cost to MxN because after treating the first array, he know exactly what to do with the rest and could blidly call the function without checking the switch loop again. I just don't know how to simulate this idea in Java languages. Please help.
Message was edited by:
principles
This is not really an algorithms question. You are not looking for an algorithm you are looking for a way to mimic a Fortran computed GOTO, or a C array of function pointers in Java. This is a java programming question.
But since you are already here...
I assume that you really meant to say switch(array[ i ]) in your code and not switch(array)
If you had an array of function pointers fp[K] you could use array[ i ] as an index to pluck out a function to execute ie. something like fp[array[ i ]].execute();
Furthermore, once you have passed through your first array of ints, you now know the order you will always be doing things so you could create a fp2[] where the elements are in that final order. In other words fp2[ i ] = fp[array[ i ]]; then you can just execute fp2 in order.
So how do you build function pointers in Java? You encapsulate the function into an object. Here is one way
abstract class Function{
abstract public void f();
public static final int K = xxxx; // presumably you know how many functions you have
public static Function[] fp = new Function[K];
private static int nextOpenSlot = 0; // for filling function array
private Function(){fp[nextOpenSlot++] = this;} // add function to fp table
static { // create the K different functions.
// use anonymous classes to define a new version of the abstract class, one for each function.
new Function(){public void f(){.. yer code goes here just as it would be in any class...}} // f0
new Function(){public void f(){.. yer code goes here...}} // f1
new Function(){public void f(){.. yer code goes here...}} // f2
...
}
}
Now you can just pluck a function out of the fp array and execute it. On pass one you produce fp2
Function[] fp2 = new Function[N];
for(int i =0; i<N; i++){fp2 = Function.fp[array[i]];} // build execution array
//then you do all the passes in one step
for(int m = 0; m><M; m++){int i = 0; while(i><N){fp2[i++].f()}}
standard caveats - no compilation done, no testing, and no assurances that this is actually valid java code. I don't do anonymous classes all that often so may have the syntax wrong.
I also have no idea why the charming forum formatter (at least in the preview mode) decided to convert my legal and correct m "less than" M into m><M. So be aware that the code you see is NOT the code that I wrote. Clearly I am not the only idiot out there that doesn't bother to test or debug code destined for a forum. It even tossed in a little extra greater than sign at the end of my standard sign off - no extra charge.
Enjoy!>
