My question is quite simple. I am implementing a greedy algorithm technique over the coefficients of a matrix and selecting the best coefficient according to some criteria. The matrix size is 50x1000. In every iteration a single coefficient is selected for operations. The problem before the initiation of the algorithm is out of 50,000 coefficients I have 25,000 candidate coefficients which I should process. Now in the first iteration I have to select the best coefficient among the 25,000 and in the successive iterations I have to select one from 24999, 24998, 24997. So as you see, the algorithm is quite time consuming because in each iteration I have to calculate the benefit of all the coefficients and select the best one according to the benefit and this benefit processing is a further matrix operation which is also time consuming. Do you have any idea how to reduce the computation time of the algorithm? My implementation language is java. Any help or ideas are appreciated.
"[...] in each iteration I have to calculate the benefit of all the coefficients and select the best one [...]"
Do you have to re-calculate them, because the benefit of them will change between single iterations or do you mean that you currently just calculate them in each iteration?
Iff the benefit of your coefficients will remain static between iterations you can follow one of the methods recommended by Rens or Marino.
But if your problem domain has a dynamic nature and you need to re-calculate them in each iteration, because your benefit function or something else will change over time, you can try out a technique called fitness approximation as
used in (evolutionary) optimization. There, one has to struggle with expensive fitness/benefit functions, too.
The actual fitness function is used for the initial population and afterwards one uses approximated models (also called surrogates or metamodels) of the fitness function.
Maybe you can transfer these concepts to your problem. The population is your matrix of coefficients and you need to find (or dynamically adapt) a model of your benefit function.
Maybe this (possibly combined with the data-structures as recommended by Rens and Marino) could boost the performance.
Just to get into the topic:
http://en.wikipedia.org/wiki/Fitness_approximation
http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4424972
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1299903
I find your question a little difficult to understand, but if I understand correctly, your problem is that selection of the coefficient takes too long. Assuming that's the case:
If you restrict the evaluation/benefit function to a specific set of functions that is transitive and symmetric, you can find the right coeficient much faster (O(n log n), if I'm not mistaken); you can also employ a time/memory trade-off and maintain an additional datastructure that keeps track of the best coeficients, so that you can query it in O(1). The problem with that is that you might need O(n) storage and additional processing to keep the datastructure ordered (intuitively, using a heap would probably work best, although it costs O(log n) to remove and O(log n) to re-add elements).
(edit:) Of course, it may not be possible to restrict the benefit function. In that case, the time/memory tradeoff may still help you, but that's really beyond my capabilities to say just on the basis of your question
Rens's reply is what I would have done as well: assign a benefit score value to the coefficients as you compute them, not later, and sort these benefit values into an array with their indices. When you will have finished the computig, the first benefit value is already there, top of the list.
"[...] in each iteration I have to calculate the benefit of all the coefficients and select the best one [...]"
Do you have to re-calculate them, because the benefit of them will change between single iterations or do you mean that you currently just calculate them in each iteration?
Iff the benefit of your coefficients will remain static between iterations you can follow one of the methods recommended by Rens or Marino.
But if your problem domain has a dynamic nature and you need to re-calculate them in each iteration, because your benefit function or something else will change over time, you can try out a technique called fitness approximation as
used in (evolutionary) optimization. There, one has to struggle with expensive fitness/benefit functions, too.
The actual fitness function is used for the initial population and afterwards one uses approximated models (also called surrogates or metamodels) of the fitness function.
Maybe you can transfer these concepts to your problem. The population is your matrix of coefficients and you need to find (or dynamically adapt) a model of your benefit function.
Maybe this (possibly combined with the data-structures as recommended by Rens and Marino) could boost the performance.
Just to get into the topic:
http://en.wikipedia.org/wiki/Fitness_approximation
http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4424972
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1299903
Please, give to us your problem description as a model. Why do we have to assume "what do you mean"? Why do we have to ask like "Maybe you can ...", "May you want ...", "May you mean ...", etc. Your exact model description lets us to give you absolutely relevant answer on your problem.
I would also like to encourage you to tell more about your problem.
A general thing with matrices is that you need to fix the way you traverse them. The inner loop always needs to be on the second index, not the first. Reversing that order might easily be punished with a factor of four.
Second: Java might not be the best for your problem. With this very modest matrix size you can easily go into R which is optimized for matrix and vector manipulations. That might be worth a try.
All comments and suggestions are really appreciated i am planning to present you people with more concise version of the problem including some source code and documentions
Well I have tried many variations including the suggestions provided abocee on how to solve this issue but still in vien. What I am now planning is to convert/translate the code from java to c++ as java treat arrays as object which is on heap and this also consume time if i am not wrong than heap is on virtual memory what you people think does this will solve my problem
We're talking about two different types of heaps here I think! The heap you talk about is where dynamic memory allocation is done. The heap Rens talks about is a data structure which implements a priority queue, where one includes or removes an element in logarithmic time. You can also use a binomial heap where inclusion is done in constant amortized time. The real problem remains whether you need to recalculate "benefit" at each iteration or not. Do you?
Using the heap or the stack should not have a significant impact on your resource consumption, unless your heap is very fragmented. Writing in C++ may have advantages in speed, if you have the time and expertise necessary to perform the optimalizations. Java has advantages here, in that it provides JiT, which allows the virtual machine to optimize on-the-fly (when compiling bytecode->machine code), rather than only at compile time (when compiling Java->bytecode and C++ -> machine code). It depends entirely on the problem, your skills as a C++ programmer and your target machine(s) which is faster.
Jean Goulet the problem you identified is exactly that i have to recalculate. Can you people check my second question posed on this issue as I have only posted two questions check that one as that question contains a link to the paper in which the algorithm really is. Thanks Ren for for your valuable comment. Many thanks everyone here
- Badges
- Science method