2010年05月01日 13:15 [Edit]

perl - 配列の∪と∩

これを解くためには、配列の∩(交わり、intersection)がわかればいいのですが…

perlかPHPで解決したいです。 複数(最大200程度)の配列があり、 それぞれ有している数字(それぞれ最大50程度)のうち、 二つ以上の値が同じ配列名を抜き出す。 という事をし.. - 人力検索はてな
複数(最大200程度)の配列があり、 それぞれ有している数字(それぞれ最大50程度)のうち、 二つ以上の値が同じ配列名を抜き出す。

実にエレガントな方法が、Perl Cookbookに載っています。


以下、実例。

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

sub union(\@\@){
  my ($ar, $br) = @_;
  my %union;
  $union{$_}++ for (@$ar, @$br);
  return keys %union;
}

sub intersection(\@\@){
  my ($ar, $br) = @_;
  my (%union, %intersection);
  $union{$_}++ && $intersection{$_}++ for (@$ar, @$br);
  return keys %intersection;
}

my @a = qw/0 1 2 3 4 5 6 7 8 9/;
my @b = qw/0 2 4 6 8 10 12 14 16 18/;
local ($, , $\) = (",", "\n");  # to pretty-print
print intersection(@a, @b);
print union(@a, @b);


これだけだと慣れていない人はハァ?だと思うので、少し解説しますか。

まずfor (@$ar, @$br)ですが、これで両配列の全要素を順送りに$_に代入していることはおわかりいただけるかと思います。$union{$_}++で、その要素をキーとするハッシュエントリーが存在しなければそこに1を設定し、なければ2に設定します。++は後置なので、$union{$_}が存在しているときのみ&&が成立。$intersection{$_}++が実行されるわけです。

あとは、最後にハッシュ%intersectionのキーだけ抜き出してしまえば、それが配列の∩ということになるわけです。

配列の問題をハッシュで解くというのは、perlで「開発」が進み、今ではハッシュを内蔵する各言語で盛んに用いられています。ぐぐるのもよいのですが、こういう時こそ Cookbook です。一冊常備しておくことをお勧めします。

Dan the Perl Monger


この記事へのトラックバックURL

この記事へのトラックバック
404 Blog Not Found:perl - 配列の∪と∩に想定内の返事が。 Perl Cookbook (English) Christiansen / Torkington [邦訳: Perlクックブック] 2010-05-01 - methaneの日記一方、Pythonはsetの演算子を定義した。 もちろんPerlでも定義できます。
perl - にも集合オブジェクトと演算を【404 Blog Not Found】at 2010年05月05日 04:24
小飼弾さんのブログ記事 perl ?? 配列の∪と∩を見て、Rubyだったらどう書くんだっけ? と思ってしまった。 a1 = [1, 2, 3, 4, 5] a2 = [2, 4, 6, 8] union = (a1 + a2).uniq intersect = a1.select {|e| a2.include?(e)}
配列のintersectとunion【いたさんのブログ】at 2010年05月01日 23:31