3
$\begingroup$

Let's say I have an algorithm something like as follows:

1 eliminate stuff from a list called reactions
2 for each element in reactions:
3    if one thing is computable:
4        compute it
5    else:
6        eliminate element from reactions, GOTO 1

Can I change it too

1 eliminate stuff from a list called reactions
2 while length of reactions is > 0:
3    while thing is computable:
4        for each element in reactions
5            compute it and append it to list called relevant_reactions
6            eliminate element from reactions
7    eliminate element from reactions

without any changes in efficiency? If there are any ways to improve the efficiency please let me know.

For reference, this algorithm is from page 8 of the paper Reachability Problems for Continuous Chemical Reaction Networks. The reason this question is important is because the main result of this paper is showing that the algorithm runs in polynomial time.

The reason the 6th and 7th lines are the same is to eliminate both those elements where the thing is not computable and those where it is computable (those are moved to a new list). I feel like there's a better way to do that part, however, so any advice there would be appreciated.


I should point out that the main reason I am rewriting the algorithm is to remove the GOTO 1. It's hard to implement in Python 3 (my language of choice) and it seems to be generally considered bad practice.

I should also point out what exactly the "thing is computable" is for sake of context/completeness. Basically, that line is computing a vector (that must be $\in \mathbb{Q}^R_{\geq 0}$) that is multiplied by a matrix and when added to another vector should equal another vector. The vector elements are concentrations of chemicals. The matrix contains the net change of various reactions. It would look something like this: (vector that represents current state of the system) + (matrix of net change of every reaction in the list reactions)*(vector we are solving for) = (vector representing current state) and the element in reactions (the one in the iteration of the for loop, also in the vector we are solving for) must be greater than 0. If you found that confusing, no wonder, I did too (especially the last part). The relevant part in the paper is line 3 of Algorithm 1 in section 3. The exact line is

Compute a vector $F_{\rho}\in\mathbb{Q}^R_{\geq 0}$ such that $\mathbf{c}+\mathbf{M}F_{\rho} = \mathbf{d}$ and $F_{\rho}(\rho) > 0$, if one exists

$\endgroup$
  • $\begingroup$ @Raphael I've tried reading through this question/answer but I'm afraid it's over my head. I don't really understand it at all. I'm not sure how to calculate each step's complexity. I'm also not sure how to get into the right "operational semantics" - I read through the article, but it's again over my head. $\endgroup$ – heather May 20 '17 at 13:59
  • $\begingroup$ @heather " I'm not sure how to calculate each step's complexity." -- then you have to unfold the steps! You give very high-level pseudo-code, which of course does not have any formal semantics. The approach from that question only works once you've written down the algorithm in sufficient detail. $\endgroup$ – Raphael May 20 '17 at 19:24
3
$\begingroup$

With the question as it is written right now, I have no idea what "one thing" and "thing" are, the second version modifies a list named "relevant_reactions" that isn't present in the first version, so all in all I would say that your question is impossible to answer.

You say that "goto" is considered bad practice, but instead of removing the "goto", you complete rewrote everything from scratch. If you don't like the "goto" here's a way that doesn't change your algorithm at all:

1 eliminate stuff from a list called reactions
2 all_done = false
3 while all_done is false
4     all_computable = true
5     for each element in reactions:
6         if all_computable is false:
7             do nothing
8         else if one thing is computable:
9             compute it
10        else:
11            eliminate element from reactions, all_computable = false
12     if all_computable is true:
13         all_done = true
$\endgroup$
2
$\begingroup$

Modern languages are heavily optimized, so much so that it is hard to predict if minor code changes will make an algorithm run faster. In particular with matrix math, whether the language implementation replaces loops with vector instructions or offloads parallelizable operations to a GPU is going to matter much more than pretty much anything you can adjust by hand.

What you should always do is code for completeness and correctness and only then use a profiler on the executable if it's not running fast enough. Optimize the parts that the profiler tells you consume the most CPU time.

$\endgroup$
  • 1
    $\begingroup$ Apologies, but this doesn't really answer the question. My problem is using GOTO is considered bad practice, and is hard to implement in my language of choice. I was planning on using a profiler at the end, but this seemed to me important enough to change. $\endgroup$ – heather May 20 '17 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.