In my experience the majority of programs which run into performance problems on time spent inserting and deleting items into arrays can be more easily fixed by doing inserts and deletes as bulk operations, using grep or map when you can, and when you can't then incrementally building up a new array with repeated calls to push.

While it looks like a lot of work to build a new array from scratch, it is a lot less work than it is to do a lot of manual manipulations of the array, each of which involve moving around large chunks of the existing array.

This observation will allow you to fix the vast majority of performance problems arising from having to do a lot of detail manipulation of arrays. But there are a very small number of programs which simply must do a lot of inserting and deleting which cannot be fixed. The odds are very small that you have one of those. This is so even if you don't see offhand how to fix the program to avoid the issue. (It takes some experience to find the fixes.) But for that infinitesmal remainder, I would recommend that you tie the array to a data structure (eg DB_File's BTREE implementation) that has slower accessing but allows inserts and deletes to be done much faster.

Voila! Works like magic! (In fact magic what does makes tie work behind the scenes...)

In reply to Re (tilly) 1: Using a hash for an ordered set can make sense by tilly
in thread Using a hash for an ordered set can make sense by stefp

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.