实测R的vector和list结构比python对应的list和dict慢近千倍，怎么破？

你需要用数据的思维你看你的问题

tapply(v, k, unique)

1. k <- sample(1:10000, 500000, replace= TRUE)
   
2. 
   
3. v <- sample(1:10000, 500000, replace= TRUE)
   
4. 
   
5. system.time(result <- tapply(v, k, unique))
   
6. 
   
7. user  system elapsed
   
8.   0.123   0.010   0.133
   
9. 
   
10. 50万组不到1秒

复制代码

用logical operator， 和dplyr的package，可以把时间缩到1.5秒
library(dplyr)
k <- round(runif(500000, min = 0, max=1), digits = 2) * 100
v <- round(runif(500000, min = 0, max=1), digits = 2) * 100
tot <-
  data.frame(k, v) %>%
  arrange(k, v) %>%
  unique()
out <- with(tot, split(v, k))


   user  system elapsed
  1.556   0.000   1.554

ntsean 发表于 2016-1-7 03:07

您的代码对效率的提升，主要是来自于您是用sample做整数抽样，形成的数据是integer类型，而原来的模拟方法，形成的数据是double类型，两者处理起来速度差别很大。

好眼力。简答测试了一下，速度差在3.5倍左右

suimong 发表于 2016-1-7 21:52
好眼力。简答测试了一下，速度差在3.5倍左右

您这测试包好用啊！学到了。

cheetahfly 发表于 2016-1-6 16:11
我听着都很高兴

抱歉，我过于乐观了。其实我处理的原始数据是50万条，归并后就只有10万条左右，最初处理大约15分钟，第一次向量化后约240秒，用split优化后3秒。

这个帖子持续热闹，让我又学到不少东西！

感谢“suimong”同学，他在18楼的发言一针见血：这个问题的本质是分割和去冗两个核心环节，对应split和unique函数就能解决；也感谢“ntsean”同学，他的tapply是目前调用函数最少的解决方案。

在本帖持续讨论的同时，另外一个帖子“求教：如何分割一个很大的字符矢量？”（https://bbs.pinggu.org/thread-4166951-1-1.html）也给了我很大启发，其中，“万人往LVR”同学的代码为我打开了另外一条思路；“suimong”同学的效率测试让我明白——在某些情况下split()也有可能成为不可小觑的性能瓶颈——在本例中就是这种状况。经大致分析，其原因很可能是由于split(x,f)中的f是专门针对factor类型，而把numeric型转化成factor型耗费巨量时间。（将k向量as.factor之后，split(v,k)的耗时基本上可以忽略不计了）

于是，我想能否专门针对numeric类型进行优化呢？按照“万人往LVR”同学的思路，我瞎写了一个split.num小函数，专门针对f参数是numeric vector时的分割：

1. split.num <- function(xn, fn) {
   
2.   idx <- order(fn)
   
3.   fno <- fn[idx]
   
4.   xno <- xn[idx]
   
5.   len <- length(fno)
   
6.   pos.e <- c(which((fno[-len]-fno[-1])!=0),len)
   
7.   pos.b <- c(1,(pos.e[-length(pos.e)]+1))
   
8.   result <- lapply(1:length(pos.b), function(i) xno[pos.b[i]:pos.e[i]])
   
9.   return(result)
   
10. }

复制代码

另外，根据楼主真实数据的特征，我将模拟k和v的方式稍微改变了一下，以达到“归并后有10万条左右”的效果。
我目前桌面的电脑CPU是i3，测试结果如下：

测试结束后，特意逐项比较了一下split和split.num的计算结果是否完全一致，答案是肯定的。

如果按照最初的k和v的模拟方法（归并后大概100条左右），split.num解决方案速度在0.3秒左右。无论如何，都在我的破电脑上实现了1秒以内完成了。

好了，我可以狗带了

......

好吧，其实还是有些不甘心。在整个过程中split.num()耗时的占比仍然太大，大家还有什么好的思路进一步优化吗？

经过一个周末的思考，我再把这个问题的解决方案优化了一步。

首先，各位同学别怪我在这个问题上的较真，因为“split”的问题是R语言数据处理中的一个普遍性问题，大神Hadley Wickham在其文章The Split-Apply-Combine Strategy for Data Analysis中就将Split-Apply-Combine的操作方法提升到了策略的高度，并因此有了plyr软件包。故而，将split的各种可能的瓶颈研究清晰，并提出针对性的优化方案，将终究会使大家未来的数据研究工作受益。

这次我的思路是从factor这一环节展开的。split()对factor参数与非factor参数的效率可谓天差地远：

1. k <- round(runif(500000, min=0, max=1), digits=5) * 1e5
   
2. v <- round(runif(500000, min=0, max=1), digits=1) * 1e1
   
3. k.f <- as.factor(k)
   
4. system.time(split(v,k))
   
5.     用户 系统 流逝
   
6.     1.21 0.00 1.22
   
7. system.time(split(v,k.f))
   
8.     用户 系统 流逝
   
9.     0.03 0.00 0.03

复制代码

由此，可知split环节的瓶颈其实是在as.factor环节。

而之前“ntsean”同学的发言让我无意中发现integer数据类型和double数据类型在as.factor环节也有着非常大的差别，比如：

1. k1 <- sample(1:100000, 500000, replace = T)
   
2. typeof(k)
   
3.     [1] "double"
   
4. typeof(k1)
   
5.     [1] "integer"
   
6. system.time(as.factor(k))
   
7.     用户 系统 流逝
   
8.     1.2  0.0  1.2
   
9. system.time(as.factor(k1))
   
10.     用户 系统 流逝
    
11.     0.15 0.00 0.15

复制代码

至此，我推测数据类型是制约as.factor环节的一个重要因素，也是可以优化的一个重要方向。

我仔细观察了一下as.factor和factor两个函数，这两个函数都是用R语言编写的，并非用C语言。虽然我没有完全搞清楚其机理，但我猜测将integer和double的数据类型分开不同的程序处理仅仅是为了容错性上的考虑，而并非是技术性上的限制。

于是我将as.factor源程序中的一段抽取了出来，单独写了一个函数：

1. factor.num <- function(x) {
   
2.   levels <- sort(unique.default(x))
   
3.   f <- match(x, levels)
   
4.   levels(f) <- as.character(levels)
   
5.   class(f) <- "factor"
   
6.   f
   
7. }

复制代码

测试了一下，对double数据类型的操作是没有问题的，且效率提升了很多：

1. system.time(as.factor(k))
   
2.     用户 系统 流逝
   
3.     1.18 0.00 1.19
   
4. system.time(factor.num(k))
   
5.     用户 系统 流逝
   
6.     0.24 0.01 0.25
   
7. identical(as.factor(k), factor.num(k))
   
8.     [1] TRUE

复制代码

这下好了，我将在28楼的测试思路延续到新的含有factor.num()的解决方案上来，且我将每种方法均用30次测试，观测均值和中位数。第一种方法是“suimong”的lapply方法，第二种方法是“ntsean”的tapply方法，第三种是我用split.num()的解决办法（在本帖28楼有说明），第四种方法是本楼用factor.num()函数的方法。最后将结果检验了一下，没有问题。


OK，执行效率再进一步，在我的i3 CPU上基本0.6秒左右可以完成，不同的电脑上可能会更快。

通过这个例子，让我对R语言的优化有了很直观的感悟，其中一条，有些函数由于考虑容错性、兼容性的要求，往往代码会比较多，在一些比较极端的对优化要求很高的场合，如果针对具体数据的特点，去掉函数不必要的容错代码，有可能大幅提高执行效率。

不知我这一思路有没有错漏，多谢各位指正！

好了，以我的水平，已经在这个问题上发挥到极致了，现在我真的可以狗带了

真的是学习了。
system.time(lapply(split(v, factor.num(k)), unique))
   user  system elapsed
  0.048   0.004   0.057

把grouping 这部分用factor.num来运算，在我的laptop上可以提高到0.1秒以内。