存档

文章标签 ‘归并’

逆序对 | 逆序数

2012年7月16日 3 条评论

---

设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)【《算法导论》2-4】

现给出一个数列,求该数列中的逆序对数(逆序数)。本节给出三种方法:方法一是最直接的暴力方法;方法二是基于归并分治的思想;方法三是基于线段树的。

解法一

暴力方法最直接,也最容易想到,两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:

	int sum = 0;
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			if(arr[i] > arr[j])
			{
				++sum;
			}
		}
	}
	return sum;

解法二

这种方法最初见于《算法导论》,这里先附上《算法导论》2-4关于逆序对的几点讨论:

阅读全文...

海量数据处理之归并、堆排、前K方法的应用:一道面试题

2011年9月8日 6 条评论

 

最初关注海量处理方面是因为好久以前在西安交大BBS算法版上看到一个牛人总结的帖子,收集了起来,后来发现网上铺天盖地地转载过,那个帖子提供了一些解决问题很好的思路,所以就零碎地整理过海量数据处理方面的一些方法,但终归没有深入并做一个稍微细致的思考,从这篇博文开始,希望能坚持整理出来。

下面一道面试题是以前大雄考过我的,据说是那时一些公司常问的类型题目,这里回顾并总结一下,欢迎大家讨论并提出问题。

题目:一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右

分析:

本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词

  1. 词频统计

词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

  • 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。

问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。

怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b

  • 归并b:将数据分为5段,分段时对每个词hashhash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。

分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种,至于具体的hash函数,就不讨论了,哈哈

阅读全文...