ツイッターで見かけた御題なのですが、（学校の課題などで）ありそうなので、置いておきます。
# お試しデータを作る
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)
})
*1:3000万件でも3割ぐらいしか削れないので、Rのsort関数が速く、max関数が遅いんじゃないかと言う疑惑が・・・
