海量数据问题总结

海量数据问题:数据量很大,无法直接用有限的内存存储,也就是无法一次性通过排序等处理数据。

Hash:hash本质上是一种映射函数,将键值映射为一个数值(存储位置)。查找的话当然键值冲突越少越好,但如果只是单纯的分成小文件,只要保证相同的数据在同一组,冲不冲突也无所谓。

hash_map/hash_set:(IP, IP_count)

(在这里刚开始有一个问题^0.0^,这个hash_map的键是不是无冲突。。一个对应一个索引。。。后来想了想我只是逻辑上使用这个功能,查找O(1),具体的无需多管了)

top K问题:最大K个用最小堆,最小K个用最大堆。(一个值就是最大最小值问题)

直接排序:直接排序的时间复杂度是nlogn,而采用大顶堆等,直接和堆顶元素比较,如果大于或小于直接舍弃,否则花费logn时间调整堆,所以整体的时间小于nlogn。

分治:如果一个大文件分解为多个小文件(相同的元素必须位于同一个文件中,所以分解文件并不是按照顺序直接分解,一般采用hash法),则需要对每一个小文件求top K。

合并:最后对多个小文件的top K求解最后的top K(可以继续采用最大最小堆方法,数量少也可以排序)。

 set/hash_set:set查询插入时间很稳定,logn加上红黑树的调整,hash_set不稳定,最小o(1),最差o(n),他们的性能有待比较,红黑树着重数据的随机性,hash着重统计的特性。

倒排索引:

原文地址:https://www.cnblogs.com/mdumpling/p/8260553.html