Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)

by sundialsvc4 (Abbot)
on Sep 26, 2011 at 13:31 UTC ( #927878=note: print w/ replies, xml ) Need Help??


in reply to An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)

I think that the “You’re Doing It Wrong” post hits the nail on the head:   in most algorithms, it is only (the avoidance of) page faults that really matters.   Thus, if you are looking for “the first all-zero row,” your strategy should be one that avoids hitting every element in the row, because you know that worst-case you are going to cause every virtual-storage page associated with the matrix to be paged-in one at a time (only to discover that no such row exists).   The trade-off is always time vs. space, and so you can solve the problem by maintaining a hash-table or tree, keyed by row-number, which tells you which (range of) rows currently contain all-zero.   And, you reinforce the process by sorting the list of things that you’re going to search for in that hash-or-tree, to minimize the page-faulting activity associated with that data structure.

A so-called “sparse” data structure choice is also usually indicated here, because ... if the row contains zero, why are you “storing” it at all?   You only need to store that which is not the default value (e.g. zero).

When processing the data structure, you know-about and take advantage of the principle of locality of reference, sorting the list of elements you’re going to update or search for, so that the “next” hit is likely to be “close to” the previous one, thus improving the odds that no additional page-fault will occur.

None of these are theoretical, mathematical-abstraction issues.   They are boots-on-the-ground hard principles of proven worth in terms of the one thing that we cannot manufacture:   time.

As far as goto is concerned, I believe that the original notion remains valid:   unpredictable flows of control within an application are highly undesirable and should be avoided when it makes good engineering sense to do so ... which happens to be “almost all the time.”   One of the best observations I’ve seen so far is that there are usually two specific cases where you want to use goto:

  1. You want to cut-short an inner loop.
  2. An “exception to the normal rule” has occurred.
These two special-cases are handled by other programming constructs – last and exception-handling, respectively – and both of these are very well-defined and easy to write compiler support for.   You can still generate good, efficient object-code for each of these constructs, with nary a goto in sight.

One of the key technical issues with goto is that it says, “go to here from anywhere-else,” while saying nothing at all about either the context that you are coming from, or the context that you are going to.   It is extremely difficult to generate good, optimizable object-code in that case.   On the other hand, sometimes goto is absolutely vital:   the code that is generated by yacc is (as far as I recall...) loaded with them.


Comment on Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://927878]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2014-12-23 05:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (135 votes), past polls