Inky资料

本文主要介绍Inky资料 方法和在新技术下所面对的“挑战”,方便大家深入理解Inky资料 过程。本文也将分享Inky资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

目录
  • 1 前缀树结构(trie)、桶排序、排序总结
    • 1.1 前缀树结构
    • 1.2 不基于比较的排序-桶排序
      • 1.2.1 计数排序
      • 1.2.2 基数排序
    • 1.3 排序算法的稳定性
      • 1.3.1 稳定的排序
      • 1.3.2 不稳定的排序
      • 1.3.3 排序稳定性对比
    • 1.4 排序算法总结
    • 1.5 排序常见的坑点
    • 1.6 工程上对排序的改进

1 前缀树结构(trie)、桶排序、排序总结

1.1 前缀树结构

单个字符串中,字符从前到后的加到一颗多叉树上

字符放在路上,节点上有专属的数据项(常见的是pass和end值)

所有样本都这样添加。如果没有路就新建,如果有路就复用

沿途节点的pass值增加1.每个字符串结束时来到的节点end值增加1

一个字符串数组中,所有字符串的字符数为N,整个数组加入前缀树种的代价是O(N)

功能一:构建好前缀树之后,我们查询某个字符串在不在前缀树中,某字符串在这颗前缀树中出现了几次都是特别方便的。例如找"ab"在前缀树中存在几次,可以先看有无走向a字符的路径(如果没有,直接不存在),再看走向b字符的路径,此时检查该节点的end标记的值,如果为0,则前缀树中不存在"ab"字符串,如果e>0则,e等于几则"ab"在前缀树种出现了几次

功能二:如果单单是功能一,那么哈希表也可以实现。现查询所有加入到前缀树的字符串,有多少个以"a"字符作为前缀,来到"a"的路径,查看p值大小,就是以"a"作为前缀的字符串数量

package class05;  import java.util.HashMap;  public class Code02_TrieTree {  	public static class Node1 { 	        // pass表示字符从该节点的路径通过 		public int pass; 		// end表示该字符到此节点结束 		public int end; 		public Node1[] nexts;  		public Node1() { 			pass = 0; 			end = 0; 			// 每个节点下默认26条路,分别是a~z 			// 0    a 			// 1    b 			// 2    c 			// ..   .. 			// 25   z 			// nexts[i] == null   i方向的路不存在 			// nexts[i] != null   i方向的路存在 			nexts = new Node1[26]; 		} 	}  	public static class Trie1 { 	         // 默认只留出头节点 		private Node1 root;  		public Trie1() { 			root = new Node1(); 		}                  // 往该前缀树中添加字符串 		public void insert(String word) { 			if (word == null) { 				return; 			} 			char[] str = word.toCharArray(); 			// 初始引用指向头节点 			Node1 node = root; 			// 头结点的pass首先++ 			node.pass++; 			// 路径的下标 			int path = 0; 			for (int i = 0; i < str.length; i++) { // 从左往右遍历字符 			    // 当前字符减去'a'的ascii码得到需要添加的下个节点下标 				path = str[i] - 'a'; // 由字符,对应成走向哪条路 				// 当前方向上没有建立节点,即一开始不存在这条路,新开辟 				if (node.nexts[path] == null) { 					node.nexts[path] = new Node1(); 				} 				// 引用指向当前来到的节点 				node = node.nexts[path]; 				// 当前节点的pass++ 				node.pass++; 			} 			// 当新加的字符串所有字符处理结束,最后引用指向的当前节点就是该字符串的结尾节点,end++ 			node.end++; 		}                  // 删除该前缀树的某个字符串 		public void delete(String word) { 		        // 首先要查一下该字符串是否加入过 			if (search(word) != 0) { 			    // 沿途pass-- 				char[] chs = word.toCharArray(); 				Node1 node = root; 				node.pass--; 				int path = 0; 				for (int i = 0; i < chs.length; i++) { 					path = chs[i] - 'a'; 					// 在寻找的过程中,pass为0,提前可以得知在本次删除之后,该节点以下的路径不再需要,可以直接删除。 					// 那么该节点之下下个方向的节点引用置为空(JVM垃圾回收,相当于该节点下的路径被删了) 					if (--node.nexts[path].pass == 0) { 						node.nexts[path] = null; 						return; 					} 					node = node.nexts[path]; 				} 				// 最后end-- 				node.end--; 			} 		}                 // 在该前缀树中查找 		// word这个单词之前加入过几次 		public int search(String word) { 			if (word == null) { 				return 0; 			} 			char[] chs = word.toCharArray(); 			Node1 node = root; 			int index = 0; 			for (int i = 0; i < chs.length; i++) { 				index = chs[i] - 'a'; 				// 寻找该字符串的路径中如果提前找不到path,就是未加入过,0次 				if (node.nexts[index] == null) { 					return 0; 				} 				node = node.nexts[index]; 			} 			// 如果顺利把word字符串在前缀树中走完路径,那么此时的node对应的end值就是当前word在该前缀树中添加了几次 			return node.end; 		}  		// 所有加入的字符串中,有几个是以pre这个字符串作为前缀的 		public int prefixNumber(String pre) { 			if (pre == null) { 				return 0; 			} 			char[] chs = pre.toCharArray(); 			Node1 node = root; 			int index = 0; 			for (int i = 0; i < chs.length; i++) { 				index = chs[i] - 'a'; 				// 走不到最后,就没有 				if (node.nexts[index] == null) { 					return 0; 				} 				node = node.nexts[index]; 			} 			// 顺利走到最后,返回的pass就是有多少个字符串以当前pre为前缀的 			return node.pass; 		} 	}          /**         * 实现方式二,针对各种字符串,路径不仅仅是a~z对应的26个,用HashMap<Integer, Node2>表示ascii码值对应的node。         **/ 	public static class Node2 { 		public int pass; 		public int end; 		public HashMap<Integer, Node2> nexts;  		public Node2() { 			pass = 0; 			end = 0; 			nexts = new HashMap<>(); 		} 	}  	public static class Trie2 { 		private Node2 root;  		public Trie2() { 			root = new Node2(); 		}  		public void insert(String word) { 			if (word == null) { 				return; 			} 			char[] chs = word.toCharArray(); 			Node2 node = root; 			node.pass++; 			int index = 0; 			for (int i = 0; i < chs.length; i++) { 				index = (int) chs[i]; 				if (!node.nexts.containsKey(index)) { 					node.nexts.put(index, new Node2()); 				} 				node = node.nexts.get(index); 				node.pass++; 			} 			node.end++; 		}  		public void delete(String word) { 			if (search(word) != 0) { 				char[] chs = word.toCharArray(); 				Node2 node = root; 				node.pass--; 				int index = 0; 				for (int i = 0; i < chs.length; i++) { 					index = (int) chs[i]; 					if (--node.nexts.get(index).pass == 0) { 						node.nexts.remove(index); 						return; 					} 					node = node.nexts.get(index); 				} 				node.end--; 			} 		}  		// word这个单词之前加入过几次 		public int search(String word) { 			if (word == null) { 				return 0; 			} 			char[] chs = word.toCharArray(); 			Node2 node = root; 			int index = 0; 			for (int i = 0; i < chs.length; i++) { 				index = (int) chs[i]; 				if (!node.nexts.containsKey(index)) { 					return 0; 				} 				node = node.nexts.get(index); 			} 			return node.end; 		}  		// 所有加入的字符串中,有几个是以pre这个字符串作为前缀的 		public int prefixNumber(String pre) { 			if (pre == null) { 				return 0; 			} 			char[] chs = pre.toCharArray(); 			Node2 node = root; 			int index = 0; 			for (int i = 0; i < chs.length; i++) { 				index = (int) chs[i]; 				if (!node.nexts.containsKey(index)) { 					return 0; 				} 				node = node.nexts.get(index); 			} 			return node.pass; 		} 	}       	public static class Right {  		private HashMap<String, Integer> box;  		public Right() { 			box = new HashMap<>(); 		}  		public void insert(String word) { 			if (!box.containsKey(word)) { 				box.put(word, 1); 			} else { 				box.put(word, box.get(word) + 1); 			} 		}  		public void delete(String word) { 			if (box.containsKey(word)) { 				if (box.get(word) == 1) { 					box.remove(word); 				} else { 					box.put(word, box.get(word) - 1); 				} 			} 		}  		public int search(String word) { 			if (!box.containsKey(word)) { 				return 0; 			} else { 				return box.get(word); 			} 		}  		public int prefixNumber(String pre) { 			int count = 0; 			for (String cur : box.keySet()) { 				if (cur.startsWith(pre)) { 					count += box.get(cur); 				} 			} 			return count; 		} 	}  	// for test 	public static String generateRandomString(int strLen) { 		char[] ans = new char[(int) (Math.random() * strLen) + 1]; 		for (int i = 0; i < ans.length; i++) { 			int value = (int) (Math.random() * 6); 			ans[i] = (char) (97 + value); 		} 		return String.valueOf(ans); 	}  	// for test 	public static String[] generateRandomStringArray(int arrLen, int strLen) { 		String[] ans = new String[(int) (Math.random() * arrLen) + 1]; 		for (int i = 0; i < ans.length; i++) { 			ans[i] = generateRandomString(strLen); 		} 		return ans; 	}  	public static void main(String[] args) { 		int arrLen = 100; 		int strLen = 20; 		int testTimes = 100000; 		for (int i = 0; i < testTimes; i++) { 			String[] arr = generateRandomStringArray(arrLen, strLen); 			Trie1 trie1 = new Trie1(); 			Trie2 trie2 = new Trie2(); 			Right right = new Right(); 			for (int j = 0; j < arr.length; j++) { 				double decide = Math.random(); 				if (decide < 0.25) { 					trie1.insert(arr[j]); 					trie2.insert(arr[j]); 					right.insert(arr[j]); 				} else if (decide < 0.5) { 					trie1.delete(arr[j]); 					trie2.delete(arr[j]); 					right.delete(arr[j]); 				} else if (decide < 0.75) { 					int ans1 = trie1.search(arr[j]); 					int ans2 = trie2.search(arr[j]); 					int ans3 = right.search(arr[j]); 					if (ans1 != ans2 || ans2 != ans3) { 						System.out.println("Oops!"); 					} 				} else { 					int ans1 = trie1.prefixNumber(arr[j]); 					int ans2 = trie2.prefixNumber(arr[j]); 					int ans3 = right.prefixNumber(arr[j]); 					if (ans1 != ans2 || ans2 != ans3) { 						System.out.println("Oops!"); 					} 				} 			} 		} 		System.out.println("finish!");  	}  }  

1.2 不基于比较的排序-桶排序

例如:一个代表员工年龄的数组,排序。数据范围有限,对每个年龄做词频统计。arr[0~200] = 0,M=200

空间换时间

1.2.1 计数排序

桶排序思想下的排序:计数排序 & 基数排序  1、 桶排序思想下的排序都是不基于比较的排序  2、 时间复杂度为O(N),二维空间复杂复杂度为O(M)  3、 应用范围有限,需要样本的数据状况满足桶的划分 

缺点:与样本数据状况强相关。

1.2.2 基数排序

应用条件:十进制数据,非负

[100,17,29,13,5,27] 进行排序 =>  1、找最高位的那个数的长度,这里100的长度为3,其他数前补0,得出  [100,017,029,013,005,027]  2、 准备10个桶,对应的数字0~9号桶,每个桶是一个队列。根据样本按个位数字对应进桶,相同个位数字进入队列,再从0号桶以此倒出,队列先进先出。个位进桶再依次倒出,得出:  [100,013,005,017,027,029]  3、 再把按照个位进桶倒出的样本,再按十位进桶,再按相同规则倒出得:  [100,005,013,017,027,029]  4、再把得到的样本按百位进桶,倒出得:  [005,013,017,027,029,100]  此时达到有序!  

思想:先按各位数字排序,各位数字排好序,再用十位数字的顺序去调整,再按百位次序调整。优先级依次递增,百位优先级最高,百位优先级一样默认按照上一层十位的顺序…

结论:基于比较的排序,时间复杂度的极限就是O(NlogN),而不基于比较的排序,时间复杂度可以达到O(N)。在面试或刷题,估算排序的时间复杂度的时候,必须用基于比较的排序来估算

/** * 计数排序 **/ package class05;  import java.util.Arrays;  public class Code03_CountSort {          // 计数排序 	// only for 0~200 value 	public static void countSort(int[] arr) { 		if (arr == null || arr.length < 2) { 			return; 		} 		int max = Integer.MIN_VALUE; 		for (int i = 0; i < arr.length; i++) { 			max = Math.max(max, arr[i]); 		} 		int[] bucket = new int[max + 1]; 		for (int i = 0; i < arr.length; i++) { 			bucket[arr[i]]++; 		} 		int i = 0; 		for (int j = 0; j < bucket.length; j++) { 			while (bucket[j]-- > 0) { 				arr[i++] = j; 			} 		} 	}  	// for test 	public static void comparator(int[] arr) { 		Arrays.sort(arr); 	}  	// for test 	public 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()); 		} 		return arr; 	}  	// for test 	public 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; 	}  	// for test 	public 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; 	}  	// for test 	public 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(); 	}  	// for test 	public static void main(String[] args) { 		int testTime = 500000; 		int maxSize = 100; 		int maxValue = 150; 		boolean succeed = true; 		for (int i = 0; i < testTime; i++) { 			int[] arr1 = generateRandomArray(maxSize, maxValue); 			int[] arr2 = copyArray(arr1); 			countSort(arr1); 			comparator(arr2); 			if (!isEqual(arr1, arr2)) { 				succeed = false; 				printArray(arr1); 				printArray(arr2); 				break; 			} 		} 		System.out.println(succeed ? "Nice!" : "Fucking fucked!");  		int[] arr = generateRandomArray(maxSize, maxValue); 		printArray(arr); 		countSort(arr); 		printArray(arr);  	}  } 

下面代码的思想:

例如原数组[101,003,202,41,302]。得到按个位的词频conut数组为[0,2,2,1,0,0,0,0,0,0]。通过conut词频累加得到conut’为[0,2,4,5,5,5,5,5,5,5],此时conut’的含义表示个位数字小于等于0的数字有0个,个位数字小于等于1的有两个,个位数字小于等于2的有4个……

得到conut’之后,对原数组[101,003,202,41,302]从右往左遍历。根据基数排序的思想,302应该是2号桶最后被倒出的,我们已经知道个位数字小于等于2的有4个,那么302就是4个中的最后一个,放在help数组的3号位置,相应的conut’小于等于2位置的词频减减变为3。同理,41是1号桶的最后一个,个位数字小于等于1的数字有两个,那么41需要放在1号位置,小于等于1位置的词频减减变为1,同理……

实质增加conut和count’结构,避免申请十个队列结构,不想炫技直接申请10个队列结构,按基数排序思想直接做没问题

实质上,基数排序的时间复杂度是O(Nlog10max(N)),log10N表示十进制的数的位数,但是我们认为基数排序的应用样本范围不大。如果要排任意位数的值,严格上就是O(Nlog10max(N))

/** * 基数排序 **/ package class05;  import java.util.Arrays;  public class Code04_RadixSort {          // 非负数,十进制,如果负数需要深度改写这个方法 	// only for no-negative value 	public static void radixSort(int[] arr) { 		if (arr == null || arr.length < 2) { 			return; 		} 		radixSort(arr, 0, arr.length - 1, maxbits(arr)); 	}          // 计算数组样本中最大值的位数 	public static int maxbits(int[] arr) { 		int max = Integer.MIN_VALUE; 		for (int i = 0; i < arr.length; i++) { 			max = Math.max(max, arr[i]); 		} 		int res = 0; 		while (max != 0) { 			res++; 			max /= 10; 		} 		return res; 	}  	// arr[l..r]排序  ,  digit:最大值的位数 	// l..r    [3, 56, 17, 100]    3 	public static void radixSort(int[] arr, int L, int R, int digit) { 	    // 由于十进制的数,我们依10位基底 		final int radix = 10; 		int i = 0, j = 0; 		// 有多少个数准备多少个辅助空间 		int[] help = new int[R - L + 1]; 		for (int d = 1; d <= digit; d++) { // 有多少位就进出几次 			// 10个空间 		        // count[0] 当前位(d位)是0的数字有多少个 			// count[1] 当前位(d位)是(0和1)的数字有多少个 			// count[2] 当前位(d位)是(0、1和2)的数字有多少个 			// count[i] 当前位(d位)是(0~i)的数字有多少个 			int[] count = new int[radix]; // count[0..9] 			for (i = L; i <= R; i++) { 				// 103的话  d是1表示个位 取出j=3 				// 209  1   9 				j = getDigit(arr[i], d); 				count[j]++; 			} 			// conut往conut'的转化 			for (i = 1; i < radix; i++) { 				count[i] = count[i] + count[i - 1]; 			} 			// i从最后位置往前看 			for (i = R; i >= L; i--) { 				j = getDigit(arr[i], d); 				help[count[j] - 1] = arr[i]; 				// 词频-- 				count[j]--; 			} 			// 处理完个位十位...之后都要往原数组copy 			for (i = L, j = 0; i <= R; i++, j++) { 				arr[i] = help[j]; 			} 		} 		 		 		 		 	}  	public static int getDigit(int x, int d) { 		return ((x / ((int) Math.pow(10, d - 1))) % 10); 	}  	// for test 	public static void comparator(int[] arr) { 		Arrays.sort(arr); 	}  	// for test 	public 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()); 		} 		return arr; 	}  	// for test 	public 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; 	}  	// for test 	public 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; 	}  	// for test 	public 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(); 	}  	// for test 	public static void main(String[] args) { 		int testTime = 500000; 		int maxSize = 100; 		int maxValue = 100000; 		boolean succeed = true; 		for (int i = 0; i < testTime; i++) { 			int[] arr1 = generateRandomArray(maxSize, maxValue); 			int[] arr2 = copyArray(arr1); 			radixSort(arr1); 			comparator(arr2); 			if (!isEqual(arr1, arr2)) { 				succeed = false; 				printArray(arr1); 				printArray(arr2); 				break; 			} 		} 		System.out.println(succeed ? "Nice!" : "Fucking fucked!");  		int[] arr = generateRandomArray(maxSize, maxValue); 		printArray(arr); 		radixSort(arr); 		printArray(arr);  	}  }  

1.3 排序算法的稳定性

稳定性是指同样大小的样本在排序之后不会改变相对次序。基础类型稳定性没意义,用处是按引用传递后是否稳定。比如学生有班级和年龄两个属性,先按班级排序,再按年龄排序,那么如果是稳定性的排序,不会破坏之前已经按班级拍好的顺序

稳定性排序的应用场景:购物时候,先按价格排序商品,再按好评度排序,那么好评度实在价格排好序的基础上。反之不稳定排序会破坏一开始按照价格排好的次序

1.3.1 稳定的排序

1、 冒泡排序(处理相等时不交换)

2、 插入排序(相等不交换)

3、 归并排序(merge时候,相等先copy左边的)

1.3.2 不稳定的排序

1、 选择排序

2、 快速排序 (partion过程无法保证稳定)

3、 堆排序 (维持堆结构)

1.3.3 排序稳定性对比

排序 时间复杂度 空间复杂度 稳定性
选择排序 O(N^2) O(1)
冒泡排序 O(N^2) O(1)
插入排序 O(N^2) O(1)
归并排序 O(NlogN) O(N)
随机快拍 O(NlogN) O(logN)
堆排序 O(NlogN) O(1)
计数排序 O(N) O(M)
堆排序 O(N) O(N)

1.4 排序算法总结

  1. 不基于比较的排序,对样本数据有严格要求,不易改写
  2. 基于比较的排序,只要规定好两个样本怎么比较大小就可以直接复用
  3. 基于比较的排序,时间复杂度的极限是O(NlogN)
  4. 时间复杂度O(NlogN)、额外空间复杂度低于O(N),且稳定的基于比较的排序是不存在的
  5. 为了绝对的速度选择快排(快排的常数时间低),为了节省空间选择堆排序,为了稳定性选归并

1.5 排序常见的坑点

归并排序的额为空间复杂度可以变为O(1)。“归并排序内部缓存法”,但是将会变的不稳定。不考虑稳定不如直接选择堆排序

“原地归并排序”是垃圾帖子,会让时间复杂度变成O(N ^2)。时间复杂度退到O(N ^2)不如直接选择插入排序

快速排序稳定性改进,“01 stable sort”,但是会对样本数据要求更多。对数据进行限制,不如选择桶排序

在整形数组中,请把奇数放在数组左边,偶数放在数组右边,要求所有奇数之间原始次序不变,所有偶数之间原始次序不变。要求时间复杂度O(N),额为空间复杂度O(1)。这是个01标准的partion,奇偶规则,但是快速排序的partion过程做不到稳定性。所以正常实现不了,学术论文(01 stable sort,不建议碰,比较难)中需要把数据阉割限制之后才能做到

1.6 工程上对排序的改进

稳定性考虑:值传递,直接快排,引用传递,归并排序

充分利用O(NlogN)和O(N^2)排序各自的优势:根据样本量底层基于多种排序实现,比如样本量比较小直接选择插入排序。

比如Java中系统实现的快速排序

Inky资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » Inky资料

提供最优质的资源集合

立即查看 了解详情