赞
踩
关于实战算法都需要了解哪些?一文带你详细了解,欢迎收藏!
100亿黑名单URL,每个64B,问这个黑名单要怎么存?判断一个URL是否在黑名单中
散列表:
如果把黑名单看成一个集合,将其存在hashmap中,貌似太大了,需要640G,明显不科学。
它实际上是一个很长的二进制矢量和一系列随机映射函数。
它可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。对于布隆过滤器而言,它的本质是一个位数组:位数组就是数组的每个元素都只占用1 bit,并且每个元素只能是0或者1。
在数组中的每一位都是二进制位。布隆过滤器除了一个位数组,还有K个哈希函数。当一个元素加入布隆过滤器中的时候,会进行如下操作:
使用K个哈希函数对元素值进行K次计算,得到K个哈希值。
根据得到的哈希值,在位数组中把对应下标的值置为1。
2GB内存在20亿整数中找到出现次数最多的数
通常做法是使用哈希表对出现的每一个数做词频统计,哈希表的key是某个整数,value记录整数出现的次数。本题的数据量是20亿,有可能一个数出现20亿次,则为了避免溢出,哈希表的key是32位(4B),value也是32位(4B),那么一条哈希表的记录就需要占用8B。
当哈希表记录数为2亿个时,需要16亿个字节数(8*2亿),需要至少1.6GB内存(16亿/2^30,1GB==2^30个字节==10亿)。则20亿个记录,至少需要16GB的内存,不符合题目要求。
解决办法是将20亿个数的大文件利用哈希函数分成16个小文件,根据哈希函数可以把20亿条数据均匀分布到16个文件上,同一种数不可能被哈希函数分到不同的小文件上,假设哈希函数够好。然后对每一个小文件用哈希函数来统计其中每种数出现的次数,这样我们就得到16个文件中出现次数最多的数,接着从16个数中选出次数最大的那个key即可。
40亿个非负整数中找到没有出现的数
对于原问题,如果使用哈希表来保存出现过的数,那么最坏情况下是40亿个数都不相同,那么哈希表则需要保存40亿条数据,一个32位整数需要4B,那么40亿*4B= 160亿个字节,一般大概10亿个字节的数据需要1G的空间,那么大概需要16G的空间,这不符合要求。
我们换一种方式,申请一个bit数组,数组大小为4294967295,大概为40亿bit,40亿/8=5亿字节,那么需要0.5G空间,bit数组的每个位置有两种状态0和1,那么怎么使用这个bit数组呢?呵呵,数组的长度刚好满足我们整数的个数范围,那么数组的每个下标值对应4294967295中的一个数,逐个遍历40亿个无符号数,例如,遇到20,则bitArray[20]=1;遇到666,则bitArray[666]=1,遍历完所有的数,将数组相应位置变为1。
40亿个非负整数中找到一个没有出现的数,内存限制10MB
10亿个字节的数据大概需要1GB空间处理,那么10MB内存换算过来就是可以处理1千万字节的数据,也就是8千万bit,对于40亿非负整数如果申请bit数组的话,40亿bit /0.8亿bit=50,那么这样最少也得分50块来处理,下面就以64块来进行分析解答吧。
总结一下进阶的解法
根据10MB的内存限制,确定统计区间的大小,就是第二次遍历时的bitArr大小。
利用区间计数的方式,找到那个计数不足的区间,这个区间上肯定有没出现的数。
对这个区间上的数做bit map映射,再遍历bit map,找到一个没出现的数即可。
自己的想法
如果只是找一个数,可以高位模运算,写到64个不同的文件,然后在最小的文件中通过bitArray一次处理掉。
40亿个无符号整数,1GB内存,找到所有出现两次的数
对于原问题,可以用bit map的方式来表示数出现的情况。具体地说,是申请一个长度为4294967295×2的bit类型的数组bitArr,用2个位置表示一个数出现的词频,1B占用8个bit,所以长度为4294967295×2的bit类型的数组占用1GB空间。怎么使用这个bitArr数组呢?遍历这40亿个无符号数,如果初次遇到num,就把bitArr[num2+1]和bitArr[num2]设置为01,如果第二次遇到num,就把bitArr[num2+1]和bitArr[num2]设置为10,如果第三次遇到num,就把bitArr[num2+1]和bitArr[num2]设置为11。以后再遇到num,发现此时bitArr[num2+1]和bitArr[num2]已经被设置为11,就不再做任何设置。遍历完成后,再依次遍历bitArr,如果发现bitArr[i2+1]和bitArr[i2]设置为10,那么i就是出现了两次的数。
找到100亿个URL中重复的URL
原问题的解法使用解决大数据问题的一种常规方法:把大文件通过哈希函数分配到机器,或者通过哈希函数把大文件拆成小文件。一直进行这种划分,直到划分的结果满足资源限制的要求。首先,你要向面试官询问在资源上的限制有哪些,包括内存、计算时间等要求。在明确了限制要求之后,可以将每条URL通过哈希函数分配到若干机器或者拆分成若干小文件,这里的“若干”由具体的资源限制来计算出精确的数量。
例如,将100亿字节的大文件通过哈希函数分配到100台机器上,然后每一台机器分别统计分给自己的URL中是否有重复的URL,同时哈希函数的性质决定了同一条URL不可能分给不同的机器;或者在单机上将大文件通过哈希函数拆成1000个小文件,对每一个小文件再利用哈希表遍历,找出重复的URL;或者在分给机器或拆完文件之后,进行排序,排序过后再看是否有重复的URL出现。总之,牢记一点,很多大数据问题都离不开分流,要么是哈希函数把大文件的内容分配给不同的机器,要么是哈希函数把大文件拆成小文件,然后处理每一个小数量的集合。
海量搜索词汇,找到最热TOP100词汇的方法
最开始还是用哈希分流的思路来处理,把包含百亿数据量的词汇文件分流到不同的机器上,具体多少台机器由面试官规定或者由更多的限制来决定。对每一台机器来说,如果分到的数据量依然很大,比如,内存不够或其他问题,可以再用哈希函数把每台机器的分流文件拆成更小的文件处理。
处理每一个小文件的时候,哈希表统计每种词及其词频,哈希表记录建立完成后,再遍历哈希表,遍历哈希表的过程中使用大小为100的小根堆来选出每一个小文件的top100(整体未排序的top100)。每一个小文件都有自己词频的小根堆(整体未排序的top100),将小根堆里的词按照词频排序,就得到了每个小文件的排序后top100。然后把各个小文件排序后的top100进行外排序或者继续利用小根堆,就可以选出每台机器上的top100。不同机器之间的top100再进行外排序或者继续利用小根堆,最终求出整个百亿数据量中的top100。对于top K的问题,除哈希函数分流和用哈希表做词频统计之外,还经常用堆结构和外排序的手段进行处理。
10MB内存,找到100亿整数的中位数
内存够:内存够还慌什么啊,直接把100亿个全部排序了,你用冒泡都可以...然后找到中间那个就可以了。但是你以为面试官会给你内存??
内存不够:题目说是整数,我们认为是带符号的int,所以4字节,占32位。
假设100亿个数字保存在一个大文件中,依次读一部分文件到内存(不超过内存的限制),将每个数字用二进制表示,比较二进制的最高位(第32位,符号位,0是正,1是负),如果数字的最高位为0,则将这个数字写入file_0文件中;如果最高位为1,则将该数字写入file_1文件中。
从而将100亿个数字分成了两个文件,假设file_0文件中有60亿个数字,file_1文件中有40亿个数字。那么中位数就在file_0文件中,并且是file_0文件中所有数字排序之后的第10亿个数字。(file_1中的数都是负数,file_0中的数都是正数,也即这里一共只有40亿个负数,那么排序之后的第50亿个数一定位于file_0中)
现在,我们只需要处理file_0文件了(不需要再考虑file_1文件)。对于file_0文件,同样采取上面的措施处理:将file_0文件依次读一部分到内存(不超内存限制),将每个数字用二进制表示,比较二进制的次高位(第31位),如果数字的次高位为0,写入file_0_0文件中;如果次高位为1,写入file_0_1文件中。
现假设file_0_0文件中有30亿个数字,file_0_1中也有30亿个数字,则中位数就是:file_0_0文件中的数字从小到大排序之后的第10亿个数字。
抛弃file_0_1文件,继续对file_0_0文件根据次次高位(第30位)划分,假设此次划分的两个文件为:file_0_0_0中有5亿个数字,file_0_0_1中有25亿个数字,那么中位数就是file_0_0_1文件中的所有数字排序之后的 第5亿个数。
按照上述思路,直到划分的文件可直接加载进内存时,就可以直接对数字进行快速排序,找出中位数了。
设计短域名系统,将长URL转化成短的URL.
利用放号器,初始值为0,对于每一个短链接生成请求,都递增放号器的值,再将此值转换为62进制(a-zA-Z0-9),比如第一次请求时放号器的值为0,对应62进制为a,第二次请求时放号器的值为1,对应62进制为b,第10001次请求时放号器的值为10000,对应62进制为sBc。
将短链接服务器域名与放号器的62进制值进行字符串连接,即为短链接的URL,比如:t.cn/sBc。
重定向过程:生成短链接之后,需要存储短链接到长链接的映射关系,即sBc ->URL,浏览器访问短链接服务器时,根据URL Path取到原始的链接,然后进行302重定向。映射关系可使用K-V存储,比如Redis或Memcache。
假设有这么一个场景,有一条新闻,新闻的评论量可能很大,如何设计评论的读和写
前端页面直接给用户展示、通过消息队列异步方式入库
读可以进行读写分离、同时热点评论定时加载到缓存
显示网站的用户在线数的解决思路
维护在线用户表
使用Redis统计
显示网站并发用户数
每当用户访问服务时,把该用户的ID写入ZSORT队列,权重为当前时间;
根据权重(即时间)计算一分钟内该机构的用户数Zrange;
删掉一分钟以上过期的用户Zrem;
假设目前有1000w个记录(这些查询串的重复度比较高,虽然总数是1000w,但如果除去重复后,则不超过300w个)。请统计最热门的10个查询串,要求使用的内存不能超过1G。(一个查询串的重复度越高,说明查询它的用户越多,也就越热门。)
HashMap法
虽然字符串总数比较多,但去重后不超过300w,因此,可以考虑把所有字符串及出现次数保存在一个HashMap中,所占用的空间为300w*(255+4)≈777M(其中,4 表示整数占用的4个字节)。由此可见,1G的内存空间完全够用。
思路如下
首先,遍历字符串,若不在map中,直接存入map,value记为1;若在map中,则把对应的value加1,这一步时间复杂度O(N)
。
接着遍历map,构建一个10个元素的小顶堆,若遍历到的字符串的出现次数大于堆顶字符串的出现次数,则进行替换,并将堆调整为小顶堆。
遍历结束后,堆中10个字符串就是出现次数最多的字符串。这一步时间复杂度O(Nlog10)
。
前缀树法
当这些字符串有大量相同前缀时,可以考虑使用前缀树来统计字符串出现的次数,树的结点保存字符串出现次数,0表示没有出现。
思路如下
在遍历字符串时,在前缀树中查找,如果找到,则把结点中保存的字符串次数加1,否则为这个字符串构建新结点,构建完成后把叶子结点中字符串的出现次数置为1。
最后依然使用小顶堆来对字符串的出现次数进行排序。
线性切割法,一个区间切N-1刀。越早越多
二倍均值法,【0~剩余金额 / 剩余人数*2】中随机,相对均匀
- public class QuickSort {
- public static void swap(int[] arr, int i, int j) {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- /* 常规快排 */
- public static void quickSort1(int[] arr, int L , int R) {
- if (L > R) return;
- int M = partition(arr, L, R);
- quickSort1(arr, L, M - 1);
- quickSort1(arr, M + 1, R);
- }
- public static int partition(int[] arr, int L, int R) {
- if (L > R) return -1;
- if (L == R) return L;
- int lessEqual = L - 1;
- int index = L;
- while (index < R) {
- if (arr[index] <= arr[R])
- swap(arr, index, ++lessEqual);
- index++;
- }
- swap(arr, ++lessEqual, R);
- return lessEqual;
- }
- /* 荷兰国旗 */
- public static void quickSort2(int[] arr, int L, int R) {
- if (L > R) return;
- int[] equalArea = netherlandsFlag(arr, L, R);
- quickSort2(arr, L, equalArea[0] - 1);
- quickSort2(arr, equalArea[1] + 1, R);
- }
- public static int[] netherlandsFlag(int[] arr, int L, int R) {
- if (L > R) return new int[] { -1, -1 };
- if (L == R) return new int[] { L, R };
- int less = L - 1;
- int more = R;
- int index = L;
- while (index < more) {
- if (arr[index] == arr[R]) {
- index++;
- } else if (arr[index] < arr[R]) {
- swap(arr, index++, ++less);
- } else {
- swap(arr, index, --more);
- }
- }
- swap(arr, more, R);
- return new int[] { less + 1, more };
- }
-
-
- // for test
- public static void main(String[] args) {
- int testTime = 1;
- int maxSize = 10000000;
- int maxValue = 100000;
- boolean succeed = true;
- long T1=0,T2=0;
- for (int i = 0; i < testTime; i++) {
- int[] arr1 = generateRandomArray(maxSize, maxValue);
- int[] arr2 = copyArray(arr1);
- int[] arr3 = copyArray(arr1);
- // int[] arr1 = {9,8,7,6,5,4,3,2,1};
- long t1 = System.currentTimeMillis();
- quickSort1(arr1,0,arr1.length-1);
- long t2 = System.currentTimeMillis();
- quickSort2(arr2,0,arr2.length-1);
- long t3 = System.currentTimeMillis();
- T1 += (t2-t1);
- T2 += (t3-t2);
- if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
- succeed = false;
- break;
- }
- }
- System.out.println(T1+" "+T2);
- // System.out.println(succeed ? "Nice!" : "Oops!");
- }
-
-
- private static int[] generateRandomArray(int maxSize, int maxValue) {
- int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
- for (int i = 0; i < arr.length; i++) {
- arr[i] = (int) ((maxValue + 1) * Math.random())
- - (int) (maxValue * Math.random());
- }
- return arr;
- }
- private static int[] copyArray(int[] arr) {
- if (arr == null) return null;
- int[] res = new int[arr.length];
- for (int i = 0; i < arr.length; i++) {
- res[i] = arr[i];
- }
- return res;
- }
- private static boolean isEqual(int[] arr1, int[] arr2) {
- if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
- return false;
- if (arr1 == null && arr2 == null)
- return true;
- if (arr1.length != arr2.length)
- return false;
- for (int i = 0; i < arr1.length; i++)
- if (arr1[i] != arr2[i])
- return false;
- return true;
- }
- private static void printArray(int[] arr) {
- if (arr == null)
- return;
- for (int i = 0; i < arr.length; i++)
- System.out.print(arr[i] + " ");
- System.out.println();
- }
- }
- public static void merge(int[] arr, int L, int M, int R) {
- int[] help = new int[R - L + 1];
- int i = 0;
- int p1 = L;
- int p2 = M + 1;
- while (p1 <= M && p2 <= R)
- help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
- while (p1 <= M)
- help[i++] = arr[p1++];
- while (p2 <= R)
- help[i++] = arr[p2++];
- for (i = 0; i < help.length; i++)
- arr[L + i] = help[i];
- }
- public static void mergeSort(int[] arr, int L, int R) {
- if (L == R)
- return;
- int mid = L + ((R - L) >> 1);
- process(arr, L, mid);
- process(arr, mid + 1, R);
- merge(arr, L, mid, R);
- }
- public static void main(String[] args) {
- int[] arr1 = {9,8,7,6,5,4,3,2,1};
- mergeSort(arr, 0, arr.length - 1);
- printArray(arr);
- }
- // 堆排序额外空间复杂度O(1)
- public static void heapSort(int[] arr) {
- if (arr == null || arr.length < 2)
- return;
- for (int i = arr.length - 1; i >= 0; i--)
- heapify(arr, i, arr.length);
- int heapSize = arr.length;
- swap(arr, 0, --heapSize);
- // O(N*logN)
- while (heapSize > 0) { // O(N)
- heapify(arr, 0, heapSize); // O(logN)
- swap(arr, 0, --heapSize); // O(1)
- }
- }
- // arr[index]刚来的数,往上
- public static void heapInsert(int[] arr, int index) {
- while (arr[index] > arr[(index - 1) / 2]) {
- swap(arr, index, (index - 1) / 2);
- index = (index - 1) / 2;
- }
- }
- // arr[index]位置的数,能否往下移动
- public static void heapify(int[] arr, int index, int heapSize) {
- int left = index * 2 + 1; // 左孩子的下标
- while (left < heapSize) { // 下方还有孩子的时候
- // 两个孩子中,谁的值大,把下标给largest
- // 1)只有左孩子,left -> largest
- // 2) 同时有左孩子和右孩子,右孩子的值<= 左孩子的值,left -> largest
- // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值, right -> largest
- int largest = left+1 < heapSize && arr[left+1]> arr[left] ? left+1 : left;
- // 父和较大的孩子之间,谁的值大,把下标给largest
- largest = arr[largest] > arr[index] ? largest : index;
- if (largest == index)
- break;
- swap(arr, largest, index);
- index = largest;
- left = index * 2 + 1;
- }
- }
- public static void swap(int[] arr, int i, int j) {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- public static void main(String[] args) {
- int[] arr1 = {9,8,7,6,5,4,3,2,1};
- heapSort(arr1);
- printArray(arr1);
- }
- public class Singleton {
- private volatile static Singleton singleton;
- private Singleton() {}
- public static Singleton getSingleton() {
- if (singleton == null) {
- synchronized (Singleton.class) {
- if (singleton == null) {
- singleton = new Singleton();
- }
- }
- }
- return singleton;
- }
- }
- // 基于linkedHashMap
- public class LRUCache {
- private LinkedHashMap<Integer,Integer> cache;
- private int capacity; //容量大小
- public LRUCache(int capacity) {
- cache = new LinkedHashMap<>(capacity);
- this.capacity = capacity;
- }
- public int get(int key) {
- //缓存中不存在此key,直接返回
- if(!cache.containsKey(key)) {
- return -1;
- }
- int res = cache.get(key);
- cache.remove(key); //先从链表中删除
- cache.put(key,res); //再把该节点放到链表末尾处
- return res;
- }
- public void put(int key,int value) {
- if(cache.containsKey(key)) {
- cache.remove(key); //已经存在,在当前链表移除
- }
- if(capacity == cache.size()) {
- //cache已满,删除链表头位置
- Set<Integer> keySet = cache.keySet();
- Iterator<Integer> iterator = keySet.iterator();
- cache.remove(iterator.next());
- }
- cache.put(key,value); //插入到链表末尾
- }
- }
- //手写双向链表
- class LRUCache {
- class DNode {
- DNode prev;
- DNode next;
- int val;
- int key;
- }
- Map<Integer, DNode> map = new HashMap<>();
- DNode head, tail;
- int cap;
- public LRUCache(int capacity) {
- head = new DNode();
- tail = new DNode();
- head.next = tail;
- tail.prev = head;
- cap = capacity;
- }
- public int get(int key) {
- if (map.containsKey(key)) {
- DNode node = map.get(key);
- removeNode(node);
- addToHead(node);
- return node.val;
- } else {
- return -1;
- }
- }
- public void put(int key, int value) {
- if (map.containsKey(key)) {
- DNode node = map.get(key);
- node.val = value;
- removeNode(node);
- addToHead(node);
- } else {
- DNode newNode = new DNode();
- newNode.val = value;
- newNode.key = key;
- addToHead(newNode);
- map.put(key, newNode);
- if (map.size() > cap) {
- map.remove(tail.prev.key);
- removeNode(tail.prev);
- }
- }
- }
- public void removeNode(DNode node) {
- DNode prevNode = node.prev;
- DNode nextNode = node.next;
- prevNode.next = nextNode;
- nextNode.prev = prevNode;
- }
- public void addToHead(DNode node) {
- DNode firstNode = head.next;
- head.next = node;
- node.prev = head;
- node.next = firstNode;
- firstNode.prev = node;
- }
- }
- package com.concurrent.pool;
- import java.util.HashSet;
- import java.util.Set;
- import java.util.concurrent.ArrayBlockingQueue;
- import java.util.concurrent.BlockingQueue;
- public class MySelfThreadPool {
- //默认线程池中的线程的数量
- private static final int WORK_NUM = 5;
- //默认处理任务的数量
- private static final int TASK_NUM = 100;
- private int workNum;//线程数量
- private int taskNum;//任务数量
- private final Set<WorkThread> workThreads;//保存线程的集合
- private final BlockingQueue<Runnable> taskQueue;//阻塞有序队列存放任务
- public MySelfThreadPool() {
- this(WORK_NUM, TASK_NUM);
- }
- public MySelfThreadPool(int workNum, int taskNum) {
- if (workNum <= 0) workNum = WORK_NUM;
- if (taskNum <= 0) taskNum = TASK_NUM;
- taskQueue = new ArrayBlockingQueue<>(taskNum);
- this.workNum = workNum;
- this.taskNum = taskNum;
- workThreads = new HashSet<>();
- //启动一定数量的线程数,从队列中获取任务处理
- for (int i=0;i<workNum;i++) {
- WorkThread workThread = new WorkThread("thead_"+i);
- workThread.start();
- workThreads.add(workThread);
- }
- }
- public void execute(Runnable task) {
- try {
- taskQueue.put(task);
- } catch (InterruptedException e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- public void destroy() {
- System.out.println("ready close thread pool...");
- if (workThreads == null || workThreads.isEmpty()) return ;
- for (WorkThread workThread : workThreads) {
- workThread.stopWork();
- workThread = null;//help gc
- }
- workThreads.clear();
- }
- private class WorkThread extends Thread{
- public WorkThread(String name) {
- super();
- setName(name);
- }
- @Override
- public void run() {
- while (!interrupted()) {
- try {
- Runnable runnable = taskQueue.take();//获取任务
- if (runnable !=null) {
- System.out.println(getName()+" readyexecute:"+runnable.toString());
- runnable.run();//执行任务
- }
- runnable = null;//help gc
- } catch (Exception e) {
- interrupt();
- e.printStackTrace();
- }
- }
- }
- public void stopWork() {
- interrupt();
- }
- }
- }
-
-
- package com.concurrent.pool;
-
-
- public class TestMySelfThreadPool {
- private static final int TASK_NUM = 50;//任务的个数
- public static void main(String[] args) {
- MySelfThreadPool myPool = new MySelfThreadPool(3,50);
- for (int i=0;i<TASK_NUM;i++) {
- myPool.execute(new MyTask("task_"+i));
- }
- }
- static class MyTask implements Runnable{
- private String name;
- public MyTask(String name) {
- this.name = name;
- }
- public String getName() {
- return name;
- }
- public void setName(String name) {
- this.name = name;
- }
- @Override
- public void run() {
- try {
- Thread.sleep(1000);
- } catch (InterruptedException e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- System.out.println("task :"+name+" end...");
- }
- @Override
- public String toString() {
- // TODO Auto-generated method stub
- return "name = "+name;
- }
- }
- }
- public class Storage {
- private static int MAX_VALUE = 100;
- private List<Object> list = new ArrayList<>();
- public void produce(int num) {
- synchronized (list) {
- while (list.size() + num > MAX_VALUE) {
- System.out.println("暂时不能执行生产任务");
- try {
- list.wait();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- for (int i = 0; i < num; i++) {
- list.add(new Object());
- }
- System.out.println("已生产产品数"+num+" 仓库容量"+list.size());
- list.notifyAll();
- }
- }
-
-
- public void consume(int num) {
- synchronized (list) {
- while (list.size() < num) {
- System.out.println("暂时不能执行消费任务");
- try {
- list.wait();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- for (int i = 0; i < num; i++) {
- list.remove(0);
- }
- System.out.println("已消费产品数"+num+" 仓库容量" + list.size());
- list.notifyAll();
- }
- }
- }
-
-
- public class Producer extends Thread {
- private int num;
- private Storage storage;
- public Producer(Storage storage) {
- this.storage = storage;
- }
- public void setNum(int num) {
- this.num = num;
- }
- public void run() {
- storage.produce(this.num);
- }
- }
-
-
- public class Customer extends Thread {
- private int num;
- private Storage storage;
- public Customer(Storage storage) {
- this.storage = storage;
- }
- public void setNum(int num) {
- this.num = num;
- }
- public void run() {
- storage.consume(this.num);
- }
- }
-
-
- public class Test {
- public static void main(String[] args) {
- Storage storage = new Storage();
- Producer p1 = new Producer(storage);
- Producer p2 = new Producer(storage);
- Producer p3 = new Producer(storage);
- Producer p4 = new Producer(storage);
- Customer c1 = new Customer(storage);
- Customer c2 = new Customer(storage);
- Customer c3 = new Customer(storage);
- p1.setNum(10);
- p2.setNum(20);
- p3.setNum(80);
- c1.setNum(50);
- c2.setNum(20);
- c3.setNum(20);
- c1.start();
- c2.start();
- c3.start();
- p1.start();
- p2.start();
- p3.start();
- }
- }
- public class blockQueue {
- private List<Integer> container = new ArrayList<>();
- private volatile int size;
- private volatile int capacity;
- private Lock lock = new ReentrantLock();
- private final Condition isNull = lock.newCondition();
- private final Condition isFull = lock.newCondition();
- blockQueue(int capacity) {
- this.capacity = capacity;
- }
- public void add(int data) {
- try {
- lock.lock();
- try {
- while (size >= capacity) {
- System.out.println("阻塞队列满了");
- isFull.await();
- }
- } catch (Exception e) {
- isFull.signal();
- e.printStackTrace();
- }
- ++size;
- container.add(data);
- isNull.signal();
- } finally {
- lock.unlock();
- }
- }
- public int take() {
- try {
- lock.lock();
- try {
- while (size == 0) {
- System.out.println("阻塞队列空了");
- isNull.await();
- }
- } catch (Exception e) {
- isNull.signal();
- e.printStackTrace();
- }
- --size;
- int res = container.get(0);
- container.remove(0);
- isFull.signal();
- return res;
- } finally {
- lock.unlock();
- }
- }
- }
-
-
- public static void main(String[] args) {
- AxinBlockQueue queue = new AxinBlockQueue(5);
- Thread t1 = new Thread(() -> {
- for (int i = 0; i < 100; i++) {
- queue.add(i);
- System.out.println("塞入" + i);
- try {
- Thread.sleep(500);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- });
- Thread t2 = new Thread(() -> {
- for (; ; ) {
- System.out.println("消费"+queue.take());
- try {
- Thread.sleep(800);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
-
-
- });
- t1.start();
- t2.start();
- }
- package com.demo.test;
- import java.util.concurrent.locks.Condition;
- import java.util.concurrent.locks.ReentrantLock;
- public class syncPrinter implements Runnable{
- // 打印次数
- private static final int PRINT_COUNT = 10;
- private final ReentrantLock reentrantLock;
- private final Condition thisCondtion;
- private final Condition nextCondtion;
- private final char printChar;
- public syncPrinter(ReentrantLock reentrantLock, Condition thisCondtion, Condition nextCondition, char printChar) {
- this.reentrantLock = reentrantLock;
- this.nextCondtion = nextCondition;
- this.thisCondtion = thisCondtion;
- this.printChar = printChar;
- }
- @Override
- public void run() {
- // 获取打印锁 进入临界区
- reentrantLock.lock();
- try {
- // 连续打印PRINT_COUNT次
- for (int i = 0; i < PRINT_COUNT; i++) {
- //打印字符
- System.out.print(printChar);
- // 使用nextCondition唤醒下一个线程
- // 因为只有一个线程在等待,所以signal或者signalAll都可以
- nextCondtion.signal();
- // 不是最后一次则通过thisCondtion等待被唤醒
- // 必须要加判断,不然虽然能够打印10次,但10次后就会直接死锁
- if (i < PRINT_COUNT - 1) {
- try {
- // 本线程让出锁并等待唤醒
- thisCondtion.await();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- } finally {
- reentrantLock.unlock();
- }
- }
-
-
- public static void main(String[] args) throws InterruptedException {
- ReentrantLock lock = new ReentrantLock();
- Condition conditionA = lock.newCondition();
- Condition conditionB = lock.newCondition();
- Condition conditionC = lock.newCondition();
- Thread printA = new Thread(new syncPrinter(lock, conditionA, conditionB,'A'));
- Thread printB = new Thread(new syncPrinter(lock, conditionB, conditionC,'B'));
- Thread printC = new Thread(new syncPrinter(lock, conditionC, conditionA,'C'));
- printA.start();
- Thread.sleep(100);
- printB.start();
- Thread.sleep(100);
- printC.start();
- }
- }
- //手太阴肺经 BLOCKING Queue
- public class FooBar {
- private int n;
- private BlockingQueue<Integer> bar = new LinkedBlockingQueue<>(1);
- private BlockingQueue<Integer> foo = new LinkedBlockingQueue<>(1);
- public FooBar(int n) {
- this.n = n;
- }
- public void foo(Runnable printFoo) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- foo.put(i);
- printFoo.run();
- bar.put(i);
- }
- }
- public void bar(Runnable printBar) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- bar.take();
- printBar.run();
- foo.take();
- }
- }
- }
-
-
- //手阳明大肠经CyclicBarrier 控制先后
- class FooBar6 {
- private int n;
- public FooBar6(int n) {
- this.n = n;
- }
- CyclicBarrier cb = new CyclicBarrier(2);
- volatile boolean fin = true;
- public void foo(Runnable printFoo) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- while(!fin);
- printFoo.run();
- fin = false;
- try {
- cb.await();
- } catch (BrokenBarrierException e) {}
- }
- }
- public void bar(Runnable printBar) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- try {
- cb.await();
- } catch (BrokenBarrierException e) {}
- printBar.run();
- fin = true;
- }
- }
- }
-
-
- //手少阴心经 自旋 + 让出CPU
- class FooBar5 {
- private int n;
-
-
- public FooBar5(int n) {
- this.n = n;
- }
- volatile boolean permitFoo = true;
- public void foo(Runnable printFoo) throws InterruptedException {
- for (int i = 0; i < n; ) {
- if(permitFoo) {
- printFoo.run();
- i++;
- permitFoo = false;
- }else{
- Thread.yield();
- }
- }
- }
- public void bar(Runnable printBar) throws InterruptedException {
- for (int i = 0; i < n; ) {
- if(!permitFoo) {
- printBar.run();
- i++;
- permitFoo = true;
- }else{
- Thread.yield();
- }
- }
- }
- }
-
-
-
-
-
-
- //手少阳三焦经 可重入锁 + Condition
- class FooBar4 {
- private int n;
-
-
- public FooBar4(int n) {
- this.n = n;
- }
- Lock lock = new ReentrantLock(true);
- private final Condition foo = lock.newCondition();
- volatile boolean flag = true;
- public void foo(Runnable printFoo) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- lock.lock();
- try {
- while(!flag) {
- foo.await();
- }
- printFoo.run();
- flag = false;
- foo.signal();
- }finally {
- lock.unlock();
- }
- }
- }
-
-
- public void bar(Runnable printBar) throws InterruptedException {
- for (int i = 0; i < n;i++) {
- lock.lock();
- try {
- while(flag) {
- foo.await();
- }
- printBar.run();
- flag = true;
- foo.signal();
- }finally {
- lock.unlock();
- }
- }
- }
- }
-
-
- //手厥阴心包经 synchronized + 标志位 + 唤醒
- class FooBar3 {
- private int n;
- // 标志位,控制执行顺序,true执行printFoo,false执行printBar
- private volatile boolean type = true;
- private final Object foo= new Object(); // 锁标志
-
-
- public FooBar3(int n) {
- this.n = n;
- }
- public void foo(Runnable printFoo) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- synchronized (foo) {
- while(!type){
- foo.wait();
- }
- printFoo.run();
- type = false;
- foo.notifyAll();
- }
- }
- }
-
-
- public void bar(Runnable printBar) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- synchronized (foo) {
- while(type){
- foo.wait();
- }
- printBar.run();
- type = true;
- foo.notifyAll();
- }
- }
- }
- }
-
-
-
-
- //手太阳小肠经 信号量 适合控制顺序
- class FooBar2 {
- private int n;
- private Semaphore foo = new Semaphore(1);
- private Semaphore bar = new Semaphore(0);
- public FooBar2(int n) {
- this.n = n;
- }
-
-
- public void foo(Runnable printFoo) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- foo.acquire();
- printFoo.run();
- bar.release();
- }
- }
- public void bar(Runnable printBar) throws InterruptedException {
- for (int i = 0; i < n; i++) {
- bar.acquire();
- printBar.run();
- foo.release();
- }
- }
- }
¤ 拓展阅读 ¤
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。