Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Data Structures wanted; apply within.

by Falkkin (Chaplain)
on Mar 09, 2001 at 06:40 UTC ( [id://63152]=perlmeditation: print w/replies, xml ) Need Help??

I'm currently enrolled in a Data Structures & Algorithms class. A fair portion of the class involves coding some common algorithms. Unfortunately, the languages used for the class are Java and C++, but I figured it would be good practice to try implementing a few of these algorithms in Perl.

Most of the algorithms described in our text (the White Book, by Cormen, Leiserson, and Rivest) are rather slick, and I can see that many of them would make useful Perl modules. As long as I've committed myself to implementing some of these algorithms in Perl, I figured I might as well make my results into modules, with the eventual intent that they might (if properly done) end up in CPAN.

Unfortunately (for me), quite a few of the interesting algorithms, such as Boyer-Moore string searching and hashtables, are already Perl built-ins, and most of the others (such as a variety of heaps, red/black trees, and efficient sorting algorithms) are already in CPAN. Thus, I have a few questions to ask of my fellow monks:

  • What are some interesting algorithms that you've personally implemented and found enlightening? The main point of my little project here is to enhance my learning, so if there are any algorithms or data structures that have somehow fundamentally changed how you think about programming, I'd be very interesting in knowing about them.
  • Are there any data structures/algorithms modules not on CPAN that should be implemented?
  • Are there any modules on CPAN that you've used and found somehow deficient? If there are any modules that simply need maintenance, a code review, or better documentation, I'd be willing to talk to the authors and ask if they'll take my help.

To let you know what I'm presently thinking, here are a few options I'm pondering:

  • The Graph package, by Jarkko Hietaniemi, appears to be derived straight from Mastering Algorithms with Perl, and is relatively complete. The only irk I have with it is the documentation, which (in my opinion) could be better. I may end up playing with these modules a bit and seeing if I couldn't write some better documentation for them.
  • Another possibility with the Graph modules would be to create a GUI front-end that allows the user to create instances of graphs in a graphical environment and perform various operations on them. I don't see this sort of thing as a very practical application, but perhaps it could be used to teach basic graph theory or to solve simple graph problems.
  • Implementing a basic decision-tree structure. There doesn't seem to be one on CPAN, and I could create a decision tree based on the Tree::Nary module. This would be interesting to me because I'm interested in AI (mostly for the purposes of game-playing, though ;)).
Thank you, in advance, for any comments or suggestions you may have. :)

Replies are listed 'Best First'.
Re: Data Structures wanted; apply within.
by Dragonfly (Priest) on Mar 09, 2001 at 12:59 UTC
    Well, it has been discussed that Net::Ping is due for a bit of maintainance, or possibly a more thorough overhaul, because of the fact that it doesn't report ICMP packets correctly unless it is run as root, which presents a security problem.

    It is an important (not to mention popular) module, so not only would it be a good candidate for your project, but also an opportunity to learn about network and socket programming, and you also might benefit from a bit of parallel programming while you're at it.

    Another aspect is that you'd get the chance to optimize the algorithms that the module uses, since there are several different approaches that would likely work in the actual implementation.

    In any case, good luck in your project, whatever you choose!

      On this note, is there a page or node that has a list of modules that are either needed or have been negligected or abandonded by their respective authors and could use some tidying up or the like? I'm still working on my web site redesign, but I'd like some useful project after that to take up...
      Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
      As you can see from this node, I've already taken your idea into consideration. Thanks greatly for the suggestion.
Re: Data Structures wanted; apply within.
by Lexicon (Chaplain) on Mar 09, 2001 at 13:10 UTC
    I don't know of any useful algorithms offhand that aren't available in perl (since I havn't looked) but here are some algorithms you should try, if only for the experience gained.

    Definatly, absolutly, try some Red Black trees.. Graph-related algorithms are some of my favorite. Djaikstra's Algorithm and others are also fun. Pick up your Data Structures book and just start going at it for any of them that you can't find on CPAN. I doubt Perl actually is used so often for Graph applications though, as they're often seriously computationally intensive and you'd want them a little more optimized.

    There's an algorithm for constant time array initialization algorithm that I really really like. It's a memory hog (uses 3 arrays instead of one) but it has it's uses.

    I've been deriving (since I can't find one online) a Array_Combinator algorithm which will enumerate and return all possible combinations (not permutations) of a given number of elements in an Array (that'll make more sense when I post it Monday).

    For more educational pleasure, go impliment a simple standard encryption/decryption algorithm, like RSA. I did that for a math class once, and it was more difficult than I expected, but worth it.

    Honestly, most anything useful that you'll study in this class will already be on CPAN or simply can't be generalized enough to be made into a module (like the constant time array initialization. It's just not that advanced enough of a class if you are still studying Red-Black trees. ;) I'll pick up a couple of my textbooks tonight and see if I can find anything else for ya though.

    -Lexicon

(jeffa) Re: Data Structures wanted; apply within.
by jeffa (Bishop) on Mar 09, 2001 at 07:03 UTC
    Try to build a red-black tree sometime. I had to write mine in C++, if I still didn't have the shakes I'd try to write a Perl version.

    UPDATE: Hey! No peeking! But it is interesting that it uses the algorithm from "The White Book" . . .

    Jeff

    can't sleep . . . red black tree'll eat me
    
    
      There is already a Tree::RedBlack module, as I (indirectly) mentioned in my post above; on the other hand, maybe I should implement my own Red-Black tree for purposes of self-amusement(?)....
Re: Data Structures wanted; apply within. (give me all your modules)
by deprecated (Priest) on Mar 10, 2001 at 07:12 UTC
      Are there any modules on CPAN that you've used and found somehow deficient? If there are any modules that simply need maintenance, a code review, or better documentation, I'd be willing to talk to the authors and ask if they'll take my help.

    oh baby, i've got a few for you.

    • Net::Traceroute, with all due respect to the author, is hopelessly fubar. Often it returns the host being 255.255.255.255 or 0.0.0.0 with no errors whatsoever. It actually is just a parser for the system `traceroute` call and thus cant be expected to think very hard. The ever-so-cool cleen otherwise known as bind has constructed a small perl script to create raw packets -- it would be very easy to implement traceroute from this.
    • Archive::Tar was never intended to work with scalars instead of files, and does not play with others. See relevant post here. Working with IO::Scalar would make it excellent, but i should be able to just slurp in a file, detar it, and write it out. It doesnt let you do that.
    • Convert::UU seems to have almost no purpose for being anymore since perl 5+ has pack 'u'.
    • XML::DOM has given me no end of trouble as of late...

    and these are just the modules that have recently irritated me. there are others... :)

    --
    transcending "coolness" is what makes us cool.

Re: Data Structures wanted; apply within.
by Adam (Vicar) on Mar 10, 2001 at 00:22 UTC
    This reminds me of a quote, but -as it usually goes- I can't remember who said it, or even the exact wording. Basically, it was: "Show me your algorithms and I will need to ask about the data structure. Show me your data structures and I will know your algorithms."

    Does anyone know the actual quote, and/or the author? Thanks

      The quote you're looking for is from Fred Brooks. See this node.
        Thanks. That is exactly what I was looking for.
Re: Data Structures wanted; apply within.
by DeaconBlues (Monk) on Mar 09, 2001 at 22:19 UTC

    On CPAN there is a module Sort::Fields which sorts arrays of strings which are delimited into fields. I have been thinking of using this as a base for another module which sorts strings with fixed-width fields instead of delimited fields.

    You can help make this for me!?!?

      Sure:
      @sorted = sort{ substr($a,$pos,$length) cmp substr($b,$pos,$length)} @list;
      It's no module, but it works...

      Hope this helps,

      Jeroen
      "We are not alone"(FZ)

        Thanks, but the power of the module is that it allows your to sort on any number of columns. For example:
        first sort on substr($string, $foo0, $bar0), then
        then sort on substr($string, $foo1, $bar1) , then
        then sort on substr($string, $foo2, $bar2) , ... and so on.

      I can look into it... presently, I'm looking into writing some patches for Net::Ping, because that appears to be a major module that needs help, but I'll keep your suggestion in mind. Thanks.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2024-03-29 06:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found