急勾配の判定 in Perl DouKaku?

有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．

任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．

必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．

foreachの方が分かりやすかったかも。計算量はΘ(n)のはずです。

use List::MoreUtils qw/all/;
sub is_super_dec(@) {
  my $total = 0;
  all { ($_ > $total) and do { $total += $_; 1 } } reverse @_;
}

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

sub is_steep_array{
    my @arr = reverse @_;
    my $sum = 0;
    $sum < $_ ? $sum += $_ : return () for @arr;
    1;
}
print 'true' if is_steep_array(9,4,2,1);

後ろから見ていくことで、効率的になっていますね。 pop使えば、reverseする手間も省けていいんじゃないかなーと思います。

sub isSteep2{
    my($x,$q) = 0;
    $x < ($q = pop||return 1) ? $x += $q : return 0 while 1;
}

再帰的に書いてみました。
計算量(という表現でいいかは別として、)は一律に要素数と一致するはず。たぶん。

Tabが一律4半角スペースなのでインデントがおかしいですけどそこはスルーでお願いします。

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

sub isSteep{
    my $x = shift||return 1,0;
    my @y = isSteep(@_);
    return $y[0]&&$x>$y[1]?1:0,$y[1]+$x;
}

my @a1    = (\@{[100, 30, 10, 4, 1]},
      \@{[10, 30, 100]},
      \@{[10, 4, 2, 1]},
      \@{[10, 5, 4, 2]});

print join(', ',@{$_}),' is',((isSteep(@{$_}))[0]?'':'n\'t'),' a steep array.',$/ for@a1;

#8973のボトルネックはreverseした値を配列にコピーしているところですね。

for(each)に直接渡すと最適化されるのでpopよりずっと速いです。以下ベンチマーク。

use Benchmark qw/cmpthese/;

my @steep = map { 2 ** $_ } reverse 0 .. 49;

cmpthese(100_000,
         { pop    => sub { is_steep0(@steep) },
           rev_cp => sub { is_steep1(@steep) },
           rev    => sub { is_steep2(@steep) },
           nk_pop => sub { is_steep3(@steep) },
           sk_rev => sub { is_steep4(@steep) } });

sub is_steep0 {
  my $total = 0;
  while (my $i = pop) {
    return unless $total < $i;
    $total += $i;
  }
  return 1;
}

sub is_steep1 {
  my $total = 0;
  my @rev = reverse @_;
  for my $i (@rev) {
    return unless $i > $total;
    $total += $i;
  }
  return 1;
}

sub is_steep2 {
  my $total = 0;
  for my $i (reverse @_) {
    return unless $i > $total;
    $total += $i;
  }
  return 1;
}

# http://ja.doukaku.org/comment/9251/
sub is_steep3 {
  my ($x,$q) = 0;
  $x < ($q = pop||return 1) ? $x += $q : return 0 while 1;
}

sub is_steep4 {
  my $total = 0;
  $total < $_ ? $total += $_ : return 0 for reverse @_;
  return 1;
}

DouKaku?

急勾配の判定

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq