Как инвертировать массив?

Question

В этом сценарии

#!/usr/bin/perl -w

use strict;

my @ar = (1,2,10,3,5);

@ar = sort {$a <=> $b} @ar;

содержит @ar теперь содержит (1,2,3,5,10).

Теперь я хотел бы получить обратный массив, т.е. (4,6,7,8,9).

Любые предложения, как это можно сделать?

Answer 1

При работе с операциями над множествами хэши работают хорошо:

my %have = map {$_ => 1} @ar;

my @inv  = grep {not $have{$_}} 1 .. 10;

print "@inv\n"; # 4 6 7 8 9

Если вы не будете знать границы заранее, и хотели бы определить их по минимальному / максимальному значению @ar, поскольку его сортировка становится легкой:

my @inv = grep {not $have{$_}} $ar[0] .. $ar[-1];

Answer 2

Это хорошее приложение для интеллектуального сопоставления:

  @inverse = grep { ! ($_ ~~ @ar) } 1..10;

Выбирает все значения от 1 до 10, которых нет в @ar.

Answer 3

Acme :: Инструменты

use warnings;
use strict;
use Acme::Tools qw(minus);

my @ar = (1,2,10,3,5);
@ar = sort {$a <=> $b} @ar; 
my @all = 1..10;
my @inv = minus( \@all, \@ar );
print "@ar\n";
print "@inv\n";

Answer 4

Поскольку вы знаете, что массив отсортирован, есть только 1 значение, с которым вам нужно сравнивать в любой момент времени, поэтому вы можете сделать это:

my @ar = (1,2,10,3,5);

@ar = sort {$a <=> $b} @ar;

my @inverse = do {
  my $i = 0;
  grep { $_ != $ar[$i] or (++$i, 0) } 1 .. $ar[-1]
};

Как написано здесь, вам не нужна проверка на $i, выходящую из конца массива, потому что диапазон заканчивается на $ar[-1]. Если вы измените это условие, то вам нужно будет проверить $i > $#ar или просто нажать N + 1 на @ar перед вычислением обратного значения и вывести его потом (где N - максимальное значение диапазона). Этот код также предполагает, что в массиве не будет повторяющихся значений.

Я решил сравнить ведущих кандидатов, используя 5000 чисел от 1 до 10 000:

use 5.010;
use Benchmark 'cmpthese';

my (@orig, %used);
while (@orig < 5000) {
  my $rand = 1 + int rand 10000;
  push @orig, $rand unless $used{$rand}++;
}

my @ar = sort {$a <=> $b} @orig;

cmpthese(-3, {
  sorted => sub {
    push @ar, 10001;
    my @inverse = do {
      my $i = 0;
      grep { $_ != $ar[$i] or (++$i, 0) } 1 .. 10000
    };
    pop @ar;
  },

  unsorted => sub {
    @ar = sort {$a <=> $b} @orig;

    push @ar, 10001;
    my @inverse = do {
      my $i = 0;
      grep { $_ != $ar[$i] or (++$i, 0) } 1 .. 10000
    };
    pop @ar;
  },

  hash => sub {
    my %have = map {$_ => 1} @ar;

    my @inverse = grep {not $have{$_}} 1 .. 10000;
  },

  smartmatch => sub {
    my @inverse = grep { ! ($_ ~~ @ar) } 1 .. 10000;
  },
});

На Perl 5.10.1 я получил:

              Rate smartmatch       hash   unsorted     sorted
smartmatch 0.708/s         --      -100%      -100%      -100%
hash         180/s     25279%         --        -7%       -67%
unsorted     193/s     27183%         8%         --       -65%
sorted       551/s     77745%       207%       185%         --

Как видите, многократное умное сопоставление с массивом медленное . Мой подход примерно такой же скорости, как и подход на основе хеша, если вы включите время, необходимое для сортировки @ar. Если вы игнорируете это (возможно, вам придется сортировать @ar в любом случае по другим причинам), то мой подход примерно в два раза быстрее, чем хеш.

Answer 5

Вот решение с использованием Set :: IntSpan.

#!/usr/bin/perl
use strict;
use warnings;
use Set::IntSpan;

my @ar = (1,2,10,3,5); 
@ar = sort {$a <=> $b} @ar;

# min - max of given set
my $range = Set::IntSpan->new( "$ar[0]-$ar[-1]" );
# members of set
my $used  = Set::IntSpan->new( @ar );

# Calculates the missing numbers
my $unused = $range->diff( $used );

print join " ", $unused->elements;

Answer 6

Просто

@inv = sort {$b <=> $a} @ar;

Если вы хотите инвертировать случайный несортированный массив:

my @inv;
while(scalar @ar){
    push @inv pop @ar;
}

Answer 7

Мой Perl немного ржавый, но вот основная идея.

# Put the contents of `@ar` into the keys 
# of a temporary hash variable (to make lookups easy)
my %temp_hash = %{{ map { $_ => 1 } @ar }};

# Then use a `for` loop starting at the first value
# in `@ar` and ending at the last value:
for (my $i = $ar[0]; $i <= $ar[$#ar-1]; $i++) {
    # For each value of your loop counter,
    # check whether that value exists as a key 
    # in your temporary hash variable. 
    # If it doesn't, push it on to your inverse array:
    push @inverse_array, $i if (not exists $temp_hash{$i});
}

Работа выполнена!