[JDK optimization strategy] java.util.Arrays sort of

2010-05-12  来源:本站原创  分类:Tech  人气:192 

On the inscription: JDK, there are many algorithm has the bright spot, it is worth to study.

] [Java.uti.Arrays to operate the array contains (such as sorting and searching) in various ways. This article we study a number of masters to write sorting algorithm.


(1) sorting an array of basic data types, such as Arrays.sort (int []) and so on. After using a quick sort tuning. The algorithm is adapted from Jon L. Bentley and M. Douglas McIlroy co-author of Engineering a Sort Function ", Software-Practice and Experience Vol. 23 (11) P. 1249-1265 (November 1993). This algorithm is in many data sets provided n * log (n) performance, which led to other quick sort would reduce the quadratic performance.

The following are in tune JDK source code for quick sort algorithm:

/**
     *  Adds the specified range of the integer array sorted in ascending order  .
     * x[]  Pending row array
     * off  First off from the array elements beginning sort
     * len  The length of the array
     */
    private static void sort1(int x[], int off, int len) {
        // Optimization  1: In a small  (size<7) Array, directly into a sort of efficiency than quick sort high  .
        if (len < 7) {
            for (int i=off; i<len+off; i++)
                for (int j=i; j>off && x[j-1]>x[j]; j--)
                        swap(x, j, j-1);
            return;
        }

        // Optimization  2: Carefully select a Division element, i.e. the pivot
        // If you are a small array  (size<=7), Directly from the Middle element as the pivot
        // If it is a medium-sized arrays  (7=<size<=40), The first in the array.  . Tail three locations on the number of intermediate size in a pivot
        // If it is a large array  (size>40), The nine specified number in a pseudo-random number in the  ( The number of intermediate size  s)
        int m = off + (len >> 1);
        if (len > 7) {
            int l = off;
            int n = off + len - 1;
            if (len > 40) {
                        int s = len/8;
                        l = med3(x, l, l+s, l+2*s);
                        m = med3(x, m-s,   m,   m+s);
                        n = med3(x, n-2*s, n-s, n);
            }
            m = med3(x, l, m, n);
        }
        int v = x[m];

        // Optimization  3: Every time the pivot of Division v  , Which results in a form a shape such as
(<v)* v*
 (>v)* An array of  

 // Stage 1, formation   v* (<v)* (>v)* v*  An array of
        int a = off, b = a, c = off + len - 1, d = c;
        while(true) {
            while (b <= c && x[b] <= v) {
                        if (x[b] == v)
                            swap(x, a++, b);
                        b++;
            }
            while (c >= b && x[c] >= v) {
                        if (x[c] == v)
                            swap(x, c, d--);
                        c--;
            }
            if (b > c)
                break;
            swap(x, b++, c--);
        }

        // Phase II, will, and pivot equal exchange to the middle of the array element
        int s, n = off + len;
        s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
        s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

        // Phase three, recursive sort and pivot not equal interval are elements
        if ((s = b-a) > 1)
            sort1(x, off, s);
        if ((s = d-c) > 1)
            sort1(x, n-s, s);
    }

★ Optimization 1: small (size <7) in the array, directly into the sort of efficiency than the high-speed sorting.

Do not have a ranking in any case are the best "summary based on the comparison of internal order." O (N ^ 2) level of the sort seems to be worse than all the more advanced sort. There are in fact not the case, Arrays of sort () algorithm gave us a good example. When the row of the array to be very small when the (JDK in the size threshold INSERTIONSORT_THRESHOLD = 7), rather than directly into the fast row sorting, merge sort is better.

The reason is simple. Array of small, relatively simple algorithm is the number of no more than the number of advanced algorithms. On the contrary, such as fast row, merge sort algorithm using recursion and other advanced operations, operating costs of higher pay.

★ Optimization 2: well-chosen partition element, that is the pivot.

Fast row has a worst-case, which degenerated into the worst start sorting efficiency (see "exchange sort"). The main causes leading to this choice is not able to pivot the entire array is divided into two roughly equal parts. For example, the basic order of the array, select the first element will be generated as the pivot of this degeneration.

That being the case, we can look Arryas.sort () is how we choose to pivot.

● If it is small-scale arrays (size <= 7), directly taking the middle element as pivot.

● If it is medium-sized array (7 = <size <= 40), the first in the array, in the end the number three position in the middle of the size of the number taken as the pivot ● If it is large-scale array (size> 40) , at 9, fetch a specified number of pseudo-median (the middle number of the size of s)

Small scale, such as to avoid borrowing from an array of smaller or larger numbers as the number of pivot. It is worth mentioning that a large scale, the first in the array to find nine data ( Can through the source code Faxian the 9 position of the data is more evenly distributed across the array only); and then every 3 months data Zhao in the median; Finally, on 3 and then find the median median as a pivot.

Think about this carefully chosen pivot, making quick arrangements for a very small probability of a worst-case incident.

★ Optimization 3: According to the pivot v divided to form a shape like (<v)* v* (> v) * array

Conventional rapid ordering scheme, is making moves to the pivot element in the array than the middle. All the elements before the pivot is less than or equal to the pivot, then all the elements greater than pivot. However, with the pivot element equal and can not be moved to a position near the pivot. This is the Arrays.sort () algorithm optimization greatly.

We give an example to illustrate the details of 15,93,15,41,6,15,22,7,15,20 Optimization Arrays

First pivot: v = 15

Stage 1, the formation of v * (<v)* (> v) * v * array:

15:15, 7,6, 41,20,22,93, 15:15

We found, with the pivot element equal on both sides to move to the array. While smaller than the pivot elements and pivot larger than the separate elements have also come.

Phase II will pivot and exchange with the pivot element equal to the middle position of the array

7,6, 15:15, 15:15, 41,20,22,93

Stage III, recursive sorting and pivot elements are not equal interval (7,6) and (41,20,22,93)

Think about it more for repeat element array, such optimization can undoubtedly get better efficiency.

(1) sorting an array object, such as Arrays.sort (Object []) so. After using a modified merge sort. There are also several optimized its glittering.

Here is the improved JDK source code merge sort algorithm:

/**
     *  Adds the specified range of an array of objects according to the natural order of ascending order  .
     * src[]  The original question row of an array
     * dest[]  Purpose to row array
     * low  To be ranked lower bound of the array location
     * high  To be the upper bound of an array of row position
     * off  First off from the array elements beginning sort
     */
    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // Optimization  1: Very small array of sort, the efficiency of direct insertion sort rather than merging to high  .
        // Scale up within the INSERTIONSORT_THRESHOLD = 7
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        //  Recursive sort dest half element and assigned to  src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // Optimization  2: If low child list of the highest element smaller than the high child list of the minimum elements, it ignores the merge
        // If you need merging both ends  low~(middle-1),middle~high Have been ordered, i.e.  src[mid-1]==src[mid].
        // Then simply copy the src  low~high You can assign values to corresponding dest  , There is no need to merge  .
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // The src is a two-part merge  , And assigned to  dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

★ Optimization 1: Quicksort with the above

★ Optimization 2: If the low sub-list is less than the maximum element of the list of high sub-minimum element, ignore the merger. The optimization of the basic order of the sequence of measures is no doubt a great efficiency improvement.

相关文章
  • [JDK optimization strategy] java.util.Arrays sort of 2010-05-12

    On the inscription: JDK, there are many algorithm has the bright spot, it is worth to study. ] [Java.uti.Arrays to operate the array contains (such as sorting and searching) in various ways. This article we study a number of masters to write sorting

  • Use of java.util.Arrays 2011-05-06

    java.util.Arrays features: 1. The tools are sorted features eight basic data types, Like public static void sort (char [] a) method. Can also specify the sort of start and end public static void sort (char [] a, int fromIndex, int toIndex) Also be ab

  • java.util.Collections.sort right to sort the List 2010-03-23

    List<userDO> list = new ArrayList<userDO>(); java.util.Collections.sort(list, new Comparator<userDO>(){ @Override public int compare(userDO o1, userDO o2) { return o2.getId().compareTo(o1.getId()); }});

  • Java 容器 & 泛型:四.Colletions.sort 和 Arrays.sort 的算法 2015-04-18

    Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket 本来准备讲 Map集合 ,还是喜欢学到哪里总结吧.最近面试期准备准备,我是一员,成功被阿里在线笔试秒杀回绝.平常心,继续努力.这次带来 Collections 和 Arrays 类中的经典算法剖析. 一.Colletions和Arrays Collentions 此类完全是服务容器的"包装器".提供了一些操作或者返回容器的静态方法.而Arrays是用来操作数组的各种方法.其中它们的联系在于

  • ava.util.Arrays and java.util.Collections 2011-04-20

    First have to know two classes: java.util.Arrays and java.util.Collections (the difference between attention and Collection) Collection is a collection of top-level interface to the framework, and Collections contains many static methods are. We use

  • language-sensitive class of java.util 2010-08-19

    In the util package, there are several classes with the language, time zone and other related classes. It is these java classes, so with the language or time zone-sensitive items to achieve them has become quite easy, and safe. Including the Date, Ca

  • Sorting an array Arrays.sort (Collection) 2010-03-29

    package com.j2se.sort; import java.text.RuleBasedCollator; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; public class ArraysSort { public static void main(String[] args) { // intArraySortByAsc(); // stringArraySo

  • java的arrays数组排序示例分享 2013-12-08

    排序算法,基本的高级语言都有一些提供.C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(不是Array).用这些排序时,都可以写自己的排序规则 Java API对Arrays类的说明是:此类包含用来操作数组(比如排序和搜索)的各种方法. 1.对基本数据类型的数组的排序 说明: (1)Arrays类中的sort()使用的是"经过调优的快速排序法"; (2)比如int[],double[],char[]等基数据类型的数组,Arrays类之只是提供了默认的升

  • java多线程学习-java.util.concurrent详解(四) BlockingQueue 2015-04-09

    前面一篇blog 我们主要探讨了ScheduledThreadPoolExecutor定时器的使用 --------------------------------------------------------------------------------- 7.BlockingQueue "支持两个附加操作的 Queue,这两个操作是:获取元素时等待队列变为非空,以及存储元素时等待空间变得可用." 这里我们主要讨论BlockingQueue的最典型实现:LinkedBlockin

  • Arrays.asList returns ArrayList is not a java.util.ArrayList, call the newspaper UnsupportedOperationException 2010-09-14

    Calling code: String[] tmpIds = ids.split(","); rt = Arrays.asList(tmpIds); rt.add(String.valueOf(userId)); Arrays.asList (tmpIds) returns a fixed-size list /** * Returns a fixed-size list backed by the specified array. (Changes to * the returne

  • JDK java.util.logging.Logger to the configuration file control of log output 2009-12-25

    Simple implementation in the next class java.util.logging.Logger to use JDK logging. Way mainly along the lines of log4j configuration file used to configure the log output. Network java.util.logging.Logger article on how to use a lot of, but not a c

  • 编译环境与生成环境的JDK版本不一样,报:java.util.zip.ZipException: 2014-09-10

    发布应用的时候,发现生产环境报将编译环境编译好的WAR包拿到生产环境,报异常如下: [java] view plain copy Caused by: java.util.zip.ZipException: error in opening zip file at java.util.zip.ZipFile.open(Native Method) at java.util.zip.ZipFile.<init>(ZipFile.java:127) at java.util.jar.JarFile

  • JDK learning - java. Util.concurrent blocking queue - 1 2010-07-30

    Tiger java.util.concurrent package provides the framework in the collection BlockingQueue interface and added five block queue class. Briefly put, blocking queue, which means that when the queue is no space, adding elements of the thread to perform o

  • JDK learning - java. Util.concurrent.ConcurrentMap output and input 2010-07-30

    The new interface and ConcurrentHashMap java.util.concurrent.ConcurrentMap achieve key does not exist only in the element added to the map, only the key exists and can be mapped to a specific value to remove an element from the map. ConcurrentMap in

  • Performance Optimization of Java 2009-05-25

    Java in the mid nineties after the impressive win at the same time, but also attracted some criticism. Won the admiration of the major Java are cross-platform interoperability, the so-called "Write Once, Run Anywhere". However, because of Java's

  • JDK1.5 in the thread pool (java.util.concurrent.ThreadPoolExecut) 2010-03-29

    In the multi-threaded master of the contributions of Doug Lea, in the JDK1.5 added a number of features for concurrent support of, for example: the thread pool. I. Introduction thread pool category java.util.concurrent.ThreadPoolExecutor, common cons

  • java.util collections Xiangjie 2010-03-26

    Doing Java development, we often want to use some of the data collection, JDK provides us with a range of application classes to implement basic data structures. These classes are in the java.util package. A brief description of this: Collection List

  • Java.util.concurrent need to know about the 5 things (1) 2010-08-10

    This Author: Ted Neward Address: http://www.ibm.com/developerworks/java/library/j-5things4.html This concurrent programming guide for beginners (like me) = = through concurrent multi-threaded programming ~ Collections Description: Write to good execu

  • JDK1.5 reproduced in thread pool (java.util.concurrent.ThreadPoolExecutor) Brief Introduction to 2010-10-20

    Doug Lea in the multi-threaded master of the contribution, in JDK1.5 added support for many of the complicated features, such as: the thread pool. I. Introduction thread pool class java.util.concurrent.ThreadPoolExecutor, common construction methods

  • JAVA中Collections.sort()实现List排序的公共方法和自定义方法 2013-08-09

    本文是受开源中国中的一篇文章启发而写(找不到连接了,所以暂时木法贴出来,一旦找到立马贴出来),个别内容参考了开源中国会员的讨论,感谢! 1.java提供的默认list排序方法 主要代码: List<String> list = new ArrayList(); list.add("刘媛媛"); list.add("王硕"); list.add("李明"); list.add("刘迪"); list.add(&quo