Top K Big问题
问题
从十万个数中找出前一百个较大的数，让你来实现你会如何实现？
算法
一般人们很容易想到的算法是，在程序中定义一个大数组，将这十万个数进行排序，再定义一个元素为一百的数组将排在前一百是数选出放在这个数组中。
改进算法：
只要停下来想想很容易发现，在上面的算法中存在一个很大的问题，做了很多的无用功，
我们要的是前一百一个数，后面的九万九千九百个数的排序都的多余的，换句话说那是在浪费时间，
是算法低效的原因所在。
现在我们可以换一中思维，假设在这十万个数中前一百个就是其中最大的，将其取出。
再对其排序。用一个指针指向这一百个元素中最小的那个。
将这个最小的元素和后面的九万九千九百个数比较，
如果后面的数比这个小数大，那就交换。并将前一百个数重新排序，
再将里面最小的和后面的比较。一直这样循环，直到和后面的数比较完。
这样只要都大数组扫描一边就可以完成，可以很大的改善程序的效率。
实现
样例输入
class _7TopKBig{
public static void main(String[] args)
{
int kb = 1024;
int mb = 1024*1024;
int K = 100;
int[] a = new int[mb];//4mb
for(int i=0; i<mb; ++i)
{
//int seed = (int)
int r = (int) (1000000 * Math.random());
a[i] = r;
}
int[] heap = new int[K];
System.arraycopy(a, 0, heap, 0, K);
/*构建初始堆*/
for(int i=(K>>1); i>=0; --i)
adjustHeap(heap, i, K-1);
/*查找topK*/
for(int i=K; i<mb; ++i)
{
if(a[i]>heap[0])
{
heap[0] = a[i];
adjustHeap(heap, 0, K-1);
}
}
/*堆排序*/
for(int i=K-1; i>=0; --i)
{
int tmp = heap[0];
heap[0] = heap[i];
heap[i] = tmp;
adjustHeap(heap, 0, i-1);
}
/*打印*/
for(int i=0; i<K; ++i)
{
System.out.print(heap[i] + "\t");
}
System.out.print("\n");
}
private static void adjustHeap(int[] a, int s, int e)
{
if(a==null)
return;
int len = a.length;
if(s<0||e>=len||s>e)
return;
int tmp = a[s];
for(int i=(2*s+1); i<=e; i=(2*i+1))
{
if(i<=e-1 && a[i]>=a[i+1])
i++;
if(tmp < a[i])
break;
a[s] = a[i];
s=i;
}
a[s] = tmp;
}
}Bloomfilter
问题
我们经常要判断一个元素是否在一个集合中，比如网络爬虫实现的时候需要判断一个网址是否被访问过等等。 最简单的方法就是将集全部的元素存在内存里，遍历去检查。可以通过HashTable这样的数据结构来存储。 但是当数据量一旦变大的时候，内存中不足以放下所有元素的时候，问题就会凸显出来。 比如一个email地址假如平均占用20个字节，一亿个就是2G，几十亿个地址可能需要上百G的内存，这样一般的服务器是无法存储的。
算法
布隆过滤器能很好的解决这个问题，原理是使用多个hash函数来产生多个信息指纹，然后映射到一个大的数字范围内，把对应位置的bit位置为1。 优点是存储效率高 缺点是有可能出现误判，所以只能用在对准确率要求不是100%的情况下。 当然也可以通过白名单的方式来解决这个误判问题。
实现
/**
* Bloomfilter implementation
*
* @author xmtsui
*/
import java.util.BitSet;
class _6SimpleBloomFilter
{
private static final int DEFAULT_SIZE = 2 << 24;
private BitSet bits = new BitSet(DEFAULT_SIZE);
private static final int[] seeds = new int []{5,7,11,13,31,37,61};//生成六个随机种子
private SimpleHash[] func=new SimpleHash[seeds.length];//6个随机数产生器
public static void main(String[] args)
{
String value = "test@test.com";
_6SimpleBloomFilter filter=new _6SimpleBloomFilter();
System.out.println(filter.bits.size());//物理
System.out.println(filter.bits.length());//逻辑
System.out.println(filter.contains(value));
for(int i=0; i<1000; i++)
filter.add(value+"_"+i);
filter.add(value);
long start1 = System.currentTimeMillis();
for(int i=0; i<10000; i++)
// System.out.println(filter.contains(value));
filter.contains(value);
long end1 = System.currentTimeMillis();
long time1 = end1 - start1;
for(int i=1000; i<2000; i++)
filter.add(value+"_"+i);
long start2 = System.currentTimeMillis();
for(int i=0; i<10000; i++)
// System.out.println(filter.contains(value));
filter.contains(value);
long end2 = System.currentTimeMillis();
long time2 = end2 - start2;
System.out.println("For big data, time1: " + time1 + "| time2: "+ time2);
}
public _6SimpleBloomFilter()
{
for(int i = 0; i < seeds.length; i++)
{
func[i]=new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
//添加的时候要使用每一个hash函数计算一遍，设置bitset的位
public void add(String value)
{
for(SimpleHash f : func)
{
bits.set(f.hash(value), true);
}
}
//判断相等的时候同
public boolean contains(String value)
{
if(value ==null)
{
return false;
}
boolean ret = true;
for(SimpleHash f : func)
{
ret=ret && bits.get(f.hash(value));
}
return ret;
}
public static class SimpleHash
{
private int cap;
private int seed;
public SimpleHash(int cap, int seed)
{
this.cap = cap;
this.seed = seed;
}
public int hash(String value)
{
int result=0;
int len= value.length();
for(int i= 0; i< len; i++)
{
result = seed* result + value.charAt(i);
}
return (cap - 1)& result;
}
}
}Bitmap
问题
给你一堆8位电话号码列表，数量在千万级，要求从中找出所有重复的电话号码，需要时间复杂度尽可能小
算法
很容易想到空间换时间的解法，但如果是基础数据类型或者String的话，耗费的内存会很大。 比如存int，1000万个就是40M内存。我们可以考虑采用bit位来表示数值范围，这样1000万个bit占用的空间为10000000/8/1024/1024mb大概为1mb多些。
实现
class _4Bitmap{
public static void main(String[] args)
{
//创建一个具有10000000位的bitset 初始所有位的值为false
java.util.BitSet bitSet = new java.util.BitSet(10000000);
//将指定位的值设为true
bitSet.set(9999, true);
//输出指定位的值
System.out.println(bitSet.get(9999));
System.out.println(bitSet.get(9998));
Runtime rt_jmm = Runtime.getRuntime();
long total_jmm = rt_jmm.totalMemory();
long max_jmm = rt_jmm.maxMemory();
int MB_JMM = 1024*1024;
int KB_JMM = 1024;
System.out.println("total : " + total_jmm/MB_JMM + " mb");
System.out.println("max : " + max_jmm/MB_JMM + " mb");
long free1_jmm = rt_jmm.freeMemory();
int[] nums = new int[KB_JMM];
for(int i=KB_JMM-1; i>=0; --i)
{
int rand = (int)(1000*Math.random());
nums[i] = rand;
// nums[i] = i;
}
java.util.BitSet bits = new java.util.BitSet();
for(int i=0; i<KB_JMM; ++i)
{
if(!bits.get(nums[i]))
bits.set(nums[i], true);
else
System.out.print("the same"+ i);
}
int flag=0;
for(int i=0; i<KB_JMM; ++i)
{
if(bits.get(i))
{
flag++;
System.out.print(i + " ");
}
}
System.out.println(flag);
long free2_jmm = rt_jmm.freeMemory();
System.out.println("used : " + (free1_jmm-free2_jmm)/MB_JMM + " mb");
}
}