Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

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

by davido (Cardinal)
on Sep 24, 2011 at 19:28 UTC ( [id://927675]=perlmeditation: print w/replies, xml ) Need Help??

This is a long meditation, and much of it is wrapped in <readmore> tags so that it doesn't fill the Meditations section with too much text for those who are not interested in the topic. ....ok, here goes...

A few of you are probably aware that I enjoy CS history. The wisdom of some of the earlier innovators in the science of computing is often just as relevant today as it was 30 to 50 years ago. And often the insight encountered when reading old articles is surprising.

In 1968 the Dutch computer scientist Edsger Djikstra published a letter that was originally to be entitled "A Case Against the GO TO Statement", advocating the abolition of 'goto', and the strengthening of structured languages such that 'goto' becomes unnecessary. He posited that a language with a sufficiently expressive grammar wouldn't need goto, and that, in fact, the use of goto makes the disconnect between code-space and execution-time (or chronology) conceptually difficult for the mind to follow. The implication being that such code is harder to write, maintain, and even comprehend useful algorithms.

When the publication's editor, Niklaus Wirth (of Pascal and Modula-II fame) received the letter, prior to publishing it he changed its title to the imortally famous (within those circles) title, "Goto Statement Considered Harmful." Having read the article, as well as some of his other works, I would have to assess that the title, as bold as it is, doesn't rise to the level of disdain Dijkstra had for 'goto', while on the other hand, his original 1968 article seems to fall a little short in putting forward a set of arguments that could present an open and shut case.

But whatever the reason, a few years later (ok, 20 years later, in 1987) a writer-in to the publication "Communications of the ACM" (the same publication where Dijkstra's letter was originally published almost 20 years earlier) sent a letter entitled "'GOTO Considered Harmful' Considered Harmful" that made several assertions suggesting that the mindless abolition of all 'goto's was causing programmers to go to a lot of extra work, and costing millions of dollars in lost productivity. He used an example of a programming challenge that was made easier by use of Goto: Let X be an N x N matrix of 0's and 1's. Find the first row that contains all zeros. He published the following code (obviously not Perl) to make his point:

for i := 1 to n do begin for j := 1 to n do if x[i,j] <> 0 then goto reject; writeln ('The first all-zero row is ', i ); break; reject: end;

I apologize right now for any typos that I may have contributed to the above code; I copied it out of a PDF of a scan of the publication, and think I got it 'character for character' right. I like the "First all-zero row in an NxN matrix" problem because it's fairly simple to implement a number of ways, and because optimizing it to terminate as soon as a match is found almost always involves some sort of short circuit that could be construed by a tight-assed purist as using a disguised version of goto (more on that later).

Rubin went on to show in code that I won't post (but which you can read in the links I provided) that the non-goto versions were longer, required flags, and were more complicated to follow. He then put forth an example of those types of solutions, but reworked to eliminate the need for a flag; it took nine lines (in the same language, which appears to be Pascal).

In a series of followup letters, later that year in the same publication, under the title, "" 'GOTO Considered Harmful' Considered Harmful" Considered Harmful?", it was mentioned that Rubin's non-goto examples were made more complex by inadequacies in the language. Moore proposed a solution that required a non-existent feature in Pascal, but that simplified the problem further. Another followup point seemed to be that while 'goto' is useful sometimes, often its need is created by inadequacies in the language itself. It advocated forms of goto that had more limited semantics (eg., break, next, last, etc.). Several solutions were posted in Pascal and C.

Eventually Dijkstra responded with another letter, "On a Somewhat Disappointing Correspondence." In it, he swiftly mops up Rubin's examples by showing them to contain bugs, or successes by accident.

And of course in 2009 Mark Jason Dominus weighed in through his Universe of Discourse blog with a blog entry entitled, "Dijkstra Was Not Insane"

All this is a pretty good read if you find that sort of thing interesting (which I do). But the real purpose of this meditation is to give a couple Perl examples (and possibly solicit others in Perl or other high-level languages).

In the following code you will find four techniques, each wrapped in a subroutine. The first is recursive (just for the sake of being 'possible'). The second is a simple iterative approach (it most closely echos the non-goto versions of code presented in some of the articles I linked to). The thrid is the highest-level; it uses List::MoreUtils 'firstidx' and 'all' functions, and essentially accomplishes the task in a single line of code if you exclude the subroutine's "setup" and framework. This is probably the preferable approach from a standpoint of clarity.

Then the last approach is a "higher order" functional iterator technique, which manufactures an iterator function, and tests the iterator against a test function which was passed in to the gizmo by function reference along with a test param list. The goal here was a generic functional approach that could easily be made specific to the problem. It's obviously much more complex than the List::MoreUtils approach, and for no particularly good reason other than to demonstrate another technique.

All of the approaches are designed to be an optimized O(n), where by "optimized" I mean that each row test fails as early as possible, and as soon as the first matching row is found, the tests exit immediately. The recursive approach is going to suffer in terms of performance by the call-frame overhead. The functional iterator approach also will suffer from a performance standpoint since each iteration requires a function call to the iterator. But it is a solution that uses tools that are general enough to be applicable to other sorts of tests.

That leaves the simple iterative approach and the List::MoreUtils approach as the "realistic" techniques. Both are an optimized O(n) without extra call-stack overhead found in the other versions. My personal opinion is that the List::MoreUtils version is the highest-level, easiest to understand, and completely devoid of gotos or disguised "limited semantic gotos" (hidden internals could be written in whatever ugly method the author of those functions wants though).

While on the subject of "limited semantic gotos", I suppose that a purist would consider the use of 'last', 'next', multiple 'return' statements, and in other languages, 'break' to be a form of goto; particularly if a label used. If we look at that as "a bad thing", I don't know how we'll ever get past the use of some form of 'goto' in practical programming. On the other hand, if we look at these as tools that take the controversial 'goto' and turn it into less "harmful" short-circuits, it would seem that Perl (as well as many other modern languages) has come a long way since the 60's.

It would be interesting to me to see what other constructs or approaches people might employ in solving the "first all-zero row in an NxN matrix" problem. For one thing, there is probably a better recursive approach. And I'm sure someone could come up with a simpler "functional iterator" approach as well, that retains generic utility. Here is the code I came up with to present a few alternatives.

#/usr/bin/env perl use strict; use warnings; use List::MoreUtils qw/all firstidx/; use v5.12; my @array = ( [ qw/ 1 1 1 1 1 / ], [ qw/ 0 1 1 0 0 / ], [ qw/ 0 0 0 0 1 / ], [ qw/ 0 0 0 0 0 / ], [ qw/ 0 1 0 1 0 / ], ); # Test recursive. if( defined( my $row_index = firstrow_recursive( \@array, # Test data 0 # Begin on row 0. ) ) ) { response( $row_index, 'recursive' ); } # Test iterative if( defined( my $row_index = firstrow_iterative( \@array ) ) ) { response( $row_index, 'simple iterative' ); } # Test moreutils if( defined( my $row_index = firstrow_moreutils( \@array ) ) ) { response( $row_index, 'List::MoreUtils' ); } # Test firstrow_function_iterator if( defined( my $row_index = firstrow_functional_iterator( \@array, # Test data \&test_row, # Test function [ 0 ] # Test function params (0 as test pattern) ) ) ) { response( $row_index, 'functional iterator' ); } # -------------------------- Plain iterative version --------- sub firstrow_iterative { my $matrix = shift; ROW: foreach my $row_idx ( 0 .. $#{ $matrix } ) { foreach my $col ( @{ $matrix->[$row_idx] } ) { next ROW if $col != 0; } return $row_idx; } return undef; } # -------------------------- List::MoreUtils version ---------- sub firstrow_moreutils { my $matrix = shift; if( ( my $index = firstidx { all { $_ == 0 } @$_ } @{ $matrix } ) >= 0 ) { return $index; } return undef; } # -------------------------- Recursive version -------------- sub firstrow_recursive { my ( $array, $row_ix ) = @_; my $row = $array->[ $row_ix ]; return undef unless defined $row; if( homogenous_row( $row, 0 ) ) { return $row_ix; } else { return firstrow_recursive( $array, $row_ix +1 ); } } sub homogenous_row { my $row = shift; my $find = shift; foreach my $col ( @{$row} ) { return 0 if $col != $find; } return 1; } # -------------------------- Function functional iterator version -- sub firstrow_functional_iterator { my $matrix = shift; my $test = shift; my $test_params = shift; my $iterator = make_iterator( $matrix ); my $index = 0; while( defined( my $row = $iterator->() ) ) { return $index if $test->( $row, @{ $test_params } ); $index++; } return undef; } sub make_iterator { my $matrix = shift; my $row_idx = 0; return sub { if( not defined( $matrix->[$row_idx] ) ) { $row_idx = 0; return undef; } return $matrix->[$row_idx++]; } } sub test_row { my $row = shift; my $find = shift; foreach my $col ( @{$row} ) { return 0 if $col != $find; } return 1; } # -------------------- Output helper ----------------------- sub response { my( $row, $technique ) = @_; say "First matrix row to contain all zeros is $row,", " using $technique approach."; }

One regret I have with several of these examples is that by wrapping them in functions I had to change "last" to "return" several times. The result is the same, but I liked the way they worked out with "last" as inline code better than with "return" as subroutines. ...Not really important, but now that I've mentioned it you should be able to spot pretty quickly how the simple iterative approach, in particular, would be slightly different if written inline instead as of a subroutine.

Again, I'd love to see a few other creative techniques.

Point of clarification: I suggest that these are O(n) solutions, yet they all contain nested loops. How could this be? Let 'n' be the total size of the data set, so for NxN where "N" is 5, n (the size of the total data set) = 25. Nobody mentioned it, but I thought that point required refinement.


Dave

Replies are listed 'Best First'.
Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by CountZero (Bishop) on Sep 24, 2011 at 20:10 UTC
    This seems to work as well:
    use Modern::Perl; my @array = ( [ qw/ 1 1 1 1 1 / ], [ qw/ 0 1 1 0 0 / ], [ qw/ 0 0 0 0 1 / ], [ qw/ 0 0 0 0 0 / ], [ qw/ 0 1 0 1 0 / ], ); my $rownumber = 0; for my $row (@array) { do {say "row $rownumber has all zeroes"; last} unless (join '', @$ +row)+0; $rownumber++ }

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

      I like that because it only does one comparison per row.

      I considered a join approach too, but had two concerns. First, while it works in the specific case, if the NxN matrix held more complex strings, it could fail, so I saw it as not general enough to a broader application of the problem. Nevertheless, the problem itself is specific, and your version works great.

      The other concern is that it lacks the optimization of failing as soon as the first non-zero entry is found on a given row. By joining the row, we're already implicitly touching the entire row. On the other hand, it does have the merit of only doing one comparison per row, which is nice. The shortcoming is that it has to join the entire row even if the first element of the row would result in a rejected row.

      Fun!


      Dave

      That's slightly dangerous, because it doesn't work with all possible number formats. An entry of 0e0 (which is a valid zero) causes the comparison to disregard all non-zeros after it, as does two 0.0s (though it warns).

      Of course if one knows that the entries are always exactly 0 or 1, it's quite an elegant solution.

Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by moritz (Cardinal) on Sep 24, 2011 at 20:18 UTC

    My first impulse was to write basically the List::MoreUtils solutions in Perl 6. It has all() and .all built in, but no firstidx, so the solution goes through the detour of creating (index => value) pairs first:

    my @array = [ qw/ 1 1 1 1 1 / ], [ qw/ 0 1 1 0 0 / ], [ qw/ 0 0 0 0 1 / ], [ qw/ 0 0 0 0 0 / ], [ qw/ 0 1 0 -1 0 / ], ; say @array.pairs.first({.value.all == 0 }).key;

    Now .all == 0 should ring a bell for Perl 6 developers, there's a simplification around the corner:

    say @array.pairs.first(*.value.none).key;

    A good solution always plays to the strength of the language that it is implemented in. If Perl 6 didn't have junctions, I'd go the route of calculating the sum instead, which is readily available:

    say @array.pairs.first({ 0 == [+] .value.list}).key;

    (This assumes that no negative entries are allowed. If they are allowed, one could add a >>.abs after the .list to fix it).

    Another approach is to use the fact that 0 is the only number that evaluates to False in boolean context:

    say @array.pairs.first({ not [||] .value.list}).key;

    In both cases I make use of the fact that [op] applies the operator op to a list of values.

Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by BrowserUk (Patriarch) on Sep 24, 2011 at 21:37 UTC
    One regret I have with several of these examples is that by wrapping them in functions I had to change "last" to "return" several times.

    You seem to see the use of return as a poor substitute for last, but to my way of thinking, it is the correct solution. This because it should work in any language that supports subroutines including those in use back when this debate was first started, in a clear and direct way free of flags and gotos and short-circuiting at every opportunity:

    #! perl -slw use strict; sub checkRow { my $ref = shift; $_ and return 1 for @$ref; return; } sub firstAllZeroRow { my $ref = shift; checkRow( $ref->[ $_ ] ) // return $_ for 0 .. $#$ref; return; } my @array = ( [ qw/ 1 1 1 1 1 / ], [ qw/ 0 1 1 0 0 / ], [ qw/ 0 0 0 0 1 / ], [ qw/ 0 0 0 0 0 / ], [ qw/ 0 1 0 1 0 / ], ); print firstAllZeroRow( \@array ); __END__ C:\test>junk50 3

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by GrandFather (Saint) on Sep 24, 2011 at 21:45 UTC

    In Perl we frown on the old C style for loop because almost always there is a better way to do it with a Perl foreach style loop. However, not always. The iterator variant below uses a C style loop to remember the last column and last row dealt with to allow a simple last to short circuit the loops with the state of the loop counter propagating the success or failure.

    my $i; for ($i = 0; $i < @array; ++$i) { my $row = $array[$i]; my $j; for ($j = 0; $j < @$row; ++$j) { last if $row->[$j]; } last if $j == @$row; } print "All zero row at $i\n" if $i != @array;

    Given CountZero's test matrix prints:

    All zero row at 3
    True laziness is hard work
Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by davido (Cardinal) on Sep 24, 2011 at 20:44 UTC

    So I walked away from my meditation for a few minutes and thought of an other solution. Let's assume that the matrix has a pretty random distribution of 0's and 1's, and consequently, that all-zero rows is not a frequent occurrence. The solutions I posted above attempt to reject a row as early as possible to take advantage of this possibility.

    There's another option, and that's to test each row's column 0 on the first iteration. On the second iteration, only test column 1 for those rows that passed the first test. Then for column 2, only test the remaining rows that are still with us. ...and so on.

    I do think that such a solution would require a second array of row numbers to test on the next go-around. That single-dimensional array would start out N rows long, and after each pass would contain fewer elements, each containing a row number from the primary matrix that is still in the running to be tested.

    Computationally I don't think that in an average case such an algorithm would gain anything. It seems that if the original algorithms already eliminate each row as quickly as possible, turning the test on its side and still rejecting rows as quickly as possible would only add programming complexity, an additional memory requirement, while not gaining anything in either average or worst case.

    When I have a moment I'll implement it and add it as an update to this node. At the moment my wife and kids are wondering why I'm holding them up from their outing. ;)

    Update: As promised, here is a version of the search for first row in a matrix containing all zeros, which searches each column, eliminating each row where a non-zero was found in the current column scan. It rejects entire rows from subsequent searches as soon as a non-zero is found, but walks the matrix column by column rather than row by row. The worst case is still O(n) for the size of the data set. In fact I can't think of a situation where there would be a performance gain. And we've got the misfortune of having to also keep track of row numbers in a separate array. So it's really not a win in any regard. But I thought the concept was sort of cool anyway, so here it is:

    use strict; use warnings; use v5.12; my @array = ( [ qw/ 1 0 1 0 1 / ], [ qw/ 0 1 0 1 0 / ], [ qw/ 0 0 1 1 0 / ], [ qw/ 0 0 0 0 1 / ], [ qw/ 0 0 0 0 0 / ], ); if( defined( my $result = find_first_sideways( \@array ) ) ) { say "First row containing all zeros is $result."; } else { say "No rows found to contain all zeros."; } sub find_first_sideways { my $matrix = shift; my @scan = ( 0 .. $#{ $matrix } ); my $depth = 0; while( @scan > 0 and $depth < @{ $matrix->[0] } ) { @scan = grep{ $matrix->[$_][$depth] == 0 } @scan; $depth++; } if( defined( $scan[0] ) ) { return $scan[0]; } else { return undef; } }

    Dave

Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by JavaFan (Canon) on Sep 24, 2011 at 23:05 UTC
    While on the subject of "limited semantic gotos", I suppose that a purist would consider the use of 'last', 'next', multiple 'return' statements, and in other languages, 'break' to be a form of goto; particularly if a label used.
    Uhm, not just a purist. "Goto" is like pregnancy - there isn't a halfway of doing it. Dijkstra's paper isn't about the four letters "g", "o", "t", and "o". His arguments against "goto" hold against "last", "next" and "return" in exactly the same way. Dijkstra's point is, (and IIRC, that's what Dominus wrote as well) that if you want to do any kind of formal proving of your program, life becomes much, much easier if your blocks of code have exactly one entry point, and exactly one exit point. Goto breaks that. And so do "last", "next", "redo", "die", and "return".

      That is exactly right; an excellent interpretation of Dijkstra's paper and Dominus's analysis! Any block that has more than one entry (this doesn't happen quite as often), or more than one exit (this happens a lot) will be difficult to come up with a formal proof. And this is why last, next, etc., can be seen as "limited semantic" forms of goto.

      As I think it over, I can't come up with any good explanation of where we might jump into code blocks at multiple entry points. An exception might be a given/when block. If fall-through is used, then the block has multiple entry points. And if fall-through isn't used, it has multiple entry and exit points. But on the other hand, given/when can be compared to a chain of if-else blocks, so in that sense perhaps the notion of multiple entry/exit points may sort of break down.

      So where do we have an example of common coding practices that involve multiple entry points?


      Dave

        So where do we have an example of common coding practices that involve multiple entry points?

        Around the time of Dijkstra's paper, computed gotos were both possible and quite common in several prominent languages--Fortran, COBOL, BASIC (not forgetting assembler of all flavours). Later, C's switch, which may superficially resemble an if/elseif/else cascade, is actually a computed goto and far more efficient, as only one condition is ever tested.

        For many purposes, the computed goto -- in the form of C switch statement -- is still invaluable. Almost every generated parser consists of a nest of switch statements.

        Any block that has more than one entry ... or more exit ... will be difficult to come up with a formal proof.

        As a reason (for anything), this is (IMO) a crock. How much commercial code is ever formally proven? Effectively none.

        Why?

        • Because in order to make code provable, it has to be ham-strung in so many ways, that it creates verbosity.
        • Writing code that is provably correct is an order of magnitude harder than writing code that isn't.
        • Once written, you have to pay again to have it proven correct.
        • Verifying that proof is harder than producing it.
        • As is famously claimed, even once you've proven it correct, it doesn't mean it will work.
        • And every time you change anything, you've have to start the proofing again.

        There have been many attempts at producing computer languages that can be formally proven. Very few have ever heard of them and no one uses them. For very good reasons.

        Guard statements, in the form of conditional early returns, nexts & lasts may be hard for the formalists to handle and reason about, but for practical programming, they can and do greatly simplify the handling of exceptional and boundary conditions.

        Formalists don't like handling exceptions. Often this is because they don't have the formal notations for doing do. And when they do invent such notations, they are so complex and shrouded in mystery -- think Haskell's Maybe Monad -- that most people don't understand them.

        Heck. Formalists don't even like handling such practical matters as integer size limitations and floating point inaccuracies. It is often possible to prove an algorithm correct mathematically, only for it to fail horribly and mysteriously when intermediate results are bigger than platform limits for integers or FP values. The classic example is the typical calculation of the mid point in many divide & conquer algorithms. Where mid = ( lo + hi ) / 2 can go out of bounds.

        Ham-stringing the programmer to make life easier for the formal proofing that will never happen is simply bad reasoning.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
        So where do we have an example of common coding practices that involve multiple entry points?
        I wouldn't call it "common", but Duff's Device is an example of multiple entry points.

        In fact, any block of code with labels, and jumps to those labels (or in BASIC, line numbers) has blocks with multiple entry points.

      ... if you want to do any kind of formal proving of your program, life becomes much, much easier if your blocks of code have exactly one entry point, and exactly one exit point.

      Certainly a more practical conclusion should be "functional units should do one and only one thing, and that thing well" instead of "avoid obvious flow control at any language level lower than the language primitive which enables functional units". Otherwise you have trouble with if.


      Improve your skills with Modern Perl: the free book.

        Certainly a more practical conclusion should be "functional units should do one and only one thing, and that thing well"
        Eh? I don't follow. How's that even remotely related to having structured blocks?
        avoid obvious flow control at any language level lower than the language primitive which enables functional units". Otherwise you have trouble with if.
        How's that? An if construct is well understood when it comes to formal proofs, and it's a block with exactly one entry, and one exit point:
        ,---> then-block ---, / T \ pre ---> expression ---+ +---> post \ F / `---> else-block ---'
Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by johngg (Canon) on Sep 24, 2011 at 22:24 UTC

    Using List::Util->sum() and grep seems to work.

    knoppix@Microknoppix:~$ perl -MList::Util=sum -E ' > @array = ( > [ qw{ 1 1 1 1 1 } ], > [ qw{ 0 1 1 0 0 } ], > [ qw{ 0 0 0 0 1 } ], > [ qw{ 0 0 0 0 0 } ], > [ qw{ 0 1 0 1 0 } ], > [ qw{ 0 0 0 0 0 } ], > ); > say qq{First all-zero row is @{ [ > ( grep { ! sum @{ $array[ $_ ] } } 0 .. $#array )[ 0 ] ] }};' First all-zero row is 3 knoppix@Microknoppix:~$

    I hope this is of interest.

    Update: I'm stupid! It's even simpler to use List::Util->first() instead of grep.

    knoppix@Microknoppix:~$ perl -MList::Util=sum,first -E ' > @array = ( > [ qw{ 1 1 1 1 1 } ], > [ qw{ 0 1 1 0 0 } ], > [ qw{ 0 0 0 0 1 } ], > [ qw{ 0 0 0 0 0 } ], > [ qw{ 0 1 0 1 0 } ], > [ qw{ 0 0 0 0 0 } ], > ); > say q{First all-zero row is }, > first { ! sum @{ $array[ $_ ] } } 0 .. $#array;' First all-zero row is 3 knoppix@Microknoppix:~$

    Update 2: Stupid and naive :-( List::Util->sum() is not a good tool as it will fail on something as simple as the new second row below. Using a List::Util->first() within another List::Util->first() might be better.

    knoppix@Microknoppix:~$ perl -MList::Util=first -E ' > @array = ( > [ qw{ 1 1 1 1 1 } ], > [ qw{ 1 0 0 -1 0 } ], > [ qw{ 0 1 1 0 0 } ], > [ qw{ 0 0 0 0 1 } ], > [ qw{ 0 0 0 0 0 } ], > [ qw{ 0 1 0 1 0 } ], > [ qw{ 0 0 0 0 0 } ], > ); > > $found = first { > $i = $_; > $res = first { > $array[ $i ]->[ $_ ] != 0 > } 0 .. $#{ $array[ $i ] }; > ! defined $res; > } 0 .. $#array; > say > q{First all-zero row is -> }, > defined $found > ? $found > : q{none found}; > ' First all-zero row is -> 4 knoppix@Microknoppix:~$

    Cheers,

    JohnGG

      But how many individual values are tested? (Ie. grep will examine an entire row even if the first value in that row is non-zero. Etc.)


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

        I think I've seen it written somewhere that List::Util->first() will efficiently break out as soon as it finds the first item that passes the condition rather than testing all of the items. I've tried to confirm this by looking at the module source but failed to find the relevant code :-s

        Cheers,

        JohnGG

Re: An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful)
by ambrus (Abbot) on Sep 25, 2011 at 07:47 UTC

    I am quite partial to the while with stop variable solution. This can be coded easily in almost any language in a goto-less way, and C compilers these days should be able to optimize the stop variables away so it's as efficient as the solution with goto. It is also easy to derive by hand from the version using last.

    Here's a perl implementation, but written in such a style that it's easy to translate to other languages. I show two versions. Either version of the function returns the index of the first all-zero row, or -1 if none of the rows are non-zero.

    use warnings; use 5.014; use strict; sub first_allzero_row_a { my($a) = @_; my($r, $q, $c, $f, $o); $o = -1; $r = 0; $q = 0; while (!$q && $r < @$a) { $c = 0; $f = 0; while (!$f && $c < @{$$a[$r]}) { if (0 != ${$$a[$r]}[$c]) { $f = 1; } else { $c++; } } if (!$f) { $q = 1; $o = $r; } else { $r++; } } $o; } sub first_allzero_row_b { my($a) = @_; my($r, $q, $o); $o = -1; $r = 0; $q = 0; while (!$q && $r < @$a) { if (is_allzero($$a[$r])) { $q = 1; $o = $r; } else { $r++; } } $o; } sub is_allzero { my($a) = @_; my($c, $f); $c = 0; $f = 0; while (!$f && $c < @$a) { if (0 != $$a[$c]) { $f = 1; } else { $c++; } } !$f; }

    A more difficult example for using this style can be found in the notebook info1-gy4 (fallback if previous link is broken), near the middle. This I wrote for an introduction to programming course (though here we're interested in the extra material we haven't really covered on the course). The programs are in baby-Python.

    The problem solved is the following. (I encourage you all to try to write your own solutions for this one.) We would like to demonstrate a theorem of Gauss that says any natural number can be written as a sum of three triangular numbers. The triangular numbers are the numbers of form n*(n+1)/2 where n is an integer. For this, we want to print one such decomposition to three triangular numbers for each number up to 80. You must not print more than one solution per number, because that would degenerate to a wall of text, and it would also be hard to see whether any number is skipped.

    The two relevant solutions, translated to perl for your convenience, can be found in Write any natural number as sum of three triangular numbers (second and third solutions). (The output of the two solutions differ, but they're equally valid.)

    Update: moved triangular numbers example code from this reply to separate meditation.

      I'm not arguing with your preference here -- personal preference, and the right to it, is a very strong instinct of mine -- but I simply do not understand how you can prefer this level of complexity to this level of simplicity?

      Can you offer any thoughts that might help me understand your preference?


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
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

    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://927675]
Front-paged by keszler
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (6)
As of 2024-03-19 08:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found