Liang' Blog

Illustration of a bird flying.
  • Java线程池概述

    内容提要 最近,在公司做了几次技术分享,将slides上的内容整理成博客。本文的主要内容包括如下几个部分: 背景 Java线程池类型 线程池参数与使用实例 ThreadPoolExecutor实现 总结 本文将主要讲解ThreadPoolExecutor的使用、参数解释以及内部实现,对于ScheduedThreadPoolExecutor与ForkJoinPool只会简单提及。 一、背景 我们为什么需要使用线程池,直接new Thread岂不是很方便?如果我们在编写Demo或者开发个小型的Java应用程序,那么这种方法的确没什么问题。但是如果我们在开发大型的企业级应用,那么直接创建线程是一种糟糕的实践,会造成如下问题: 直接new Thread使创建线程的代码分散在项目各个地方,不利于维护(指代码上的) 当你的Runnable执行完毕线程无法复用造成资源浪费 直接new Thread不遍于控制线程的数量(启动多少个线程不受限制,想new就new) 那么这些问题有什么缺点呢?对于第一条是显然的。对于第二条,你可能以为创建线程的代价和创建一个对象的代价差不多,但除了创建对象外,还可能会在OS层面创建线程(这取决于JVM实现)。线程是一种宝贵的资源(每个线程有自己的调用栈、PC、IR),频繁创建销毁开销很大。对于第三条,创建大量的线程显而易见会带来昂贵的调度开销,要知道线程调度需要做保留现场、恢复现场等一些列操作。 二、Java线程池类型 为了实现不同类型的线程池,定义了三个接口:Executor、 ExecutorService 、ScheduledExecutorService接口,他们都位于java.util.concurrent包下。 Executor:能够执行Runnable的简单接口,只含有execute一个方法 ExecutorService :继承自Executor,添加了shutdown、submit、invokeAll等方法,以支持异步执行 ScheduledExecutorService:继承自ExecutorService,支持周期性地执行任务 Java线程池目前有三个实现,分别是ThreadPoolExecutor、ScheduledThreadPoolExecutor、ForkJoinPool。ThreadPoolExecutor可以根据构造方法实现不同类型的线程池(或者使用Executors类),但是不支持定时任务;ScheduledExecutorService支持定时执行;ForkJoinPool利用Fork-join框架,实现了work-stealing,对于执行时间差异很大的任务使用该类型线程池能够实现负载均衡。图1展示了他们直接的继承/实现关系。 三、线程池参数与使用实例 下面我们分别介绍这三个线程池的构造方法,这样我们才能够知道如何创建线程池。因为每种线程池都有多个构造方法,我们只介绍参数最复杂的那一个。 1. ThreadPoolExecutor 构造方法 corePoolSize: 当线程池中线程数量小于corePoolSize, 即使这些线程是空闲的,也不会被销毁。但如果调用方法allowCoreThreadTimeOut(true),表示核心线程池的线程在没有任务到达的时候,keepAliveTime时间后销毁。 maximumPoolSize:限定线程池最大数量。当线程池中线程数达到corePoolSize时,且任务队列workQueue以及满了,就会创建新线程直到数量达到maxiumPoolSize。注意,如果workQueue是一个无界队列(unbounded)时,该参数是无效的,因为你无论添加多少任务workQueue都不会满。 keepAliveTime:当线程数大于corePoolSize时,多余线程的存活时间。 unit:keepAliveTime参数的时间单位 workQueue:用于存放尚未执行任务的队列,元素必须是Runnable。workQueue必须是一个阻塞队列,例如LinkedBlockingQueue、ArrayBlockingQueue。 threadFactory:创建线程时所使用的线程工厂,默认为Executors.defaultThreadFactor。如果你想让创建的线程带有自定义name或者优先级时,可以传入自己实现的线程工厂。 handler:在某种情况下(下面会提到),无法提交任务所执行的处理策略。目前有如下内置的handler实现。 AbortPolicy 直接拒绝新任务,并抛出RejectedExecutionException异常 CallerRunsPolicy 用当前线程的execute方法执行被拒绝的任务,如果执行器已经关闭则丢弃任务 DiscardPolicy 默默地丢弃新到的任务 DiscardOldestPolicy 丢弃最老的一个未执行的任务并执行当前任务 线程池逻辑 图2描述了线程创建与入队的逻辑。如果从线程创建和入队的角度分别观察,能够整理出如下规则。 线程创建规则 当线程池中线程数量小于corePoolSize时,将会创建新线程(即使之前创建当线程处于空闲) 如果线程数量大于等于corePoolSize且小于maximumPoolSize时,只有队列已满才会创建新线程 入队规则 如果线程数量小于corePoolSize,优先创建线程而不入队…

    September 30, 2019
  • 312. 戳气球

    题目描述 有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。 求所能获得硬币的最大数量。 说明: 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 示例: 输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []   coins = 315 + 358…

    August 31, 2019
  • 174. 地下城游戏

    题目描述 一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。 有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。 为了尽快到达公主,骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 例如,考虑到如下布局的地下城,如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。 -2 (K) -3 3 -5 -10 1 10 30 -5 (P) 说明: 骑士的健康点数没有上限。 任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/dungeon-game 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DP 题目给定的数组dungeon存放了走入每个房间造成的血量变化,为了救出公主,要求到达右下角(P)时扣除外血量至少为1,因此我们可以从P点逆行回到起点K,求出起点K要求的最少血量。我们定义一个二维数组dp[|dungeon|+1][|dungeon[0]|+1],dp数组比原数组“大了一圈“,这样做能够方便我们统一地处理逻辑,否则需要判断边界条件。到达P点以后还会扣除或者增加血量,所以走过P点到达右方或下方的血量至少需要1。 图1展示了题目的例子计算dp数组后的结果。要想求出到达位置i,j需要的最少血量,那么可以从位置i+1,j与i,j+1逆推而来。例如dp[2][1]=1,dp[1][2]=5,dungeon[1][1] = -10,说明我们只需要在位置1,1有血量11,就能够到达[2][1]。还有一点要注意,血量不可能为负数。例如在2,1处能够加血30,那我们不能说到达2,1时只需要-29点血量,然后再给我加上30变成1,这是不对的,血量不能为负值。所以在计算完min(dp[i+1][j], dp[i][j+1])+dungeon[i][j]还需要对1取最大。 该解法时间复杂度为O(m*n),m与n为dungeon数组长与宽。全部代码如下:

    August 27, 2019
  • 39. 组合总和

    题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [   [2,2,2,2],   [2,3,3],   [3,5] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 在上一篇文章“代码模版-排列与组合”我们介绍了排列与组合的实现方法,在这道题中,我们将会在组合算法上进行一些修改来解这道题目。我们先观察下组合算法的实现。 在这道题目中,要求数字可以重复选取,但是上面的代码每次都会选取新的一个数字。我们将递归调用combination(arr, depth + 1, i + 1, curr, result)改成combination(arr, depth + 1, i, curr,…

    August 23, 2019
  • 代码模版 – 排列与组合

    有的时候题目想不出来,或者只能用搜索来解决(如Leetcode – 39题),我们就可以用排列/组合搜索答案。下面的排列与组合模板都使用DFS来实现,非常易懂且方便记忆。 1. 排列 方法private void permutation(int[] arr, int depth, int[] curr, boolean[] visited, List<int[]> result)实现了求arr的所有排列,并且将结果保存的result中。depth表示目前正在填充curr的第几位,visited数组记录了之前已经访问的元素。在for循环中,我们遍历每个之前没有访问过位置,并在visited标记为true,防止下一次递归调用访问同一元素。当depth达到数组arr的长度时,我们复制curr的内容到result中。 2. 组合 这里的组合指的是从n个元素中挑选c个元素,而不考虑元素的顺序。方法void combination(int[] arr, int depth, int start, int[] curr, List<int[]> result)实现了从arr中挑选|curr|个元素。depth表示我们正在填充curr的第几位,start参数表明我们从arr中第几个位置开始挑选元素。与排列算法相比,我们不需要visited数组。因为我们总是从start之后挑选元素,所以不会出现挑选重复元素的情况。

    August 22, 2019
  • 307. 区域和检索 – 数组可修改

    题目描述 给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。 update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。 示例: Given nums = [1, 3, 5] sumRange(0, 2) -> 9update(1, 2)sumRange(0, 2) -> 8说明: 数组仅可以在 update 函数下进行修改。 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/range-sum-query-mutable著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Prefix sum 我们可以预先计算出前缀和存储在数组中,prefix[i] = num[0]+…+nums[i]。这样,当需要求得范围[i,j]的和时,我们可以通过prefix[j]-prefix[i-1]在O(1)的时间计算出结果。但是当nums[i]发生更新操作,那么我们不得不重新计算prefix[i]之后的前缀和,时间复杂度为O(n)。 全部代码如下: 解法2 – Fenwick Tree(树状数组) Fenwick Tree也称为树状数组,它可以在O(logn)的时间得到任意前缀和,并同时支持在O(logn)时间内支持动态单点值的修改。空间复杂度O(n)。为了实现Fenwick Tree,我们需要一个函数lowbit(x),他是用来求得数值x最低位第一个1所代表到数值,例如x = 0110,lowbit(x) = 0010; x = 0101, lowbit(x) = 0001。…

    June 28, 2019
  • 337. 打家劫舍 III

    题目描述 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。 示例 1: 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 示例 2: 输入: [3,4,5,1,3,null,1]   3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/house-robber-iii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1…

    June 24, 2019
  • 110. 平衡二叉树

    题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 https://leetcode-cn.com/problems/balanced-binary-tree/ 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/balanced-binary-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 我们就按照定义来,求得节点左右子树的高度(在实现时用的深度),如果相差不超过1,这个子树就是平衡二叉树。我们递归地对每一个节点都进行这样的判断,直到最后轮到判断跟节点。如果跟节点也满足这样的定义,那么这棵树就是平衡二叉树。 对于求得一个顶点的深度的算法,时间复杂度为O(n)。但是二叉树有n个节点,总体时间复杂度为O(n^2)。如果树是链式结构,那么空间复杂度最高,为O(n)。全部代码如下: 解法2 – Bottom-up Bottom-up算法自下而上地求得每个顶点的高度,根据左右子树的高度差判断是否平衡。如果某个顶点的左右子树的高度之差已经超过1了,那么我们也不必要继续向上判断了。这样,我们发现有任何一颗子树是不平衡的,我们就可以提前终止算法。就算了所有的子树都是平衡点,所有顶点也只扫描一次。 因此Bottom-up算法的时间复杂度O(n),空间复杂度O(n)。全部代码如下:

    June 20, 2019
  • 104. 二叉树的最大深度

    题目描述 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DFS 这是道经典的BinaryTree的模版题,我们声明函数private int helper(TreeNode node, int depth) ,当node是叶子结点时返回depth,如果node的左子树非空则递归调用helper(node.left, depth+1);当node的右子树非空,则递归调用helper(node.right, depth+1); 当node为空,则返回0。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – BFS 当然这道题也可以用BFS来做,我们需要一个队列,还有一个Map<TreeNode, Integer>用来存放节点对应的深度。如果node的左子树非空,就将它如队列,然后depth+1放入map中;右子树同理。然后还需要一个存放答案的变量ans,如果取出节点的深度大于ans就更新它,最后返回ans。 复杂度和解法1相同,但因为用到了Map导致overhead比较大,实际运行时间比解法1慢很多。全部代码如下:

    June 19, 2019
  • 133. 克隆图

    题目描述 给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。 示例: 输入: {“$id”:”1″,”neighbors”:[{“$id”:”2″,”neighbors”:[{“$ref”:”1″},{“$id”:”3″,”neighbors”:[{“$ref”:”2″},{“$id”:”4″,”neighbors”:[{“$ref”:”3″},{“$ref”:”1″}],”val”:4}],”val”:3}],”val”:2},{“$ref”:”4″}],”val”:1} 解释: 节点 1 的值是 1,它有两个邻居:节点 2 和 4 。 节点 2 的值是 2,它有两个邻居:节点 1 和 3 。 节点 3 的值是 3,它有两个邻居:节点 2 和 4 。 节点 4 的值是 4,它有两个邻居:节点 1 和 3 。 提示: 节点数介于 1 到 100 之间。 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点p 的邻居。 必须将给定节点的拷贝作为对克隆图的引用返回。 来源:力扣(LeetCode)…

    June 18, 2019
←Previous Page
1 2 3 4 … 10
Next Page→

Liang' Blog

Proudly powered by WordPress