Computer Science

heather

12:43 AM

hello

is anyone around?

I have a question about algorithmic complexity, and I'm looking at the canonical post

118

Q: Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms, but most answers seem to be tailor-made. On the o...

and having a lot of trouble.

vzn

1:40 AM

@heather hi, just try to write out your question, if it has some effort its ok on main site

heather

@vzn, it doesn't really have much effort because I have no idea - I am asking on another chat site.

vzn

@heather somewhere else on SE, another room? feel free to ask here

heather

discussion is going on in hbar

nbro

@heather What's the question? Even though I may not answer it, since I have to leave in a few minutes, someone else later will see it here and, eventually, try to answer it.

heather

specifically, I want to know a. whether or not this algorithm is polynomial time and b. whether or not this algorithm is more or less efficient than another. the algorithm in question being the third here, compared to the first on the same question

from my conversation with dmckee in hbar it seems that the third is slower than the first, but may still be in polynomial time

nbro

1:46 AM

@heather You're not asking directly about the performance of the algorithms, but how they work, at least from what I think is your original question.

heather

I'm sorry, I don't know much about it - what's the distinguishing factor between the two?

nbro

Between the two what?

heather

"performance" vs. "how they work" - as far as I can tell i'm asking about the former not latter

nbro

From your question: "without any changes in efficiency or how the algorithm works?"

heather

hmm, okay, i should edit the question then. i also just realized (with the help of dmckee) an error in the third algorithm, so i'll try to rewrite it.

nbro

1:51 AM

the only question I can identify from that sentence is how does the algorithm work.

vzn

@heather looking at the paper. find it very advanced/ theoretical/ hard to follow. but it could probably be simplified some.

heather

@vzn, yeah, it's way over my head.

i'm working on it though =)

vzn

@heather there is an area of CS using dynamic equations to simulate computation...

nbro

@heather Maybe you should also number the lines of the pseudocode in your question. That GOTO 1 isn't understandable (or at least one can't be sure about its meaning) in that context...

heather

@nbro okay

vzn

1:57 AM

other comment is that serious coders never use GOTO... it was given up decades ago wrt "good style/ best practices" etc...

nbro

@vzn probably that's just pseudocode...

heather

@vzn yeah...that's why i'm trying to rewrite it =)

@nbro it literally says in the algorithm in the paper "GOTO 1"

where 1 is the line (that will soon be) marked one

nbro

@heather so, your problem is just about removing the goto 1? For a moment I thought you wanted to add a new operation in the else block...

heather

@nbro nope.

it's about the goto.

nbro

@vzn By the way, goto is considered bad practice (in general), but in a few cases you can't avoid it, and is actually convienent!

heather

2:04 AM

my question is updated (again) to more accurately reflect my problem

nbro

Does the "thing that is computable" depend on the reactions?

(btw I really have to leave, but, at least, now your question, I think, is more understandable, and I hope somebody will help you faster)

heather

The "thing that is computable" is computing a vector 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.

nbro

@heather well, my question was if these vectors or matrices depend on some element contained in "reactions"

heather

yes.

as I understand it, yes.

I updated my question with further explanation

heather

3:02 AM

good night

iTayb

7:48 AM

does anymore here has a moment to look into cs.stackexchange.com/questions/75638/… ?

i find this question interesting, but it looks like it didn't get any answers yet

Evil

3:44 PM

@heather your code still differs, unless some checks are ommited. With complexity, they differ by constant, but to optimise it the mere loops are not enough. It depends on the functions called and execution time taken.

heather

@Evil how does it differ?

(I'm honestly about ready to give up and just use GOTO even though it's supposed to be bad practice.)

Evil

goto is not a bad practice. Abusing it or making a loop is.

E1:
eliminate(reactions);
foreach(element in reactions) {
if(element.isComputable()){
element.compute();
} else {
reactions.remove(element);
}
}
goto E1;

eliminate(reactions);

while(reactions.length > 0) {

foreach(element in reactions) {
if(element.isComputable()) {
element.compute();
relevant_reactions.push(element);
reactions.remove(element);
}
}
}

Og no, chat destroyed my formatting :/

Anyway, the conditions differ. Also the code seems a bit like busy waiting. The two versions differ where in fact it spends the not productive time. If you have some change in external scope that indicates the change that some reactions are computable then run it, otherwise it essentially loops utilizing CPU

goto was created for one important reason: if you have a dozen of nested loops and the innermost one is to find some solution, when it finds it all outter loops must be communicated, e.g. by variable "running". So it makes a control flow polluted by checks.

After finding solution goto to escape loop is preffered (by those who accept it as proper instruction). But goto in some languages allows to go backward or jump into nested loop. This is hard to read and check. Then it is a disaster.

heather

so in this case GOTO is fine?

but the problem is GOTO isn't supported by python

i think

i mean, i guess i could use this

11

A: Is there a label/goto in Python?

I recently wrote a function decorator that enables goto in Python, just like that: from goto import with_goto @with_goto def range(start, stop): i = start result = [] label .begin if i == stop: goto .end result.append(i) i += 1 goto .begin label .end ...

Evil

3:59 PM

no, but not because of "goto" itself, but because of busy wait. Both solutions are looping like crazy. I assume that there are some dependencies on external state (even time). So after executing instructions like some_potential_computable_may_appear();

Invoke the function from there

Also, if there are some uncomputable reactions (like never), you will not mannage to do it without threads

heather

i'm sorry, i don't quite understand what you mean. both algorithms are inefficient?

Evil

No clue, it depends on what you compute and how long it takes. But the flow is bad.

E1: dosomething(); goto E1; is the same as while(true) dosomething();

while(true) is ok for server, for something that must run forever (until interrupt or shutdown), but it is not that good to run computations

For example oxygen is needed, but it is lacking right now. Take your code and without goto pack it into a function (let me call it probableReaction). Now some event or call resources.onNewStuff = probableReaction. Somewhere call resources.add(oxygen)

So the loop does not run all the time, one check after some event, if this is more complicated put some variable e.g. changed = false, and when there was actual computation, flug it and run once more.

heather

4:19 PM

no, it isn't adding anything to a list (the original algorithm)

Evil

Ok, but it was a pseudocode? Anyway, I may translated it poorly, your second code has a nice stop property, after each iteration one reaction was eliminated, either computed or not, but I changed it assuming it was not intentional.

heather

@Evil what?

I intended it to eliminate reactions

either eliminate completely or move to a second list, so the while len(reactions) >0: loop would work

Evil

But only if computed, right?

heather

if not computable, it is eliminated completely, if computed, it is moved to a second list.

(and removed from the first)

the original, it is merely run until everything that cannot be computed is eliminated, but I didn't know how to do that w/o a GOTO, so I used the length check and moved to a different list.

Evil

Mhm, ok, so the both codes will run exactly reactions.length times, so these are the same, but the "while" one is nicer.

So in that case, don't use goto, because it is really that bad practice everyone mentions.

It is a simple loop in disguise, so it is the case when normal loop should be used.

Mhm, no, there is no escape from goto, the goto code runs forever, while code doesn't. To make it work there should be check if no more reactions goto E2, E2 label placed after the code. So you have a winner.

heather

4:37 PM

so mine is more efficient than the original algorithm?

Evil

No, the original is broken, yours is not. If you fix the original these works similar, yours pushes the reactions to some list, so it is a constant time operation * number of elements.

heather

how is the original broken? it does end.

it restarts everytime it hits upon something not computable, but that uncomputable thing is removed, so eventually it will be able to run all the way through, either because the list is empty or everything in the list is computable.

Evil

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

Goto is in "else" clause or not?

heather

GOTO is in else clause

Evil

I probably finally got it. So there are no differences then.

sorry, my bad, I read it on mobile and "goto" is in new line ;)

heather

4:44 PM

@Evil not a problem =)

so they are both the same efficiency?

and also, is there anyway to make my algorithm more efficient?

anyway, you could put that as an answer =)

Evil

@heather no. These are only loops, that execute the same number if times. They differ by number of checks and push onto list. It really does not make any difference. If you want to speed it up, you have to rewrite actuall computation, use threads, GPU, or something else, change the accuracy.

heather

okay.

Evil

If foreach works as intended, the goto is in fact not needed, it will only restart the foreach loop, if elements are at the end of the list, it is bad idea. Sorry, now read it without line folds. It is essentially superflous.

Just put eliminate in else clause, after discarding goto, and it seems ok

@heather I do not have a time ;)

heather

5:02 PM

@Evil but it is necessary - so the removing elements from the list works, actually - i think there might be a problem with that.

eliminate stuff from a list called reactions
while len(reactions) > 0:
    while thing is computable:
        for i in reactions:
            relevant_reactions.append(compute whatever)
            reactions.del(i)
    reactions.del(i)

^if i do it like this, in python

i'm not sure the loop will work, because it deletes the value in (i) so the value that was in i+1 moves to i, so it skips something

so there is an error - I just realized this!

hmm, how to fix...

maybe list comprehension...

Evil

Just a hint. Do profile the code, check what takes the highest share of overall time -> this is what you want to optimise. Not some loops.

heather

yeah - first i'll have to fix this error though. thank you for your help!

Evil

10:50 PM

@heather I just skimmed the original text. I wonder if this goto means that the matrices to calculate are dependent?

Because otherwise it would be nice to thread all calculations and then gather good ones, if there are no false positives it still may run that way.

Transcript for