using references to point to sliding window array

问题:

here is my problem: I have 2 arrays. One is character array and represents a sliding window. Characters gets shifted from the beginning and pushed at the end. I would like to use a second array to store references to array slices that 'follow' the characters as they move along. Example:

my @char_array = ('h','e','l','l','o','w','o','r','l','d');
my $char_arr_ref=[@char_array[1..$#char_array]]; 
print @$char_arr_ref, "\n"; # slice contains 'elloworld';
shift(@char_array);
push(@char_array), 'x';
print @$char_arr_ref, "\n"; # slice still contains 'elloworld', not 'lloworldx' as I need;

IN other words, I would like to be able to use a second array with references to array slices (as I would do with a pointer array in C for example).

Is there an idiomatic way to do this in Perl?

UPDATE: this is part of a larger program to do fast text searches. I was going to use a hash of references (say, instead of the the 'index' function which is painfully slow. And I need to do this in Perl.

回答1:

In C, your windows might be implemented using pointer arithmetic.

const char* s = str+1;
const char* e = str+len;
for (const char* p=s; p!=e; ++p) putc(*p);

Except pointer arithmetic wouldn't allow you to resize the buffer (push @char_array, 'x';). Even in C, you'd have to use offsets.

size_t si = 1;
size_t ei = len;
for (size_t i=si; i!=e1; ++i) putc(str[i]);

This is fortunate, because Perl doesn't have pointers, much less pointer arithmetic. But offsets? No problem!

my @char_array = split //, 'helloworld';
my ($s, $e) = (1, $#char_array);
say @char_array[$s..$e];    # elloworld
shift @char_array;
push @char_array, 'x';
say @char_array[$s..$e];    # lloworldx

If we're actually talking about chars, a string would be more efficient.

my $char_array = 'helloworld';
my ($s, $e) = (1, length($char_array));
say substr($char_array, $s, $e-$s+1);    # elloworld
$char_array =~ s/^.//s;
$char_array .= 'x';
say substr($char_array, $s, $e-$s+1);    # lloworldx

In fact, if we're actually talking about chars, we're quite lucky since we can use an lvalue substr and let Perl handle the offsets for us!

my $char_array = 'helloworld';
my $substr_ref = \substr($char_array, 1, length($char_array)-1);
say $$substr_ref;        # elloworld
$char_array =~ s/^.//s;
$char_array .= 'x';
say $$substr_ref;        # lloworldx

Way easier than C with more or less all the same benefits!

回答2:

I'm not sure what you're doing, and I have my doubts about whether it is appropriate for a "fast text search" program. However, you could accomplish what you want by using a trivial subroutine instead of a reference:

#!usr/bin/perl
use strict;
use warnings;

my @char_array = ('h','e','l','l','o','w','o','r','l','d');
sub char_arr_slice { return @char_array[1..$#char_array] };

print char_arr_slice, "\n"; 

shift(@char_array);
push(@char_array, 'x');

print char_arr_slice, "\n";

Note: Why do I have my doubts? Because character arrays are rarely the right way to deal with strings in Perl. This approach is likely to be less efficient and much clunkier than using Perl's built-in string-handling facilities (especially regular expressions).

回答3:

Here is an implementation using an overloaded object:

#!/usr/bin/perl
use strict; use warnings; use feature 'say';

my @array = qw( H e l l o W o r l d );
my $window = SlidingWindow->new(\@array, 1, -1);
say "@$window";
shift @array;
push @array, "x";
say "@$window";

{
    package SlidingWindow;
    use overload '@{}' => sub {
        my ($self) = @_;
        # manage negative indices
        my $min = $self->{min} >= 0 ? $self->{min}
                                    : $#{ $self->{array} } + 1 + $self->{min};
        my $max = $self->{max} >= 0 ? $self->{max}
                                    : $#{ $self->{array} } + 1 + $self->{max};
        return +[ @{ $self->{array} }[$min .. $max] ];
    };
    sub new {
        my ($class, $arrayref, $min, $max) = @_;
        return bless +{
            array => $arrayref,
            min => $min,
            max => $max,
        } => $class;
    }
}

Output:

e l l o W o r l d
l l o W o r l d x

Of course, you have the overhead of a method call, but Perl simply doesn't have pointers. If you are complaining that index is too slow (which can't be any faster), you can only improve your algorithm, not your implementation.

Update

Ikegami pointed out that substr might be a viable option. The following solution does not have the beauty of actually using arrays, but instead of an array of chars, we use a string. This isn't the same in Perl: strings are far more efficient.

my $charray = "HelloWorld";
say substr($charray, 1);
substr($charray, 0, 1) = "";
$charray .= "x";
say substr($charray, 1);

Output:

elloWorld
lloWorldx