Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Fortran Programming Language

many "ifs" versus linked list of true cases


I want to solve a large set, say 5000, of numbered, quite similar
problems but with different values of certain arguments in each case.
Solution of each case is by iteration; the number of iterations
required for a given case could be large or small, depending on the
values of parameters.  The maximum number of necessary iterations is
perhaps 50, but only a small proportion of cases are likely to require
very many iterations.

For particular reasons I want my outer loop to be iteration number; so
that on a given iteration, I may or may not need to process a given
case, according to whether or not it has been solved.

My question is, which is more efficient:  on each iteration, to ask in
each of 5000 cases whether say "solved(case) == .TRUE.", or to
maintain a linked list integer indices of so-far-unsolved cases and
cycle over that list each time, deleting cases from the list as they
are solved?

I have a suspicion that "it depends," but if anyone has a sense that
one method is likely to be better, I'd like to know about it.  There
was some suggestion in earlier discussions here that allocations
aren't all that cheap, so is the seeming elegance of not always asking
"is this case solved?" is outweighed by the expense of that?

The short answer is that 250,000 executions of an "if" statement might
not cost you enough to make this worth worrying about.  But you probably
knew that.

If you'd rather do the linked list, you don't have to allocate a node
for each case;  you allocate one integer array, next_unsolved(0:cases),
initialize next_unsolved(i) = i + 1 for i < cases and
next_unsolved(cases) = -1.  Pretend case 0 is always unsolved.  When
next_unsolved(0) .eq. -1, you're done.

Or something like that.  Have fun.

Louis

On 21 May, 19:59, Mark Morss <mfmo@aep.com> wrote:

Why should it need allocation to ask if a particular case is solved?
Is "solved(case)" a function, or just an array element? If it's an
array then there need be no allocation in the loop - it's just a
simple test on an array element. You can set up the array just once
before the iteration starts.

So, I'm not 100% clear what you are trying to do - but it seems you
are trying to solve ~5000 similar problems all at once in one big
iteration loop.

Do you have a really good reason to try and do all 5000 cases all at
once, instead of doing them one at a time?! In your first iteration,
when *all* the problems are unsolved, you may need ~5000 times as much
memory if you solve them all at once than if you solve them one after
another! Can you keep it simple and save memory by solving them one at
a time? Just do all the iterations on problem 1 until it's solved,
then the same for problem 2, then 3,... The code might be shorter and
simpler to test too.

But anyway, let's assume you do *have *to solve them all at once,
then:

a) Computing 5000 'if' statements don't take long on a modern PC -
just seconds or less. So, if checking whether a particular problem is
solved with a single 'if' statement is a *substantial* part of the
code run time then it seems each problem must run so quickly that it's
not worth worrying about run time at all... (unless you're an
optimisation fanatic for the love of it, in which case you will try
both approaches and 10 others too just for fun :-) )

or

b) If each problem *does* take a while to solve, then the work
required to perform check is likely to be *minuscule* compared to the
work done solving the 5000 problems! So I would suggest you
concentrate on improving the algorithm used to solve each problem and
keep the other code as simple as possible. Linked list codes will be
complex to write, test and document. Concentrate on coding and
debugging time as well as run time - IMHO it would be very easy to
waste days of coding in order to save a few seconds (and life's short
enough already)!

Good luck,
andy

Just to ensure I grok what you mean:

You have to solve 5000 similar equations in an iterative loop and you want to check which
of those have been solved in each loop trip since the number of iterations required may be
slightly different for each equation?

What about something like:

   INTEGER, PARAMETER :: N = 5000, MAX_ITER = 100
   LOGICAL :: solved(N) = .FALSE.
   INTEGER :: unsolved(N)
   INTEGER :: i, m, iter

   iter = 0
   iteration_loop: DO
     iter = iter + 1
     IF ( ALL(solved) .OR. iter > MAX_ITER ) EXIT iteration_loop

     m = COUNT(.NOT. solved)
     unsolved(1:m) = PACK((/(i,i=1,N)/), .not.solved)

     ! Try to solve remaining unsolved equations
     unsolved_loop: DO i = 1, m

       ... solution code ...

       ! If equation was solved, update logical list
       ! and move to the next equation in this iteration
       IF ( ...solution reached... ) THEN
         solved(unsolved(i)) = .TRUE.
         CYCLE unsolved_loop
       END IF

       ... other stuff, e.g. updating parameters for next ...
       ... iteration for this as yet unsolved equation? ...

     END DO unsolved_loop
   END DO iteration_loop

   WRITE(*,*)ALL(solved)  ! T if all solved, F if max iterations reached

?

Of course, you would most likely replace the inner "unsolved_loop"  with some fancy matrix
manipulation but you get the idea.

cheers,

paulv

--
Paul van Delst             Ride lots.
CIMSS @ NOAA/NCEP/EMC               Eddy Merckx

The general rule for determining which method is faster is to try it
both ways.  If speed really is important the time spent coding will be
insignificant.  If speed isn't really important why worry about which
method to use?

Mark Morss wrote:
> My question is, which is more efficient:  on each iteration, to ask in
> each of 5000 cases whether say "solved(case) == .TRUE.", or to
> maintain a linked list integer indices of so-far-unsolved cases and
> cycle over that list each time, deleting cases from the list as they
> are solved?

> I have a suspicion that "it depends," but if anyone has a sense that
> one method is likely to be better, I'd like to know about it.  There
> was some suggestion in earlier discussions here that allocations
> aren't all that cheap, so is the seeming elegance of not always asking
> "is this case solved?" is outweighed by the expense of that?

Asking in 5000 cases whether solved(case) == .TRUE. will take an
entirely negligible amount of time.  The code for it is one line,
perhaps three at the most, and trivally simple.

Getting a linked-list thingy to work will most likely take a
non-negligible amount of programming time, and will likely be buggy on
the first draft.  It cannot possibly save any significant amount of
runtime, because there isn't a significant amount of runtime to be saved.

I think that gives you a pretty clear winner.

(It may be that the second one could be done fairly simply too, but I
think I'd save that for after I had the system working.)

- Brooks

--
The "bmoses-nospam" address is valid; no unmunging needed.

On May 21, 2:59 pm, Mark Morss <mfmo@aep.com> wrote:

Everyone gave excellent advice; thanks very much to all for taking the
time.
Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc