From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.7 required=5.0 tests=BAYES_00,MSGID_RANDY autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,14f7200925acb579 X-Google-Attributes: gid103376,public From: Robert Dewar Subject: Re: No Go To's Forever! Date: 2000/03/23 Message-ID: <8bdbof$t19$1@nnrp1.deja.com> X-Deja-AN: 601313372 References: <8bbsc6$aes$1@nnrp1.deja.com> X-Http-Proxy: 1.0 x32.deja.com:80 (Squid/1.1.22) for client 205.232.38.14 Organization: Deja.com - Before you buy. X-Article-Creation-Date: Thu Mar 23 15:03:52 2000 GMT X-MyDeja-Info: XMYDJUIDrobert_dewar Newsgroups: comp.lang.ada X-Http-User-Agent: Mozilla/4.61 [en] (OS/2; I) Date: 2000-03-23T00:00:00+00:00 List-Id: In article , tmoran@bix.com wrote: > >Well that's a different algorithm. It tests J against D'Last > >twice as often as my formulation. > I would hardly call that a different algorithm. Rather a > different implementation of the same algorithm. But if you > want to call it different... Of course it is different, it does a different sequence of computations. The algorithm you give is computationally equivalent, but you actually need to prove this, it is not self evident! An algorithm is a prescription for a sequence of computations, a different sequence is a different algorithm! > That's > going to be a relatively miniscule slowdown. If the data is > in order, yours does N comparisons against J and mine does > N+1. > If the data is sorted backwards, the worst case, yours does > N + N*(N-1)/2 + N*(N-1)*(N-2)/6 comparisons against J and mine > does an additional N*(N-1)/2+1 That's 66% more when N=2 (5 vs 3) > declining to 3% more when N=100 (171,701 vs 166,750) and so forth. > Hardly "twice as many". And nobody who cared would use this > algorithm anyway. Yes, but we are not talking efficiency here, we are talking expression of algorithms. It is a sloppy response to change the algorithm and then claim that pragmatically it is just as good. That's not the point here at all. We are not trying to write efficient sorting algorithms (this particular algorithm is of course chosen to be space efficient). Now let's look at your attempted rewrite: J := D'first; while J < D'last loop if D (J) >= D (J + 1) then -- sorted so far J := J+1; -- continue else Swap (D (J), D (J + 1)); -- out of order, move item J := D'first; -- and start over end if; end loop; The objection here is again to the duplicated code. You have to study this to see that the two assignments to J are identical. Yes, in a trivial case like this, the code duplication is small, but you must see that it is interesting that your only solutions so far involve code duplication to get rid of the goto. It is not at ALL clear that this is a good trade off. Additional code, other things being equal is unlikely to be a good thing. In a larger example, you can find the code duplication getting worse, and even need to introduce a procedure to minimize it. (side comment: from a pragmatic point of view, the reason we use this algorithm is that it is short, so making it longer by duplicating code is a bit counter productive). Pragmatically of course, the whole idea of the that J is always D'First. Unlike my original, where this is evident without scanning the program, here you have a loop whose advertised invariant. I still find the original far clearer. Note that you felt it was necesary to comment the reassignment to J as "start over", but what could be clearer code to match the conceptual idea of "start over" than going back to the beginning. Really it is just like an instruction in a manual saying, "Now you have completed your first reading, turn back to page 1 and start reading again". Let's once again look at my original: > <> > for J in 1 .. N - 1 loop > if D (J) < D (J + 1) then > Swap (D (J), D (J + 1)); > goto Do_It_Again; > end if; > end loop; Just for interest, note that my version has 7 lines, 48 tokens ' yours has 9 lines, 60 tokens Furthermore, you have lost the fundamental point that the inner loop is a FOR loop. We always prefer for loops to while loops since they lead to a much clearer notion of total correctness. Yes, it is true that the outer loop is a while loop and that is fundamental, but I find your formulation really obscures the fact that we have two nested loops here. In fact I would NEVER rewrite this algorithm the way you did if I did not have a goto. Instead I would write it this way if I had a continue statement: Outer : loop Inner : for J in 1 .. N - 1 loop if D (J) < D (J + 1) then Swap (D (J), D (J + 1)); continue Outer; end if; end loop Inner; exit Outer; end loop Outer; That's also 9 lines, and 58 tokens, but preserves the essential element of two nested loops. If your coding standards allow limited use of gotos to simulate CONTINUE then that's the best approach if you are not allowed the original goto. If you are writing in Ada with your hands tied behind your back (no gotos) then the clearest formulation is Continue := True; Outer : while Continue loop Continue := False; Inner : for J in 1 .. N - 1 loop if D (J) < D (J + 1) then Swap (D (J), D (J + 1)); Continue := True; exit Inner; end if; end loop Inner; end loop Outer; I am not very fond of this idiom for continue (I prefer the goto idiom for continue), but it is very familiar, so it seems fine. This again avoids any code duplication, and preserves the essential structure of the algorithm as two nested loops. Indeed the more I look at your rewriting, the less I like it, you have replaced a goto you don't like with spaghetti assignments that obscure the structure of the algorithm. Replacing a for loop with a while loop with an increment is bad in any case. Replacing it with a while loop that plays games with the control variable to obtain the effect of two nested loops expressed with one loop at the syntactic level is really quite nasty. I am always amazed by the extent to which people are willing to go in writing obscure code to avoid gotos; A triumph of form over substance :-) Sent via Deja.com http://www.deja.com/ Before you buy.