Como posso verificar se uma matriz Perl contém um valor específico?

239

Eu estou tentando descobrir uma maneira de verificar a existência de um valor em uma matriz sem percorrer a matriz.

Estou lendo um arquivo para um parâmetro. Eu tenho uma longa lista de parâmetros com os quais não quero lidar. Eu coloquei esses parâmetros indesejados em uma matriz @badparams.

Quero ler um novo parâmetro e, se ele não existir @badparams, processá-lo. Se existir @badparams, vá para a próxima leitura.

Mel
fonte
3
Para o registro, a resposta depende da sua situação. Parece que você deseja fazer pesquisas repetidas; portanto, usar um hash como o jkramer sugere é bom. Se você quiser apenas fazer uma pesquisa, é melhor iterar. (E, em alguns casos, você pode querer busca binária em vez de usar um hash!)
Cascabel
5
grep perldoc -f
Éter
6
Para o registro (e isso pode ser totalmente inaplicável à sua situação), geralmente é uma idéia melhor identificar 'bons valores' e ignorar o resto, em vez de tentar eliminar 'valores ruins' conhecidos. A pergunta que você precisa fazer é se é possível que haja alguns valores ruins que você ainda não conhece.
Grant McLean

Respostas:

187

Simplesmente transforme a matriz em um hash:

my %params = map { $_ => 1 } @badparams;

if(exists($params{$someparam})) { ... }

Você também pode adicionar mais parâmetros (exclusivos) à lista:

$params{$newparam} = 1;

E depois obtenha uma lista de parâmetros (únicos) de volta:

@badparams = keys %params;
jkramer
fonte
38
Para o registro, esse código ainda itera pela matriz. A chamada do mapa {} simplesmente facilita a digitação dessa iteração.
Kenny Wyland
3
Eu faria isso apenas se seus valores em @badparams forem pseudo-estáticos e você planeja fazer muitas verificações no mapa. Eu não recomendaria isso para uma única verificação.
Aaron T Harris
Isso não vai dar certo para uma matriz com vários itens com o mesmo valor?
Rob Wells
3
@ RobWells não, funcionará bem. Na próxima vez em que vir o mesmo valor, ele substituirá a entrada no hash, que neste caso a define 1novamente.
andrewrjones
222

Melhor finalidade geral - matrizes especialmente curtas (1000 itens ou menos) e codificadores que não têm certeza de quais otimizações melhor atendem às suas necessidades.

# $value can be any regex. be safe
if ( grep( /^$value$/, @array ) ) {
  print "found it";
}

Foi mencionado que o grep passa por todos os valores, mesmo que o primeiro valor na matriz corresponda. Isso é verdade, porém o grep ainda é extremamente rápido na maioria dos casos . Se você estiver falando de matrizes curtas (menos de 1.000 itens), a maioria dos algoritmos será bastante rápida. Se você está falando de matrizes muito longas (1.000.000 de itens), o grep é aceitavelmente rápido, independentemente de o item ser o primeiro, o meio ou o último da matriz.

Casos de otimização para matrizes mais longas:

Se sua matriz estiver classificada , use uma "pesquisa binária".

Se a mesma matriz for repetidamente pesquisada várias vezes, copie-a primeiro para um hash e depois verifique o hash. Se a memória for uma preocupação, mova cada item da matriz para o hash. Mais memória eficiente, mas destrói a matriz original.

Se os mesmos valores forem pesquisados ​​repetidamente na matriz, crie um cache preguiçosamente. (à medida que cada item é pesquisado, verifique primeiro se o resultado da pesquisa foi armazenado em um hash persistente. se o resultado da pesquisa não for encontrado no hash, pesquise na matriz e coloque o resultado no hash persistente para que da próxima vez encontre-o no hash e pule a pesquisa).

Nota: essas otimizações só serão mais rápidas ao lidar com matrizes longas. Não otimize demais.

Aaron T Harris
fonte
12
O til duplo foi introduzido no Perl 5.10
Pausado até novo aviso.
15
@DennisWilliamson ... e no 5.18 é considerado experimental .
Xaerxess 31/10/2013
5
Evite a correspondência inteligente no código de produção. É instável / experimental, com aviso prévio.
Vector Gorgoth 26/11/2013
1
Acho também mais legível, mas Não use diz que não é eficiente e verifica todos os elementos, mesmo que seja o primeiro.
Giordano
7
Não use if ("value" ~~ @array). ~~ é um recurso experimental chamado Smartmatch. O experimento parece ser considerado uma falha e será removido ou modificado em uma versão futura do Perl.
yahermann
120

Você pode usar o recurso smartmatch no Perl 5.10 da seguinte maneira:

Para a pesquisa literal de valor, fazer o procedimento abaixo.

if ( "value" ~~ @array ) 

Para pesquisa escalar, o procedimento abaixo funcionará como acima.

if ($val ~~ @array)

Para a matriz embutida que estiver fazendo abaixo, funcionará como acima.

if ( $var ~~ ['bar', 'value', 'foo'] ) 

No Perl 5.18, o smartmatch é marcado como experimental, portanto, você precisa desativar os avisos ativando o pragma experimental , adicionando abaixo ao seu script / módulo:

use experimental 'smartmatch';

Como alternativa, se você deseja evitar o uso de smartmatch - então, como Aaron disse, use:

if ( grep( /^$value$/, @array ) ) {
  #TODO:
}
Bitmap
fonte
4
Isso é bom, mas parece ser novo no Perl 5.10. Levou algum tempo antes de descobrir por que estou recebendo erros de sintaxe.
Igor Skochinsky
17
Aviso: você pode evitar esse, pois o operador tem um comportamento aparentemente diferente em versões diferentes e, entretanto, foi marcado como experimental . Portanto, a menos que você tenha controle total sobre sua versão perl (e quem a possui), provavelmente deve evitá-la.
Labirinto
1
Eu gosto desta explicação sobre por que a configuração use experimental 'smartmatch'é recomendada. Como tenho controle da minha versão perl (sistema interno), uso a no warnings 'experimental::smartmatch';instrução
Lepe
43

Esta postagem do blog discute as melhores respostas para esta pergunta.

Como um breve resumo, se você pode instalar os módulos CPAN, as soluções mais legíveis são:

any(@ingredients) eq 'flour';

ou

@ingredients->contains('flour');

No entanto, um idioma mais comum é:

any { $_ eq 'flour' } @ingredients

Mas por favor, não use a first()função! Ele não expressa a intenção do seu código. Não use o ~~operador "Correspondência inteligente": está quebrado. E não use grep()nem a solução com um hash: eles repetem a lista inteira.

any() irá parar assim que encontrar seu valor.

Confira a postagem do blog para mais detalhes.

mascip
fonte
8
qualquer necessidadeuse List::Util qw(any);. List::Utilestá nos módulos principais .
Onlyjob 26/09/15
13

Método 1: grep (pode ser cuidadoso enquanto se espera que o valor seja um regex).

Tente evitar o uso grep, se estiver procurando recursos.

if ( grep( /^$value$/, @badparams ) ) {
  print "found";
}

Método 2: pesquisa linear

for (@badparams) {
    if ($_ eq $value) {
       print "found";
       last;
    }
}

Método 3: usar um hash

my %hash = map {$_ => 1} @badparams;
print "found" if (exists $hash{$value});

Método 4: smartmatch

(adicionado no Perl 5.10, marcado é experimental no Perl 5.18).

use experimental 'smartmatch';  # for perl 5.18
print "found" if ($value ~~ @badparams);

Método 5: usar o módulo List::MoreUtils

use List::MoreUtils qw(any);
@badparams = (1,2,3);
$value = 1;
print "found" if any {$_ == $value} @badparams;
Kamal Nayan
fonte
12

O benchmark do @ eakssjo está quebrado - mede a criação de hashes em loop versus a criação de regexes em loop. Versão fixa (mais eu adicionei List::Util::firste List::MoreUtils::any):

use List::Util qw(first);
use List::MoreUtils qw(any);
use Benchmark;

my @list = ( 1..10_000 );
my $hit = 5_000;
my $hit_regex = qr/^$hit$/; # precompute regex
my %params;
$params{$_} = 1 for @list;  # precompute hash
timethese(
    100_000, {
        'any' => sub {
            die unless ( any { $hit_regex } @list );
        },
        'first' => sub {
            die unless ( first { $hit_regex } @list );
        },
        'grep' => sub {
            die unless ( grep { $hit_regex } @list );
        },
        'hash' => sub {
            die unless ( $params{$hit} );
        },
    });

E resultado (é para iterações 100_000, dez vezes mais do que na resposta do @ eakssjo):

Benchmark: timing 100000 iterations of any, first, grep, hash...
       any:  0 wallclock secs ( 0.67 usr +  0.00 sys =  0.67 CPU) @ 149253.73/s (n=100000)
     first:  1 wallclock secs ( 0.63 usr +  0.01 sys =  0.64 CPU) @ 156250.00/s (n=100000)
      grep: 42 wallclock secs (41.95 usr +  0.08 sys = 42.03 CPU) @ 2379.25/s (n=100000)
      hash:  0 wallclock secs ( 0.01 usr +  0.00 sys =  0.01 CPU) @ 10000000.00/s (n=100000)
            (warning: too few iterations for a reliable count)
Xaerxess
fonte
6
Se você deseja testar vários elementos, a criação antecipada do hash economiza seu tempo. Mas se você quer apenas saber se ele contém um único elemento, não possui o hash. Portanto, a criação do hash deve fazer parte do tempo de computação. Ainda mais para a expressão regular: você precisa de um novo regexp para cada elemento que procura.
fishinear próximo de 24/01
1
@ fishinear True, mas se você estiver interessado apenas em uma verificação, não em várias, obviamente é uma micro-otimização imaginar o método mais rápido, porque esses microssegundos não importam. Se você quiser refazer essa verificação, o hash é o caminho a seguir, pois o custo de criação do hash é pequeno o suficiente para ser ignorado. Os benchmarks acima medem apenas diferentes formas de teste, sem incluir nenhuma configuração. Sim, isso pode ser inválido no seu caso de uso, mas novamente - se você estiver fazendo apenas uma verificação única, use o que for mais legível para você e seus companheiros.
Xaerxess
10

Embora seja fácil de usar, parece que a solução converter em hash custa bastante desempenho, o que foi um problema para mim.

#!/usr/bin/perl
use Benchmark;
my @list;
for (1..10_000) {
    push @list, $_;
}

timethese(10000, {
  'grep'    => sub {
            if ( grep(/^5000$/o, @list) ) {
                # code
            }
        },
  'hash'    => sub {
            my %params = map { $_ => 1 } @list;
            if ( exists($params{5000}) ) {
                # code
            }
        },
});

Resultado do teste de benchmark:

Benchmark: timing 10000 iterations of grep, hash...
          grep:  8 wallclock secs ( 7.95 usr +  0.00 sys =  7.95 CPU) @ 1257.86/s (n=10000)
          hash: 50 wallclock secs (49.68 usr +  0.01 sys = 49.69 CPU) @ 201.25/s (n=10000)
aksel
fonte
5
O uso List::Util::firsté mais rápido, pois para de iterar quando encontra uma correspondência.
amigos estão dizendo sobre robearl
1
-1 Sua referência tem defeitos, grepé significativamente mais lenta que a criação de hash e a pesquisa, uma vez que o primeiro é O (n) e o último O (1). Apenas faça a criação de hash apenas uma vez (fora do loop) e pré-calcule o regex para medir apenas os métodos ( veja minha resposta ).
Xaerxess
4
@Xaerxess: No meu caso, eu queria fazer uma pesquisa, então acho justo contar a criação de hash / regex e a pesquisa / grep. A tarefa seria fazer muitas pesquisas, acho que sua solução é melhor.
aksel
3
Se você deseja fazer apenas uma iteração, a diferença é indistinguível entre qualquer um dos métodos que você escolher, portanto, qualquer parâmetro de referência está errado, já que neste caso é uma micro otimização ruim.
Xaerxess
2
O regex é compilado apenas uma vez, pois possui o sinalizador 'o'.
Apoc 29/04
3

@files é uma matriz existente

my @new_values =  grep(/^2[\d].[\d][A-za-z]?/,@files);

print join("\n", @new_values);

print "\n";

/^2interest\dd.[\dd[A-za-zunette?/ = valores começando em 2 aqui você pode colocar qualquer expressão regular

Rohan
fonte
2

Você certamente quer um hash aqui. Coloque os parâmetros incorretos como chaves no hash e decida se existe um parâmetro específico no hash.

our %bad_params = map { $_ => 1 } qw(badparam1 badparam2 badparam3)

if ($bad_params{$new_param}) {
  print "That is a bad parameter\n";
}

Se você estiver realmente interessado em fazê-lo com uma matriz, veja List::UtilouList::MoreUtils

David M
fonte
0

Há duas maneiras de você fazer isto. Você pode usar os valores lançados em um hash para uma tabela de pesquisa, conforme sugerido pelas outras postagens. (Vou adicionar apenas outro idioma.)

my %bad_param_lookup;
@bad_param_lookup{ @bad_params } = ( 1 ) x @bad_params;

Mas se são dados principalmente de caracteres de palavras e não muitos meta, você pode despejá-los em uma alternância de regex:

use English qw<$LIST_SEPARATOR>;

my $regex_str = do { 
    local $LIST_SEPARATOR = '|';
    "(?:@bad_params)";
 };

 # $front_delim and $back_delim being any characters that come before and after. 
 my $regex = qr/$front_delim$regex_str$back_delim/;

Essa solução teria que ser ajustada para os tipos de "valores ruins" que você está procurando. E, novamente, pode ser totalmente inapropriado para certos tipos de strings, portanto, ressalte o emptor .

Axeman
fonte
1
Você também pode escrever @bad_param_lookup{@bad_params} = (), mas precisaria usar existspara testar a associação.
Greg Bacon
-1
my @badparams = (1,2,5,7,'a','zzz');

my $badparams = join('|',@badparams);   # '|' or any other character not present in params

foreach my $par (4,5,6,7,'a','z','zzz')
{
    if ($badparams =~ /\b$par\b/)
    {
        print "$par is present\n";
    }
    else
    {
        print "$par is not present\n";
    }
}

Convém verificar a consistência numérica dos espaços à esquerda

Sarja
fonte