海量数据处理
对于海量数据而言,由于无法将其一次性装进内存进行处理,必须将其通过散列映射方法分割成相应的小块数据,然后在对各个小块数据通过hash_map进行统计或其他操作 采用分治思想: 例1:从海量日志提取出某日访问百度次数最多的那个IP【例题可以采用散列函数+hash_map+堆的方式解答问题】 1.采用散列映射:先从海量日志里提取出访问百度的所有IP写入一个大文件中,接着采取散列映射方法(hash(IP)%1000),把整个大文件数据映射到1000个小文件中【相同的IP只有可能映射到同一个文件】 2.hash_map统计:大文件形成1000个小文件后,便可以采用hash_map(ip,count)分别对1000个小文件的IP进行频率统计,找出每个小文件中出现频率最高的IP【遍历每个小文件中的ip,如果出现一次,就将count+=1,统计完成后将hash_map中的数据放入数组中,使用堆/快速排序统计每个文件出现频率最高的那个IP】。因此能找出1000个IP 3.采用堆/快速排序:统计1000个IP中频率最高的IP后,找出出现频率最高的那个IP 例2:有一个1GB大小的文件,每行都是一个词,每个词大小是16B,内心大小限制1M,寻找出现频率最高的100个词【例题可以采用散列函数+hash_map+归并的方式解答问题】 1.采用散列映射:对于每个词,执行hash(x)%5000,将值存到5000个小文件中。此时每个小文件大小是1G/5000=200K,如果有文件超过1M,那可以按照这个方法继续划分文件,直到不超过1M 2.hash_map:对每个小文件使用hash_map和红黑树的方式,得到出现频率最高的100个词,将每个文件得到的100个词再次存入新文件中,这样又可以得到5000个新文件(每个文件100个词) 3.使用归并排序,将两两文件数据载入内存对比,得到新的前100词放入新文件,直到剩下两个文件,最后对比完成就得到频率最高的100个词(频繁IO,可能还有其他做法) 例3:有海量数据分布在100台电脑中,提取出现次数最多的10个 两种情况: 第一,如果同一个元素只出现在一台电脑: 1.堆排序:使用最小堆在每台电脑求出top 10。详解,先取出10个元素构建最小堆,然后拿剩余元素和堆顶元素比较,比堆顶元素大,就拿该元素替换堆顶元素,然后再调整最小堆。重复步骤。 2.组合归并:求出每台电脑上的top 10,就把这100台电脑上的top 10组合起来,共1000个数据。在根据这1000个数据求出top 10就行了 第二,如果同一个元素重复出现在不同电脑上: 1.遍历一遍所有数据,重新散列取模。使得同一个元素只出现在单独的一台电脑上,然后采取第一种的方法统计就行了。 例4:有两个文件a和b,各存放50亿个URL,每个URL占了64B,内存限制是4GB,请找出a和b文件中共同的URL 1.散列:遍历文件a,对每个URL求取hash(URL)%1000,将文件存储到1000个小文件中(a1,a2.....),每个小文件大约300M。同样遍历b文件,形成1000个小文件(b1,b2....) 2.hash_set统计:由于只有a1和b1这样一对文件才可能出现相同的url,所以把a1文件的url存储到hash_set,遍历b1,看看是否在刚才构建的hash_set中 *多层划分思想:mapreduce *外排序:多路归并 *位图算法:查找 判重 删除 *布隆过滤器:Bloom filter *Trie树(字典树) *一般数据库使用B树索引或B+树索引而不会使用散列索引?可是hash表第一存在散列冲突问题,这个必须解决;第二hash表的一般利用率仅为50%,这就会占用大量的存储空间而实际应用的空间却不多。B树和 hash表都很灵活适用于多表查找和存储,可是当存储比例达到一定程度时hash表必须进行扩容才能维持之后的操作,而B树不用。 *倒排索引:搜索引擎 *simhash算法:比较两个文档的相识度