davidsen@sungod.crd.ge.com (William Davidsen) (07/29/89)
In article <18764@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: | Having a complete binary tree (which is a condition for heaps) means | shorter code paths. A plain binary tree will work, but if it is | unbalanced you will end up doing more comparisons than necessary. | (`Complete' means that if you number the nodes like this: | | 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 This brings up the one feature of FORTRAN which is missing and would be useful in C (and other structured languages)... the arithmetic IF. When doing tree searches and many kinds of sorts, you often have logic which looks something like this: if (a == b) { /* match found */ } else if (a < b) { /* search lower portion of the tree */ } else { /* search upper portion of the tree */ } While most compilers will get rid of common subexpressions and stuff in this case, the code generated rarely makes use of the repeated testing of flags set by one compare, and the code is not as readable as it might be. Some contruct which clearly shows what the user is trying to do would add to the readability, if not the speed, of the code. bill davidsen (davidsen@crdos1.crd.GE.COM) {uunet | philabs}!crdgw1!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
rsalz@bbn.com (Rich Salz) (07/29/89)
In <1389@crdgw1.crd.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > This brings up the one feature of FORTRAN which is missing and would >be useful in C (and other structured languages)... the arithmetic IF. Ick. The impression I have is that most folks think arithmetic IF is a bad thing. I don't really know, and it doesn't matter too much. > When doing tree searches and many kinds of sorts, you often have logic >which looks something like this: > if (a == b) { > /* match found */ > } > else if (a < b) { > /* search lower portion of the tree */ > } > else { > /* search upper portion of the tree */ > } Easy enough. First, create a helper function: int sgn(x) int x; { return x ? (x < 0 : -1 : 1) : 0; } Then: switch(sgn(a - b)) { case -1: ... break; case 0: ... break; case 1: ... break; } -- Please send comp.sources.unix-related mail to rsalz@uunet.uu.net. Use a domain-based address or give alternate paths, or you may lose out.
zdenko@csd4.milw.wisc.edu (Zdenko Tomasic) (07/29/89)
In article <1913@prune.bbn.com> rsalz@bbn.com (Rich Salz) writes: >In <1389@crdgw1.crd.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: >... >Ick. The impression I have is that most folks think arithmetic IF is >a bad thing. I don't really know, and it doesn't matter too much. > The arithmetic if is useful only with integer expression and when all three branches are different. The problem is that it forces on programmer at least 2 or 3 labels (usually with 0-3 go to's) when 1 or 2 will do in the corresponding logical if statement or 0 or 1 with if-then-else statement. "Smart" programers also often like to get "tricky" by positioning the arithmetic if branches all over the code or making "knots" in the program flow. However, most of the above is cured by DISCIPLINED PROGRAMMING and not the abolishment of the arithmetic if statement. Moral: Use it only for distinct three-way branches and other ifs for other cases (know your tools!). -- ___________________________________________________________________ Zdenko Tomasic, UWM, Chem. Dept., P.O. Box 413, Milwaukee, WI 53201 UUCP: uwvax!uwmcsd1!uwmcsd4!zdenko ARPA: zdenko@csd4.milw.wisc.edu
cc100aa@prism.gatech.EDU (Ray Spalding) (07/30/89)
In article <1913@prune.bbn.com> rsalz@bbn.com (Rich Salz) writes: >... >Easy enough. First, create a helper function: > int > sgn(x) > int x; > { > return x ? (x < 0 : -1 : 1) : 0; ^ > } >... That colon should be a question mark, I believe. My understanding of the arithmetic (3-way branch) IF in Fortran is that in ancient (pre '66) compilers it was often the ONLY type of conditional branch implemented. In an attempt to be "portable", many programmers used this type of IF exclusively. IMHO, arithmetic IFs make programs needlessly difficult to understand. This is due to the expression having to work out relative to zero, and (as was pointed out before) the number of statement labels and goto's required. I hope I never see another one. And, I certainly hope no such anachronism is ever adopted in C. -- Ray Spalding Georgia Institute of Technology, Atlanta Georgia, 30332 uucp: ...!{allegra,amd,hplabs,ut-ngp}!gatech!prism!cc100aa Internet: cc100aa@prism.gatech.edu