All of the items qualify as requirements, except for the comment about 'fast' -- that's just a guideline. You need to determine what minimum performance is acceptable (ie, it can perform all of the operations you listed, and within whatever time you decide is acceptable)

O(N) isn't the greatest, but if that's your only issue, it still might be the best implementation, especially when you're dealing with small (<1000) arrays. (small being a relative thing ... which is why we need hard numbers)

You already have your main considerations for decision making -- now decide on what the acceptable times are, and/or relative scoring. For example, you might decide that it has to be able to run some given test within (x) sec -- and the test might run just the add items, or the remove items, or it might run a combination of traversal, add/removal, searching, distance determination, etc.

I'd also suggest forgetting about your derived requirement -- just consider it in terms of speed. It's possible that an implementation that requires an extra search will be faster than a bad implementation that can 'remember' the position. (and if it's a condition that doesn't happen frequently, the speed savings for not remembering might make up for the extra searches)

In reply to Re: Advanced Data Structure Question by jhourcle
in thread Advanced Data Structure Question by Limbic~Region

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.