建设厅工作证查询网站,中国设计网络首选品牌,门户网站 移动端,广西桂林旅游攻略自由行最佳线路本章概要
数组排序Arrays.sort的使用并行排序binarySearch二分查找parallelPrefix并行前缀
数组排序
根据对象的实际类型执行比较排序。一种方法是为不同的类型编写对应的排序方法#xff0c;但是这样的代码不能复用。
编程设计的一个主要目标是“将易变的元素与稳定的元素…本章概要
数组排序Arrays.sort的使用并行排序binarySearch二分查找parallelPrefix并行前缀
数组排序
根据对象的实际类型执行比较排序。一种方法是为不同的类型编写对应的排序方法但是这样的代码不能复用。
编程设计的一个主要目标是“将易变的元素与稳定的元素分开”在这里保持不变的代码是一般的排序算法但是变化的是对象的比较方式。因此使用策略设计模式而不是将比较代码放入许多不同的排序源码中。使用策略模式时变化的代码部分被封装在一个单独的类(策略对象)中。
您将一个策略对象交给相同的代码该代码使用策略模式来实现其算法。通过这种方式您将使用相同的排序代码使不同的对象表达不同的比较方式。
Java有两种方式提供比较功能。第一种方法是通过实现 java.lang.Comparable 接口的原生方法。这是一个简单的接口只含有一个方法 compareTo()。该方法接受另一个与参数类型相同的对象作为参数如果当前对象小于参数则产生一个负值;如果参数相等则产生零值;如果当前对象大于参数则产生一个正值。
这里有一个类它实现了 Comparable 接口并演示了可比性而且使用Java标准库方法 Arrays.sort(): ArrayShow.java package com.example.test;import java.util.*;public interface ArrayShow {static void show(Object[] a) {System.out.println(Arrays.toString(a));}static void show(boolean[] a) {System.out.println(Arrays.toString(a));}static void show(byte[] a) {System.out.println(Arrays.toString(a));}static void show(char[] a) {System.out.println(Arrays.toString(a));}static void show(short[] a) {System.out.println(Arrays.toString(a));}static void show(int[] a) {System.out.println(Arrays.toString(a));}static void show(long[] a) {System.out.println(Arrays.toString(a));}static void show(float[] a) {System.out.println(Arrays.toString(a));}static void show(double[] a) {System.out.println(Arrays.toString(a));}// Start with a description:static void show(String info, Object[] a) {System.out.print(info : );show(a);}static void show(String info, boolean[] a) {System.out.print(info : );show(a);}static void show(String info, byte[] a) {System.out.print(info : );show(a);}static void show(String info, char[] a) {System.out.print(info : );show(a);}static void show(String info, short[] a) {System.out.print(info : );show(a);}static void show(String info, int[] a) {System.out.print(info : );show(a);}static void show(String info, long[] a) {System.out.print(info : );show(a);}static void show(String info, float[] a) {System.out.print(info : );show(a);}static void show(String info, double[] a) {System.out.print(info : );show(a);}
} CompType.java package com.example.test;import java.util.Arrays;
import java.util.SplittableRandom;import static com.example.test.ArrayShow.show;public class CompType implements ComparableCompType {private static int count 1;private static SplittableRandom r new SplittableRandom(47);int i;int j;public CompType(int n1, int n2) {i n1;j n2;}public static CompType get() {return new CompType(r.nextInt(100), r.nextInt(100));}public static void main(String[] args) {CompType[] a new CompType[12];Arrays.setAll(a, n - get());show(Before sorting, a);Arrays.sort(a);show(After sorting, a);}Overridepublic String toString() {String result [i i , j j ];if (count % 3 0) {result \n;}return result;}Overridepublic int compareTo(CompType rv) {return (i rv.i ? -1 : (i rv.i ? 0 : 1));}
}当您定义比较方法时您有责任决定将一个对象与另一个对象进行比较意味着什么。这里在比较中只使用i值和j值将被忽略。
get() 方法通过使用随机值初始化CompType对象来构建它们。在 main() 中get() 与 Arrays.setAll() 一起使用以填充一个 CompType类型 数组然后对其排序。如果没有实现 Comparable接口那么当您试图调用 sort() 时您将在运行时获得一个 ClassCastException 。这是因为 sort() 将其参数转换为 Comparable类型。
现在假设有人给了你一个没有实现 Comparable接口 的类或者给了你一个实现 Comparable接口 的类但是你不喜欢它的工作方式而愿意有一个不同的对于此类型的比较方法。为了解决这个问题创建一个实现 Comparator 接口的单独的类(在集合一章中简要介绍)。它有两个方法compare() 和 equals()。但是除了特殊的性能需求外您不需要实现 equals()因为无论何时创建一个类它都是隐式地继承自 ObjectObject 有一个equals()。您可以只使用默认的 Object equals() 来满足接口的规范。
集合类(注意复数;我们将在下一章节讨论它) 包含一个方法 reverseOrder()它生成一个来 Comparator比较器反转自然排序顺序。这可以应用到比较对象
import java.util.Arrays;
import java.util.Collections;import static com.example.test.ArrayShow.show;public class Reverse {public static void main(String[] args) {CompType[] a new CompType[12];Arrays.setAll(a, n - CompType.get());show(Before sorting, a);Arrays.sort(a, Collections.reverseOrder());show(After sorting, a);}
}您还可以编写自己的比较器。这个比较CompType对象基于它们的j值而不是它们的i值:
import java.util.Arrays;
import java.util.Comparator;import static com.example.test.ArrayShow.show;class CompTypeComparator implements ComparatorCompType {Overridepublic int compare(CompType o1, CompType o2) {return (o1.j o2.j ? -1 : (o1.j o2.j ? 0 : 1));}
}public class ComparatorTest {public static void main(String[] args) {CompType[] a new CompType[12];Arrays.setAll(a, n - CompType.get());show(Before sorting, a);Arrays.sort(a, new CompTypeComparator());show(After sorting, a);}
}Arrays.sort 的使用
使用内置的排序方法您可以对实现了 Comparable 接口或具有 Comparator 的任何对象数组 或 任何原生数组进行排序。这里我们生成一个随机字符串对象数组并对其排序: ConvertTo.java package com.example.test;public interface ConvertTo {static boolean[] primitive(Boolean[] in) {boolean[] result new boolean[in.length];for (int i 0; i in.length; i) {result[i] in[i]; // Autounboxing}return result;}static char[] primitive(Character[] in) {char[] result new char[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static byte[] primitive(Byte[] in) {byte[] result new byte[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static short[] primitive(Short[] in) {short[] result new short[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static int[] primitive(Integer[] in) {int[] result new int[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static long[] primitive(Long[] in) {long[] result new long[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static float[] primitive(Float[] in) {float[] result new float[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static double[] primitive(Double[] in) {double[] result new double[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}// Convert from primitive array to wrapped array:static Boolean[] boxed(boolean[] in) {Boolean[] result new Boolean[in.length];for (int i 0; i in.length; i) {result[i] in[i]; // Autoboxing}return result;}static Character[] boxed(char[] in) {Character[] result new Character[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static Byte[] boxed(byte[] in) {Byte[] result new Byte[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static Short[] boxed(short[] in) {Short[] result new Short[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static Integer[] boxed(int[] in) {Integer[] result new Integer[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static Long[] boxed(long[] in) {Long[] result new Long[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static Float[] boxed(float[] in) {Float[] result new Float[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}static Double[] boxed(double[] in) {Double[] result new Double[in.length];for (int i 0; i in.length; i) {result[i] in[i];}return result;}
}Rand.java package com.example.test;import java.util.*;
import java.util.function.*;
import static com.example.test.ConvertTo.primitive;public interface Rand {int MOD 10_000;class Boolean implements Supplierjava.lang.Boolean {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Boolean get() {return r.nextBoolean();}public java.lang.Boolean get(int n) {return get();}public java.lang.Boolean[] array(int sz) {java.lang.Boolean[] result new java.lang.Boolean[sz];Arrays.setAll(result, n - get());return result;}}class Pboolean {public boolean[] array(int sz) {return primitive(new Boolean().array(sz));}}class Byteimplements Supplierjava.lang.Byte {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Byte get() {return (byte) r.nextInt(MOD);}public java.lang.Byte get(int n) {return get();}public java.lang.Byte[] array(int sz) {java.lang.Byte[] result new java.lang.Byte[sz];Arrays.setAll(result, n - get());return result;}}class Pbyte {public byte[] array(int sz) {return primitive(new Byte().array(sz));}}class Characterimplements Supplierjava.lang.Character {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Character get() {return (char) r.nextInt(a, z 1);}public java.lang.Character get(int n) {return get();}public java.lang.Character[] array(int sz) {java.lang.Character[] result new java.lang.Character[sz];Arrays.setAll(result, n - get());return result;}}class Pchar {public char[] array(int sz) {return primitive(new Character().array(sz));}}class Shortimplements Supplierjava.lang.Short {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Short get() {return (short) r.nextInt(MOD);}public java.lang.Short get(int n) {return get();}public java.lang.Short[] array(int sz) {java.lang.Short[] result new java.lang.Short[sz];Arrays.setAll(result, n - get());return result;}}class Pshort {public short[] array(int sz) {return primitive(new Short().array(sz));}}class Integerimplements Supplierjava.lang.Integer {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Integer get() {return r.nextInt(MOD);}public java.lang.Integer get(int n) {return get();}public java.lang.Integer[] array(int sz) {int[] primitive new Pint().array(sz);java.lang.Integer[] result new java.lang.Integer[sz];for (int i 0; i sz; i) {result[i] primitive[i];}return result;}}class Pint implements IntSupplier {SplittableRandom r new SplittableRandom(47);Overridepublic int getAsInt() {return r.nextInt(MOD);}public int get(int n) {return getAsInt();}public int[] array(int sz) {return r.ints(sz, 0, MOD).toArray();}}class Long implements Supplierjava.lang.Long {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Long get() {return r.nextLong(MOD);}public java.lang.Long get(int n) {return get();}public java.lang.Long[] array(int sz) {long[] primitive new Plong().array(sz);java.lang.Long[] result new java.lang.Long[sz];for (int i 0; i sz; i) {result[i] primitive[i];}return result;}}class Plong implements LongSupplier {SplittableRandom r new SplittableRandom(47);Overridepublic long getAsLong() {return r.nextLong(MOD);}public long get(int n) {return getAsLong();}public long[] array(int sz) {return r.longs(sz, 0, MOD).toArray();}}class Floatimplements Supplierjava.lang.Float {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Float get() {return (float) trim(r.nextDouble());}public java.lang.Float get(int n) {return get();}public java.lang.Float[] array(int sz) {java.lang.Float[] result new java.lang.Float[sz];Arrays.setAll(result, n - get());return result;}}class Pfloat {public float[] array(int sz) {return primitive(new Float().array(sz));}}static double trim(double d) {return((double) Math.round(d * 1000.0)) / 100.0;}class Double implements Supplierjava.lang.Double {SplittableRandom r new SplittableRandom(47);Overridepublic java.lang.Double get() {return trim(r.nextDouble());}public java.lang.Double get(int n) {return get();}public java.lang.Double[] array(int sz) {double[] primitive new Rand.Pdouble().array(sz);java.lang.Double[] result new java.lang.Double[sz];for (int i 0; i sz; i) {result[i] primitive[i];}return result;}}class Pdouble implements DoubleSupplier {SplittableRandom r new SplittableRandom(47);Overridepublic double getAsDouble() {return trim(r.nextDouble());}public double get(int n) {return getAsDouble();}public double[] array(int sz) {double[] result r.doubles(sz).toArray();Arrays.setAll(result,n - result[n] trim(result[n]));return result;}}class Stringimplements Supplierjava.lang.String {SplittableRandom r new SplittableRandom(47);private int strlen 7; // Default lengthpublic String() {}public String(int strLength) {strlen strLength;}Overridepublic java.lang.String get() {return r.ints(strlen, a, z 1).collect(StringBuilder::new,StringBuilder::appendCodePoint,StringBuilder::append).toString();}public java.lang.String get(int n) {return get();}public java.lang.String[] array(int sz) {java.lang.String[] result new java.lang.String[sz];Arrays.setAll(result, n - get());return result;}}
}import java.util.Arrays;
import java.util.Collections;import static com.example.test.ArrayShow.show;public class StringSorting {public static void main(String[] args) {String[] sa new Rand.String().array(20);show(Before sort, sa);Arrays.sort(sa);show(After sort, sa);Arrays.sort(sa, Collections.reverseOrder());show(Reverse sort, sa);Arrays.sort(sa, String.CASE_INSENSITIVE_ORDER);show(Case-insensitive sort, sa);}
}注意字符串排序算法中的输出。它是字典式的所以它把所有以大写字母开头的单词放在前面然后是所有以小写字母开头的单词。(电话簿通常是这样分类的。)无论大小写要将单词组合在一起请使用 String.CASE_INSENSITIVE_ORDER 如对sort()的最后一次调用所示。
Java标准库中使用的排序算法被设计为最适合您正在排序的类型----原生类型的快速排序和对象的归并排序。
并行排序
如果排序性能是一个问题那么可以使用 Java 8 parallelSort()它为所有不可预见的情况(包括数组的排序区域或使用了比较器)提供了重载版本。为了查看相比于普通的sort(), parallelSort() 的优点我们使用了用来验证代码时的 JMH
dependencygroupIdorg.openjdk.jmh/groupIdartifactIdjmh-core/artifactIdversion1.29/version
/dependencyParallelSort.java import org.openjdk.jmh.annotations.*;import java.util.Arrays;State(Scope.Thread)
public class ParallelSort {private long[] la;Setuppublic void setup() {la new Rand.Plong().array(100_000);}Benchmarkpublic void sort() {Arrays.sort(la);}Benchmarkpublic void parallelSort() {Arrays.parallelSort(la);}
}parallelSort() 算法将大数组拆分成更小的数组直到数组大小达到极限然后使用普通的 Arrays .sort() 方法。然后合并结果。该算法需要不大于原始数组的额外工作空间。
您可能会看到不同的结果但是在我的机器上并行排序将速度提高了大约3倍。由于并行版本使用起来很简单所以很容易考虑在任何地方使用它而不是 Arrays.sort ()。当然它可能不是那么简单—看看微基准测试。
binarySearch二分查找
一旦数组被排序您就可以通过使用 Arrays.binarySearch() 来执行对特定项的快速搜索。但是如果尝试在未排序的数组上使用 binarySearch()结果是不可预测的。下面的示例使用 Rand.Pint 类来创建一个填充随机整形值的数组然后调用 getAsInt() (因为 Rand.Pint 是一个 IntSupplier)来产生搜索值:
import java.util.Arrays;import static com.example.test.ArrayShow.show;public class ArraySearching {public static void main(String[] args) {Rand.Pint rand new Rand.Pint();int[] a new Rand.Pint().array(25);Arrays.sort(a);show(Sorted array, a);while (true) {int r rand.getAsInt();int location Arrays.binarySearch(a, r);if (location 0) {System.out.println(Location of r is location , a[ location ] is a[location]);break; // Out of while loop}}}
}在while循环中随机值作为搜索项生成直到在数组中找到其中一个为止。
如果找到了搜索项Arrays.binarySearch() 将生成一个大于或等于零的值。否则它将产生一个负值表示如果手动维护已排序的数组则应该插入元素的位置。产生的值是 -(插入点) - 1 。插入点是大于键的第一个元素的索引如果数组中的所有元素都小于指定的键则是 a.size() 。
如果数组包含重复的元素则无法保证找到其中的那些重复项。搜索算法不是为了支持重复的元素而是为了容忍它们。如果需要没有重复元素的排序列表可以使用 TreeSet (用于维持排序顺序)或 LinkedHashSet (用于维持插入顺序)。这些类自动为您处理所有的细节。只有在出现性能瓶颈的情况下才应该使用手工维护的数组替换这些类中的一个。
如果使用比较器(原语数组不允许使用比较器进行排序)对对象数组进行排序那么在执行 binarySearch() (使用重载版本的binarySearch())时必须包含相同的比较器。例如可以修改 StringSorting.java 来执行搜索:
import java.util.Arrays;import static com.example.test.ArrayShow.show;public class AlphabeticSearch {public static void main(String[] args) {String[] sa new Rand.String().array(30);Arrays.sort(sa, String.CASE_INSENSITIVE_ORDER);show(sa);int index Arrays.binarySearch(sa, sa[10], String.CASE_INSENSITIVE_ORDER);System.out.println(Index: index \n sa[index]);}
}比较器必须作为第三个参数传递给重载的 binarySearch() 。在本例中成功是有保证的因为搜索项是从数组本身中选择的。
parallelPrefix并行前缀
没有“prefix()”方法只有 parallelPrefix()。这类似于 Stream 类中的 reduce() 方法:它对前一个元素和当前元素执行一个操作并将结果放入当前元素位置: Count.java package com.example.test;import java.util.*;
import java.util.function.*;import static com.example.test.ConvertTo.primitive;public interface Count {class Booleanimplements Supplierjava.lang.Boolean {private boolean b true;Overridepublic java.lang.Boolean get() {b !b;return java.lang.Boolean.valueOf(b);}public java.lang.Boolean get(int n) {return get();}public java.lang.Boolean[] array(int sz) {java.lang.Boolean[] result new java.lang.Boolean[sz];Arrays.setAll(result, n - get());return result;}}class Pboolean {private boolean b true;public boolean get() {b !b;return b;}public boolean get(int n) {return get();}public boolean[] array(int sz) {return primitive(new Boolean().array(sz));}}class Byteimplements Supplierjava.lang.Byte {private byte b;Overridepublic java.lang.Byte get() {return b;}public java.lang.Byte get(int n) {return get();}public java.lang.Byte[] array(int sz) {java.lang.Byte[] result new java.lang.Byte[sz];Arrays.setAll(result, n - get());return result;}}class Pbyte {private byte b;public byte get() {return b;}public byte get(int n) {return get();}public byte[] array(int sz) {return primitive(new Byte().array(sz));}}char[] CHARS abcdefghijklmnopqrstuvwxyz.toCharArray();class Characterimplements Supplierjava.lang.Character {private int i;Overridepublic java.lang.Character get() {i (i 1) % CHARS.length;return CHARS[i];}public java.lang.Character get(int n) {return get();}public java.lang.Character[] array(int sz) {java.lang.Character[] result new java.lang.Character[sz];Arrays.setAll(result, n - get());return result;}}class Pchar {private int i;public char get() {i (i 1) % CHARS.length;return CHARS[i];}public char get(int n) {return get();}public char[] array(int sz) {return primitive(new Character().array(sz));}}class Shortimplements Supplierjava.lang.Short {short s;Overridepublic java.lang.Short get() {return s;}public java.lang.Short get(int n) {return get();}public java.lang.Short[] array(int sz) {java.lang.Short[] result new java.lang.Short[sz];Arrays.setAll(result, n - get());return result;}}class Pshort {short s;public short get() {return s;}public short get(int n) {return get();}public short[] array(int sz) {return primitive(new Short().array(sz));}}class Integerimplements Supplierjava.lang.Integer {int i;Overridepublic java.lang.Integer get() {return i;}public java.lang.Integer get(int n) {return get();}public java.lang.Integer[] array(int sz) {java.lang.Integer[] result new java.lang.Integer[sz];Arrays.setAll(result, n - get());return result;}}class Pint implements IntSupplier {int i;public int get() {return i;}public int get(int n) {return get();}Overridepublic int getAsInt() {return get();}public int[] array(int sz) {return primitive(new Integer().array(sz));}}class Longimplements Supplierjava.lang.Long {private long l;Overridepublic java.lang.Long get() {return l;}public java.lang.Long get(int n) {return get();}public java.lang.Long[] array(int sz) {java.lang.Long[] result new java.lang.Long[sz];Arrays.setAll(result, n - get());return result;}}class Plong implements LongSupplier {private long l;public long get() {return l;}public long get(int n) {return get();}Overridepublic long getAsLong() {return get();}public long[] array(int sz) {return primitive(new Long().array(sz));}}class Floatimplements Supplierjava.lang.Float {private int i;Overridepublic java.lang.Float get() {return java.lang.Float.valueOf(i);}public java.lang.Float get(int n) {return get();}public java.lang.Float[] array(int sz) {java.lang.Float[] result new java.lang.Float[sz];Arrays.setAll(result, n - get());return result;}}class Pfloat {private int i;public float get() {return i;}public float get(int n) {return get();}public float[] array(int sz) {return primitive(new Float().array(sz));}}class Doubleimplements Supplierjava.lang.Double {private int i;Overridepublic java.lang.Double get() {return java.lang.Double.valueOf(i);}public java.lang.Double get(int n) {return get();}public java.lang.Double[] array(int sz) {java.lang.Double[] result new java.lang.Double[sz];Arrays.setAll(result, n - get());return result;}}class Pdouble implements DoubleSupplier {private int i;public double get() {return i;}public double get(int n) {return get();}Overridepublic double getAsDouble() {return get(0);}public double[] array(int sz) {return primitive(new Double().array(sz));}}
}ParallelPrefix1.java import java.util.Arrays;import static com.example.test.ArrayShow.show;public class ParallelPrefix1 {public static void main(String[] args) {int[] nums new Count.Pint().array(10);show(nums);System.out.println(Arrays.stream(nums).reduce(Integer::sum).getAsInt());Arrays.parallelPrefix(nums, Integer::sum);show(nums);System.out.println(Arrays.stream(new Count.Pint().array(6)).reduce(Integer::sum).getAsInt());}
}这里我们对数组应用Integer::sum。在位置0中它将先前计算的值(因为没有先前的值)与原始数组位置0中的值组合在一起。在位置1中它获取之前计算的值(它只是存储在位置0中)并将其与位置1中先前计算的值相结合。依次往复。
使用 Stream.reduce()您只能得到最终结果而使用 Arrays.parallelPrefix()您还可以得到所有中间计算以确保它们是有用的。注意第二个 Stream.reduce() 计算的结果已经在 parallelPrefix() 计算的数组中。
使用字符串可能更清楚:
import java.util.Arrays;import static com.example.test.ArrayShow.show;public class ParallelPrefix2 {public static void main(String[] args) {String[] strings new Rand.String(1).array(8);show(strings);Arrays.parallelPrefix(strings, (a, b) - a b);show(strings);}
}如前所述使用流进行初始化非常优雅但是对于大型数组这种方法可能会耗尽堆空间。使用 setAll() 执行初始化更节省内存:
import java.util.Arrays;public class ParallelPrefix3 {static final int SIZE 10_000_000;public static void main(String[] args) {long[] nums new long[SIZE];Arrays.setAll(nums, n - n);Arrays.parallelPrefix(nums, Long::sum);System.out.println(First 20: nums[19]);System.out.println(First 200: nums[199]);System.out.println(All: nums[nums.length - 1]);}
}因为正确使用 parallelPrefix() 可能相当复杂所以通常应该只在存在内存或速度问题(或两者都有)时使用。否则Stream.reduce() 应该是您的首选。
