http://875880923.iteye.com/blog/1963400

时间:2022-02-26 14:54:06

已经接触了一段时间的ACM(详见百度百科)了,每回刷杭电oj的题累了的时候,就喜欢去看Ranklist里面的排名,看看前面的牛人的格言,让自己有一点憧憬。有一天突然好奇杭电上的人做的总题数的数量与人数之间有怎样的分布规律,这样就可以知道大多数的人做了多少题就停了下来。

http://875880923.iteye.com/blog/1963400

说干就干,我先用用java代码写了一个抓取上面Ranklist网页的程序到本地后,利用正则表达式解析内容并提取其中的数据,最后导入到数据库中。技术方面不想讲的太详细,只想说下其中遇到的问题。 
抓取网页速度太慢。近两千个网页似乎抓取了近十分钟,后来采取多线程抓取网页,由于学校网速还是很慢,速度只提升了几倍。 
利用正则表达式提取网页中的内容时,由于正则表达式选取的问题有些用户名中含有<  >导致一些数据提取错误,不过后来解决了。 
导入mysql数据库太慢(数据比较多),不知道是不是可以用多线程对数据库中的同一个表进行写入,如果可以的话,效率有没有提高。

获取到数据只是第一步,接下来更麻烦的工作是数据分析了。图像比较直观,先画个图像。说明:X轴代表解决题目的数目,Y轴代表解决了这么多题的人数。虽然杭电有20多万注册量,但只有前60000名刷过的题数大于等于3,我们不考虑60000名以后的。

http://875880923.iteye.com/blog/1963400

第一次看到程序画出来的图,感到不可思议。我原先猜测图像可能会有一些波峰波谷。但是图像并没有这样的特征,而是飞速的下降直到趋于平缓。得到大致图像后,并没有结束,我想用一个函数关系来近似描述这个曲线。 
     于是我和我的室友将这些数据输入到matlab中来求拟合曲线,选取拟合程度最好的两个数据如下:

General model Power2: 
       f(x) = a*x^b+c 
Coefficients (with 95% confidence bounds): 
       a =  1.571e+004  (1.53e+004, 1.612e+004) 
       b =     -0.9897  (-1.004, -0.9758) 
       c =      -38.22  (-42.7, -33.75)

Goodness of fit: 
  SSE: 2.529e+006 
  R-square: 0.9731 
  Adjusted R-square: 0.9731 
  RMSE: 50.47

http://875880923.iteye.com/blog/1963400

General model Exp2: 
       f(x) = a*exp(b*x) + c*exp(d*x) 
Coefficients (with 95% confidence bounds): 
       a =  4.392e+004  (-5.091e+017, 5.091e+017) 
       b =     -0.1001  (-1.629e+005, 1.629e+005) 
       c = -3.835e+004  (-5.091e+017, 5.091e+017) 
       d =     -0.1001  (-1.852e+005, 1.852e+005)

Goodness of fit: 
  SSE: 3.762e+006 
  R-square: 0.96 
  Adjusted R-square: 0.9599 
  RMSE: 61.58

http://875880923.iteye.com/blog/1963400

拟合度最高的函数是 
       f(x) = a*x^b+c 
其中 
a =  1.571e+004  (1.53e+004, 1.612e+004) 
b =     -0.9897  (-1.004, -0.9758) 
c =      -38.22  (-42.7, -33.75)

让我们来使这个式子更简洁。我们不考虑a 和 c,而b近似于-1,最后得到

Y  =  1 / X

  想必大家都知道了,这就是我的题目是这个函数的原因。竟然是反比例函数,这代表什么涵义呢? 
  这样,我们规定刷的题越多越牛逼,那么这个函数说明了牛逼的程度和牛逼的人数成反比。这是什么破结论啊,不用这个我都知道啊。不过我实在没想出好的自然语言去解释这个式子,不知道读者们有什么看法。 
  但是我们更深入的去分析数据,发现刷了400题以下的占总人数的99%,而刷题数>=400的人只有1%,那些刷题过了400题的,应该就是我们口中所说的大神吧。 
     这就像我们的人生的经历,每个人都想成为人群中的1%,但是大多数人都在这之前停了下来。我们会想到一切客观的因素,来叹诉命运的不公。但事实却是,我们还不够努力。

最后送一句话给那些正在实现自己梦想途中的ACMer 
做好1000道题,区域赛就可以拿金牌了。 
                                              ----郭嵩山