也许这不是一个完美的地方来问这样的问题。
场景是我有一个大约10000000行的大日志文件。
每一行代表一个用户的活动。
大约有20种活动。
我想用这些数据生成一个树,它的边代表一种活动(和权重),而节点代表一种状态。
例如,假设我有这样的日志:
(建议日期排序正确)
user_id| activity
u1 | a1
u1 | a2
u2 | a1
u3 | a2
u3 | a3
u4 | a1
u4 | a2
u4 | a3
然后我希望得到这样的东西:
我试图保存每个状态转发,以及一个状态转发执行了多少次,如下所示。
current_state | verb | next_state | weight
0 | a1 | 1 | 3
1 | a2 | 2 | 2
0 | a2 | 3 | 1
3 | a3 | 4 | 1
2 | a3 | 5 | 1
但是状态太多了,即使我使用缓存机制将所有频繁的状态转发保存在一个哈希中,并且只有当一个状态转发从该哈希中排队出来时,我才会坚持,它仍然加载得太慢。
所以也许我需要一个算法在树的构建过程中进行修剪。
你知道怎么解决这个问题吗?
欢迎使用任何工具或软件包。
最佳答案
至少有两种方法可以做到这一点。
首先,我假设您正在保存用户及其当前状态的列表(可能是字典)因此,当您看到用户2和动词a3的日志条目时,您可以在字典中查找用户2,查看他当前处于状态3,并将他推到状态4(或其他)。
你要计算的是那些状态转换。
最简单的方法是对每个日志条目进行读取,将条目写入文件(或将其保存在列表中)。条目有(current_state, verb, next_state)
。完成所有日志条目后,加载该文件,并按current_state
和next_state
对其进行排序。你会得到的是:
state1,state2
state1,state2
...
state1,state3
state1,state3
...
您可以遍历并计数重复的行,这将告诉您每个状态转换进行了多少次。
我无法想象穿越1000万条线路会花费很长时间。如果我假设你的行有160个字符长,那还不到2GB因此,您应该能够在一分钟内读取文件,并且处理不会花费很长时间。
另一种方法是保存一个索引为
(current_state,next_state)
的字典,并在阅读每条记录时更新它它将比我描述的map/reduce技术更快,但是需要更多的内存。