Why sort?

In the world of the Web everything needs to be sorted. If the list is not sorted, it is difficult to find accurate information at a glance. In the same way, at the dinner table during festivals, people will be distinguished according to the order of seats. Even before the banquet, people will also be divided into three and six levels of social status in words.

This article focuses on sorting different data structures using the “Jvav” Api. And its implementation principle, so friends you really know “Jvav”?

For common Oracle database sorting, if the order by clause is not added, it is based on the hidden column ROWID, which cannot achieve the purpose of accurate retrieval of data, often the data set sorting will be carried out in the database. But when we want to implement the final business sorting of linked lists, trees, graphs and other complex data results, we will use the Java sorting Api. Who didn’t have a problem with bubble sorting when we first started programming? But I rarely see it after writing Java WEB CRUD.

Comparator sort

To simulate the search ranking of a treasure, first define a Pojo to compare element attributes

import lombok.*;

/** * Created by brush makes me happy, self-discipline makes me free! * Imitate a treasure to determine the final display order according to the weight */
@Data
@AllArgsConstructor
public   class MbRelatedWeightResource {

    // Machine learning recommendation value (based on the prediction of thousands of user portraits)
    private Integer mlRecommended;
    // Expose price value (bidding ranking)
    private Integer throughWeight;
    // Popularity value (calculated by page views, favorites, favorable comments, repeat purchase rate of a certain time dimension...)
    private Integer heat;
}
Copy the code

Define the interface between the Comparable internal Comparator and the Comparator external Comparator to achieve the comparison of commodity search rankings of a treasure.

import lombok.NoArgsConstructor;
import studey.advance.datastructure.pojo.MbRelatedWeightResource;

import java.util.Collections;
import java.util.Comparator;
import java.util.Objects;

/** * Created by using the following two comparator interfaces for element comparison sorting **@seeJava.lang.Com parable The suffix -able indicates that this parable can only be used for internal comparison between the same type *@seeJava.util.Com parator The -or suffix indicates that the object can be used for external comparisons between types */
public class ComparerSortRecursion {

    public static class RelatedWeightComparable extends MbRelatedWeightResource implements Comparable<MbRelatedWeightResource> {

        public RelatedWeightComparable(Integer mlRecommended, Integer throughWeight, Integer heat) {
            super(mlRecommended, throughWeight, heat);
        }

        /** * Sort by rule **@paramO Similar element * compared to the current object@returnDescending comparison result is less than return positive number; Equals returns 0; Greater than return negative; * /
        @Override
        public int compareTo(MbRelatedWeightResource o) {

            /* Keep code clean */

            // Compare the recommended values
            if(! Objects.equals(this.getMlRecommended(), o.getMlRecommended())) {
                return this.getMlRecommended() < o.getMlRecommended() ? 1 : -1;
            }

            // If the exposure prices are equal then compare
            if(! Objects.equals(this.getThroughWeight(), o.getThroughWeight())) {
                return this.getThroughWeight() < o.getThroughWeight() ? 1 : -1;
            }

            // Compare the exposure price if the recommended values are equal
            if(! Objects.equals(this.getHeat(), o.getHeat())) {
                return this.getHeat() < o.getHeat() ? 1 : -1;
            }

            return 0; }}@NoArgsConstructor
    public static class RelatedWeightComparator implements Comparator<MbRelatedWeightResource> {

        /** * Sort by rule **@paramO1 Generic object 1 *@paramO2 Generic object 2 *@returnDescending comparison result is less than return positive number; Equals returns 0; Greater than return negative; * /
        @Override
        public int compare(MbRelatedWeightResource o1, MbRelatedWeightResource o2) {
            // Compare the recommended values
            if(! Objects.equals(o1.getMlRecommended(), o2.getMlRecommended())) {return o1.getMlRecommended() < o2.getMlRecommended() ? 1 : -1;
            }

            // If the exposure prices are equal then compare
            if(! Objects.equals(o1.getThroughWeight(), o2.getThroughWeight())) {return o1.getThroughWeight() < o2.getThroughWeight() ? 1 : -1;
            }

            // Compare the exposure price if the recommended values are equal
            if(! Objects.equals(o1.getHeat(), o2.getHeat())) {return o1.getHeat() < o2.getHeat() ? 1 : -1;
            }

            return 0;
        }

        @Override
        public Comparator<MbRelatedWeightResource> reversed(a) {
            return Collections.reverseOrder(this); }}}Copy the code

Perform relevant unit tests.

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import studey.advance.basearithmetic.sort.ComparerSortRecursion;
import studey.advance.datastructure.pojo.MbRelatedWeightResource;
import studey.advance.datastructure.utils.JsonUtil;

import java.util.*;
import java.util.stream.Collectors;

/** * Created by unit tests that use the following two comparator interfaces for comparison sorting of elements */
class ComparerSortRecursionTest extends ComparerSortRecursion {

    @Test
    @displayName (" Sort from largest to smallest by internal comparator ")
    void comparableCompareTo(a) {

        ArrayList<RelatedWeightComparable> comparableToList = new ArrayList<>();
        comparableToList.add(new RelatedWeightComparable(100.51.20));
        comparableToList.add(new RelatedWeightComparable(101.1.1));
        comparableToList.add(new RelatedWeightComparable(100.50.20));
        comparableToList.add(new RelatedWeightComparable(100.51.21));
        Collections.sort(comparableToList);
        System.out.println(JsonUtil.toJson(comparableToList));
    }

    @Test
    @displayName (" Sort from largest to smallest by external comparator ")
    void comparatorCompareTo(a) {
        List<MbRelatedWeightResource> comparatorList = new ArrayList<>();
        comparatorList.add(new MbRelatedWeightResource(100.51.20));
        comparatorList.add(new MbRelatedWeightResource(101.1.1));
        comparatorList.add(new MbRelatedWeightResource(100.50.20));
        comparatorList.add(new MbRelatedWeightResource(100.51.21));
        comparatorList.sort(newRelatedWeightComparator()); System.out.println(JsonUtil.toJson(comparatorList)); }}Copy the code

** There’s nothing wrong with running these two basic unit tests, but a typical real business scenario would iterate over the sublist structure by subsorting in a for loop! 六四运动

 @Test
    @displayName (" Sort from large to small by lambda comparator ")
    void comparatorChildListSort(a) throws InterruptedException {
        List<MbRelatedWeightResource> comparatorList = new ArrayList<>();
        comparatorList.add(new MbRelatedWeightResource(100.51.20));
        comparatorList.add(new MbRelatedWeightResource(101.1.1));
        comparatorList.add(new MbRelatedWeightResource(100.50.20));
        comparatorList.add(new MbRelatedWeightResource(100.51.21));

        for (MbRelatedWeightResource relatedWeightComparable : comparatorList) {
            / / iterator and enhanced for loop will ConcurrentModificationException times for sorting
            compareToList.sort(new ComparerSortRecursion.RelatedWeightComparator());
        }
        System.out.println(JsonUtil.toJson(comparatorList));
    }
Copy the code

The for loop throw ConcurrentModificationException sorting unit test.

java.util.ConcurrentModificationException at java.util.ArrayList
I t r . c h e c k F o r C o m o d i f i c a t i o n ( A r r a y L i s t . j a v a : 901 ) a t j a v a . u t i l . A r r a y L i s t Itr.checkForComodification(ArrayList.java:901) at java.util.ArrayList Itr.next(ArrayList.java:851) at advance.basearithmetic.sort.ComparerSortRecursionTest.comparatorChildListSort (ComparerSortRecursionTest.java:45)

at java.util.ArrayList.forEach(ArrayList.java:1249)

Let’s debug the Exception source!

public class ArrayList<E> extends AbstractList<E>...{
	This field is used for iterator and list iterator implementations returned by the iterator and list iterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a concurrent modification exception under code, code delete, code before, code set, or code add. This provides fail-fast behavior rather than nondeterministic behavior in the face of concurrent modifications during iterations. * /
    protected transient int modCount = 0;
    
    public E next(a) { checkForComodification(); . }private class Itr implements Iterator<E> {

      int expectedModCount = modCount;

      final void checkForComodification(a) {
          if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

For the rest of modCount annotations, subclasses using this field are optional. ** If you want a subclass to provide a fast fail iterator, then it simply increments the field’s (int, E) and delete methods (and any other methods that it will override, resulting in a list of structural modifications). ** A single call to add (int, E) or code remove (int) must add more than one value to that field, or the iterator (and list iterator) will throw a fake code concurrent modification exception. If the implementation does not wish to provide a fast fail iterator, this field can be ignored.

The unit test called the next() method and reported an error!

Abnormal reasons, the Iterator is dependent on AbstractList, in after the success of the judgment, in the ArrayList of newly added elements, and the Iterator is not synchronized, so throw ConcurrentModificationException. A collection that iterators and syntactic sugar (enhanced for loops) cannot modify while iterating through elements. Such as ArrayList, and LinkedList, HashMap, don’t ignore modCount field data structure.

This works if you use a for loop with lambda syntax.

 for (MbRelatedWeightResource relatedWeightComparable : compareToList) {
            / / iterator and enhanced for loop will ConcurrentModificationException times for sorting
            // Lambda sort works
     comparatorList = comparatorList.stream().sorted(
         Comparator.comparing(MbRelatedWeightResource::getMlRecommended)                          .thenComparing(MbRelatedWeightResource::getThroughWeight)
         .thenComparing(MbRelatedWeightResource::getHeat).reversed())
         .collect(Collectors.toList());
 }
Copy the code

The final output of the three unit tests is unified

Comparable is not recommended because changes to POJOs are easy to maintain, the use of inherited classes in the diagram is a bit redundant, and its Api is too monolithic with only compareTo() comparison functions, Comparator has less than 20 sorting apis, which can be used for simple tasks. Not only can the Comparator be written as a lambda expression, it can also be injected into the Spring container for sorting. Maintain a Comparator external collator if multiple scenarios require a unified collation. If a single scenario collates, use a lambda expression. Thanks to the JDK for the handy weapon!

Github.com/XiaoZiShan/…

The pros and cons of Lambda sorting

Start with basic lambda syntax

import studey.advance.datastructure.utils.JsonUtil;

import java.util.*;
import java.util.stream.Collectors;

/** * Created by manipulating data with lambda syntax */
public class LambdaGrammarDemo extends ComparerSortRecursion {

    public static void main(String[] args) {

        // Data final result type list or map or set

        / / before jdk8
        // Sort the list
        List<RelatedWeightComparable> compareToList = new ArrayList<>();
        compareToList.add(new RelatedWeightComparable(101.1.1));
        compareToList.add(new RelatedWeightComparable(100.50.20));
        compareToList.add(new RelatedWeightComparable(100.51.20));
        compareToList.add(new RelatedWeightComparable(100.51.21));
        // Call the comparator to sort
        compareToList.sort(new ComparerSortRecursion.RelatedWeightComparator().reversed());

        // Get the fields to form the list
        List<String> strings = new ArrayList<String>();
        for (RelatedWeightComparable relatedWeightComparable : compareToList) {
            strings.add(relatedWeightComparable.getThroughWeight().toString());
        }
        // Just the first three arguments
        List<String> stringx = new ArrayList<String>();

        for (int i = 0; i < 3; i++) {
            stringx.add(strings.get(i));
        }
        System.out.println(JsonUtil.toJson(stringx));
        Set sf = new HashSet<>(stringx);

        // Go back to step 1, please


        // Java8 lambda expressioncompareToList.sort(RelatedWeightComparable::compareTo); JsonUtil.toJson(compareToList.stream().sorted(Comparator.comparing(RelatedWeightComparable::getHeat).thenComparing(Relat edWeightComparable::getMlRecommended)) .map(RelatedWeightComparable::getThroughWeight).limit(3).collect(Collectors.toList())); System.out.println( JsonUtil.toJson(compareToList.stream().sorted(Comparator.comparing(RelatedWeightComparable::getHeat).thenComparing(Relat edWeightComparable::getMlRecommended)). limit(3).collect(Collectors.toMap(RelatedWeightComparable::getThroughWeight, RelatedWeightComparable::getHeat))));

        compareToList.forEach(v -> {
            v.setHeat(1);
            v.setThroughWeight(0);
        });

        System.out.println(JsonUtil.toJson(compareToList.stream().map(v -> {
            v.setMlRecommended(9);
            returnv; }).collect(Collectors.toList()))); }}Copy the code

Lambda fancy sort

import studey.advance.datastructure.pojo.MbRelatedWeightResource;

import java.util.List;
import java.util.stream.Collectors;

import static java.util.Comparator.*;

/** * Created by using lambda syntax */
public class LambdaSortRecursion  {
    Lambda implements the collation of the comparator
    public List<MbRelatedWeightResource> lambdaSort(List<MbRelatedWeightResource> mbList){
        return  mbList.stream().sorted(comparing(MbRelatedWeightResource::getMlRecommended)
            .thenComparing(MbRelatedWeightResource::getThroughWeight)
            .thenComparing(MbRelatedWeightResource::getHeat)).collect(Collectors.toList());
    }

    // lambda reverses the current collection order
    public List<MbRelatedWeightResource> lambdaReversalSort(List<MbRelatedWeightResource> mbList){
        return  mbList.stream().sorted(comparing(MbRelatedWeightResource::getMlRecommended)
            .thenComparing(MbRelatedWeightResource::getThroughWeight)
            .thenComparing(MbRelatedWeightResource::getHeat).reversed()).collect(Collectors.toList());
    }

    // lambda compatible with Comparable
    public List<ComparerSortRecursion.RelatedWeightComparable> lambdaComparableSort(List<ComparerSortRecursion.RelatedWeightComparable> mbList){
        return mbList.stream().sorted(ComparerSortRecursion.RelatedWeightComparable::compareTo).collect(Collectors.toList());
    }

    // Lambda compatible Comparator
    public List<MbRelatedWeightResource> lambdaComparatorSort(List<MbRelatedWeightResource> mbList){
        return mbList.stream().
            sorted(comparing(e -> e, newComparerSortRecursion.RelatedWeightComparator())).collect(Collectors.toList()); }}Copy the code

Github.com/XiaoZiShan/…

In summary, sorting is a good thing for lambda. How does it work? Let’s begin by analyzing the syntax of lambda. Take the code above for the current collection of lambda reversals as an example.

// The following comments are based on the relevant JDK source code
mbList
// Returns a continuous stream created with the mbList collection as its source.
    .stream()
// Returns a stream consisting of the elements of the stream, sorted according to the {@code Comparator} provided. For a stream() ordered stream, sorting is stable. ParallelStream () unordered streams are not guaranteed stability.
    .sorted(
    // Build the Comparator using Comparator's Lambda-style APIcomparing(MbRelatedWeightResource::getMlRecommended) .. thenComparing(...) .reversed())// Encapsulate the return structure of the stream after processing
    .collect(Collectors.toList());
Copy the code

Lambda stream sorting principle reference.

Collector is used specifically as an argument to Stream’s Collect method.

Related articles blog.csdn.net/qq_40660787…

About Lambda sort performance analysis blog.csdn.net/weixin_4083…

The next tech blog will delve into the lambda principle.

Java sorting principle analysis

    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null.0.0); }}Copy the code

American programmer TimPeter combined the advantages of merge sort and insertion sort to achieve the TimSort algorithm, avoiding the shortcomings of merge sort and insertion sort, compared with the previous merge sort, reduce the number of merge, compared with insertion sort, introduced the concept of binary search, improve the efficiency of sorting. For partially sorted arrays, the optimal average time complexity can reach O(n). For randomly sorted arrays, the time complexity is O(nlogn) and the average time complexity is O(nlogn). TimSort replaces merge sort in the JDK.

conclusion

In fact, comparators can be used not only for sorting, but also for grouping, and if they are equal they are grouped together. Java.lang.Com parable is created in 1.2, java.util.Comparator, and java.lang.Comparable is created in 1.2, and java.util.Comparator is used for internal sorting. One is in charge of external sorting. In 1.8, several apis were enhanced, making the extension with Lambda seamless and making the JDK compatible up and down. This is probably the charm of programming. Read excellent source code, good coding health!