作者realtemper (一觉醒来傅钟前)
看板Statistics
标题Re: [程式] 一题资料库程式 很简单的
时间Sat Jun 20 08:34:28 2015
※ 引述《cawaiilulu (across)》之铭言：
(恕删)
: 没关系 这个都不用管 假设就 都两位以下数字 我主要是想问怎麽写比较"快"
我尝试写了一段应用双重 set 回圈的 code 如下（及本文末，防连结失效）
https://gist.github.com/anonymous/6f5b3f7f650a990bcfac
先讲测试结果....
测试条件：SAS 9.4 / win7 x64 / 2.9G 双核心 / ramdisk 20G（SAS工作位置）
以资料笔数 n=1k, m=500k 测试，耗时
real time 144s
CPU time 133s
因此合理估计 n=100k, m=500k 时，将花去约13300s, 即3.7小时左右
不晓得这个效率，是否符合您的期待？
然後是最佳化的想法....
首先您要求的任务，基本上时间复杂度一定是 >= O(nm) 的，
这是因为您不但需要判定「较大变数个数之最大值 (绝大多数情况会是 5)」，
还必须给出最大值的「发生次数」，
所以每一笔 n 跟每一笔 m 都非得做过一次比较，才能取得发生次数之故。
因此，能够最佳化的部份，主要就是下面这些点了：
1.尝试减少 I/O 次数（磁碟读写总是最慢的）
2.减少各种不必要的中间变数。
3.尝试一边读取、一边计算、一边更新，仅用 n*m 次资料存取就解决问题。
（i.e.就资料 I/O 的部份，把常数压到 1）
另外，这个 case 我认为 set 双回圈的作法一定远远优於 proc sql。
因为这两个表格的合并方式是不带条件的 Cartesian join，
并且用 proc sql 来处理的话，还需要制造 5 个 dummy variable，
（case when then else end 的写法，大概非这样不可，至少我写不出其他作法）
所以一定会产生一个非常庞大的 (n*m) 中间资料集，
产生大量不必要的I/O。
相较之下，data step 的 set 双回圈，在条件判断与资料输出方面，就灵活许多。
对 dataset b 的资料，可以轻易做到读完即丢(见code)，
除了结果之外，完全不需创造中间资料集，
因此空间复杂度会永远被压缩在 1*1，而不是 n*m
当然如果我有想错，也请诸位前辈不吝赐教～ m(_ _)m
附：测试程式码
%let NA = 1000; * expect 100k;
%let NB = 500000; * expect 500k;
/* generate test dataset */
data a;
ID = 0;
do while (ID < &NA);
ID + 1;
V1 = ranuni(777);
V2 = ranuni(777);
V3 = ranuni(777);
V4 = ranuni(777);
V5 = ranuni(777);
output;
end;
run;
data b;
ID = 0; * ID of b is of no use;
do while (ID < &NB);
ID + 1;
V1 = ranuni(911);
V2 = ranuni(911);
V3 = ranuni(911);
V4 = ranuni(911);
V5 = ranuni(911);
output;
end;
run;
/* match */
data result(keep=ID CNT);
set a;
N = 0; * the current maximum value of "# of bigs";
CNT = 0; * the # of occurence of current N;
i = 0; * pointer for random accessing dataset b;
do while (i < NN);
i+1;
/* read i-th obs of dataset b */
set b(rename=(V1-V5=BV1-BV5) drop=ID) point=i nobs=NN;
/* find "# of bigs" of this i-th obs */
N_this = 0;
if V1 - BV1 > 0 then N_this = N_this + 1;
if V2 - BV2 > 0 then N_this = N_this + 1;
if V3 - BV3 > 0 then N_this = N_this + 1;
if V4 - BV4 > 0 then N_this = N_this + 1;
if V5 - BV5 > 0 then N_this = N_this + 1;
/* take action based on the value of N_this */
* case 1: N_this < N -> discard all data of b (do nothing);
if N_this < N then do;
end;
* case 2: N_this = N -> update CNT;
else if N_this = N then CNT = CNT + 1;
* case 3: N_this > N -> replace N by N_this and reset CNT value;
else do;
N = N_this;
CNT = 1;
end;
/* output to see how N and CNT change gradually (should limit the
value of &NA and &NB!) */
*output;
end;
run;
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.39.232.118
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Statistics/M.1434760473.A.B0A.html
※ 编辑: realtemper (114.39.232.118), 06/20/2015 08:42:07
1F：→ MOONY135: 我的感觉会很慢 06/20 11:17
2F：→ realtemper: 请赐教 06/20 17:28
3F：→ MOONY135: 喔 我是说我上一篇的CODE 我用SQL写的 06/20 22:02
4F：→ realtemper: 嗯 试过了，你的其实不是慢，是不能解决问题 -- 因为 06/21 01:15
5F：→ realtemper: 中间资料集太大了(100*500k即达2.6G) 06/21 01:16
6F：→ realtemper: 100k*500k就会需要吃掉>2T。 06/21 01:18