How do I insert an element into an arbitrary (in range) array index?

[Anonymous Monk]

How do I insert an element into an arbitrary (in range) array index?

Originally posted as a Categorized Question.

[Russ]

Use splice with 0 for the length argument.

my @R = (1,2,3,4,5,6,7,8,9);
splice @R, 1, 0, 'Test';
print "@R\n";

prints: 1 Test 2 3 4 5 6 7 8 9

[jreades]

Algorithms with Perl (call it the Wolf book) covers just this issue in one of the early chapters

Basically, you have two choices: an array or a linked list.

The choice between these two will depend on, primarily, the size of the list.

Splice(): As lhoward indicated, inserting a value at an aribtrary index using splice is expensive.

The time for each splice() increases at a constant rate as your list grows in size. With splice(), although from the user end it looks like you just inserted something, to memory you were creating and manipulating multiple arrays (basically, a one or more copies of your original array) in memory.

This may not be a problem if your array is 10, 20, or even 100 items, but if it's 10,000 or 100,000 you're going to see a real performance hit. This brings us to...

Linked Lists: perhaps the easiest (and probably least accurate) way to describe it is to say that linked lists are array-like.

The basic principle is that you have a value (call it 'x') and a pointer (reference, call it 'a') to the next item (call it 'y') in the linked list (assuming a simple linked list).

So a(x) -> b(y) -> c(z) and so on...

Suddenly, we've radically altered the tradeoffs... To add a value q between x and y I just need to change the pointers as follows:

a(x) -> e(q) -> b(y) -> c(z) and so on...

The cost of inserting values at arbitrary locations is reduced to, I believe, O(1) -- I can insert anywhere in the list just by rearranging the pointers and that is essentially a constant time operation regardless of how big my list is...

Of course, now I might have some trouble *finding* the element, but that's another question entirely...

[lhoward]

By insert I assume you mean "put between 2 current array elements, shifting down the later ones to make room".

The unfortunate answer is that you can't do this efficiently using native perl arrays. The code to do it isn't long or complex, but as a consequence of the design of perl's arrays (which makes them so efficient at so many other operations) sacrifices had to be made. One of those is that inserting in the middle of an array is "slow" — the time it takes to do it depends on how many elements are already in the array. (In big-O notation, the operation is said to be O(n).).

my @array = qw(3 1 4 1 5 9 2 6 5 4);
my $offset = 5;
my $value = 'abc';
print "before:  @array\n";
splice @array, $offset, 0, $value;
print " after:  @array\n";

[Jorge_de_Burgos]

#!/usr/bin/perl -w
use warnings;
use strict;
use 5.10.0;

my @in_array = qw(A B C E F G);
my @out_array;
my $insert = 'D';

push @out_array,
        @in_array[0..2],
        $insert,
        @in_array[3..5];

say join (', ',  @in_array);

say join (', ',  @out_array);

exit;

I think this approach is the most human-readable. By the way, it doesn't use splice with its performance issues.

[choroba]

What issues?

#!/usr/bin/perl
use warnings;
use strict;
use Test::More tests => 3;
use Benchmark qw{ cmpthese };

my $short = ['a' .. 'z'];
my $long  = ['a' .. 'zzzzz'];

sub ar {
    my $ar = shift;
    my $mid = @$ar / 2 - 1;
    push my @r, @$ar[ 0 .. $mid ],
                'new',
                @$ar[ $mid + 1 .. $#$ar ];
    \@r
}

sub sp {
    my @r = @{+shift};
    splice @r, @r / 2, 0, 'new';
    \@r
}

diag(scalar @$_) for $short, $long;

is_deeply(ar($short), sp($short), 'same short');
is_deeply(ar($long),  sp($long),  'same long');
is_deeply(ar($short), [ 'a' .. 'm', 'new', 'n' .. 'z' ], 'expected sho
+rt');

cmpthese(-3, {
              'ar-short' => sub { ar($short) },
              'sp-short' => sub { sp($short) },
             });
cmpthese(-10, {
              'ar-long'  => sub { ar($long)  },
              'sp-long'  => sub { sp($long)  },
             });
__END__
Output:

1..3
# 26
# 12356630
ok 1 - same short
ok 2 - same long
ok 3 - expected short
             Rate ar-short sp-short
ar-short 127474/s       --     -21%
sp-short 160522/s      26%       --
        s/iter ar-long sp-long
ar-long   3.12      --    -15%
sp-long   2.64     18%      --

[Denis.Beurive]

Hello! You can use this function :

sub arrayInsertAfterPosition
{
  my ($inArray, $inPosition, $inElement) = @_;
  my @res         = ();
  my @after       = ();
  my $arrayLength = int @{$inArray};

  if ($inPosition < 0) { @after = @{$inArray}; }
  else {
         if ($inPosition >= $arrayLength)    { $inPosition = $arrayLen
+gth - 1; }
         if ($inPosition < $arrayLength - 1) { @after = @{$inArray}[($
+inPosition+1)..($arrayLength-1)]; }
       }

  push (@res, @{$inArray}[0..$inPosition],
              $inElement,
              @after);

  return @res;
}

my @tab = qw(A B C D E);
my @res = ();

@res = arrayInsertAfterPosition (\@tab, -1, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 0, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 1, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 2, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 3, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 4, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 5, 'Test');
print join(', ', @res) . "\n";

The result is :

Test, A, B, C, D, E
A, Test, B, C, D, E
A, B, Test, C, D, E
A, B, C, Test, D, E
A, B, C, D, Test, E
A, B, C, D, E, Test
A, B, C, D, E, Test

[Denis.Beurive]

Hello! You can use this function :

sub arrayInsertAfterPosition
{
  my ($inArray, $inPosition, $inElement) = @_;
  my @res         = ();
  my @after       = ();
  my $arrayLength = int @{$inArray};

  if ($inPosition < 0) { @after = @{$inArray}; }
  else {
         if ($inPosition >= $arrayLength)    { $inPosition = $arrayLen
+gth - 1; }
         if ($inPosition < $arrayLength - 1) { @after = @{$inArray}[($
+inPosition+1)..($arrayLength-1)]; }
       }

  push (@res, @{$inArray}[0..$inPosition],
              $inElement,
              @after);

  return @res;
}

my @tab = qw(A B C D E);
my @res = ();

@res = arrayInsertAfterPosition (\@tab, -1, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 0, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 1, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 2, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 3, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 4, 'Test');
print join(', ', @res) . "\n";
@res = arrayInsertAfterPosition (\@tab, 5, 'Test');
print join(', ', @res) . "\n";

The result is :

Test, A, B, C, D, E
A, Test, B, C, D, E
A, B, Test, C, D, E
A, B, C, Test, D, E
A, B, C, D, Test, E
A, B, C, D, E, Test
A, B, C, D, E, Test

[Corion]

I don't see where your subroutine is better than splice.