kelan has asked for the wisdom of the Perl Monks concerning the following question:

I'm doing something where I'll be inserting things into arbitrary places in an array based on a priority, and I need to keep the array sorted. Finding the place to put the new item is no problem, but I need to shift everything in the array over to make room for the insertion. This works: 
$idx = 45; # pretend we've already found the insertion point
@a[$idx+1 .. $#a+1] = @a[$idx .. $#a];
$a[$idx] = $newitem;

[download]
But I have vague notions of blatant inefficiency, especially for large lists. I'm worried more about speed than memory use, but I don't know how this would compare to just explicitly moving one element at a time. Is it best just to do the old: 
$idxmove = $#a;
while ($idxmove >= $idx) {
  $a[$idxmove+1] = $a[$idxmove];
  $idxmove--;
}
$a[$idx] = $newitem;

[download]

Replies are listed 'Best First'.
Re: Shifting an Array
by Abigail-II (Bishop) on Aug 29, 2002 at 13:34 UTC
    The latter more or less does the same work as the former. However, the latter does all the work in Perl, while the former does it in C. However, the usual way of doing this is by using splice, which also does the same work, and also in C: 
        splice @a => $idx, 0 => $newitem;

    [download]
    Note that they all take time linear in the size of the array. If you need to do a lot of insertions in a long list, you ought to review your algorithm, and see whether you really need to keep a sorted list. Perhaps a (balanced) tree will be better.

    Abigail

[reply]
[d/l]
[select]
      Note that they all take time linear in the size of the array. If you need to do a lot of insertions in a long list, you ought to review your algorithm, and see whether you really need to keep a sorted list. Perhaps a (balanced) tree will be better.

      I considered something like that, but I don't think it will be worth the extra complexity in this situation. Insertions (and deletions) won't be happening anywhere near as often as ordered processing of the list, which is easiest with a sorted array like this.

      I'm also curious as to how Perl does slices internally if the loop version and the slice version are more or less the same. I'd assumed that a slice becomes an anonymous list, with copies of the original values. Wouldn't that take more time to setup than just iterating through the existing one?

      Thanks for the splice tip. I wasn't aware of it:)

[reply]
        I'm also curious as to how Perl does slices internally if the loop version and the slice version are more or less the same. I'd assumed that a slice becomes an anonymous list, with copies of the original values. Wouldn't that take more time to setup than just iterating through the existing one?
        But during your iteration, you are assigning as well - so you are making copies as well.

        Abigail

[reply]
Re: Shifting an Array
by hotshot (Prior) on Aug 29, 2002 at 13:36 UTC
    why not use hash? you can add hash entries with priority as keys and as values the array content and at the end sort by keys (priority), and dump the sorted values to an array (if you need an array eventually).

    Hotshot
[reply]
Re: Shifting an Array
by LTjake (Prior) on Aug 29, 2002 at 13:43 UTC
[reply]

Back to Seekers of Perl Wisdom