Hi,

you don't give enough information on what you're doing to elicit a really useful answer.

One typical way of dealing with unordered hash entries is to maintain separately another data structure that keeps the right order.

For example, you could sort your data only once and store in a separate hash the rank of each value (with the vertex or vertex ref as a key and the rank as value). But we don't have enough information on what you do to know if this would be usable or useful in your case.

As for the complexity,, it's even more difficult to say anything without seeing your code. But, no, in general you should not need to mentally unroll Perl code to underlying C to figure out the complexity of your algorithm. But, you need to understand the complexity of the Perl constructs, though. For example, traversing an array with n entries to see if a value is there would have a O(n) complexity. A hash lookup on the same list of entries, on the other hand, would have a complexity of O(1), i.e. the complexity of a hash lookup does not depend on the size of the hash.

In reply to Re: Algorithm Complexity and Determinism of Graph Module by Laurent_R
in thread Algorithm Complexity and Determinism of Graph Module by ownlifeful

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!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • 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, details, 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, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            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.