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 的大作中提到】
: 有以下格式的数据，总共在两千万行左右。请输出一张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 的大作中提到】
: SQL? C? JAVA?
|
n*****t
发帖数: 22014 | 4 C 太简单了，一行行读，每个 id 用一个结构记录：start, end, sum,
end -start > 0 print id, sum
【在 s******g 的大作中提到】
: 任何主流语言都可。关键是思路，电脑是一台主流台式机。希望是处理时间越短越好。
|
n*****t
发帖数: 22014 | 5 有点歧义，比如一个 id 用了 2 年，这 2 年里我随便取个区间都要保证大于 100 刀
吗？
额。
【在 s******g 的大作中提到】
: 有以下格式的数据，总共在两千万行左右。请输出一张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 的大作中提到】
: 有点歧义，比如一个 id 用了 2 年，这 2 年里我随便取个区间都要保证大于 100 刀
: 吗？
:
: 额。
|
n*****t
发帖数: 22014 | 7 有点意思，性能肯定要用 C，暴力解当然也简单，怎么弄个好的算法让俺琢磨琢磨
【在 s******g 的大作中提到】
: 对，任意启始的365天的连续区间。
|
s******g
发帖数: 466 | 8 输出清单最好再给出每个ID的达标次数。
根据题目的定义，在该例中 -
ID 1 达标次数 0
ID 2 达标次数 2
ID 3 达标次数 1
【在 s******g 的大作中提到】
: 对，任意启始的365天的连续区间。
|
n*****t
发帖数: 22014 | 9 最简单的就是每个 ID 用个 list 记录付费和前 365 天的总计，每增加一笔计算这个
list，不达标的就扔出去了，以后再也不用费劲了。从最早一天开始，365 天之后这个
array 就不断减小。暂时没想出更优的。
你这个达标次数我还没理解
【在 s******g 的大作中提到】
: 输出清单最好再给出每个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 的大作中提到】
: 最简单的就是每个 ID 用个 list 记录付费和前 365 天的总计，每增加一笔计算这个
: list，不达标的就扔出去了，以后再也不用费劲了。从最早一天开始，365 天之后这个
: array 就不断减小。暂时没想出更优的。
: 你这个达标次数我还没理解
|
|
|
s******g
发帖数: 466 | 11 另外每个ID的records最小1个，最大上不封顶。请注意。
【在 s******g 的大作中提到】
: 给点提示。
: 以下>>表示这连续的两个记录累计达标。
: >>>表示该单一记录自身就达标。
: 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 的大作中提到】
: 给点提示。
: 以下>>表示这连续的两个记录累计达标。
: >>>表示该单一记录自身就达标。
: 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 的大作中提到】
: 我看了你的实例，但没明白你的定义。比如 ID 2 REC 3 为啥不算？
: 当然，暴力解，无非就是在这个 list 里最后计算一下，怎么定义都行，关键是基础的
: 算法怎么优化 。。。。
|
s******g
发帖数: 466 | |
n*****t
发帖数: 22014 | 15 等等，ID 2 2008 年是白板，不是已经 rule out 了吗？
【在 s******g 的大作中提到】
: ID2 Record 3 = $20，它离最近的其他Records都超过365天了。
|
n*****t
发帖数: 22014 | 16 艾玛，你这标题不是求最佳算法吧，是考吧？
掉坑里了，不过这坑有点意思哈
【在 s******g 的大作中提到】
: 考的就是解法。老年SDE的入门测试，呵呵。
|
s******g
发帖数: 466 | 17 不是坑。当然考试啥的是开个玩笑。
题目源自实际工作需要，网上是不会有的。不过假如招人，我们可能出此题哦。
【在 n*****t 的大作中提到】
: 艾玛，你这标题不是求最佳算法吧，是考吧？
: 掉坑里了，不过这坑有点意思哈
|
c********l
发帖数: 8138 | 18 assumption:
1 ID这一列都是已经排序好的？
2 Date这一列都是在ID排序的基础上排序好的？
3 “任意365天”区间应该改为“随意365区间”？
换句话对于每个ID只要找到一个365天就算完成目标了。
额。
【在 s******g 的大作中提到】
: 有以下格式的数据，总共在两千万行左右。请输出一张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 的大作中提到】
: 等等，ID 2 2008 年是白板，不是已经 rule out 了吗？
|
s******g
发帖数: 466 | 20 Yes.你可以随意排列。
【在 c********l 的大作中提到】
: 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 的大作中提到】
: 跳年是可以的。只要累计$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 的大作中提到】
: 不是坑。当然考试啥的是开个玩笑。
: 题目源自实际工作需要，网上是不会有的。不过假如招人，我们可能出此题哦。
|
s******g
发帖数: 466 | 23 每一个窗口可能覆盖从一个到理论上millions个Records. |
n*****t
发帖数: 22014 | 24 按照 ID 来的话就最多只有 365 个 recs 了，而且最早的是要一笔笔加，365 天之后
就只有一加一减了
【在 s******g 的大作中提到】
: 每一个窗口可能覆盖从一个到理论上millions个Records.
|
s******g
发帖数: 466 | 25 不一定哦。大户嘛，某人某天可以进上百个Records。想想看Amazon customers.
【在 n*****t 的大作中提到】
: 按照 ID 来的话就最多只有 365 个 recs 了，而且最早的是要一笔笔加，365 天之后
: 就只有一加一减了
|
n*****t
发帖数: 22014 | 26 每天上百个 rec 都累计在同一天里，不用增加 rec，sort 好的话，就是在 list->end
上操作，不用遍历 list
【在 s******g 的大作中提到】
: 不一定哦。大户嘛，某人某天可以进上百个Records。想想看Amazon customers.
|
n*****t
发帖数: 22014 | 27 可以预先 sort 的话，内存就少很多了
【在 s******g 的大作中提到】
: Yes.你可以随意排列。
|
s******g
发帖数: 466 | 28 OK，加入给你的表pre-sorted，你估计一下暴力解需要多少时间.
在此基础上，时间减半，工资翻倍。 |
n*****t
发帖数: 22014 | 29 看这意思你是有更优解哈
【在 s******g 的大作中提到】
: 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 的大作中提到】
: 假如上午写出并开始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 的大作中提到】
: 假如上午写出并开始run code，在下班前（共4小时内）出正确结果的都算通过。电脑
: 和数据的conditions前面已给出。
: 在此基础上，优胜者耗时最短。
|
s******g
发帖数: 466 | 35 不知道，我看见有run几天几夜的，所谓的暴力解，后来结果对不对都不重要了。
对了，也可以用主流统计软件解。一题多解更佳。不拘一格。
30M/
【在 n*****t 的大作中提到】
: 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 的大作中提到】
: 不知道，我看见有run几天几夜的，所谓的暴力解，后来结果对不对都不重要了。
: 对了，也可以用主流统计软件解。一题多解更佳。不拘一格。
:
: 30M/
|
s******g
发帖数: 466 | 37 Can you write down the SAS code?
【在 l*********s 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 有点意思，性能肯定要用 C，暴力解当然也简单，怎么弄个好的算法让俺琢磨琢磨
|
|
|
l*********s
发帖数: 5409 | 41 it is, but the extra labor often not worthy.
【在 p***o 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 有以下格式的数据，总共在两千万行左右。请输出一张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 的大作中提到】
: 首先感谢webbew(未必)提供的SQL。解法符合简单暴力美学。试了一下速度，想作为
: benchmark.
: 我找了一台周围能找到的最强劲的Windows 7 64bit workstation. 上面正好有一个
: 53million records data, presorted.
: 一个多小时过去了，原始数据还没有处理完200 records。
|
c***d
发帖数: 996 | 47 感觉是动态规划。 在每个id， 先找单日最高交易额， 再找二相邻最高交易额， 再找
三相邻最高交易额。返回条件是365日和100块钱。
额。
【在 s******g 的大作中提到】
: 有以下格式的数据，总共在两千万行左右。请输出一张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 的大作中提到】
: 首先感谢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 的大作中提到】
: 上古的算法书里， 有种数据结构叫 十字链表。不过在江湖上， 似乎已经销声匿迹了
|
|
|
s******g
发帖数: 466 | 51 As an update, 14小时过去了，大概只有900行原始数据被处理完。
No index。
【在 w****w 的大作中提到】
: 还没跑出来？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 的大作中提到】
: As an update, 14小时过去了，大概只有900行原始数据被处理完。
: No index。
|
w****w
发帖数: 521 | 53 python 2.6/Centos,机器是9年新的。 |
n*****t
发帖数: 22014 | 54 哥， no index 啊 。。。
【在 s******g 的大作中提到】
: 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 的大作中提到】
: 我在database上直接run了一遍，速度与你说的相符。谢谢。
: 之前我是在另一个软件里里run SQL，没想到差别那么大。
|
