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

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

谢邀。

1. 这个可以百度。当前日期如果大于该对象的expireDate就返回true。

2. 我的算法不是很6，如果有误请轻喷：先考虑对象们的expireDate是否有序。有序可以借鉴二分查找的思路。比如是从小到大，那么如果可以找到某个对象，那么后面的对象全部返回true。

Answer 2

首先，你可以先看看Date对象的compareTo方法的内部实现，会有clone操作，所以导致开销增大。

1、isExpired方法的作用是判断当前对象是否已过期，如果expireDate在当前服务器时间之前，则认为未过期，否则认为已过期；

现有相当大量的snack对象(如一个长度100万的Snack对象数组)需要执行isExpired方法

2、由于这个表达有点歧义，我分两种情况来说吧：
2.1、一个长度为100W的Snack数组，遍历执行isExpired方法，那题目考察的可能是JVM内存管理和垃圾回收机制，因为程序会串行执行这100W个对象的isExpired方法（假设忽略创建这些对象的开销），而每运行一次就会new一个Date对象，而compareTo内部又会对this.expireDate进行clone操作，所以开销会比较大；
2.2、在一定时间段内有大量的Snack对象并行执行isExpired方法，那题目侧重考察的可能就是高并发处理，如果也能扯上2.1的知识点那可以加分；

个人觉得2.2的几率大一点。

谈谈我对这段代码的优化理解：
1、用long或者int(精度要求不高的情况下)存储expireDate，如果是2.1，那可以把Date now = new Date()摞到方法外部（假设对时间的精度要求不是十分高），然后isExperied方法内部只需要比较now.getTime()和expireDate的值即可；如果是2.2且应用部署在集群环境下，那就不能在isExpired里面生成Date对象了，因为就算服务器之间有做时间同步，也是有可能发生时间不一致的情况的，例如A机器与B机器相差1秒这种情况也是有可能的。这时候可以用一个全局的时间生成器，然后应用调用这个生成器获取当前的服务器时间去做比较；
2、从业务上确认过期时间的精度，是[年|月|日|时|分|秒|毫秒]?，不同精度的存储和对比策略也是可以不同的，精度越高，成本越高。

写得比较乱。

Answer 3

如果是大量数据，每个在 isExpired() 中都去取一下时间，会比较耗时。
由于是在同一时刻顺序调用数组中每个对象的 isExpired()，可以假设是在同一时间进行比较，那么给 isExpired() 加个重载

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

在调用时可以这样

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

Answer 4

用System.currentTimeMillis()比时间

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

把数组改成优先队列，每次只需对堆顶元素执行isExpired(),性能从O(n)提高到O(1)

Answer 7

现在看到什么并行啊，我就想用Java8的新API，并行流，哈哈，所以简单实践了一下，仅供参考

1. 采用Date传统的compareTo方式比较

2. 采用Date的System.currentTimeMillis() > expiredDate.getTime()方式比较

每一种比较方式执行5遍，方便比较，同时每种方式采用3种模式去执行

1. for循环执行模式

2. 流循环执行模式

3. 并行流循环执行模式

代码类似这样：

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);
    }
    
    

最后执行结果如下：
100w量级

][2]

1000w量级

综上：感觉改不改那个时间比较方式，从测试代码来看，影响不大（也可能跟具体实际环境有关），但是采用了并行流的方式后，执行效率确实提高了，在大数量操作的数组或者集合的时候，并行流方式处理更好，JDK会根据具体环境来决定更好并发模式

Answer 8

优化有两点
1：Date对象的创建
2.compareTo()方法

Answer 9

问题中都说了“现有相当大量的snack对象(如一个长度100万的Snack对象数组)需要执行isExpired方法,执行时候发现效率低下”

这里边有两个核心问题，不知道要解决哪个。

1. 要解决大量的对象？
   2。 要解决执行效率低下。

问题1，
把这1万个对象的数组清空。就没有那么多要执行了。

问题2，
把这个 isExpire() 方法内执行的代码删除掉，这个方法什么都不干，执行效率就高了。