算法 请问如何高效率的计算最长连续子序列?

debugger · 2014年06月18日 · 最后由 jaxihe 回复于 2014年07月30日 · 9090 次阅读

假设数据库中有:

id    name         created_at
1     zhangsan     2014-01-01
2     zhangsan     2014-01-02
4     zhangsan     2014-02-01
5     zhangsan     2014-02-02
6     zhangsan     2014-02-03
7     zhangsan     2014-02-04
8     zhangsan     2014-03-01
9     zhangsan     2014-03-02
10    zhangsan     2014-03-03

其中 created_at 连续的部分是:

  • 1. 2014-01-01 到 2014-01-02,跨越 2 个日期
  • 2. 2014-02-01 到 2014-02-04,跨越 4 个日期
  • 3. 2014-03-01 到 2014-03-03,跨域 3 个日期

如何高效率的找出 2 的数据记录数和跨域日期数,假设数据库在 2 千万级别。

1 楼 已删除

擦... 这个除了遍历一遍恐怕没有什么捷径吧...

@blacktulip 假设不考虑数据库了,我的数据都在内存中了呢?

看不太懂,能否具体一点输出结果?又或者说明一下,是为了统计什么样的数据?例如:统计用户最长的连续登录天数?

@hz_qiuyuanxin 可以理解成“统计用户最长的连续登录天数”,但是不仅仅是要这个总和,把连续的每个记录数都拿到,谢谢。

#5 楼 @debugger 我现在做的项目也是这个需求,但是不是通过直接查这数据处理的,而是一个用户有多条登录统计的记录,表结构如下

# table user_endurance_records
  Column   |  Type   |                              Modifiers
------------+---------+---------------------------------------------------------------------
 id         | integer | not null default nextval('user_endurance_records_id_seq'::regclass)
 user_id    | integer |
 last_login | date    |
 amount     | integer | default 0

每天都会统计一次,其记录更新逻辑如下:

if 用户昨天有登录
  if 此用户存在 last_login 等于前天的记录
     user_endurance_records  amount 加上 1last_login 更新为昨天
  else
    新建一条 user_endurance_records
  end
end  

这样,查询某个用户的登录记录数据大概是:

  id   | user_id | last_login | amount
-------+---------+------------+--------
 51563 |      32 | 2014-05-22 |      5
 57222 |      32 | 2014-05-30 |      7
 64819 |      32 | 2014-06-01 |      1
 66525 |      32 | 2014-06-03 |      1
 69257 |      32 | 2014-06-08 |      3
 72849 |      32 | 2014-06-16 |      7

如果不那么干,那么你可能自己要写个聚合函数!以实现你要的这种比较特殊的逻辑。

数据记录数和跨越日期数是一样的吧…………

SELECT count(*)
FROM (
    SELECT *, (created_at - id) as delta  FROM T
) x
GROUP BY delta

最后再找 max 就好了……

#6 楼 @hz_qiuyuanxin 谢谢 support,你的这个数据是未生成的,可以在 after_create 或者数据库触发器处理,但是如果记录已经有 N 条存在了,可能需要 background jobs 来跑了。

#7 楼 @Kabie 谢谢,但是没看懂你的意思,另外上千万的数据记录是不能 count 的,锁表后会卡住,另外我可能用的不是 sql-based 数据库。这儿主要是求个算法,不一定要用数据库本身的方法解决 😄

这个从逻辑上来说也不难。试一下吧。

首先建一个新 model, ContiniousLogin, 对应表 continious_logins。或者放在 yml 里面

然后做一个 rake task 或者 job

User.find_each do |user|
  last_login_day = nil
  days_count      = 0

  Login.find_each(name: user.name) do |login|
    current_day = created_at.to_date
    last_login_day ||= current_day
    prev_day = current_day.prev_day

    if prev_day == last_login_day
      last_login_date = current_date
      days_count += 1
    elsif prev_day > last_login_day && days_count > 0
      ContiniousLogin.create!(name: name, last_login_day: last_login_day, days_count: days_count)
      last_login_day = nil
      days_count      = 0
    end
  end
end

逻辑大致如此,代码只做参考 :)

find_each 是每一千个一批次的,也可以调整批次大小,所以数据多少应该影响不大。当然如果时间太长可能就要另说了。

做实验时可以不用新建 model,用一个 yml 代替也行。总之有个 io 来存记录就好了。

#9 楼 @debugger 先全部取到内存中,然后按用户分组弄吧,2000 万数据其实就几百兆而已

#10 楼 @billy 是的,逻辑上比较简单的,谢谢你提供的代码参考。 #11 楼 @luikore 目前打算按顺序把日期的两两差值算出来,保存在库中,然后再用算法处理,try-try。

#9 楼 @debugger 就是说……

如果日期和 ID 都是严格递增的…… 那么日期和 ID 的差值相同的就应该是连续的了……对这个差值分组就行了……

这种需求属于常用统计,翻开我的 sql 小本本,找到一句 sql 查询就可以搞定:

select a.name, a.created_at as start, min(c.created_at) as end, (c.created_at - a.created_at) as counter
from visits      as a
left join visits as b on a.name = b.name and a.created_at = adddate(b.created_at, 1)
left join visits as c on a.name = c.name and a.created_at <= c.created_at
left join visits as d on c.name = d.name and c.created_at = adddate(d.created_at, -1)
where b.created_at is null and c.created_at is not null and d.created_at is null
group by a.name, a.created_at

输出结果

+------+------------+------------+---------+
| name | start      | end        | counter |
+------+------------+------------+---------+
| ls   | 2014-01-01 | 2014-01-02 |       1 |
| ls   | 2014-02-01 | 2014-02-05 |       4 |
| ls   | 2014-03-02 | 2014-03-03 |       1 |
| zs   | 2014-01-01 | 2014-01-02 |       1 |
| zs   | 2014-02-01 | 2014-02-04 |       3 |
| zs   | 2014-03-01 | 2014-03-03 |       2 |
+------+------------+------------+---------+

#15 楼 @quakewang 非常感谢,没用 sql 数据库,想来导入到 sql 数据库处理也不错。

#13 楼 @jaxihe 你这个是 LCS,不一样的,lz 这种清苦 O(n) 就可以了。

#17 楼 @rasefon 麻。。看成 LIS 了,审题不仔细,抱歉。。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号