in reply to We have no SPL.

Ok, what is good c or c++ implementation of a "heap" that is both fast and flexible, and can be easily ported to every platform perl runs on?

Let's take it, wrap it in XS, and put it on CPAN. The Perl community needn't re-invent any wheels that don't already exist, and are just waiting to be wrapped in XS (btw, i'm an XS newbie, so don't expect me to do it ... i'll compile it if you wish, but the real magic is up to someone, well, up to it ;)

update: If wrapping in XS is not an option, then hey, I'm all for re-implementing one from scratch ... most of the logic is already layed out...
 

Look ma', I'm on CPAN.

** The Third rule of perl club is a statement of fact: pod is sexy.

Replies are listed 'Best First'.
Re: (podmaster) Re: We have no SPL.
by ariels (Curate) on May 06, 2002 at 08:53 UTC

    The STL (C++) has priority_queue<T, Sequence, Compare>. But you can't just wrap it up for Perl, because the concepts behind the languages are too different.

    Look at priority_queue: it is specialized for one type T, it uses a vector<T> by default for storage, but can use any other random-accessible Sequence type, and it uses the desired Compare "functor" for comparison (or T's < method by default). In return, it gives you type safety, with the usual C++ guarantees. The compiled code will typically inline the comparisons and the container's code, so it can be very fast.

    There's no good translation of any of this into Perl. A useful Perl container will hold contents of all types. It will not be type safe, and the programmers using it will not expect it to be. Since access methods for containers are not standardized, it will be hard to make it work with another container. And containers and comparisons will probably need to be passed in a painfully slow way.

    It's not that the idea has no merit, nor even that C++ RULEZ 4ND P3RL SUX. Just that STL comes from a very different world.

    That said, wrapping one particular library-based implementation of a priority queue to work on standard Perl SVs would be very interesting, and quite possibly useful, too.

[reply]
[d/l]
[select]
      That said, wrapping one particular library-based implementation of a priority queue to work on standard Perl SVs would be very interesting, and quite possibly useful, too.
      That would be the idea -- something along the lines of a priority_queue<SV*,vector<SV*>,comparison_func> . Making it "nice" would require it being possible to pass a block of Perl code in as the comparison function (a la sort), which completely blows the inlining. Standard comparisons (e.g. string and numeric greater- and less-than) could still be specified as constants passed to the constructor, and implemented in pure C for speed. It would be interesting to see how much faster this would be than the Perl-only versions.

      /s

[reply]
[d/l]
Re: (podmaster) Re: We have no SPL.
by educated_foo (Vicar) on May 06, 2002 at 09:00 UTC
    The STL runs anywhere GCC runs, and probably some places it doesn't. I suspect Perl is more widely supported than (full) C++, but there's money behind getting C++ compilers up to speed, so I would suspect things will improve. At times I've thought about trying to wrap versions of the containers for SV*'s. I did something similar for an edit distance algorithm I wrote awhile back -- took an algorithm templated on iterator type, and made it work with offsets in a Perl AV. I wrote an extra layer of non-template wrappers around it, then pulled it in with Inline::CPP, and it wasn't so bad. Depending on how the interfaces work out, e.g. how often callbacks are required for comparisons, this may or may not be efficient enough. If not, re-implementing them is not too hard, and can even be educational and enjoyable sometimes.

    A bigger issue may be Perl's funky license. I know Parrot is re-implementing the kitchen sink because of licensing issues.

    /s

[reply]

In Section Meditations