s******g 发帖数: 466 | 1 有以下格式的数据,总共在两千万行左右。请输出一张ID清单。
要求是清单里的每一个ID必须在任意365天的连续区间里累计完成$100或以上的交易额。
ID Date Transaction_Amount
1 1/2/2011 $30
1 4/5/2012 $50
1 9/5/2013 $50
2 7/9/2007 $40
2 8/9/2007 $80
2 10/20/2009 $20
2 11/20/2010 $100
3 7/7/2005 $50
3 12/21/2006 $100
3 1/7/2012 $50 |
n*****t 发帖数: 22014 | 2 SQL? C? JAVA?
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有以下格式的数据,总共在两千万行左右。请输出一张ID清单。 : 要求是清单里的每一个ID必须在任意365天的连续区间里累计完成$100或以上的交易额。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : 2 7/9/2007 $40 : 2 8/9/2007 $80 : 2 10/20/2009 $20 : 2 11/20/2010 $100
|
s******g 发帖数: 466 | 3 任何主流语言都可。关键是思路,电脑是一台主流台式机。希望是处理时间越短越好。
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : SQL? C? JAVA?
|
n*****t 发帖数: 22014 | 4 C 太简单了,一行行读,每个 id 用一个结构记录:start, end, sum,
end -start > 0 print id, sum
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任何主流语言都可。关键是思路,电脑是一台主流台式机。希望是处理时间越短越好。
|
n*****t 发帖数: 22014 | 5 有点歧义,比如一个 id 用了 2 年,这 2 年里我随便取个区间都要保证大于 100 刀
吗?
额。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有以下格式的数据,总共在两千万行左右。请输出一张ID清单。 : 要求是清单里的每一个ID必须在任意365天的连续区间里累计完成$100或以上的交易额。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : 2 7/9/2007 $40 : 2 8/9/2007 $80 : 2 10/20/2009 $20 : 2 11/20/2010 $100
|
s******g 发帖数: 466 | 6 对,任意启始的365天的连续区间。
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有点歧义,比如一个 id 用了 2 年,这 2 年里我随便取个区间都要保证大于 100 刀 : 吗? : : 额。
|
n*****t 发帖数: 22014 | 7 有点意思,性能肯定要用 C,暴力解当然也简单,怎么弄个好的算法让俺琢磨琢磨
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,任意启始的365天的连续区间。
|
s******g 发帖数: 466 | 8 输出清单最好再给出每个ID的达标次数。
根据题目的定义,在该例中 -
ID 1 达标次数 0
ID 2 达标次数 2
ID 3 达标次数 1
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,任意启始的365天的连续区间。
|
n*****t 发帖数: 22014 | 9 最简单的就是每个 ID 用个 list 记录付费和前 365 天的总计,每增加一笔计算这个
list,不达标的就扔出去了,以后再也不用费劲了。从最早一天开始,365 天之后这个
array 就不断减小。暂时没想出更优的。
你这个达标次数我还没理解
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 输出清单最好再给出每个ID的达标次数。 : 根据题目的定义,在该例中 - : ID 1 达标次数 0 : ID 2 达标次数 2 : ID 3 达标次数 1
|
s******g 发帖数: 466 | 10 给点提示。
以下>>表示这连续的两个记录累计达标。
>>>表示该单一记录自身就达标。
ID Date Transaction_Amount
1 1/2/2011 $30
1 4/5/2012 $50
1 9/5/2013 $50
>>2 7/9/2007 $40
>>2 8/9/2007 $80
2 10/20/2009 $20
>>>2 11/20/2010 $100
3 7/7/2005 $50
>>>3 12/21/2006 $100
3 1/7/2012 $50
个
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最简单的就是每个 ID 用个 list 记录付费和前 365 天的总计,每增加一笔计算这个 : list,不达标的就扔出去了,以后再也不用费劲了。从最早一天开始,365 天之后这个 : array 就不断减小。暂时没想出更优的。 : 你这个达标次数我还没理解
|
|
|
s******g 发帖数: 466 | 11 另外每个ID的records最小1个,最大上不封顶。请注意。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给点提示。 : 以下>>表示这连续的两个记录累计达标。 : >>>表示该单一记录自身就达标。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : >>2 7/9/2007 $40 : >>2 8/9/2007 $80 : 2 10/20/2009 $20
|
n*****t 发帖数: 22014 | 12 我看了你的实例,但没明白你的定义。比如 ID 2 REC 3 为啥不算?
当然,暴力解,无非就是在这个 list 里最后计算一下,怎么定义都行,关键是基础的
算法怎么优化 。。。。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给点提示。 : 以下>>表示这连续的两个记录累计达标。 : >>>表示该单一记录自身就达标。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : >>2 7/9/2007 $40 : >>2 8/9/2007 $80 : 2 10/20/2009 $20
|
s******g 发帖数: 466 | 13 ID2 Record 3 = $20,它离最近的其他Records都超过365天了。
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我看了你的实例,但没明白你的定义。比如 ID 2 REC 3 为啥不算? : 当然,暴力解,无非就是在这个 list 里最后计算一下,怎么定义都行,关键是基础的 : 算法怎么优化 。。。。
|
s******g 发帖数: 466 | |
n*****t 发帖数: 22014 | 15 等等,ID 2 2008 年是白板,不是已经 rule out 了吗?
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ID2 Record 3 = $20,它离最近的其他Records都超过365天了。
|
n*****t 发帖数: 22014 | 16 艾玛,你这标题不是求最佳算法吧,是考吧?
掉坑里了,不过这坑有点意思哈
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 考的就是解法。老年SDE的入门测试,呵呵。
|
s******g 发帖数: 466 | 17 不是坑。当然考试啥的是开个玩笑。
题目源自实际工作需要,网上是不会有的。不过假如招人,我们可能出此题哦。
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 艾玛,你这标题不是求最佳算法吧,是考吧? : 掉坑里了,不过这坑有点意思哈
|
c********l 发帖数: 8138 | 18 assumption:
1 ID这一列都是已经排序好的?
2 Date这一列都是在ID排序的基础上排序好的?
3 “任意365天”区间应该改为“随意365区间”?
换句话对于每个ID只要找到一个365天就算完成目标了。
额。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有以下格式的数据,总共在两千万行左右。请输出一张ID清单。 : 要求是清单里的每一个ID必须在任意365天的连续区间里累计完成$100或以上的交易额。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : 2 7/9/2007 $40 : 2 8/9/2007 $80 : 2 10/20/2009 $20 : 2 11/20/2010 $100
|
s******g 发帖数: 466 | 19 跳年是可以的。只要累计$100+在一个连续365天的moving window里发生就算达标一次。
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 等等,ID 2 2008 年是白板,不是已经 rule out 了吗?
|
s******g 发帖数: 466 | 20 Yes.你可以随意排列。
【在 c********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : assumption: : 1 ID这一列都是已经排序好的? : 2 Date这一列都是在ID排序的基础上排序好的? : 3 “任意365天”区间应该改为“随意365区间”? : 换句话对于每个ID只要找到一个365天就算完成目标了。 : : 额。
|
|
|
c********l 发帖数: 8138 | 21 我也想到sliding window,
对于每个ID,按照时间升序
先读最早的记录,接着开始建立window,window的边界在最早的消费+365天截止
求sum,如果满足100,返回
如果不满足,窗口左边从第2条记录开始,右边相应扩大,求sum
sum如果满足100,返回
.....
也就是一个O(N)
貌似此题不难啊
次。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 跳年是可以的。只要累计$100+在一个连续365天的moving window里发生就算达标一次。
|
n*****t 发帖数: 22014 | 22 本质上是一个 2 维表
id day1 day2 ....day35 day730
1 $40 0 ... $20 ...
2 0 $20 ...
逐行计算,一个 365 day 的窗口一点点向右移,当然每次计算不用重新加,+new -
expire 就可以了。
这个是暴力解,更优的没想到。假如简化编程,当然可以用 DB, select distinct day
into memory_table,然后按照 day 统计每个 ID 过去 365 天的 sum,当然这个计算
肯定不高效。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是坑。当然考试啥的是开个玩笑。 : 题目源自实际工作需要,网上是不会有的。不过假如招人,我们可能出此题哦。
|
s******g 发帖数: 466 | 23 每一个窗口可能覆盖从一个到理论上millions个Records. |
n*****t 发帖数: 22014 | 24 按照 ID 来的话就最多只有 365 个 recs 了,而且最早的是要一笔笔加,365 天之后
就只有一加一减了
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每一个窗口可能覆盖从一个到理论上millions个Records.
|
s******g 发帖数: 466 | 25 不一定哦。大户嘛,某人某天可以进上百个Records。想想看Amazon customers.
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 按照 ID 来的话就最多只有 365 个 recs 了,而且最早的是要一笔笔加,365 天之后 : 就只有一加一减了
|
n*****t 发帖数: 22014 | 26 每天上百个 rec 都累计在同一天里,不用增加 rec,sort 好的话,就是在 list->end
上操作,不用遍历 list
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不一定哦。大户嘛,某人某天可以进上百个Records。想想看Amazon customers.
|
n*****t 发帖数: 22014 | 27 可以预先 sort 的话,内存就少很多了
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Yes.你可以随意排列。
|
s******g 发帖数: 466 | 28 OK,加入给你的表pre-sorted,你估计一下暴力解需要多少时间.
在此基础上,时间减半,工资翻倍。 |
n*****t 发帖数: 22014 | 29 看这意思你是有更优解哈
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : OK,加入给你的表pre-sorted,你估计一下暴力解需要多少时间. : 在此基础上,时间减半,工资翻倍。
|
w****w 发帖数: 521 | 30 不让贴sql code?
s elect * f rom
(
s elect a.ID,a.Date,
(
s elect sum(b.Amount)
f rom Transactions b
w here a.ID=b.ID and a.Date<=b.Date
and datediff(day,a.Date,b.Date)<365
) as OneYearTotal
f rom Transactions a
)
w here OneYearTotal>100 |
|
|
s******g 发帖数: 466 | 31 假如上午写出并开始run code,在下班前(共4小时内)出正确结果的都算通过。电脑
和数据的conditions前面已给出。
在此基础上,优胜者耗时最短。 |
n*****t 发帖数: 22014 | 32 20M 记录,每条记录大概 30 byte,读进 memory 是 600M,DISK IO 算普通硬盘 30M/
s,20 seconds。每行 record parse 的时间几乎可以忽略了,最多几分钟。
计算的话,每个记录最多需要加一次减一次,这个也就是几分钟。
正常最多半小时干完活了吧?
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假如上午写出并开始run code,在下班前(共4小时内)出正确结果的都算通过。电脑 : 和数据的conditions前面已给出。 : 在此基础上,优胜者耗时最短。
|
c******o 发帖数: 1277 | 33 不是一个sliding window么?
两个pointer, 一个list
哦, 我这个需要排过序。 就是O(n)
要是没排序,worst case就很不经济了,似乎没排过序,先排序再找更好。 |
w****w 发帖数: 521 | 34 数据如果已经在数据库里,5分钟code,每个id平均transaction数不是很高的话,5分
钟run应该够了。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假如上午写出并开始run code,在下班前(共4小时内)出正确结果的都算通过。电脑 : 和数据的conditions前面已给出。 : 在此基础上,优胜者耗时最短。
|
s******g 发帖数: 466 | 35 不知道,我看见有run几天几夜的,所谓的暴力解,后来结果对不对都不重要了。
对了,也可以用主流统计软件解。一题多解更佳。不拘一格。
30M/
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 20M 记录,每条记录大概 30 byte,读进 memory 是 600M,DISK IO 算普通硬盘 30M/ : s,20 seconds。每行 record parse 的时间几乎可以忽略了,最多几分钟。 : 计算的话,每个记录最多需要加一次减一次,这个也就是几分钟。 : 正常最多半小时干完活了吧?
|
l*********s 发帖数: 5409 | 36 you kidding, I used to do lots of data preparation in SAS, over 100 G
mortgage data, that load does not need >1 day on single PC.
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道,我看见有run几天几夜的,所谓的暴力解,后来结果对不对都不重要了。 : 对了,也可以用主流统计软件解。一题多解更佳。不拘一格。 : : 30M/
|
s******g 发帖数: 466 | 37 Can you write down the SAS code?
【在 l*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : you kidding, I used to do lots of data preparation in SAS, over 100 G : mortgage data, that load does not need >1 day on single PC.
|
p***o 发帖数: 1252 | 38 No, you can never underestimate how bad one could be in algorithms ...
I believe sorting will take more time than scanning with a sliding window,.
【在 l*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : you kidding, I used to do lots of data preparation in SAS, over 100 G : mortgage data, that load does not need >1 day on single PC.
|
n*****t 发帖数: 22014 | 39 sorting 能做当然更好,不做的话只是内存用比较多,其他问题不大,毕竟只是同一个
ID 的 list 做 sort,不会有太多
当然,如果 2KW 都是同一个 ID 的,稍微慢点,不过也就是 O(logN)
【在 p***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : No, you can never underestimate how bad one could be in algorithms ... : I believe sorting will take more time than scanning with a sliding window,.
|
b*******s 发帖数: 5216 | 40 不难
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有点意思,性能肯定要用 C,暴力解当然也简单,怎么弄个好的算法让俺琢磨琢磨
|
|
|
l*********s 发帖数: 5409 | 41 it is, but the extra labor often not worthy.
【在 p***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : No, you can never underestimate how bad one could be in algorithms ... : I believe sorting will take more time than scanning with a sliding window,.
|
l*********s 发帖数: 5409 | 42 nay, I have not used SAS for years, but google "SAS hash table", this is key
to many speed-up techniques in SAS.
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Can you write down the SAS code?
|
w****w 发帖数: 521 | 43 把我上面的sql翻成python:
#!/usr/bin/env python
import sys
from datetime import datetime, date
ids={}
fmt="%m/%d/%Y"
with open(sys.argv[1],"r") as fi:
fi.readline()
for x in fi.readlines():
v=x.rstrip("\n").split("\t")
if v[0] not in ids:
ids[v[0]]=[]
dat=datetime.strptime(v[1],fmt)
ent=[dat,float(v[2]),float(v[2])]
for y in ids[v[0]]:
dif=ent[0]-y[0]
if dif.days>=0 and dif.days<=365:
y[2]+=ent[1]
elif dif.days<=0 and dif.days>=-365:
ent[2]+=y[1]
ids[v[0]].append(ent)
for x in ids:
for y in ids[x]:
if y[2]>=100:
print x,y[0]
|
s******g 发帖数: 466 | 44 首先感谢webbew(未必)提供的SQL。解法符合简单暴力美学。试了一下速度,想作为
benchmark.
我找了一台周围能找到的最强劲的Windows 7 64bit workstation. 上面正好有一个
53million records data, presorted.
一个多小时过去了,原始数据还没有处理完200 records。 |
w***g 发帖数: 5958 | 45 才几百兆数据,有那么难吗?
额。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有以下格式的数据,总共在两千万行左右。请输出一张ID清单。 : 要求是清单里的每一个ID必须在任意365天的连续区间里累计完成$100或以上的交易额。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : 2 7/9/2007 $40 : 2 8/9/2007 $80 : 2 10/20/2009 $20 : 2 11/20/2010 $100
|
n*****t 发帖数: 22014 | 46 SQL 嵌套一般很慢,而且好像写得有问题,感觉应该有 group by。鉴于任意 365 这个
条件,SQL 不太适合,如果一定要做,先要 select id, date,然后在这个基础上 sum。
以上都是直觉。最高效的暴力解应该就是 C 了,不会比汇编慢多少。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 首先感谢webbew(未必)提供的SQL。解法符合简单暴力美学。试了一下速度,想作为 : benchmark. : 我找了一台周围能找到的最强劲的Windows 7 64bit workstation. 上面正好有一个 : 53million records data, presorted. : 一个多小时过去了,原始数据还没有处理完200 records。
|
c***d 发帖数: 996 | 47 感觉是动态规划。 在每个id, 先找单日最高交易额, 再找二相邻最高交易额, 再找
三相邻最高交易额。返回条件是365日和100块钱。
额。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有以下格式的数据,总共在两千万行左右。请输出一张ID清单。 : 要求是清单里的每一个ID必须在任意365天的连续区间里累计完成$100或以上的交易额。 : ID Date Transaction_Amount : 1 1/2/2011 $30 : 1 4/5/2012 $50 : 1 9/5/2013 $50 : 2 7/9/2007 $40 : 2 8/9/2007 $80 : 2 10/20/2009 $20 : 2 11/20/2010 $100
|
w****w 发帖数: 521 | 48 还没跑出来?ID column做了index没有?
能不能把文件放到百度云上?
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 首先感谢webbew(未必)提供的SQL。解法符合简单暴力美学。试了一下速度,想作为 : benchmark. : 我找了一台周围能找到的最强劲的Windows 7 64bit workstation. 上面正好有一个 : 53million records data, presorted. : 一个多小时过去了,原始数据还没有处理完200 records。
|
B***i 发帖数: 724 | 49 上古的算法书里, 有种数据结构叫 十字链表。不过在江湖上, 似乎已经销声匿迹了 |
n*****t 发帖数: 22014 | 50 以日期链接似乎不太必要,楼主的 input 可以 presort,两个指针对指定 ID 的 list
做运算即可,此乃少林功夫。
不知是否还有人精通关节小擒拿否?
【在 B***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上古的算法书里, 有种数据结构叫 十字链表。不过在江湖上, 似乎已经销声匿迹了
|
|
|
s******g 发帖数: 466 | 51 As an update, 14小时过去了,大概只有900行原始数据被处理完。
No index。
【在 w****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还没跑出来?ID column做了index没有? : 能不能把文件放到百度云上?
|
w****w 发帖数: 521 | 52 下面程序产生22m transactions,8分钟。
import sys
from datetime import date,timedelta
from random import randint
ID_NUM=100000
DAY_NUM=3650
StartDate=date(2004,1,1)
fmt="%m/%d/%Y"
with open(sys.argv[1],"w") as fo:
fo.write("IDtDatetAmountn")
for i in xrange(22000000):
RandonId=randint(1,ID_NUM)
RandonDate=StartDate+ timedelta(days=randint(0,DAY_NUM))
RandonAmt=5*randint(1,20)
fo.write("%dt%st%dn" % (RandonId,RandonDate.strftime(fmt),RandonAmt))
下面程序产生id,80分钟
import sys
from datetime import datetime, date
ids={}
fmt="%m/%d/%Y"
with open(sys.argv[1],"r") as fi:
fi.readline()
for x in fi.readlines():
v=x.rstrip("n").split("t")
if v[0] not in ids:
ids[v[0]]=[]
dat=datetime.strptime(v[1],fmt)
ent=[dat,float(v[2]),float(v[2])]
for y in ids[v[0]]:
dif=ent[0]-y[0]
if dif.days>=0 and dif.days<=365:
y[2]+=ent[1]
elif dif.days<=0 and dif.days>=-365:
ent[2]+=y[1]
ids[v[0]].append(ent)
with open(sys.argv[2],"w") as fo:
fo.write("IDtDaten")
for x in ids:
for y in ids[x]:
if y[2]>=2000:
fo.write("%st%sn" % (x,y[0].strftime(fmt)))
Import到sql server加id index,7分钟。
下面SQL,3分20秒开始出结果,6分20秒出光。
select * from
(
select a.Tid,a.TDate,
(
select sum(b.Amount)
from Trans_Test b
where a.Tid=b.Tid and a.TDate<=b.TDate
and datediff(day,a.TDate,b.TDate)<365
) as OneYearTotal
from Trans_Test a
) as c
where c.OneYearTotal>2000
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : As an update, 14小时过去了,大概只有900行原始数据被处理完。 : No index。
|
w****w 发帖数: 521 | 53 python 2.6/Centos,机器是9年新的。 |
n*****t 发帖数: 22014 | 54 哥, no index 啊 。。。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : As an update, 14小时过去了,大概只有900行原始数据被处理完。 : No index。
|
s******g 发帖数: 466 | 55 我在database上直接run了一遍,速度与你说的相符。谢谢。
之前我是在另一个软件里里run SQL,没想到差别那么大。 |
w****w 发帖数: 521 | 56 这就是FP的好处,过几年DB Engine更好了,再多几个核,这query一秒钟就出来了。典
型的可高并行的问题。
【在 s******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我在database上直接run了一遍,速度与你说的相符。谢谢。 : 之前我是在另一个软件里里run SQL,没想到差别那么大。
|