Hatena::ブログ(Diary)

もうカツ丼でいいよな このページをアンテナに追加 RSSフィード Twitter

2009 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 12 |
2012 | 02 | 03 | 04 | 05 | 06 | 10 | 11 | 12 |
2013 | 01 | 02 | 04 | 06 |
2014 | 06 |

2011-07-31

[][][] Rで最大部分列和問題 19:30  Rで最大部分列和問題を含むブックマーク  Rで最大部分列和問題のブックマークコメント

最大部分列和(Maximum Segment Sum、略してMSS)問題とは、与えられた整数列の部分列の和のうち最大のものを求めるという問題。

非常に簡単な例で言うと、

a = {-1, -1, 1, 1, 1, -1, -1}

という数列の最大部分列和mss(a)は{1, 1, 1}の和の3になる。

他にも、

## example
a1 <- c(8, -3, 65, -20, -45, 100, 8, -17, 4, -14)
## mss(a1) => 113 = sum(8, -3, 65, -20, -45, 100, 8)
a2 <- c(31, -41, 59, 26, -53, 58, 97, -93, -23, 84)
## mss(a2) => 187 = sum(59, 26, -53, 58, 97)

といった具合になる。

全ての部分列を求めて比較する方法

すぐ思いつくやり方は、全ての部分列を列挙し、それぞれの総和を計算して一番大きなものを探すというやり方だろう。

mss1 <- function(a){
  n <- length(a)
  s <- 0
  for(i in 1:n){
    for(j in i:n){
      s <- max(s, sum(a[i:j]))
    }
  }
  s
}

計算速度を測る関数を定義する。

test.mss <- function(fun, scale=1){
  n <- seq(100, 500, by=100) * 10^(scale-1)
  times <- numeric(length(n))
  names(times) <- as.character(n)
  for(i in 1:length(n)){
    s <- runif(n[i])
    times[i] <- system.time(fun(s))[[1]]
  }
  return(times)
}

測ってみる。

> test.mss(mss1, 1)
  100   200   300   400   500 
0.028 0.135 0.324 0.626 1.065 

f:id:Rion778:20110731195508p:image

の計算量で、長さ500の数列から最大部分列和を求めるだけで1秒程度かかる。

端っこから順次計算していくやり方

全ての部分列を求める必要はなくて、もうすこし上手いやり方がある。

a[1]、a[1]+a[2]、a[1]+a[2]+a[3]...というように頭から順に部分列を伸ばしながら和を計算していく。

和はsという変数に保持しておいて、sの最大値をmssという変数に保持しておく。もし途中でsが0を下回った場合、それまでの部分列を延長しても最大部分列和は得られないので、sを0にリセットして新たに部分列を計算していく。

mss2 <- function(a){
  s <- mss <- 0
  for(i in 1:length(a)){
    s <- s + a[i]
    if(s < 0) s <- 0
    if(mss < s) mss <- s
  }
  mss
}
> test.mss(mss2, 4)
1e+05 2e+05 3e+05 4e+05 5e+05 
0.293 0.582 0.872 1.157 1.448 

f:id:Rion778:20110731195510p:image

このやり方だとの計算量で済む。mss1よりかなり早い。

それでも長さ500000の配列の最大部分列和を求めるのに1秒強かかる。

そもそもRがいけない

Rcppを使えばRの遅さに煩わされることはない。

さらにinlineパッケージを使えば手軽にC++の恩恵にあずかれるので、使わない手はない。

library(Rcpp)
library(inline)
mss3 <- cxxfunction(signature(a = "integer"), "
IntegerVector aa(a);
int s = 0;
int mss = 0;
int n = aa.size();
for(int i=0; i<n; i++){
  s += aa[i];
  if(s < 0) s = 0;
  if(mss < s) mss = s;
}
return wrap(mss);
", plugin = "Rcpp")
> test.mss(mss3, 6)
1e+07 2e+07 3e+07 4e+07 5e+07 
0.079 0.163 0.252 0.342 0.472 

f:id:Rion778:20110731195509p:image

5千万の配列から最大部分列和求めるのに0.5秒程度で、mss2と比較してざっと300倍くらい早い。

結論

Rcpp使おう。

2011-07-24

[][] Problem 148 15:43  Problem 148を含むブックマーク  Problem 148のブックマークコメント

no title

パスカルの三角形の最初の7行に含まれる数のなかに7で割り切れるものが無いことは簡単に確認できる。

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

しかし、最初の100行まで調べると、5050ある数のうち7で割り切れない数は2361個しかない。

パスカルの三角形の最初の10億()行までに含まれる数のうち、7で割り切れない数はいくつあるか。

続きを読む

2011-07-23

[] Mac OS X 10.7 Lion入れてからやったこと 10:40  Mac OS X 10.7 Lion入れてからやったことを含むブックマーク  Mac OS X 10.7 Lion入れてからやったことのブックマークコメント

ちなみにアップデートは7/22に後先考えずやりました。

ワイプの挙動変更

スクロールが逆なのはiPhone/iPadと同じだしそのうち慣れると思うけど…

やっぱ3本指スワイプブラウザ操作とかに使いたいので、主にそのための変更。

システム環境設定 > トラックパッド > その他のジェスチャ から

それぞれ変更。

キーボードショートカットの変更

システム環境設定 > キーボード > キーボードショートカット > Mission Control > Mission Control から

  • "左(右)の操作スペースに移動"のチェックを外す

ブラウザ内のテキストエリアなんかでC-a、C-eすると操作スペース移動してしまう現象への対応。

たぶんKeyRemap4MacBookの関係だろうと思うし別のショートカット割り当てれば済む話なんだろうけどそもそも使わないので。

Firefox等で3本指スワイプすると落ちる問題への対処

MultiClutchが原因らしい。

TotalTerminalインストール

TotalTerminal is a system-wide terminal accessible via a hot-key

Visorの名前が変わったらしい。起動時もTerminal.app呼ぶのではなくTotalTerminal.appを呼ぶ。

あと色も変えた(cf.no title)。

Xcodeインストール

App StoreからXcode 4.1を検索してインストール。これでgccやらmakeやら使えるようになる。

2011-07-19

[][] Problem 147(2) 00:13  Problem 147(2)を含むブックマーク  Problem 147(2)のブックマークコメント

Forum読んだ結果程度までは計算量減らせた。一発で答えの出る公式も書いてあるんだけどどうやって導出してんのか分からない…。

あまり詳しく言うと面白みがなくなるので要点だけ書くと、

続きを読む

2011-07-18

[][] Problem 147 21:01  Problem 147を含むブックマーク  Problem 147のブックマークコメント

no title

斜め線が引かれた3x2の格子には合計で37の長方形が含まれる(上記問題文リンク先に図解)。

3x2よりも小さい格子は5つある(1x1, 2x1, 3x1, 1x2, 2x2)。これらの格子は各々次のような個数の長方形を含む。

1x1: 1

2x1: 4

3x1: 8

1x2: 4

2x2: 18

3x2に含まれる長方形の個数37と合わせると、3x2以下の格子についてそれぞれ長方形の個数を数えたものの総和は72であることがわかる。

47x43以下の全ての格子各々について含まれる長方形の個数の総和はいくつになるか。

続きを読む

2011-07-02

[]6月の買った本、読んだ本、買ったCD 22:57 6月の買った本、読んだ本、買ったCDを含むブックマーク 6月の買った本、読んだ本、買ったCDのブックマークコメント

6月は買った本割とちゃんと消化できたと思うんだ。

今月積んだ本

使う機会と機械が欲しい。

数学をいかに使うか (ちくま学芸文庫)

数学をいかに使うか (ちくま学芸文庫)

また身の丈を弁えず背伸びしてしまった感。線形代数一度きちんとやらないと読めない本が何時までも減らない…。

新釈 現代文 (ちくま学芸文庫)

新釈 現代文 (ちくま学芸文庫)

わかりやすい―園芸作物の栄養診断の手引き

わかりやすい―園芸作物の栄養診断の手引き

消費者志向を重視したトマトの栽培技術 (野菜の栽培技術シリーズ)

消費者志向を重視したトマトの栽培技術 (野菜の栽培技術シリーズ)

アブラムシ―おもしろ生態とかしこい防ぎ方

アブラムシ―おもしろ生態とかしこい防ぎ方

ベッドルームで群論を――数学的思考の愉しみ方

ベッドルームで群論を――数学的思考の愉しみ方

半分くらいまで読んだけどすごく面白い。ちなみに数式はほとんど出てこない。

堆肥・有機質肥料の基礎知識

堆肥・有機質肥料の基礎知識

今月読んだ本

神が愛した天才数学者たち (角川ソフィア文庫)

神が愛した天才数学者たち (角川ソフィア文庫)

この手の本におけるガロアの安定感相変わらずすごい。(c.f. “浪人時代”の成績表を見ると、リシャールが担当した数学と、ガロアがまったく関心をもたなかった科学や物理... - Books)

イノセント・ゲリラの祝祭 (下) (宝島社文庫 C か 1-8)

イノセント・ゲリラの祝祭 (下) (宝島社文庫 C か 1-8)

人の名前覚えたような覚えてないような感じのまま読み終えてしまったけど最後の方それなりに面白かった。

誰とでも 15分以上 会話がとぎれない!話し方 66のルール

誰とでも 15分以上 会話がとぎれない!話し方 66のルール

どうなんすかね。

「詳しくは同シリーズのミナミキイロアザミウマを…」というような丸投げが沢山あるのに肝心のミナミキイロアザミウマの本だけ絶版で入手できない…。

農耕と園藝 2011年 06月号 [雑誌]

農耕と園藝 2011年 06月号 [雑誌]

農耕と園藝 2010年 07月号 [雑誌]

農耕と園藝 2010年 07月号 [雑誌]

今月買ったCD

Evil Empire

Evil Empire

Korn

Korn

Bug

Bug

Point of Know Return

Point of Know Return

You're Living All Over Me

You're Living All Over Me

Issues

Issues

Vs

Vs

YES YES VINDICTIVE

YES YES VINDICTIVE

Green Mind

Green Mind

Korn III-Remember Who You Are

Korn III-Remember Who You Are

Grace & the Bigger Picture

Grace & the Bigger Picture