Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Algorithm design

by Phemur (Beadle)
on May 25, 2002 at 11:28 UTC ( #169259=perlmeditation: print w/ replies, xml ) Need Help??

Good day fellow Monks,

I have a question about algorithm design. Most of the Perl scripts I've examined on the site of that I've written (or more precisely, attempted to write) were created to accomplish a specific task. They involved maybe one or two algorithms to do so, and some algorithms were a bit more complicated than others.

Most professional programmers will tell you that you should do a minimum of design when building an application (that minimum varies between each programmer). But application design tends to describe the overall architecture of the program, not the algorithms.

Since Perl scripts are mostly algorithms, OO design (and other methodologies) doesn't apply here. So how do you go about designing your scripts? Do you simply bring up VI/Emacs and start coding? Do you use an algorithm design tool (like a flowchart diagrammer)? Pen and Paper?

My current approach has been writing out pseudocode, which lets me think in terms of the task, and not of the language.I find that my scripts are usually much cleaner and simpler, and that they run the first time I try them. The other benefit is that they're much easier to explain and document for others on my team. I'd like to streamline this process a bit, make it more efficient.

Thanks in advance for your advice,

Phemur

Comment on Algorithm design
Re: Algorithm design
by atcroft (Monsignor) on May 25, 2002 at 12:11 UTC

    I suspect everyone will have a little different response here, and I look forward to them myself. I enjoyed your own comments as well.

    In my job, some coding I am asked to do is maintanence, so in those cases, I try to talk to one or more of the users experiencing the difficulty or requesting the feature to try to get a feel for what is needed/wanted, then with a whiteboard or pen/pencil and paper, start to get an idea of what should happen with sample data, then begin to flesh out the necessary code snippets, modifying a copy of the code in question to provide the desired result. Test, modify, test, modify, test, ... until finally I can show it to the interested persons for feedback, then let them test it, then begin using it.

    For new programs, I do a lot of the same-get feedback on what is desired, then try to lay out sample data so I know what the expected output should be, sometimes so I can design my data structures, then begin to code (sometimes in pseudocode or snippets first), testing on sample data, until I have something I can present for feedback and usability testing (big words meaning "does it work" and "are the results usable"), then actual production use.

    Admittedly, though, sometimes something breaks and I have a very short timeframe in which to attempt a fix, in which case while I may try to do this routine, sometimes I miss something, which can make for a very flustrating and rough week or longer. (Which is why I'm glad this one is over!)

Re: Algorithm design
by vladb (Vicar) on May 25, 2002 at 13:03 UTC
    In my work, I try to follow common software development principles. Thus, I first analyze the 'needs' and then the 'means'. The former entails client specifications and requirements, whereas the latter includes the 'fun' part: design, coding, implementation, testing etc. The part you are aquiring about falls between the 'design' and 'coding' stages. Algorithm design is made much easier provided more abstract design was given due attention.

    A good case in point is Damian Conway's work on the Parse::FastDescent module. In his April 5, 2002 diary entry he stresses the importance of talking your design over with other clever developers on your team. Also, a lot of useful examples could be drawn from the way development of Perl 6 is approached. One that immediately springs to my mind is that there's always a lot of outside input on any given piece of Perl 6 design. Such discussions is the key to assuring that your future design will cover all the rough edges etc.

    Armed with a good (abstract) design, writing algorithms is made much easier. Certainly, algorithms can be either too abstract or detailed. In building my algorithm, I always attempt to follow through with a 'top-down' design principle. I would first design (discuss, test, etc.) abstract program algorithm that are concerned with the 'overall' work of my code, and only than concentrate on specific areas.

    I should also mention that design of your supporting data structures is integral to optimal and dependable algorithms. If little thought and effort is given to the design of your program's data structures, eventually your algorithm will reflect that. In my life, I have met programs which had their data structured in a sloppy or even haphazard way. Consequently, overall program flow seemed to suffer extensively. Here and there, I would notice serious lapses in program logic. It almost seemed as if the original author had gone through extreme pains to wrap his/her program code around its poorly designed data structures.

    UPDATE: was compelled to add another paragraph to further my point somewhat ;-)

    _____________________
    $"=q;grep;;$,=q"grep";for(`find . -name ".saves*~"`){s;$/;;;/(.*-(\d+) +-.*)$/; $_=["ps -e -o pid | "," $2 | "," -v "," "];`@$_`?{print"+ $1"}:{print" +- $1"}&&`rm $1`; print$\;}
      Don't forget the additional half-step at each step of your design:
      • Examine each required feature
        • Is there a CPAN module that already does this?

      ...

      • Examine each algorithm or data structure in the program design
        • Is there a CPAN module that already does this?

      I know, it's just the obvious "don't reinvent the wheel" line. Still, I get carried away with my own (imagined) cleverness sometimes, and had to make this an official part of my routine. If I don't look for pre-existing modules, I don't get to have any more coffee that day. A little self-imposed discipline there :-)


      "All you need is ignorance and confidence; then success is sure."-- Mark Twain
Re: Algorithm design
by tjh (Curate) on May 25, 2002 at 13:19 UTC
    This will be a very interesting thread for me too.

    Generally, and probably not strictly in this order, I tend to work like this:

      Gather user or desired requirements. This is usually more complex than it starts out sounding. It tends to run from UI elements, desired functionality devoid of UI requests, desired output and displays, application management functionality, user management, "what happens after that?", "what should we see on *this* screen", etc. Also included are data requirements, etc., so thinking regarding data storage, existing db mods, and the like can be worked on. My experience is that this step is repeated many, many times throughout... :)

      Gather resources based on what I know so far. That may mean investigating existing app(s), db and structure, CPAN exploration, lots of books, etc. Generally I do this pre-design to help me start thinking it through. I'll look for prior solutions, etc.

      White board, butcher paper, markers, etc. Flow charts, liberal attempts at pseudo code (which is where I get ideas about modularizing code, etc.) Often the pseudo code then gets summarized into an outline or diagram form as an overview. Try to explicity define any/all subs, objects, modules; in/out for each, etc.

      Write tests for discrete units. Often, this is where I tend to shortcut and it's a weakness.

      Code a first layer of core functionality, test. Add more functionality. Generally, I try to 'get the basic issues functioning' first, then layer onto it. At various stages I'll return to the first step to double check if we're on the right track - but the warning here is that there can be way too many changes if this is done too often. Big surprises in design or major feature creep are really undesirable at this stage... lol

      Test, etc... prior to alpha/beta.

    It's a very dynamic process for me and not as rigid as it may sound, and probably not near as formal as more professional folks may approach it. It's always seemed important to me to get the core functionality working as quickly as possible for my own morale, and for the morale of any team members and/or clients...

    I've used a few design tools, but my tendency seems to be big white boards, big pieces of paper and diagrams as thought tools first. Should the project or client seem to require formal paper stages, or if the project is complex enough, I/we certainly do them.

Re: Algorithm design
by graff (Chancellor) on May 26, 2002 at 02:29 UTC
    This thread has given me a lot of reassurance, because I find a lot of my own practice and daily experience being attested by others.

    One practice that I tend to use heavily, and try to impose on apprentice programmers when they work with me, is to start each separate file of perl code with commentary that provides summary documentation about what the code in this file is supposed to do and how it does this -- before writing any of the actual perl code. If the code is supposed to run from the command line, there must be a "$Usage" variable that gets printed to stderr when appropriate, which not only lists but briefly explains all available options (and the internal documentation can/should explain in more detail).

    In any case, this initial documentation must be clear about what the program expects as input, what it produces as output, and the nature of the task that it performs in between. For GUI applications, there should be a summary about what is presented to the user, and what sorts of decisions/choices the user is expected to make.

    But getting this commentary written FIRST, before any of the actual code, tends to keep the coding process more focused, more effective, more likely to succeed sooner, and more maintainable months later.

Re: Algorithm design
by FoxtrotUniform (Prior) on May 27, 2002 at 15:51 UTC

    For a small or medium-sized script, I like to write a throwaway version, just to get an idea of the problem, in deference to Brooks' admonition: "Plan to throw one away: you will, anyhow." That gives me a chance to try out one or two ideas without committing to them, and generally the process of coding up a solution gives me other (often better) ideas. Of course, hacking up a half-assed solution just to get started isn't all that great an idea when you know that Management's going to assume that the first working program you come up with is the Solution. In that case, it's probably better to proceed more slowly, and be more careful.

    As far as algorithm design goes, I have a fairly well developed (read: geeky and obscure) interest in "the standard Comp. Sci. algorithms" -- things like graph traversal, network flow, various and sundry data structures, etc -- and keep a handful of algorithms books around my computers. I've gotten used to trying to think of problems in "formal" terms -- "Wait a minute, this is a directed graph" -- which comes in handy when I'm trying to figure out the "how" of solving a problem. It does take some getting used to, though.

    This study also gave me a decent understanding of a few basic techniques for building algorithms -- divide and conquer, dynamic programming, recursion, and so on. It's much easier to hack up an algorithm for your particular problem with more tools in your chest than basic iteration and branching.

    --
    The hell with paco, vote for Erudil!
    :wq

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (17)
As of 2014-10-24 18:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (134 votes), past polls