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

Merci pour l'invitation.

1. Ceci peut être trouvé sur Baidu. Renvoie vrai si la date actuelle est supérieure à la date d'expiration de l'objet.

2. Mon algorithme n'est pas très bon. S'il y a une erreur, veuillez commenter : vérifiez d'abord si la date d'expiration des objets est en ordre. Orderly peut apprendre de l’idée de la recherche binaire. Par exemple, de petit à grand, si un objet peut être trouvé, tous les objets suivants renverront vrai.

Answer 2

Tout d'abord, vous pouvez jeter un œil à l'implémentation interne de la méthode Date de l'objet compareTo Il y aura des clone opérations, ce qui augmentera la surcharge.

1. La fonction de la méthode isExpired est de déterminer si l'objet actuel a expiré. Si expireDate est antérieur à l'heure actuelle du serveur, il est considéré comme n'ayant pas expiré, sinon il est considéré comme ayant expiré ;

Il existe actuellement un assez grand nombre d'objets Snack (tels qu'un tableau d'objets Snack d'une longueur de 1 million) qui doivent exécuter la méthode isExpired

2. Cette expression étant un peu ambiguë, je vais l'expliquer dans deux situations :
2.1 Un tableau Snack d'une longueur de 100W, parcourant et exécutant la méthode isExpired, la question peut examiner la mémoire JVM. gestion et mécanisme de collecte des déchets, car le programme en série exécutera les isExpired méthodes de ces 1 million d'objets (en supposant que le coût de création de ces objets soit ignoré), et à chaque exécution, un nouveau Date l'objet sera créé, et compareToEn interne, this.expireDate sera cloné, donc la surcharge sera relativement importante
Dans un certain laps de temps, il y aura un grand nombre d'objets Snack <🎜. > exécuter la méthode en parallèle , donc la question se concentre sur le test peut être un traitement à haute concurrence. Si vous pouvez également aborder les points de connaissance de 2.1, vous pouvez obtenir des points supplémentaires isExpired.

Personnellement, je pense que la probabilité de 2,2 est plus élevée.

Parlez de ma compréhension de l'optimisation de ce code :

1. Utilisez
ou long (lorsque les exigences de précision ne sont pas élevées) pour stocker int, s'il s'agit de expireDate2.1 , alors vous pouvez empiler en dehors de la méthode (en supposant que les exigences de précision temporelle ne sont pas très élevées), puis dans la méthode Date now = new Date() il vous suffit de comparer les valeurs de isExperied et now.getTime() si ; il s'agit de expireDate2.2 et l'application est déployée dans un environnement cluster, alors l'objet ne peut pas être généré dans isExpired, car même s'il y a une synchronisation horaire entre les serveurs, des incohérences horaires peuvent survenir par exemple , machine A et Il est également possible que la différence entre la machine B et la machine B soit de 1 seconde. À ce stade, vous pouvez utiliser un générateur d'heure global, puis l'application appelle ce générateur pour obtenir l'heure actuelle du serveur à des fins de comparaison Date2 Confirmez l'exactitude du
délai d'expiration du point de vue commercial ; , qui est [année | Mois | Jour | Heure | Minute | Seconde | Milliseconde] ?, les stratégies de stockage et de comparaison des différentes précisions peuvent également être différentes. Plus la précision est élevée, plus le coût est élevé.

L'écriture est plutôt brouillonne.

Answer 3

S'il y a une grande quantité de données, il faudra beaucoup de temps pour obtenir l'heure de chacune d'elles dans isExpired().
Puisque isExpired() de chaque objet du tableau est appelé séquentiellement en même temps, on peut supposer que la comparaison est effectuée en même temps, puis ajouter une surcharge isExpired() à

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

Vous pouvez le faire lorsque vous appelez

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

Answer 4

Comparez le temps avec 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

Changez le tableau en file d'attente prioritaire. Chaque fois que vous devez uniquement exécuter isExpired() sur l'élément supérieur du tas, les performances sont améliorées de O(n) à O(1)

Answer 7

Maintenant que je vois quelque chose de parallèle, je veux utiliser la nouvelle API de Java 8, flux parallèle, haha, donc je l'ai simplement pratiqué, pour référence seulement

1. Comparez en utilisant la méthode traditionnelle compareTo de Date

2. Comparez en utilisant la méthode System.currentTimeMillis() > expiredDate.getTime() de Date

Chaque méthode de comparaison est exécutée 5 fois pour faciliter la comparaison. En même temps, chaque méthode utilise 3 modes d'exécution

1. pour le mode d'exécution de boucle

2. Mode d'exécution de boucle de flux

3. Mode d'exécution de boucle de flux parallèle

Le code est similaire à ceci :

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

Le résultat final de l'exécution est le suivant :
Niveau 1 million

][2]

Niveau 1000w

Pour résumer : je pense que la méthode de comparaison du temps devrait être modifiée ou non. À en juger par le code du test, cela aura peu d'impact (cela peut aussi être lié à l'environnement réel spécifique. Cependant, après avoir adopté le parallèle). méthode de flux, l'efficacité d'exécution s'est en effet améliorée. Lors de l'exploitation d'un grand nombre de tableaux ou de collections, la méthode de flux parallèle est meilleure. Le JDK déterminera le meilleur mode de concurrence en fonction de l'environnement spécifique

.

Answer 8

Il y a deux points d'optimisation
1 : Création de l'objet Date
2 Méthode compareTo()

.

Answer 9

Il est dit dans la question qu '"il existe actuellement un grand nombre d'objets snack (tels qu'un tableau d'objets Snack d'une longueur de 1 million) qui doivent exécuter la méthode isExpired, et l'efficacité s'avère faible pendant l'exécution"

Il y a deux problèmes fondamentaux ici, et je ne sais pas lequel résoudre.

1. Vous allez résoudre un grand nombre d'objets ?
   2. Pour résoudre l’inefficacité de l’exécution.

Question 1,
Effacer le tableau de 10 000 objets. Il n’y a tout simplement pas grand-chose à faire.

Question 2,
Supprimez le code exécuté dans la méthode isExpire() Cette méthode ne fait rien et l'efficacité d'exécution sera élevée.