出现次数统计的算法

allegrox

数据源是文本文件，每行一个数值，有重复，行数为千万~亿级
要求统计所有出现的数值的重复次数
结果按反序输出到一文本文件
感觉时间复杂度和不重复的数值总量相关，如何平衡？

求最佳数据结构和算法
纯c，不会c++

bruceteen

每行一个数值 ------ 数值有多少种？比如 int16_t  是 65536 种
有重复 ------ 不重复的数值“大约”有多少种？
结果按反序 ------ 是数值的反序，还是重复次数的反序？

allegrox

bruceteen 发表于 2012-06-23 22:39
每行一个数值 ------ 数值有多少种？比如 int16_t  是 65536 种

int32_t

bruceteen 发表于 2012-06-23 22:39
有重复 ------ 不重复的数值“大约”有多少 ...

十万到百万

bruceteen 发表于 2012-06-23 22:39 结果按反序 ------ 是数值的反序，还是重复次数的反序？

重复次数的反序

_Rayx

回复 1# allegrox


    三个解决办法就能搞定：
    1.  数值大，但是不同的数的个数不多，可以用map, 做到N log M, 由于M较小，所以log M就也很小了
    2.  数值小，如最大还不超过1000W，可以用数组count，记录数字出现的个数
    3. 数值大，相同不相同的个数也多，这个就是最麻烦了，不过N log M也是可以做的，毕意1亿 logM也就30左右，还有一种解决方案是将数值分组，如先分成1-1000W,1000W-2000W,再分别统计区间内各数出现次数。

     反正，都不难。

cdtits

unix 下 wc 命令应该可以吧

hbeimf

pitonas

应该可以吧

shang2010

做互联网的数据分析啊

shang2010

_Rayx 发表于 2012-06-24 10:13
回复 1# allegrox

现在机器内存不值钱，看时间了