Beefy Boxes and Bandwidth Generously Provided by pair Networks Russ
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

One question and one suggestion.

The question: Why would I use a Treap and what benefits (and costs) would result as compared to using a normal hash for that (those) same applications?

The Suggestion: If you get around to modifying the interface to take a single custom comparator rather than the two as now (which I think makes a lot of sense), then you might also consider making the standard alpha comparator (cmp) a settable option in place of the default numeric comparator. That is to say, have a new()/tie() time option that can be set to indicate that the caller wants an alpha-sort order used rather than a numeric and then use cmp rather than <=> internally to the module rather than requiring the user to supply a comparator function that does this.

The main reason is that callbacks can be expensive. The best demonstration of this is the GRT. Even though performing a numeric sort using a GRT requires stringifying the numeric (part of the) values to be sorted, into numerically orderable strings (ie. fixed width with leading zeros), this pre-sort overhead is more than compensated for by performance gained by avoiding the need to callback into user code for the comparisons during the sort. I think that the overhead of an if or trinary conditional in the module code to determine which operator to use when inserting and/or balancing (is that the right term with a Treap?) would be easily offset by the benefit of not invoking a callback for the common cases of a 'trivial comparator', ie. numeric or alpha.

As an aside. I've long wished that perl had a numeric sort option built in (would one extra built-in called sortn be any great burden?), so that many cases where sorting numerically currently requires the overhead of a trivial callback or user block, or resorting to the GRT (or tyes recently posted variation on the theme) would become unnecessary.


Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
If I understand your problem, I can solve it! Of course, the same can be said for you.


In reply to Re: Algorithm::Treap by BrowserUk
in thread Algorithm::Treap by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others making s'mores by the fire in the courtyard of the Monastery: (11)
    As of 2014-04-19 05:35 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (478 votes), past polls