求前15分钟内出现了多少次代码，stata能做最好。

现在有两列数据，一列是时间，精确到毫秒，一列是“四个字母的代码”。  我现在想求：对于每一分钟来说，从这一分钟开始算起，前十五分钟内出现了多少个不同的代码。这是一道STATA的题目，但是我对于stata不熟悉，准备用c++做。

eg：
time                 data
00:00:00.001  abcd    ----第一组数据开始 00:00:00:000
00:00:00.001  asde
00:00:00.002  egsa...
00:00:59.999 ksag      ----第二组数据00:01:00:000
00:01:00.000  abcd
..
00:14:59.999  swfr
00:14:59.999  cwas   ----第一组数据结束00:14:59.999
00:15:00.00 sdfa
00:15:00.00 sdfg
...
00:15.59.999 jhde
00:15:59.999 seqa    ---第二组数据结束 00:15:59.999
00:16:00.00 swet
对于上面的数据，从十五分钟开始，应该求00:00:00:000到00:14:59.999之间出现了多少个不同的代码，（代码会重复出现）；然后到16分钟的时候，是求00:01:00:000到00:15:59.999之间出现了多少个不同代码。每分钟的数据量在1000个左右。十五分钟就是15000个。

我现在想的是维护一个list，读取15分钟的数据，分成第一分钟，中间十三分钟，最后一分钟三段：
1每次移动一分钟
2然后删除第一分钟，
3中间十三分钟的第一分钟变成第一分钟，
4原来的最后一分钟变成中间十三分钟的第十三分钟
5读取新一分钟变成最后一分钟

然后进行计算，我目测这个算法是O（N）的，每一分钟的数据都是跟十五分钟那个list里面的数据相比较（十五分钟内的数据应在2w以下），然后迭代N次，就是O（20000）*N。
不知道这个时间复杂度对不对，数据总量大于一千万，要是O（N2）的话就哭了。。。
暂时想用c++，不知道大家有什么建议，换语言也行。

全部扫描一遍输入(O(n))，标记出重复的code，每分钟的数据个数。如果有m个重复，不做cache的话每次qury的话复杂度应该是O(m)

坑王 发表于 2013-7-6 00:02
全部扫描一遍输入(O(n))，标记出重复的code，每分钟的数据个数。如果有m个重复，不做cache的话每次qury的话 ...

全部扫描一遍的意思是扫15分钟的，把这15分钟重复的code和每分钟数据个数标记出来；
还是扫所有的数据，把这每分钟重复的code和每分钟数据个数标记出来；

NiGuessYiXia 发表于 2013-7-6 00:07
全部扫描一遍的意思是扫15分钟的，把这15分钟重复的code和每分钟数据个数标记出来；
还是扫所有的数据， ...

所有的数据

我们先考虑一个时间点只有一个代码的问题，对于位置（时间点)i上的单词x，记录它下一次出现的位置next(形成一条链，同时记录这条链的第一个位置head[x]),从后往前扫描一遍即可
初始时，对于每个head[x]对应的位置的值加1
现在我们有M组查询[l,r]（按l从小到大排序)，l和r为时间点映射到数组下标后的值
维护两个指针a和b，a表示从左开始扫描到时间点的哪个位置，b表示查询处理到哪个位置
{
然后从左往右开始扫描a，如果a大于等于b对应的查询的l，那么我们数一下从最左边到b对应的r之间共有几个1,即为询问b对应的答案，b加1
然后，将a位置上的值减1，讲next[a]上的值加1，a加1
}
一直循环下去，直到处理完所有询问
对于动态查询一段区间内多少个1，即区间和的问题，可以用数据结构在log(N)的时间内完成(比如树状数组，binary indexed tree)，所以最后复杂度是O(Nlog(N))的,N是时间点映射后，数组的长度

对于一个时间点有多个代码的问题，我们只要把这个时间点离散成多个，在下面处理的过程中稍加修改应该就行了

希望没有讲错，好久没练习了

1guangnian 发表于 2013-7-6 08:26
我们先考虑一个时间点只有一个代码的问题，对于位置（时间点)i上的单词x，记录它下一次出现的位置next(形成 ...

谢谢回答！！！

有点不明白的：“现在我们有M组查询[l,r]（按l从小到大排序)，l和r为时间点映射到数组下标后的值”

比如我现在是第一次迭代，从00:00:00.000-00:14:59.999
初始是a应该是指向00:00:00.000，b指向0:14:59.999，对吗？
那么l和r对应什么呢？

NiGuessYiXia 发表于 2013-7-6 22:35
谢谢回答！！！

有点不明白的：“现在我们有M组查询[l,r]（按l从小到大排序)，l和r为时间点映射到数组 ...

初始时，a指向00:00:00.000映射后的下标，a需要遍历时刻映射后的数组，映射是按照时间从小到大的
b指向l最小的一组询问[l,r]:l是00:00:00.000映射后的数组下标，r是00:14:59.999映射后的数组下标
b需要遍历所有的询问

1guangnian 发表于 2013-7-6 23:04
初始时，a指向00:00:00.000映射后的下标，a需要遍历时刻映射后的数组，映射是按照时间从小到大的
b指向l ...

大致上明白了，我先写写看，不懂再问你。实在是太麻烦你了，谢谢！