イケてないプログラム(使えない成果物)に見られる3つの共通点

クイックソートの話で書いたとおり、相変わらず Excel - VBA と格闘する日々が続いております・・・orz

大企業にありがちな問題。委託開発の甘い罠・・・」でも書いたとおり、今まで外注して作ったソフトウェアってほぼ 100% の確率でイケていないものが完成してます。年末に納品されたソフトウェアのできも酷いの何のって・・・

さて、いままで見てきたイケてないプログラムのダメソースに共通して言えることが3点ありまして、

  • DRY ( Don’t Repeat Yourself ) でない。同じもしくは似たソースのコピペが至る所に散在する。
  • ロジックに無駄が多すぎ。行き当たりばったりで作った感、満点。
  • アルゴリズム知らなさすぎ。馬鹿ループ処理で時間かかりすぎ。
のいずれか、もしくは全部が当てはまります。大抵は全部ですね。こういったソースが納品されると、センス無いなぁ〜と思っちゃうわけ。こういうは案の定、要求する処理時間を大幅に上回っていたりバグが多かったりします・・・。
- スポンサーリンク -

さて、今回外注したソフトウェアのキモとなる部分の1つとして、データの組合せ問題を解くロジックとソートの問題がありました。ソートについては、「再帰処理のクイックソート vs 非再帰処理のクイックソート」で記述したので、そちらを見て頂くとして、組合せ問題もなかなかにキワモノのコードが書かれていました。

ってか、データの組合せ問題を解くロジックがアホでして、

億単位の組み合わせ生成 → バブルソート → データのフィルタリング

ってかかれていたのですが、コレではループ処理が発散して1日たっても結果は帰ってきません。
データのフィルタリング → 限定された組み合わせ生成 → クイックソート

だろ、普通はと思ったりします。あり得ない・・・

さて、順列と組合せは高校で習う数学の問題なので、殆どの方は一度は経験していると思われますが、実際プログラムの中でお目にかかることは少ないと思います。

math.jpg

取りあえず、Perl で実装してみましょう。CPAN には、Algorithm::Permute っていうモジュールがありまして、XS で書かれていて非常高速ですが、今回は頭の体操と言うことで、生 Perl で書いてみることにします。

順列 nPm で得られるデータの組み合わせを求める関数

## nPm = n(n-1)....(n-m+1) を再帰処理で全パターン生成する
sub permute {
my $m = shift; ## m 個を選択する
my (@array) = @_; ## @_ から
&permute_core($#array+1, $m, @array);
} sub permute_core {
my $n = shift; ## n 個の要素から
my $m = shift; ## m 個を選択する ## m 個選択済みなら再帰処理を終了
return @_ if(@_ <= $n-$m+1); my @result;
## 要素群 P(x) から要素をどこから取り出すか? 1 〜 n 個のパターン
for (my $i = 0; $i < @_; $i++) {
my @data = @_;
## 要素群 P(x) から i 個目の要素を1つ取り出す
my $item = splice(@data, $i, 1);
## 残った要素群 P(x+1) から次の要素を取り出す処理を再起処理にまかせる
push(@result, map { "$item,$_" } &permute_core($n, $m, @data));
}
## 要素群 P(x) の全組み合わせを返す
return @result;
} my @data = (a, b, c, d, e, f);
print join(" / ", &permute(3, @data)), "\n";


組み合わせ nCm で得られるデータの組み合わせを求める関数

sub combinatorial {
my $m = shift; ## m 個を選択する
my (@array) = @_; ## @_ から
&combinatorial_core($#array+1, $m, @array);
} sub combinatorial_core {
my $n = shift; ## n 個の要素から
my $m = shift; ## m 個を選択する ## m 個選択済みなら再帰処理を終了
return @_ if($m==1);
my @result;
## 要素群 P(x) から要素をどこから取り出すか? 1 〜 n 個のパターン
for (my $i = 0; $i < @_; $i++) {
my @data = @_;
## 要素群 P(x) から i 個目の要素を1つ取り出す
my $item = splice(@data, $i, 1);
## 使用済みの要素は破棄する
@data = splice(@data, $i);
## 残った要素群 P(x+1) から次の要素を取り出す処理を再起処理にまかせる
push(@result, map { "$item,$_" } &combinatorial_core($#data, $m-1, @data));
}
## 要素群 P(x) の全組み合わせを返す
return @result;
} my @data = (a, b, c, d, e, f);
print join(" / ", &combinatorial(4, @data)), "\n";

再帰処理のプログラムって慣れないと頭がパニックりますよね。僕自信、高校の数学を公式をかなり忘れてしまっているのを痛感しました。

- スポンサーリンク -