ツイッターで見かけた御題なのですが、(学校の課題などで)ありそうなので、置いておきます。
# お試しデータを作る
set.seed(20150208)
n <- 30
df <- data.frame(type=c("A", "B", "C")[round(runif(n, min=0.5, max=3.5))], value=60 - ((1:n)-10)^2)
# タイプごとに最大値を求める
tapply(df$value, df$type, max)
# 2番目の値を求める
tapply(df$value, df$type, function(x){
# 降順ソートをして2番目を返す
# 最大値が複数ありえる場合は、後述の「最大値を除外する: O(n)が2回」のコードか、追記したコードを使ってください
sort(x, decreasing=TRUE)[2]
})
奥村晴彦氏から計算量がO(n log n)でオセーヨってツッコミが来たので、O(n)になるように改良してみましたが、300万件でもuserで2割ぐらいしか時間を削れませんでした*1。小選挙区の数は300しかないので(謎)、遅いコードで許してください。
以下は時間計測に使ったコードです。
set.seed(20150208)
# 300万件でテスト
n <- 3000000
# データは散らばるようにしておく
df <- data.frame(type=c("A", "B", "C")[round(runif(n, min=0.5, max=3.5))], value=runif(n, min=0, max=n))
# ソートする遅い版: O(n log n)
gc();gc();system.time({
tapply(df$value, df$type, function(x){
sort(x, decreasing=TRUE)[2]
})
})
# 最大値を除外する: O(n)が2回
gc();gc();system.time({
tapply(df$value, df$type, function(x){
max( x[x!=max(x)] )
})
})
# コメントで示唆されたもの: O(n)が2回
gc();gc();system.time({
tapply(df$value, df$type, function(x){
x[which(x==max(x))] <- NA;
max(x, na.rm=TRUE)
})
})
追記(2018年5月19日)
これでは同値で1位があったときに2番目に大きい数字が取れないと言う指摘があったので、(上述の最大値を除外する: O(n)が2回のコードでも良いのですが)max2関数を定義して正しく処理できるようにします。
# データセットを作る
set.seed(20180519)
df2 <- data.frame(type=c("A", "B", "C")[round(runif(n, min=0.5, max=3.5))], value=round(runif(n)*10))
# データセットのタイプ別の値をソートして並べ替える
tapply(df2$value, df2$type, sort)
#
# 2番目もしくはranking番目に大きい数字を戻す関数
# 該当がなければNA
#
max2 <- function(x, ranking=2){
y <- sort(x, decreasing=TRUE)
m <- ranking
p <- 1
while(1<m && p<length(y)){
if(y[p]>y[p+1]){
m <- m - 1
}
p <- p + 1
}
if(1<m){
return(NA)
}
y[p]
}
# 2番目を求める
tapply(df2$value, df2$type, max2)
# 3番目を求める
tapply(df2$value, df2$type, function(x){
max2(x, ranking=3)
})