java - 一道优化的小代码题目, 面试题

Question

问题:

1. Snack类的isExpired方法实现了什么功能?

2. 现有相当大量的snack对象(如一个长度100万的Snack对象数组)需要执行isExpired方法,执行时候发现效率低下, 请分析原因, 并给出优化方案?

为了方便交流学习, 我把完整的题目都贴出来了, 我主要的问题是第二问, 大家有没有好的办法?

代码如下:

public class Snack { 
    
    public Snack(String name, Date expirDate){ 
        this.name = name;
        this.expireDate = expireDate;
    }
    
    private String name;
    private Date expireDate;
    
    public boolean isExpired(){
        Date now = new Date();
        return now.compareTo(this.expireDate) > 0 ;
    }

}

Answer 1

Thanks for the invitation.

1. This can be found on Baidu. Returns true if the current date is greater than the object's expireDate.

2. My algorithm is not very accurate. Please correct me if I am wrong: first consider whether the expireDate of the objects is in order. Orderly can learn from the idea of ​​​​binary search. For example, from small to large, if an object can be found, all subsequent objects will return true.

Answer 2

First, you can look at the Date对象的compareTo方法的内部实现，会有clone operation first, so the overhead increases.

1. If isExpired方法的作用是判断当前对象是否已过期，如果expireDate is before the current server time, it is considered not expired, otherwise it is considered expired;

There are currently quite a large number of snack objects (such as an array of Snack objects with a length of 1 million) that need to execute the isExpired method

2. Since this expression is a bit ambiguous, I will explain it in two situations:
2.1. A Snack array with a length of 100W, traversing and executing the isExpired method, the question may be about JVM memory management and garbage collection mechanism, because the program will execute the isExpired method of these 1 million objects serially (assuming that the cost of creating these objects is ignored), and a new Date object, and compareTo will internally perform a clone operation on this.expireDate, so the overhead will be relatively large; isExpired方法，那题目考察的可能是JVM内存管理和垃圾回收机制，因为程序会串行执行这100W个对象的isExpired方法（假设忽略创建这些对象的开销），而每运行一次就会new一个Date对象，而compareTo内部又会对this.expireDate进行clone操作，所以开销会比较大；
2.2、在一定时间段内有大量的Snack对象并行执行isExpired2.2. There are a large number of Snacks within a certain period of time If the object

parallel

executes the isExpired method, then the question may focus on high concurrency processing. If you can also relate to the knowledge points of 2.1, you can get extra points;

Personally, I think 2.2 is more likely.
long或者int(精度要求不高的情况下)存储expireDate，如果是2.1，那可以把Date now = new Date()摞到方法外部（假设对时间的精度要求不是十分高），然后isExperied方法内部只需要比较now.getTime()和expireDate的值即可；如果是2.2且应用部署在集群环境下，那就不能在isExpired里面生成DateTalk about my optimization understanding of this code:
1. Use the object, because even if there is time synchronization between servers, time inconsistencies may occur. For example, the difference between machine A and machine B is 1 second. This situation is also possible. At this time, you can use a global time generator, and then the application calls this generator to obtain the current server time for comparison; 2. Confirm the accuracy of the

expiration time from the business, which is [year | month | day | hour | minutes | seconds | milliseconds]?, the storage and comparison strategies of different precisions can also be different. The higher the precision, the higher the cost.

The writing is rather messy. 🎜

Answer 3

If there is a large amount of data, add an overload to each isExpired() 中都去取一下时间，会比较耗时。
由于是在同一时刻顺序调用数组中每个对象的 isExpired()，可以假设是在同一时间进行比较，那么给 isExpired()

public boolean isExpired(long now) {
    return now > this.expireDate.getTime();
}

You can do this when calling

long now = System.currentTimeMillis();
for (int i = 0; i < all.length; i++) {
    all[i].isExpired(now);
}

Answer 4

Use System.currentTimeMillis() to compare time

Answer 5

public class Snack { 
    
    public Snack(String name, long expiredTime){ 
        this.name = name;
        this.expiredTime = expiredTime;
    }
    
    private String name;
    private long expiredTime;
    
    public boolean isExpired(){
        return System.currentTimeMillis() > expiredTime;
    }

}

Answer 6

Change the array into a priority queue, and only need to execute isExpired() on the top element of the heap each time, and the performance is improved from O(n) to O(1)

Answer 7

Now that I see something parallel, I want to use the new API of Java 8, parallel stream, haha, so I simply practiced it, for reference only

1. Use the traditional compareTo method of Date to compare

2. Compare using Date’s System.currentTimeMillis() > expiredDate.getTime() method

Each comparison method is executed 5 times to facilitate comparison, and each method uses 3 modes to execute

1. for loop execution mode

2. Stream loop execution mode

3. Parallel stream loop execution mode

The code is similar to this:

Snack[] arr = LongStream.iterate(0, a -> a+1).limit(1000000l).mapToObj(Snack::new).toArray(Snack[]::new);
Snack1[] arr1 = LongStream.iterate(0, a -> a+1).limit(1000000l).mapToObj(Snack1::new).toArray(Snack1[]::new);

        System.out.println("采用Date类compareTo进行时间比较的方式");
        for (int j = 0; j<5; j++){

            // for循环方式
            System.out.print("for循环方式-第" + j + "次耗时：" + forLoop(arr) + " ");

            // 流循环方式
            System.out.print("流循环方式-第" + j + "次耗时：" + streamLoop(arr) + " ");

            // 并行流循环方式
            System.out.println("并行流循环方式-第" + j + "次耗时：" + streamParallelLoop(arr));
        }

        System.out.println("采用Date类time进行时间比较的方式");
        for (int j = 0; j<5; j++){

            // for循环方式
            System.out.print("for循环方式-第" + j + "次耗时：" + forLoop(arr1) + " ");

            // 流循环方式
            System.out.print("流循环方式-第" + j + "次耗时：" + streamLoop(arr1) + " ");

            // 并行流循环方式
            System.out.println("并行流循环方式-第" + j + "次耗时：" + streamParallelLoop(arr1));
        }

    /**
     * for循环方式
     * @param arr
     * @return
     */
    private static long forLoop(ISnack[] arr){
        LocalDateTime begin = LocalDateTime.now();
        for (int i = 0; i<arr.length; i++){
            arr[i].isExpired();
        }
        LocalDateTime end = LocalDateTime.now();
        return begin.until(end, ChronoUnit.MILLIS);
    }

    /**
     * 流循环方式
     * @param arr
     * @return
     */
    private static long streamLoop(ISnack[] arr){
        LocalDateTime begin = LocalDateTime.now();
        Arrays.stream(arr).forEach(ISnack::isExpired);
        LocalDateTime end = LocalDateTime.now();
        return begin.until(end, ChronoUnit.MILLIS);
    }

    /**
     * 并行流循环方式
     * @param arr
     * @return
     */
    private static long streamParallelLoop(ISnack[] arr){
        LocalDateTime begin = LocalDateTime.now();
        Arrays.stream(arr).parallel().forEach(ISnack::isExpired);
        LocalDateTime end = LocalDateTime.now();
        return begin.until(end, ChronoUnit.MILLIS);
    }
    
    

The final execution result is as follows:
100w level

][2]

1000w level

To sum up: I feel that whether to change the time comparison method or not, judging from the test code, the impact is not big (it may also be related to the specific actual environment), but after adopting the parallel flow method, the execution efficiency has indeed improved, in large quantities When operating arrays or collections, the parallel stream method is better. The JDK will determine the better concurrency mode according to the specific environment

Answer 8

There are two optimization points
1: Creation of Date object
2.compareTo() method

Answer 9

It is said in the question "There are currently a large number of snack objects (such as a Snack object array with a length of 1 million) that need to execute the isExpired method, and the efficiency is found to be low during execution"

There are two core problems here, and I don’t know which one to solve.

1. Having a large number of objects to solve?
   2. To solve the inefficiency of execution.

Question 1,
Clear the array of 10,000 objects. There just isn’t that much to do.

Question 2,
Delete the code executed in the isExpire() method. This method does nothing and the execution efficiency is high.