对N个D维数据，给定P个维度的取值，求出现次数解决思路

对N个D维数据，给定P个维度的取值，求出现次数
有N个D维的数据，每一维的取值范围di已知，且都是一个较小的正整数。
维度上的取值用从0到di-1的整数表示。
数据范围：
N在50万左右，D<=20，个别di<128，大部分di<15。
应用1：
给定P个维度上的取值，要求输出满足这个条件的记录的数量。
应用2：
给出P个维度，给定其中前P-1个维度的取值（0<=P<=D）,要求输出第P维取各个值时满足条件的记录的数量。

请问应该用什么算法比较好？

首先对输入预处理是肯定的，合并完全相同的记录为它的出现次数，应该用怎样的结构来存储？ 算法 索引 预处理 数据结构
[解决办法]
由于每一个维度的上下限都比较小，可以按照维度进行桶排序
[解决办法]
我感觉你这需求跟数据库查表这么像呢，按照数据库那么整就行，无非就是建索引可以一个或者多个索引，插入删除都维护这个索引保证下次查询的效率。
[解决办法]
话说B树可否
[解决办法]

引用:

引用:换成数据库语言的话，是不是第一个就是count(*) where Dim1=... and Dim2=... and ...，第二个是前一个然后多加个group by DimP？
嗯 用sql是这样的
我们用程序怎么高效实现呢？

SQL的做法是单次全表扫描
[解决办法]

引用:

引用:引用:引用:换成数据库语言的话，是不是第一个就是count(*) where Dim1=... and Dim2=... and ...，第二个是前一个然后多加个group by DimP？
嗯 用sql是这样的
我们用程序怎么高效实现呢？……

这个再要优化那就只能针对数据特点了。
[解决办法]

引用:

引用:
由于每一个维度的上下限都比较小，可以按照维度进行桶排序
这只能做到每一个列有序 怎么做到列集合的有序呢

个人认为没有必要做到列集合的有序--除非你能确认每次都查相同的列集合。
我觉得可以按每一列排序后，可以在需要检索的列集合中找到某一个特定列k，使得满足k条件的点最少，然后在最少的列中进行二次查找。

查看更多 下一篇