精华内容
下载资源
问答
  • 本文将收录《剑指offer:50道金典面试题》、LeetCode上部分经典题目以及其他【据结构和算法】数面试题。 PS:持续更新中,敬请期待~~ 正    文 一、剑指offer:50道金典面试题 ...

    文章目录


    前    言

    本文将收录《剑指offer:50道金典面试题》、LeetCode上部分经典题目以及其他【据结构和算法】数面试题。

    PS:目录中有粉红色标注的题目是已经附带答案


    正    文

    一、剑指offer:50道金典面试题

    面试题1:赋值运算符函数

    在这里插入图片描述

    class CMyString
    {
    public:
    	CMyString(char* pData = NULL);
    	CMyString(const CMyString& str);
    	~CMyString(void);
    
    private:
    	char* m_pData;
    }
    

    \qquad

    解题思路
    java只能重载“+”和“+=”两个运算符,别的都不可以。

    面试题2:实现单例模式

    在这里插入图片描述
    \qquad

    解法一:饿汉式(线程安全,效率高,不能延时加载,典型的以空间换时间)
    public class Singleton {
    	private static Singleton instance = new Singleton();
     
    	// 私有化构造方法
    	private Singleton() {
     
    	}
     
    	public static Singleton getInstance() {
    		return instance;
    	}
     
    }
    

    饿汉式是典型的空间换时间,当类装载的时候就会创建类实例,不管你用不用,先创建出来,然后每次调用的时候,就不需要判断了,节省了运行时间。

    \qquad

    解法二:懒汉式(线程不安全,能延时加载,以时间换空间)
    public class Singleton {
    	//2.本类内部创建对象实例
    	private static Singleton instance = null;
     
    	/**
    	* 1.构造方法私有化,外部不能new
    	*/
    	private Singleton() {
     
    	}
     
    	//3.提供一个公有的静态方法,返回实例对象
    	public static Singleton getInstance() {
    		if (instance == null) {
    			instance = new Singleton();
    		}
    		return instance;
    	}
    }
    

    调用顺序时序图:
    在这里插入图片描述
    单例模式的懒汉式体现了缓存的思想,延时加载就是一开始不要加载资源或者数据,一直 等,等到马上就要使用这个资源的或者数据了,躲不过去了才去加载。

    懒汉式是定性的时间换空间,不加同步的懒汉式是线程不安全的,如下示例:
    在这里插入图片描述
    那么如何解决这个问题呢?
    就是接下来我们要讲的解法三——使用双重检查加锁机制实现单例模式

    \qquad

    解法三:Double CheckLock实现单例(线程安全,能延时加载,以时间换空间)——面试官期待的解法之一
    public class Singleton {
    	private volatile static Singleton instance = null;
     
    	// 私有化构造方法
    	private Singleton() {
     
    	}
     
    	public static Singleton getInstance() {
    		if (instance == null) {
    			synchronized (Singleton.class) {
    				if (instance == null) {
    					instance = new Singleton();
    				}
    			}
     
    		}
    		return instance;
    	}
    	
    }
    

    \qquad

    解法四:静态内部类实现(线程安全,效率高,可延时加载)——面试官期待的解法之一
    public class Singleton {
    	private static class SingletonHoler {
    		/**
    		 * 静态初始化器,由JVM来保证线程安全
    		 */
    		private static Singleton instance = new Singleton();
    	}
     
    	private Singleton() {
    	}
     
    	public static Singleton getInstance() {
    		return SingletonHoler.instance;
    	}
     
    }
    

    \qquad

    解法五:枚举类(线程安全,效率高,不能延时加载,可以天然的防止反射和反序列化调用)
    public enum Singleton {
    	uniqueInstance;// 定义一个枚举的元素,它 就代表了Singleton的一个实例
     
    	public void singletonOperation() {
    		// 功能处理
    		System.err.println("功能处理");
    	}
     
    }
    

    \qquad

    扩展阅读

    java 单例模式的几种实现方式(包含防止单例模式被破坏的解决方案)


    面试题3:二维数组中的查找

    在这里插入图片描述

    解题思路

    别从左到右一个一个比,先比右上角的或左下角的,如果要找的数比这个数小,剔除这一列,比较前一列的第一个数。如果大,剔除这一行,再比较该列下一个数。

    注意:如果先比左上角或右下角的是不行的。

    代码实现
    import java.util.Scanner;
     
    public class Find{
    	public static void main(String[] args){
    		int[][] array = input();
    		if(array != null){
    			System.out.println("请输入要找的数:");
    			Scanner sc = new Scanner(System.in);
    			int target = sc.nextInt();	
    			if(find(array,target) == true){
    				System.out.println("找到了!");
    			}else{
    				System.out.println("没找到!");
    			}
    		}
     
    	}
    	static int[][] input(){
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请输入二维数组行数:");
    		int rowNumber = sc.nextInt();
    		System.out.println("请输入二维数组列数:");
    		int colNumber = sc.nextInt();
    		int[][] array = new int[rowNumber][colNumber];
    		if(rowNumber != 0 && colNumber != 0){
    			for(int i=0;i<rowNumber;i++){
    				System.out.println("请输入第"+(i+1)+"行的"+(colNumber)+"个数。");
    				for(int j=0;j<colNumber;j++){
    					array[i][j] = sc.nextInt();
    				}
    			}
    			return array;
    		}else {
    			System.out.println("输入有误!数组为空!");
    			return null;
    		}
    	}
    	static boolean find(int[][] array,int target){
    		int row = 0;
    		int col = array[0].length-1;
    		while(row<array.length && col>=0){
    			if(array[row][col] == target){
    				return true;
    			}
    			else if(array[row][col] > target){
    				col--;
    			}else{
    				row++;
    			}
    		}
    		return false;
    	}
    }
    

    面试题4:替换空格

    在这里插入图片描述


    面试题5:反向打印链表

    在这里插入图片描述


    面试题6:重建二叉树

    在这里插入图片描述


    面试题7:用两个栈实现队列(附带用两个队列实现栈)

    在这里插入图片描述
    \qquad

    解题思路
    添加元素即压入一个栈s1,删除元素的话,把s1中的元素按顺序先弹出再压入栈s2中,这是弹出栈s2的元素就能实现先进先出了。

    \qquad

    代码实现
    public class CQueue {
    	private Stack<Integer> stack1 = new Stack<>();
    	private Stack<Integer> stack2 = new Stack<>();
    	
    	public void appendTail(int elem){
    		//添加元素就直接向stack1添加
    		stack1.push(elem);
    		System.out.println("stack1:" + stack1.toString());
    	}
    	public void deleteHead(){
    		//删除分三种情况:1,stack2不空,直接从它里头弹出。2,stack2空,stack1不空,把1中先弹再压到2,再从2弹出。3,两都空。
    		if(!stack2.isEmpty()){
    			stack2.pop();
    		}else if(!stack1.isEmpty()){
    			while(!stack1.isEmpty()){
    				stack2.push(stack1.pop());
    			}
    			stack2.pop();
    		}else{
    			System.out.println("两个栈都空了");
    		}
    		System.out.println("stack1:" + stack1.toString());
    		System.out.println("stack2:" + stack2.toString());
    	}
    	public static void main(String[] args) {
    		CQueue test = new CQueue();
    		test.appendTail(1);
    		test.appendTail(2);
    		test.appendTail(3);
    		test.deleteHead();
    		test.deleteHead();
    		test.appendTail(4);
    		test.deleteHead();
    	}
    }
    

    \qquad

    相关题:用两个队列实现栈

    \qquad

    解题思路
    添加元素即向一个队列q1添加元素,删除元素的话,把q1的元素按顺序出队然后入队到q2,最后q1剩下一个元素,就是要出栈的元素,再添加元素的话,向非空的队列添加。

    \qquad

    代码实现
    import java.util.Queue;
    import java.util.LinkedList;
     
    //以下是相关题,两个队列实现栈。
    public class CStack {
    	//是LinkedList类实现了Queue接口
    	private static Queue<Integer> queue1 = new LinkedList<>();
    	private static Queue<Integer> queue2 = new LinkedList<>();
    	
    	private void appendTail(int elem){
    		//Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。
    		//它们的优点是通过返回值可以判断成功与否,add()和remove()方法在失败的时候会抛出异常。 
    		//如果要使用前端而不移出该元素,使用element()或者peek()方法。
    		//这里是向非空的队列里添加值。都为空的话向队列1添加。
    		if(!queue2.isEmpty()){
    			queue2.offer(elem);
    		}else{
    			queue1.offer(elem);
    		}
    		System.out.println("queue1:" + queue1.toString());
    		System.out.println("queue2:" + queue2.toString());
    	}
    	private void deleteHead(){
    		//一个表示空队列,一个表示非空队列
    		Queue<Integer> emptyQueue = queue1;
    		Queue<Integer> notEmptyQueue = queue2;
    		if(!emptyQueue.isEmpty()){
    			emptyQueue = queue2;
    			notEmptyQueue = queue1;
    		}
    		//除了非空队列的最后一个元素,别的都按顺序移到空队列
    		while(notEmptyQueue.size()!=1){
    			emptyQueue.offer(notEmptyQueue.poll());
    		}
    		//删除刚才留下的最后一个元素
    		notEmptyQueue.poll();
    		
    		System.out.println("queue1:" + queue1.toString());
    		System.out.println("queue2:" + queue2.toString());
    	}
     
    	public static void main(String[] args) {
    		CStack test = new CStack();
    		test.appendTail(1);
    		test.appendTail(2);
    		test.appendTail(3);
    		test.deleteHead();
    		test.appendTail(4);
    		test.deleteHead();
    	}
    }
    

    面试题8:旋转数组的最小数字

    在这里插入图片描述


    \qquad

    面试题9:斐波那契数列

    在这里插入图片描述
    \qquad

    被面试官鄙视的解法
    public class Fibonacci {
        /**
         * 递归实现
         */
        public static long fib_rec(int n){
            int[] arr = {0,1};
            if(n <= 2){
                return arr[n-1];
            }
            return fib_rec(n-1)+fib_rec(n-2);
        }
    }
    

    \qquad

    面试官期待的解法
    public class Fibonacci {
         /**
         * 数组+for循环实现(其实就是 动态规划 思想)
         */
        public static long fib_for(int n){
            int[] arr = {0,1};
            if(n < 2){
               return arr[n];
            }
            long first,sencond,res;
            first=0;
            sencond=1;
            res=0;
            for (int i=2;i<n;i++){
                res = first + sencond;
                first = sencond;
                sencond = res;
            }
            return res;
        }
    }
    

    \qquad
    在这里插入图片描述

    这个题目可以使用动态规划来求解,可以参考我的 动态规划? so easy!!!
    这篇文章里的 【题目实战】中的 【爬楼梯】的例子。


    面试题10:二进制中 1 的个数

    在这里插入图片描述


    面试题11:数值的整数次方

    在这里插入图片描述


    面试题12:打印 1 到最大的 n 位数

    在这里插入图片描述


    面试题13:在O(1)时间删除链表结点

    在这里插入图片描述


    面试题14:调整数组顺序使数组中奇数位于偶数前

    在这里插入图片描述


    面试题15:链表中倒数第K个结点

    在这里插入图片描述


    面试题16:反转链表

    在这里插入图片描述


    面试题17:合并两个排序的链表

    在这里插入图片描述
    在这里插入图片描述


    面试题18:树的子结构

    在这里插入图片描述


    面试题19:二叉树的镜像

    在这里插入图片描述


    面试题20:顺时针打印矩阵

    在这里插入图片描述
    在这里插入图片描述


    面试题21:包含 min 函数的栈

    在这里插入图片描述


    面试题22:栈的压人、弹出序列

    在这里插入图片描述


    面试题23:从上往下打印二叉树

    在这里插入图片描述


    面试题24:二叉搜索树的后序遍历序列

    在这里插入图片描述


    面试题25:二叉树中和为某一值的路径

    在这里插入图片描述


    面试题26:复杂链表的复制

    在这里插入图片描述


    面试题27:二叉搜索树和双向链表

    在这里插入图片描述


    面试题28:字符串的排序

    在这里插入图片描述


    面试题29:数组中出现次数超过一半的数字

    在这里插入图片描述


    面试题30:最小的 k 个数

    在这里插入图片描述


    面试题31:连续子数组的最大和(动态规划思想)

    在这里插入图片描述
    这个题目可以使用动态规划来求解,可以参考我的 动态规划? so easy!!!
    这篇文章里的 【题目实战】中的 【最大子序和】的例子。


    面试题32:从1到n整数中1出现的次数

    在这里插入图片描述


    面试题33:把数组排成最小的数

    在这里插入图片描述


    面试题34:丑数

    在这里插入图片描述


    面试题35:第一个只出现一次的字符

    在这里插入图片描述


    面试题36:数组中的逆序对

    在这里插入图片描述


    面试题37:两个链表的第一个公共节点

    在这里插入图片描述


    面试题38:数字在排序数组中出现的次数

    在这里插入图片描述


    面试题39:二叉树的深度

    在这里插入图片描述


    面试题40:数组中只出现一次的数字

    在这里插入图片描述


    面试题41:和为s的两个数字与和为s的连续正数序列

    在这里插入图片描述

    在这里插入图片描述


    面试题42:翻转单词顺序与左旋转字符串

    在这里插入图片描述
    在这里插入图片描述


    面试题43:n个骰子的点数(动态规划)

    在这里插入图片描述


    面试题44:扑克牌的顺子

    在这里插入图片描述


    面试题45:圆圈中最后剩下的数字(约瑟夫环问题)

    在这里插入图片描述


    面试题46:求1+2+…+n

    在这里插入图片描述


    面试题47:不用加减乘除做加法(位运算)

    在这里插入图片描述


    面试题48:设计一个不能被继承的类(final修饰 )


    面试题49:字符串转整数


    面试题50:二叉树两个结点的最低公共祖先


    二、LeetCode上经典题目

    三、其他面试题(理论知识)

    1.说说常见的集合有哪些。

    Map 接口和Collection 接口是所有集合类框架的父接口:
    Collcetion 接口的子接口包括:Set 接口和List 接口。
    Map 接口的实现类主要有:HashMap、HashTable、ConcurrentHashMap 以及Properties
    等。
    Set 接口的实现类主要有:HashSet、TreeSet、LinkedHashSet 等。
    List 接口的实现类主要有:ArrayList、LinkedList、Stack 以及 Vector 等。

    2. HashMap 与 HashTable 的区别。

    主要有以下几点区别。
    HashMap 没有考虑同步,是线程不安全的;HashTable 在关键方法(put、get、contains、
    size 等)上使用了Synchronized 关键字,是线程安全的。
    HashMap 允许Key/Value 都为null,后者Key/Value 都不允许为null。
    HashMap 继承自AbstractMap 类;而HashTable 继承自Dictionary 类。
    在jdk1.8 中,HashMap 的底层结构是数组+链表+红黑树,而HashTable 的底层结构是
    数组+链表。
    HashMap 对底层数组采取的懒加载,即当执行第一次put 操作时才会创建数组;而
    HashTable 在初始化时就创建了数组。
    HashMap 中数组的默认初始容量是 16 ,并且必须是 2 的指数倍数,扩容时
    newCapacity=2oldCapacity;而HashTable 中默认的初始容量是11,并且不要求必须是2 的
    指数倍数,扩容时newCapacity=2
    oldCapacity+1。 在hash 取模计算时,HashTable 的模数一般为素数,简单的做除取模结果会更为均匀,
    int index = (hash & 0x7FFFFFFF) % tab.length;
    HashMap 的模数为2 的幂,直接用位运算来得到结果,效率要大大高于做除法,i = (n - 1) & hash。

    3. HashMap 是怎么解决哈希冲突的

    哈希冲突:当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们
    就把它叫做哈希碰撞。
    在Java 中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址
    容易,插入和删除困难。链表的特点是:寻址困难,但插入和删除容易。所以我们将数组和
    链表结合在一起,发挥两者的优势,使用一种叫做链地址法的方式来解决哈希冲突。这样我
    们就可以拥有相同哈希值的对象组织成的一个链表放在hash 值对应的bucket 下,但相比
    Key.hashCode() 返回的 int 类型,我们 HashMap 初始的容量大小
    DEFAULT_INITIAL_CAPACITY = 1 << 4(即2 的四次方为16)要远小于int 类型的范围,所
    以我们如果只是单纯的使用hashcode 取余来获取对应位置的bucket,这将会大大增加哈希
    碰撞的几率,并且最坏情况下还会将HashMap 变成一个单链表。所以肯定要对hashCode 做
    一定优化。
    来看HashMap 的hash()函数。上面提到的问题,主要是因为如果使用hashCode 取余,
    那么相当于参与运算的只有hashCode 的低位,高位是没有起到任何作用的,所以我们的思
    路就是让**hashCode 取值出的高位也参与运算,进一步降低hash 碰撞的概率,使得数据分
    布更平均,我们把这样的操作称为扰动,在JDK 1.8 中的hash()函数相比在JDK 1.7 中的4 次
    位运算,5 次异或运算(9 次扰动),在1.8 中,只进行了1 次位运算和1 次异或运算(2 次
    扰动),更为简洁了。两次扰动已经达到了高低位同时参与运算的目的,提高了对应数组存
    储下标位置的随机性和均匀性。
    通过上面的链地址法(使用散列表)和扰动函数,数据分布更为均匀,哈希碰撞也减少
    了。但是当HashMap 中存在大量的数据时,假如某个bucket 下对应的链表中有n 个元素,
    那么遍历时间复杂度就变成了O(n),针对这个问题,JDK 1.8 在HashMap 中新增了红黑树的
    数据结构,进一步使得遍历复杂度降低至O(logn)。
    简单总结一下HashMap 是如何有效解决哈希碰撞的:
    使用链地址法(散列表)来链接拥有相同hash 值的元素;
    使用2 次扰动(hash 函数)来降低哈希冲突的概率,使得概率分布更为均匀;
    引入红黑树进一步降低遍历的时间复杂度。

    4. HashMap 中为什么数组长度要保证 2 的幂次方。

    只有当数组长度为 2 的幂次方时,h&(length-1)才等价于 h%length,可以用位运算来
    代替做除取模运算,实现了 key 的定位,2 的幂次方也可以减少冲突次数,提高 HashMap 的
    查询效率;
    当然,HashTable 就没有采用 2 的幂作为数组长度,而是采用素数。素数的话是用简
    单做除取模方法来获取下标 index,而不是位运算,效率低了不少,但分布也很均匀。

    5.什么是 Java 集合的快速失败机制“fail-fast”, 以及安全失败“fail-safe”。

    “fail-fast”是Java 集合的一种错误检测机制,当多个线程对集合进行结构上的改变
    的操作时,有可能会产生fail-fast 机制。
    例如:假设存在两个线程(线程1、线程2),线程1 通过Iterator 在遍历集合A 中的
    元素,在某个时候线程2 修改了集合A 的结构(是结构上面的修改,而不是简单的修改集合
    元素的内容),那么这个时候程序就会抛出ConcurrentModificationException 异常,从而
    产生fail-fast 机制。
    原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个modCount 变
    量。集合在被遍历期间如果内容发生变化,就会改变odCount的值。每当迭代器使用
    hashNext()/next()遍历下一个元素之前,都会检测modCount 变量是否为expectedmodCount
    值,是的话就返回遍历;否则抛出异常ConcurrentModification,终止遍历。
    Java.util 包下的集合类都是快速失败机制,不能在多线程下发生并修改(迭代
    过程中被修改)。
    与“fail-fast”对应的是“fail-safe”。
    采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先copy 原
    有集合内容,在拷贝的集合上进行遍历。由于迭代时是对原集合的拷贝的值进行遍历,所以在
    遍历过程中对原集合所作的修改并不能被迭代器检测到 , 所以不会触发
    ConcurrentModificationException 异常。
    基于拷贝内容的迭代虽然避免了ConcurrentModificationException 异常,但同样地,
    迭代器并不能访问到修改后的内容,简单来说,迭代器遍历的是开始遍历那一刻拿到的集合
    拷贝,在遍历期间原集合发生的修改迭代器行为是不知道的。
    Java.util.concurrent 包下的容器都是安全失败的,可以在多线程下并发使用,并发修
    改。

    6. ArrayList 和 LinkedList 的区别。

    主要有以下几点区别:
    LinkedList 实现了List 和Deque 接口,一般称为双向链表;ArrayList 实现了List 接
    口,是动态数组。
    LinkedList 在插入和删除数据时效率更高,ArrayList 在查找某个index的数据时效率
    更高。
    LinkedList 比ArrayList 需要更多内存。

    7. HashSet 是如何保证数据不可重复的。

    HashSet 的底层其实就是HashMap,只不过HashSet 是实现了Set 接口,并且把数据作
    为Key 值,而Value 值一直使用一个相同的虚值来保存。由于ashMap 的K 值本身就不允许
    重复,并且在HashMap 中如果K/V 相同时,会用新的V 覆盖掉旧的V,然后返回旧的V,那么
    在HashSet 中执行这一句话始终会返回一个false,导致插入失败,这样就保证了数据的不
    可重复性。

    8. BlockingQueue 是什么。

    Java.util.concurrent.BlockingQueue 是一个队列,在进行检索或移除一个元素的时
    候,它会等待队列变为非空;当添加一个元素时,它会等待队列中的可用空间。BlockingQueue
    接口是Java 集合框架的一部分,主要用于实现生产者-消费者模式。这样我们就不需要担心
    等待生产者有可用的空间,以及消费者有可用的对象。因为它们都在BlockingQueue 的实现
    类中被处理了。
    Java 提供了几种 BlockingQueue 的实现,比如 ArrayBlockingQueue 、
    LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue 等。

    9. JDK8 中 HashMap 为什么选用红黑树而不是 AVL 树

    在平常我们用HashMap的时候,HashMap里面存储的key是具有良好的hash算法的key(比
    如String、Integer等包装类),冲突几率自然微乎其微,此时链表几乎不会转化为红黑树,
    但是当key为我们自定义的对象时,我们可能采用了不好的hash算法,使HashMap中key的冲
    突率极高,但是这时HashMap为了保证高速的查找效率,引入了红黑树来优化查询了。
    因为从时间复杂度来说,链表的查询复杂度为o(n);而红黑树的复杂度能达到o(logn);
    比如若hash算法写的不好,一个桶中冲突1024个key,使用链表平均需要查询512次,但是红
    黑树仅仅10次,红黑树的引入保证了在大量hash冲突的情况下,HashMap还具有良好的查询
    性能。
    红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于
    插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的
    不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡
    有时候代价较大,所以效率不如红黑树。

    10. JDK8 中 HashMap 链表转红黑树的阈值为什么选 8?

    HashMap 在jdk1.8 之后引入了红黑树的概念,表示若桶中链表元素超过8 时,会自动
    转化成红黑树;若桶中元素小于等于6 时,树结构还原成链表形式。
    HashMap源码作者通过泊松分布算出,当桶中结点个数为8时,出现的几率是亿分之6的,
    因此常见的情况是桶中个数小于8的情况,此时链表的查询性能和红黑树相差不多,因为红黑
    树的平均查找长度是log(n),长度为8 的时候,平均查找长度为3,如果继续使用链表,平
    均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速
    度也很快的,但是转化为树结构和生成树的时间并不会太短。
    亿分之6这个几乎不可能的概率是建立在良好的hash算法情况下,例如String,Integer
    等包装类的hash算法,如果一旦发生桶中元素大于8,说明是不正常情况,可能采用了冲突
    较大的hash算法,此时桶中个数出现超过8的概率是非常大的,可能有n个key冲突在同一个
    桶中,这个时候就必要引入红黑树了。
    另外,上下阈值选择6 和8 的情况下,中间有个差值7 可以防止链表和树之间频繁的转
    换。假设一下,如果设计成链表个数超过8 则链表转换成树结构,链表个数小于8 则树结构
    转换成链表,如果一个HashMap 不停的插入、删除元素,链表个数在8 左右徘徊,就会频繁
    的发生树转链表、链表转树,效率会很低。

    11. 说下几种常见的排序算法及其复杂度

    a. 快速排序:
    i. 原理:快速排序采⽤用的是⼀种分治的思想,它先找⼀个基准数(⼀般选择第⼀个值),
    然后将⽐这个基准数⼩的数字都放到它的左边,然后再递归调⽤,分别对左右两边快速排序,
    直到每⼀边只有⼀个数字.整个排序就完成了.
    1.选定⼀个合适的值(理想情况中值最好,但实现中⼀般使⽤用数组第⼀个值),称为
    “枢轴”(pivot)。
    2.基于这个值,将数组分为两部分,较⼩的分在左边,较⼤的分在右边。
    3.可以肯定,如此⼀轮下来,这个枢轴的位置⼀定在最终位置上。
    4.对两个⼦数组分别重复上述过程,直到每个数组只有⼀个元素。
    5.排序完成。
    ii. 复杂度:O(n)
    b. 冒泡排序:
    i. 原理:冒泡排序其实就是逐⼀⽐较交换,进⾏⾥外两次循环,外层循环为遍历所有数
    字,逐个确定每个位置,⾥层循环为确定了了位置后,遍历所有后面没有确定位置的数字,与
    该位置的数字进⾏⽐较,只要⽐该位置的数字⼩,就和该位置的
    数字进⾏交换.
    ii. 复杂度:O(n^2),最佳时间复杂度为O(n)
    c. 直接插⼊入排序:
    i. 原理:直接插⼊入排序是将从第⼆个数字开始,逐个拿出来,插⼊到之前排好序的数
    列列⾥.
    ii. 复杂度:O(n^2),最佳时间复杂度为O(n)
    d. 直接选择排序:
    i. 原理:直接选择排序是从第⼀个位置开始遍历位置,找到剩余未排序的数据⾥里里最 ⼩的,找到最⼩的后,再做交换。
    ii. 复杂度:O(n^2)

    12. Hashmap 什么时候进行扩容呢?

    当 hashmap 中的元素个数超过数组大小 loadFactor 时,就会进行数组扩容,
    loadFactor 的默认值为 0.75,也就是说,默认情况下,数组大小为 16,那么当 hashmap 中
    元素个数超过 160.75=12 的时候,就把数组的大小扩展为 216=32,即扩大一倍,然后重新
    计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知
    hashmap 中元素的个数,那么预设元素的个数能够有效的提高 hashmap 的性能。
    比如说,我们有 1000 个元素 new HashMap(1000), 但是理论上来讲 new HashMap(1024)
    更合适,不过上面已经说过,即使是 1000,hashmap 也自动会将其设置为 1024。 但是 new
    HashMap(1024) 还不是更合适的,因为 0.75*1000 < 1000, 也就是说为了让 0.75 * size >
    1000, 我们必须这样 new HashMap(2048) 才最合适,既考虑了 & 的问题,也避免了 resize
    的问题。

    13. HashSet 和 TreeSet 有什么区别?

    HashSet 是由一个 hash 表来实现的,因此,它的元素是无序的。
    TreeSet 是由一个树形的结构来实现的,它里面的元素是有序的。

    14. LinkedHashMap 的实现原理?

    LinkedHashMap 也是基于 HashMap 实现的,不同的是它定义了一个 Entry header,这
    个 header 不是放在 Table 里,它是额外独立出来的。
    LinkedHashMap 通过继承 hashMap 中 的 Entry, 并添加两个属性 Entry
    before,after, 和 header 结合起来组成一个双向链表,来实现按插入顺序或访问顺序排
    序。LinkedHashMap 定义了排序模式 accessOrder,该属性为 boolean 型变量,对于访问
    顺序,为 true;对于插入顺序,则为 false。一般情况下,不必指定排序模式,其迭代顺
    序即为默认为插入顺序。

    15. 什么是迭代器 (Iterator)?

    Iterator 接口提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返
    回迭代 器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素, 但是不可以
    直接调用集合的 remove(Object Obj) 删除,可以通过迭代器的 remove() 方法删除。

    16. Iterator 和 ListIterator 的区别是什么?

    下面列出了他们的区别:
    Iterator 可用来遍历 Set 和 List 集合,但是 ListIterator 只能用来遍历 List。
    Iterator 对集合只能是前向遍历,ListIterator 既可以前向也可以后向。
    ListIterator 实现了 Iterator 接口,并包含其他的功能,比如:增加元素,替换元
    素,获取前一个和后一个元素的索引,等等。

    17. Collection 和 Collections 的区别。

    collection 是集合类的上级接口, 继承与它的接口主要是 set 和 list。
    collections 类是针对集合类的一个帮助类. 它提供一系列的静态方法对各种集合的
    搜索, 排序, 线程安全化等操作。

    \qquad

    总    结

    本文主要汇总了《剑指offer》50道金典面试题,及部分LeetCode上经典题目。

    PS 答案还在整理中,敬请期待~~

    展开全文
  • Java实现:HMM+维特比算法词性标注

    千次阅读 多人点赞 2020-10-18 09:40:42
    除了用jieba等分词词性标注工具,不如自行写一个算法实现同样的功能,下面将详细介绍Java实现的HMM+维特比算法实现词性标注。在给定的单词发射矩阵和词性状态转移矩阵,完成特定句子的词性标注

    目录

    一、前言:词性标注

    二、经典维特比算法(Viterbi)

    三、算法实现

    四、完整代码

    五、效果演示:

    六、总结


    一、前言:词性标注

    词性标注(Part-Of-Speech tagging, POS tagging),是语料库语言学中将语料库中单词的词性按其含义和上下文内容进行标记的文本数据处理技术。词性标注可以由人工或特定算法完成,使用机器学习(machine learning)方法实现词性标注是自然语言处理(NLP)的研究内容。常见的词性标注算法包括隐马尔可夫模型(Hidden Markov Model, HMM)、条件随机场(Conditional random fields, CRFs)等。

    在进入本篇算法的应用和实践之前,建议学习以下两篇内容,会有更好更容易的理解。

    1、隐马尔可夫模型(HMM)来龙去脉(一)(https://blog.csdn.net/Charzous/article/details/108111860)

    2、隐马尔可夫模型(HMM)来龙去脉(二)(https://blog.csdn.net/Charzous/article/details/108111860)

    本篇实践的目标:

    除了用jieba等分词词性标注工具,不如自行写一个算法实现同样的功能,这个过程可以对理论知识更好地理解和应用。下面将详细介绍使用HMM+维特比算法实现词性标注。在给定的单词发射矩阵和词性状态转移矩阵,完成特定句子的词性标注。

    二、经典维特比算法(Viterbi)

    词性标注使用隐马尔可夫模型原理,结合维特比算法(Viterbi),具体算法伪代码如下:

    维特比算法正是解决HMM的三个基本问题中的第二个问题:在给定的观察序列中,找出最优的隐状态序列。应用在词性标注上,就是找到概率最大化的单词的词性。

    下面是对维特比算法更加容易的解释:

    1. 观察序列长度 T,状态个数N
    2. for 状态s from 1 to N:do
    3.     //计算每个状态的概率,相当于计算第一观察值的隐状态t=1
    4.      v[s,1] = a(0,s)*b(O1|s) //初始状态概率 * 发射概率
    5.     //回溯保存最大概率状态
    6.     back[s,1]=0
    7. //计算每个观察(词语)取各个词性的概率,保存最大者
    8. for from 观察序列第二个 to T do:
    9.     for 状态s from 1 to N:do
    10.     //当前状态由前一个状态*转移*发射(该状态/词性下词t的概率),保存最大者
    11.       v[s,t]=max v[i,t-1]*a[i,s]*b(Ot | s)
    12.       //保存回溯点,该点为前一个状态转移到当前状态的最大概率点
    13.       back[s,t]=arg{1,N} max v[i,t-1]*a(i,s)
    14.  //最后
    15.   v[T]=max v[T]
    16.   back[T] = arg{1,N} max v[T]
    17.  //回溯输出隐状态序列

    三、算法实现

    第一步,拆分算法计算问题,计算状态转移概率矩阵和符号发射概率矩阵方法:

    根据给出的单词出现次数和词性状态矩阵,使用computeProp()方法计算得到发射概率矩阵和状态转移矩阵。

    public void computeProp(float[][] A) {//计算概率矩阵
            int i, j;
            float[] t = new float[A.length];
            //平滑数据,对数组每个元素值加一
            for (i = 0; i < A.length; i++) {
                for (j = 0; j < A[i].length; j++) {
                    A[i][j] += 1;
                    t[i] += A[i][j];
                }
            }
            //计算当前元素在该行中的概率
            for (i = 0; i < A.length; i++)
                for (j = 0; j < A[i].length; j++)
                    A[i][j] /= t[i];
    
        }

    得到状态转移概率矩阵如下:

     

    得到符号发射概率矩阵如下:

    第二步,核心算法。本程序的关键部分是维特比算法的实现,计算得到最大概率的隐状态,然后保存最佳状态转移位置。对于每个观察值,先计算对应的可能的隐状态。

    public int[] Viterbi(float[][] A, float[][] B, String[] O,double[] init) {
            int back[][] = new int[A.length][O.length];
            float V[][] = new float[A.length][O.length];
            int i, s, k, t;
    
            for (i = 0; i < A.length; i++) {
                V[i][0] = (float) (init[i] * B[i][0]);
                back[i][0] = i;
            }
            //计算每个观察值的取隐状态中的最大概率
            for (t = 1; t < O.length; t++) {
                int[][] path = new int[A.length][O.length];
                //遍历每个隐状态,计算状态转移到当前状态的概率,得到最大概率状态
                for (s = 0; s < A.length; s++) {
                    float maxSProb = -1;
                    int preS = 0;
                    for (i = 0; i < A.length; i++) {
                        float prob = V[i][t - 1] * A[i][s] * B[s][t];//B[s][t]为隐状态s到观察值t的发射概率
                        if (prob > maxSProb) {
                            maxSProb = prob;
                            preS = i;
                        }
                    }
                    //保存该状态的最大概率
                    V[s][t] = maxSProb;
                    //记录路径
                    System.arraycopy(back[preS],0,path[s],0,t);
                    path[s][t]=s;//最大概率状态转移记录
                }
                back=path;//更新最优路径
            }
    
            //回溯路径,找到最后状态
            float maxP = -1;
            int lastS = 0;
            for (s = 0; s < A.length; s++) {
                if (V[s][O.length - 1] > maxP) {
                    maxP = V[s][O.length - 1];
                    lastS = s;
                }
            }
            return back[lastS];//返回最佳路径
        }

     以上是维特比算法,重要的代码语句解析可见注释。算法实现了将待标注句子使用维特比算法计算最大概率,得到最佳路径。

    网上大部分使用了python实现该算法,python写起来简单,所以我尝试使用java实现,期间遇到了一些小问题,后来不断debug解决问题。得到正确的java编写的维特比算法。

     

    四、完整代码

    
    
    /*
     *  hmm_viterbi.java
     * Copyright (c) 2020-10-17
     * author : Charzous
     * All right reserved.
     */
    
    public class hmm_viterbi {
    
        public int[] Viterbi(float[][] A, float[][] B, String[] O) {
            int back[][] = new int[A.length][O.length];
            float V[][] = new float[A.length][O.length];
            double[] init = {0.2, 0.1, 0.1, 0.2, 0.3, 0.1};
            int i, s, k, t;
    
            for (i = 0; i < A.length; i++) {
                V[i][0] = (float) (init[i] * B[i][0]);
                back[i][0] = i;
            }
            //计算每个观察值的取隐状态中的最大概率
            for (t = 1; t < O.length; t++) {
                int[][] path = new int[A.length][O.length];
                //遍历每个隐状态,计算状态转移到当前状态的最大概率
                for (s = 0; s < A.length; s++) {
                    float maxSProb = -1;
                    int preS = 0;
                    for (i = 0; i < A.length; i++) {
                        float prob = V[i][t - 1] * A[i][s] * B[s][t];//B[s][t]为隐状态s到观察值t的发射概率
                        if (prob > maxSProb) {
                            maxSProb = prob;
                            preS = i;
                        }
                    }
                    //保存该状态的最大概率
                    V[s][t] = maxSProb;
                    //记录路径
                    System.arraycopy(back[preS],0,path[s],0,t);
                    path[s][t]=s;
                }
                back=path;
            }
    
    
            //回溯路径
            float maxP = -1;
            int lastS = 0;
            for (s = 0; s < A.length; s++) {
                if (V[s][O.length - 1] > maxP) {
                    maxP = V[s][O.length - 1];
                    lastS = s;
                }
            }
            return back[lastS];
        }
    
        public void computeProp(float[][] A) {
            int i, j;
            float[] t = new float[A.length];
            //平滑数据,对数组每个元素值加一
            for (i = 0; i < A.length; i++) {
                for (j = 0; j < A[i].length; j++) {
                    A[i][j] += 1;
                    t[i] += A[i][j];
                }
            }
            //计算当前元素在该行中的概率
            for (i = 0; i < A.length; i++)
                for (j = 0; j < A[i].length; j++)
                    A[i][j] /= t[i];
    
            System.out.println();
    //        for (i = 0; i < A.length; i++) {
    //            for (j = 0; j < A[i].length; j++)
    //                System.out.print(A[i][j] + " ");
    //            System.out.println();
    //        }
    
        }
    
        public static void main(String[] args) {
            //状态转移矩阵
            float A[][] = {{0, 0, 0, 48636, 0, 19}, {1973, 0, 426, 187, 0, 38}, {43322, 0, 1325, 17314, 0, 185}, {1067, 3720, 42470, 11773, 614, 21392}, {6072, 42, 4758, 1476, 129, 1522}, {8016, 75, 4656, 1329, 954, 0}};
            //发射矩阵
            float B[][] = {{0, 0, 0, 0, 0, 0, 69016, 0}, {0, 10065, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 5484, 0, 0, 0, 0}, {10, 0, 36, 0, 382, 108, 0, 0}, {43, 0, 133, 0, 0, 4, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 48809}};
    
            int i, j;
            //语料库词语
            String[] word = {"bear", "is", "move", "on", "president", "progress", "the", "."};
            //待标注句子
            String O[] = {"The", "bear", "is", "on", "the", "move", "."};
            //语料库词性
            String Q[] = {"/AT ", "/BEZ ", "/IN ", "/NN ", "/VB ", "/PERIOD "};
            String seq="Bear move on the president .";
            String Os[]=seq.split(" ");
            for (String w:O)
                System.out.println(w);
    
            float emission[][] = new float[B.length][O.length];
    
            hmm_viterbi hmmViterbi = new hmm_viterbi();
            hmmViterbi.computeProp(A);
    
            //计算观察序列的转移矩阵
            //根据待标注句子的词计算出每个单词的出现次数矩阵
            for (i = 0; i < O.length; i++) {
                int r = 0;
                for (int t = 0; t < word.length; t++) {
                    if (O[i].equalsIgnoreCase(word[t]))
                        r = t;
                }
                for (j = 0; j < B.length; j++)
                    emission[j][i] = B[j][r];
            }
            hmmViterbi.computeProp(emission);
            int path[];
            path=hmmViterbi.Viterbi(A, emission, O);
    
            for (i=0;i<O.length;i++){
                System.out.print(O[i]+Q[path[i]]);
            }
    
    //        for (int p:path)
    //            System.out.print(p+" ");
    
        }
    }

    五、效果演示:

    对于本实验的词性标注,简单设计了交互界面,方面测试不同句子的标注结果。在给定的测试句子”The bear is on the move .”上,实验结果如下:

    The/AT bear/NN is/BEZ on/IN the/AT move/NN ./PERIOD

    然后根据语料库自己造了一个句子,仅供测试用:”The president is bear .”实验结果:The/AT president/NN is/IN bear/NN ./PERIOD

    感觉还可以,当然这只是一个例子,更确切需要更大的语料库。

    六、总结

    本篇详细介绍Java实现的HMM+维特比算法实现词性标注。在给定的单词发射矩阵和词性状态转移矩阵,完成特定句子的词性标注。这个任务可以在刚接触HMM和维特比算法进行词性标注作为实践,为之后实现特定语料库的词性标注铺垫。在完成本任务时,java编程实现算法时遇到了一些的问题,如:最佳路径的保存,回溯路径的返回。经过了一段时间的debug,实现了最基本的算法对句子进行词性标注。完成这个任务后,对HMM+Viterbi 算法的词性标注有了更深刻的理解,之后准备完成第三个任务:基于人民日报数据集的中文词性标注,可以对该算法进行更实际的应用,加深知识的理解。


    我的CSDN博客:https://blog.csdn.net/Charzous/article/details/109138830

    展开全文
  • TF-IDF(term frequency–inverse document frequency)是一种用于信息检索与数据挖掘的常用加权技术。TF意思是词频(Term Frequency),IDF意思是逆文本频率指数(Inverse Document Frequency)。
  • 该标记器是使用 Viterbi 算法Java 编写的。 评估脚本是用 Python 编写的,由哥伦比亚大学自然语言处理 (COMS 4705) 教授 Michael Collins 提供(连同初始数据)。 运行步骤 测试都在每个班级的主要内容中。 但是...
  • java GC算法

    2019-03-09 18:19:12
    然而在传统的C/C++等要求显式释放内存的编程语言中,记得在合适的时候释放内存是一个很有难度的工作,因此Java等编程语言都提供了基于垃圾回收算法的内存管理机制: 垃圾内存回收算法 常见的垃圾回收算法有引用计数...

    一般来说,程序使用内存的方式遵循先向操作系统申请一块内存,使用内存,使用完毕之后释放内存归还给操作系统。然而在传统的C/C++等要求显式释放内存的编程语言中,记得在合适的时候释放内存是一个很有难度的工作,因此Java等编程语言都提供了基于垃圾回收算法的内存管理机制:

    垃圾内存回收算法

    常见的垃圾回收算法有引用计数法(Reference Counting)、标注并清理(Mark and Sweep GC)、拷贝(Copying GC)和逐代回收(Generational GC)等算法,其中Android系统采用的是标注并删除和拷贝GC,并不是大多数JVM实现里采用的逐代回收算法。由于几个算法各有优缺点,所以在很多垃圾回收实现中,常常可以看到将几种算法合并使用的场景,本节将一一讲解这几个算法。

    引用计数回收法(Reference Counting GC)

    引用计数法的原理很简单,即记录每个对象被引用的次数。每当创建一个新的对象,或者将其它指针指向该对象时,引用计数都会累加一次;而每当将指向对象的指针移除时,引用计数都会递减一次,当引用次数降为0时,删除对象并回收内存。采用这种算法的较出名的框架有微软的COM框架,如代码清单14 - 1演示了一个对象引用计数的增减方式。

    代码清单14 - 1 引用计数增减方式演示伪码

    Object *obj1 = new Object(); // obj1的引用计数为1
    
    Object *obj2 = obj1; // obj1的引用技术为2
    
    Object *obj3 = new Object();
    
     
    
    obj2 = NULL; // obj1的引用计数递减1次为1。
    
    obj1 = obj3; // obj1的引用计数递减1次为0,可以回收其内存。
    

    通常对象的引用计数都会跟对象放在一起,系统在分配完对象的内存后,返回的对象指针会跳过引用计数部分,如代码清单14 - 1所示:
    在这里插入图片描述

    图 14 - 1 采用引用计数对象的内存布局示例

    然而引用计数回收算法有一个很大的弱点,就是无法有效处理循环引用的问题,由于Android系统没有使用该算法,所以这里不做过多的描述,请有兴趣的读者自行查阅相关文档。

    标注并清理回收法(Mark and Sweep GC)

    在这个算法中,程序在运行的过程中不停的创建新的对象并消耗内存,直到内存用光,这时再要创建新对象时,系统暂停其它组件的运行,触发GC线程启动垃圾回收过程。内存回收的原理很简单,就是从所谓的"GC Roots"集合开始,将内存整个遍历一次,保留所有可以被GC Roots直接或间接引用到的对象,而剩下的对象都当作垃圾对待并回收,如代码清单14 - 3:

    代码清单14 - 2 标注并清理算法伪码

    void GC()  
    {
    SuspendAllThreads();
             
    List<Object> roots = GetRoots();    
    foreach ( Object root : roots ) {  
    Mark(root);    
    }             
    Sweep();    
    ResumeAllThreads(); 
    }
    

    算法通常分为两个主要的步骤:

    标注(Mark)阶段:这个过程的伪码如代码清单14 - 2所示,针对GC Roots中的每一个对象,采用递归调用的方式(第8行)处理其直接和间接引用到的所有对象:
    代码清单14 - 3 标注并清理的标注阶段伪码

    void Mark(Object* pObj) {
    if ( !pObj->IsMarked() ) {
         // 修改对象头的Marked标志
    4.     pObj->Mark();    
    5.     // 深度优先遍历对象引用到的所有对象  
    6.     List<Object *> fields = pObj->GetFields();    
    7.     foreach ( Object* field : fields ) {   
    8.     Make(field); // 递归处理引用到的对象  
    9.     }
    10. }    
    11. }
    

    如果对象引用的层次过深,递归调用消耗完虚拟机内GC线程的栈空间,从而导致栈空间溢出(StackOverflow)异常,为了避免这种情况的发生,在具体实现时,通常是用一个叫做标注栈(Mark Stack)的数据结构来分解递归调用。一开始,标注栈(Mark Stack)的大小是固定的,但在一些极端情况下,如果标注栈的空间也不够的话,则会分配一个新的标注栈(Mark Stack),并将新老栈用链表连接起来。

    与引用计数法中对象的内存布局类似,对象是否被标注的标志也是保存在对象头里的,如图 14 - 2所示。
    在这里插入图片描述

    图 14 - 2 标注和清理算法中的对象布局

    如图 14 - 2是垃圾回收前的对象之间的引用关系;GC线程遍历完整个内存堆之后,标识出所以可以被"GC Roots"引用到的对象-即代码清单14 - 2中的第4行,结果如图 14 - 3中高亮的部分,对于所有未被引用到(即未被标注)的对象,都将其作为垃圾收集。

    图 14 - 3 回收内存垃圾之前的对象引用关系
    在这里插入图片描述

    在这里插入图片描述

    图 14 - 4 GC线程标识出所有不能被回收的对象实例

    清理(SWEEP)阶段:即执行垃圾回收过程,留下有用的对象,如图 14 - 4所示,代码清单14 - 3是这个过程的伪码,在这个阶段,GC线程遍历整个内存,将所有没有标注的对象(即垃圾)全部回收,并将保留下来的对象的标志清除掉,以便下次GC过程中使用。
    代码清单14 - 4 标注和清理法中的清理过程伪码

    void Sweep() {
    Object *pIter = GetHeapBegin();
         while ( pIter < GetHeapEnd() ) {
         if ( !pIter->IsMarked() )
         Free(pIter);
         else
         pIter->UnMark();    
    9.     pIter = MoveNext(pIter);
    10.      }    
    11. }
    

    在这里插入图片描述

    图 14 - 5 GC线程执行完垃圾回收过程后的对象图

    这个方法的优点是很好地处理了引用计数中的循环引用问题,而且在内存足够的前提下,对程序几乎没有任何额外的性能开支(如不需要维护引用计数的代码等),然而它的一个很大的缺点就是在执行垃圾回收过程中,需要中断进程内其它组件的执行。

    标注并整理回收法(Mark and COMPACT GC)

    这个是前面标注并清理法的一个变种,系统在长时间运行的过程中,反复分配和释放内存很有可能会导致内存堆里的碎片过多,从而影响分配效率,因此有些采用此算法的实现(Android系统中并没有采用这个做法),在清理(SWEEP)过程中,还会执行内存中移动存活的对象,使其排列的更紧凑。在这种算法中,,虚拟机在内存中依次排列和保存对象,可以想象GC组件在内部保存了一个虚拟的指针 – 下个对象分配的起始位置 ,如图 14 - 6中演示的示例应用,其GC内存堆中已经分配有3个对象,因此"下个对象分配的起始位置"指向已分配对象的末尾,新的对象"object 4"(虚线部分)的起始位置将从这里开始。

    这个内存分配机制和C/C++的malloc分配机制有很大的区别,在C/C++中分配一块内存时,通常malloc函数需要遍历一个"可用内存空间"链表,采取"first-first"(即返回第一块大于内存分配请求大小的内存块)或"best-fit"( 即返回大于内存分配请求大小的最小内存块),无论是哪种机制,这个遍历过程相对来说都是一个较为耗时的时间。然而在Java语言中,理论上,为一个对象分配内存的速度甚至可能比C/C++更快一些,这是因为其只需要调整指针"下个对象分配的起始位置"的位置即可,据Sun的工程师估计,这个过程大概只需要执行10个左右的机器指令。

    在这里插入图片描述

    图 14 - 6 在GC中为对象分配内存

    由于虚拟机在给对象分配内存时,一直不停地向后递增指针"下个对象分配的起始位置",潜台词就是将GC堆当做一个无限大的内存对待的,为了满足这个要求,GC线程在收集完垃圾内存之后,还需要压缩内存 – 即移动存活的对象,将它们紧凑的排列在GC内存堆中,如图 14 - 7是Java进程内GC前的内存布局,执行回收过程时,GC线程从进程中所有的Java线程对象、各线程堆栈里的局部变量、所有的静态变量和JNI引用等GC Root开始遍历。

    图 14 - 7中,可以被GC Root访问到的对象有A、C、D、E、F、H六个对象,为了避免内存碎片问题,和满足快速分配对象的要求,GC线程移动这六个对象,使内存使用更为紧凑,如图 14 - 7所示。由于GC线程移动了存活下来对象的内存位置,其必须更新其他线程中对这些对象的引用,如图 14 - 7中,由于A引用了E,移动之后,就必须更新这个引用,在更新过程中,必须中断正在使用A的线程,防止其访问到错误的内存位置而导致无法预料的错误。

    在这里插入图片描述

    图 14 - 7 垃圾回收前的GC堆上的对象布局及引用关系

    在这里插入图片描述

    图 14 - 8 GC线程移动存活的对象使内存布局更为紧凑

    注意现代操作系统中,针对C/C++的内存分配算法已经做了大量的改进,例如在Windows中,堆管理器提供了一个叫做"Look Aside List"的缓存针对大部分程序都是频繁分配小块内存的情形做的优化,具体技术细节请可以参阅笔者的在线付费技术视频:

    调试堆溢出问题(上): http://product.china-pub.com/3502598
    调试堆溢出问题(中): http://product.china-pub.com/3502599
    调试堆溢出问题(下): http://product.china-pub.com/3502600

    拷贝回收法(Copying GC)

    这也是标注法的一个变种, GC内存堆实际上分成乒(ping)和乓(pong)两部分。一开始,所有的内存分配请求都有乒(ping)部分满足,其维护"下个对象分配的起始位置"指针,分配内存仅仅就是操作下这个指针而已,当乒(ping)的内存快用完时,采用标注(Mark)算法识别出存活的对象,如图 14 - 9所示,并将它们拷贝到乓(pong)部分,后续的内存分配请求都在乓(pong)部分完成,如图 14 - 10。而乓(pong)里的内存用完后,再切换回乒(ping)部分,使用内存就跟打乒乓球一样。

    在这里插入图片描述
    图 14 - 9 拷贝回收法中的乒乓内存块

    在这里插入图片描述

    图 14 - 10 拷贝回收法中的切换乒乓内存块以满足内存分配请求

    回收算法的优点在于内存分配速度快,而且还有可能实现低中断,因为在垃圾回收过程中,从一块内存拷贝存活对象到另一块内存的同时,还可以满足新的内存分配请求,但其缺点是需要有额外的一个内存空间。不过对于回收算法的缺点,也可以通过操作系统地虚拟内存提供的地址空间申请和提交分布操作的方式实现优化,因此在一些JVM实现中,其Eden区域内的垃圾回收采用此算法。

    逐代回收法(Generational GC)

    也是标注法的一个变种,标注法最大的问题就是中断的时间过长,此算法是对标注法的优化基于下面几个发现:

    大部分对象创建完很快就没用了 – 即变成垃圾;
    每次GC收集的90%的对象都是上次GC后创建的;
    如果对象可以活过一个GC周期,那么它在后续几次GC中变成垃圾的几率很小,因此每次在GC过程中反复标注和处理它是浪费时间。
    可以将逐代回收法看成拷贝GC算法的一个扩展,一开始所有的对象都是分配在"年轻一代对象池" 中 – 在JVM中其被称为Young,如图 14 - 11:

    在这里插入图片描述

    图 14 - 11 逐代(generational) GC中开始对象都是分配在年轻一代对象池(Young generation)中

    第一次垃圾回收过后,垃圾回收算法一般采用标注并清理算法,存活的对象会移动到"老一代对象池"中– 在JVM中其被称为Tenured,如图 14 - 12,而后面新创建的对象仍然在"年轻一代对象池"中创建,这样进程不停地重复前面两个步骤。等到"老一代对象池"也快要被填满时,虚拟机此时再在"老一代对象池"中执行垃圾回收过程释放内存。在逐代GC算法中,由于"年轻一代对象池"中的回收过程很快 – 只有很少的对象会存活,而执行时间较长的"老一代对象池"中的垃圾回收过程执行不频繁,实现了很好的平衡,因此大部分虚拟机,如JVM、.NET的CLR都采用这种算法。

    在这里插入图片描述

    图 14 - 12 逐代GC中将存活的对象挪到老一代对象池

    在逐代GC中,有一个较棘手的问题需要处理 – 即如何处理老一代对象引用新一代对象的问题,如图 14 - 13中。由于每次GC都是在单独的对象池中执行的,当GC Root之一R3被释放后,在"年轻一代对象池"中执行GC过程时,R3所引用的对象f、g、h、i和j都会被当做垃圾回收掉,这样就导致"老一代对象池"中的对象c有一个无效引用。

    在这里插入图片描述

    图 14 - 13 逐代GC中老一代对象引用新对象的问题

    为了避免这种情况,在"年轻一代对象池"中执行GC过程时,也需要将对象C当做GC Root之一。一个名为"Card Table"的数据结构就是专门设计用来处理这种情况的,"Card Table"是一个位数组,每一个位都表示"老一代对象池"内存中一块4KB的区域 – 之所以取4KB,是因为大部分计算机系统中,内存页大小就是4KB。当用户代码执行一个引用赋值(reference assignment)时,虚拟机(通常是JIT组件)不会直接修改内存,而是先将被赋值的内存地址与"老一代对象池"的地址空间做一次比较,如果要修改的内存地址是"老一代对象池"中的地址,虚拟机会修改"Card Table"对应的位为 1,表示其对应的内存页已经修改过 - 不干净(dirty)了,如图 14 - 14。

    在这里插入图片描述
    图 14 - 14 逐代GC中Card Table数据结构示意图

    当需要在 "年轻一代对象池"中执行GC时, GC线程先查看"Card Table"中的位,找到不干净的内存页,将该内存页中的所有对象都加入GC Root。虽然初看起来,有点浪费, 但是据统计,通常从老一代的对象引用新一代对象的几率不超过1%,因此"Card Table"的算法是一小部分的时间损失换取空间。

    感谢文章:http://www.cnblogs.com/killmyday/archive/2013/06/12/3132518.html的作者:donjuan

    展开全文
  • java雪花算法工具类

    万次阅读 2021-06-04 09:58:13
    创建一个SnowFlake的工具类,然后把下面的代码粘过去就可以了 /** * Twitter_Snowflake<br> * SnowFlake的结构如下(每部分用-分开):<br>... * 1位标识,由于long基本类型在Java中是带

    创建一个SnowFlake的工具类,然后把下面的代码粘过去就可以了

    
        /**
         * Twitter_Snowflake<br>
         * SnowFlake的结构如下(每部分用-分开):<br>
         * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 -
         * 000000000000 <br>
         * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
         * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
         * 得到的值),这里的的开始时间截
         * ,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。
         * 41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
         * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
         * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
         * 加起来刚好64位,为一个Long型。<br>
         * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,
         * SnowFlake每秒能够产生26万ID左右。
         */
    
        // ==============================Fields===========================================
        /** 开始时间截 (2015-01-01) */
        private static final long twepoch = 1420041600000L;
    
        /** 机器id所占的位数 */
        private static final long workerIdBits = 5L;
    
        /** 数据标识id所占的位数 */
        private static final long datacenterIdBits = 5L;
    
        /** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
        private static final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    
        /** 支持的最大数据标识id,结果是31 */
        private static final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    
        /** 序列在id中占的位数 */
        private static final long sequenceBits = 12L;
    
        /** 机器ID向左移12位 */
        private static final long workerIdShift = sequenceBits;
    
        /** 数据标识id向左移17位(12+5) */
        private static final long datacenterIdShift = sequenceBits + workerIdBits;
    
        /** 时间截向左移22位(5+5+12) */
        private static final long timestampLeftShift = sequenceBits + workerIdBits
                + datacenterIdBits;
    
        /** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */
        private  static final long sequenceMask = -1L ^ (-1L << sequenceBits);
    
        /** 工作机器ID(0~31) */
        private static long workerId;
    
        /** 数据中心ID(0~31) */
        private static long datacenterId;
    
        /** 毫秒内序列(0~4095) */
        private static long sequence = 0L;
    
        /** 上次生成ID的时间截 */
        private static long lastTimestamp = -1L;
    
        // ==============================Constructors=====================================
        /**
         * 构造函数
         *
         * @param workerId
         *            工作ID (0~31)
         * @param datacenterId
         *            数据中心ID (0~31)
         */
        public SnowFlake(long workerId, long datacenterId) {
            if (workerId > maxWorkerId || workerId < 0) {
                throw new IllegalArgumentException(String.format(
                        "worker Id can't be greater than %d or less than 0",
                        maxWorkerId));
            }
            if (datacenterId > maxDatacenterId || datacenterId < 0) {
                throw new IllegalArgumentException(String.format(
                        "datacenter Id can't be greater than %d or less than 0",
                        maxDatacenterId));
            }
            SnowFlake.workerId = workerId;
            SnowFlake.datacenterId = datacenterId;
        }
    
        // ==============================Methods==========================================
        /**
         * 获得下一个ID (该方法是线程安全的)
         *
         * @return SnowflakeId
         */
        public static synchronized long nextId() {
            long timestamp = timeGen();
    
            // 如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
            if (timestamp < lastTimestamp) {
                throw new RuntimeException(
                        String.format(
                                "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                                lastTimestamp - timestamp));
            }
    
            // 如果是同一时间生成的,则进行毫秒内序列
            if (lastTimestamp == timestamp) {
                sequence = (sequence + 1) & sequenceMask;
                // 毫秒内序列溢出
                if (sequence == 0) {
                    // 阻塞到下一个毫秒,获得新的时间戳
                    timestamp = tilNextMillis(lastTimestamp);
                }
            }
            // 时间戳改变,毫秒内序列重置
            else {
                sequence = 0L;
            }
    
            // 上次生成ID的时间截
            lastTimestamp = timestamp;
    
            // 移位并通过或运算拼到一起组成64位的ID
            return ((timestamp - twepoch) << timestampLeftShift) //
                    | (datacenterId << datacenterIdShift) //
                    | (workerId << workerIdShift) //
                    | sequence;
        }
    
        /**
         * 阻塞到下一个毫秒,直到获得新的时间戳
         *
         * @param lastTimestamp
         *            上次生成ID的时间截
         * @return 当前时间戳
         */
        protected static long tilNextMillis(long lastTimestamp) {
            long timestamp = timeGen();
            while (timestamp <= lastTimestamp) {
                timestamp = timeGen();
            }
            return timestamp;
        }
    
        /**
         * 返回以毫秒为单位的当前时间
         *
         * @return 当前时间(毫秒)
         */
        protected static long timeGen() {
            return System.currentTimeMillis();
        }
    
        public SnowFlake() {
            this(0, 0);
        }
    
        // 生成id
        public static String getId() {
            return String.valueOf(SnowFlake.nextId());
        }
    
        // ==============================Test=============================================
        /** 测试 */
        public static void main(String[] args) {
            System.out.println(SnowFlake.nextId());
        }
    

    注:本文为转载文章,因为转载的人太多了,并且都没有标注出原作者,所以原创作者无从考究。

    展开全文
  • 隐马尔可夫模型(Hidden Markov Model,HMM) ...维特比(viterbi)算法与中文词性标注(三) ——词性标注实现 参考文献 [1] 一文搞懂HMM(隐马尔可夫模型) [2] HMM模型和Viterbi算法 [3] 简单理解viterbi算法
  • java笔试题算法 基本工具: 中科院NLPIR(推荐) ...FudanNLP采用Java编写,提供了API的访问调用方式,包含机器学习算法数据集。 主要功能包括:中文分词,词性标注,实体名识别,关键词抽取,依存句法分析,时间短
  • OPENCV EM算法详解和JAVA实现

    千次阅读 2017-08-23 23:03:56
    2EM算法是一种非监督的学习算法,它的输入数据事先不需要进行标注。相反,该算法从给定的样本集中,能计算出高斯混和参数的最大似然估计。也能得到每个样本对应的标注值,类似于kmeans聚类(输入样本数据,输出样本...
  • Java多线程结合银行家算法避免死锁实践

    千次阅读 多人点赞 2020-02-05 22:49:26
    ​ 在前几篇文章中,我们讨论了银行家算法,包含其数据结构、算法步骤和安全性算法。关于银行家算法的具体细节,请参看这篇博文。 ​ 在另一篇文章中,我们使用了Java来模拟实现了银行家算法,并使用一个例子来验证...
  • 一、Java的四大存储结构如下图红色框标注: 二、四大存储结构的基本概述如下: 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存结构中。 索引结构和...
  • Java 标注(Annotation)详解

    万次阅读 2012-03-09 16:13:30
    数据的作用 如果要对于元数据的作用进行分类,目前还没有明确的定义,不过我们可以根据它所起的作用,大致可分为三类: l 编写文档:通过代码里标识的元数据生成文档。 l 代码分析:通过代码里标识的元数据对...
  • 问题处理涉及图模型、单源最短路径问题的Dijkstra算法、旅行商问题的回溯和分支限界算法以及相关数据在文件中的存储和使用,是对相关内容的综合利用和整合。设计过程基于构建相关问题模型并围绕软件生存周期展开,从...
  • java 数据类型转换

    千次阅读 2018-11-20 11:20:32
      本博文部分原创,部分转载整理,侵删!...数据类型的转换遵循原则:范围小的数据类型,可以转换成范围大的数据类型。eg:byte转int。范围大的数据类型不可以转换成范围小的数据类型。 jav...
  • 下面是大数据常用算法,快速排序的java实现(基于字符串hash值的顺序排序 ,下面会标注排序不同的数据需要改写的比较代码,只需要改写比较代码就能实现不同数据的排序) 快速排序(Quicksort)是对冒...
  • (update 2012.12.28 关于本项目下载及运行的常见问题 FAQ见 newsgroup18828文本分类器、文本聚类器、关联分析频繁模式挖掘算法Java实现工程下载及运行FAQ )本文主要内容如下:对newsgroup文档集进行预处理,提取出...
  • 开源NLP标注工具及NLP数据

    千次阅读 2020-03-26 20:13:34
    自然语言处理标注工具是指通过可视化界面,以清晰、快捷的方式对文本数据进行标注的工具,该工具通常以系统形式展现,包含前端展示、后端系统与数据库三部分组成。 二、自然语言标注平台能做什么 文本分类(对文本...
  • 2019年常见Elasticsearch 面试题答案详细解析(下)

    千次阅读 多人点赞 2019-12-26 15:51:03
    1.Elasticsearch 是一个分布式的 RESTful 风格的搜索和数据分析引擎。 (1)查询 : Elasticsearch 允许执行和合并多种类型的搜索 — 结构化、非结构化、地理位置、度量指标 — 搜索方式随心而变。 (2)分析 : ...
  • 文章目录什么是垃圾如何找到垃圾引用计数(Reference Count)根可达算法(Root Searching)如何清理垃圾标记清除 (Mark-Sweep)复制 (Copying)标记压缩 (Mark-Compact)JVM分代算法新生代老年代垃圾回收器种类Java 1.3...
  • 主要介绍了Java编程实现比对两个文本文件并标记相同与不同之处的方法,涉及java针对文本文件的读取、遍历、判断等相关操作技巧,需要的朋友可以参考下
  • 由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,...
  • 算法工程师职业方向及技术要求

    千次阅读 2021-05-13 16:35:18
    点上方人工智能算法与Python大数据获取更多干货在右上方···设为星标★,第一时间获取资源仅做学术分享,如有侵权,联系删除转载于 :作者|explorer来源|知乎算法(A...
  • Java算法---求面积

    千次阅读 2015-12-02 09:03:07
    今天在做牛客网编程题时遇到了这样一个问题,分享一下: ... 输入包含多组数据,每组数据第一行包含两个正整数n(3≤n≤10)和m(3≤m≤10)。紧接着有n行,每行m个数字,代表地图,数字之间无空格。数据保证只有一片
  • 这篇将使用Java实现基于规则的中文分词算法,一个中文词典将实现准确率高达85%的分词结果。使用经典算法:正向最大匹配和反向最大匹配算法,然后双剑合璧,双向最大匹配。
  • 简谈Java中的数据交互

    千次阅读 2018-03-17 00:52:46
    对于程序而言,数据算法是最关键的两个部分,这两个部分支撑着整个程序的运行。在这里,我们简单聊一聊基于Java数据打交道的那些事 保存对象的手段 – 序列化 Java序列化简介 首先抛出一个简单的定义:Java...
  • 用户画像

    千次阅读 2018-12-03 22:25:44
    有事实标准验证的特点:数据+学习,可以验证结果,比如:以注册填写性别为标注集,用ML算法摸索用户行为不性别之间的关系。无事实标准验证的特点,方法是假设+实现,只能验证过程,比如:流失用户 = 半年未交易用户,...
  • 文章目录自然语言处理系列二十一词性标注词性标注原理总结 自然语言处理系列二十一 词性标注 词性标注(Part-Of-Speech tagging, POS tagging)也被称为语法标注(grammatical tagging)或词类消疑(word-category ...
  • 以下文章来源于数据魔术师 ,作者周航 欲下载本文相关的代码及算例,请关注公众号【程序猿声】,后台回复【TSVRPJAVA】不包括【】即可 前言 大家好呀! 眼看这9102年都快要过去了,小编也是越来越感觉着急了:...
  • TextRank算法提取关键词的Java实现

    千次阅读 2016-10-26 10:31:34
    TextRank算法提取关键词的Java实现
  • 对于K个类别的数据选取K个质心 距离第 个质心最近的点归为 类 2、算法具体步骤: - 选取K个随机点,将其标注为K个类别 - 计算样本点到这K个随机点的距离,根据距离最近的第i个点将其分类i类 - 根据分类的结果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,459
精华内容 8,983
关键字:

java数据标注算法

java 订阅