Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

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

by Anonymous Monk
on Sep 03, 2000 at 23:55 UTC ( [id://30939]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question: (arrays)

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

Originally posted as a Categorized Question.

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

Replies are listed 'Best First'.
Re: How do I insert an element into an arbitrary (in range) array index?
by Russ (Deacon) on Sep 04, 2000 at 00:52 UTC
    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
Re: How do I insert an element into an arbitrary (in range) array index?
by jreades (Friar) on Sep 06, 2000 at 01:17 UTC

    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...

Re: How do I insert an element into an arbitrary (in range) array index?
by lhoward (Vicar) on Sep 04, 2000 at 00:07 UTC
    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";
Re: How do I insert an element into an arbitrary (in range) array index?
by Jorge_de_Burgos (Beadle) on Nov 09, 2009 at 12:46 UTC
    #!/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.
      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% --
      ($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord }map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
Re: How do I insert an element into an arbitrary (in range) array index?
by Denis.Beurive (Initiate) on Jul 07, 2010 at 12:38 UTC

    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
Re: How do I insert an element into an arbitrary (in range) array index?
by Denis.Beurive (Initiate) on Jul 06, 2010 at 13:51 UTC

    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

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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://30939]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2024-04-12 18:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found