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

Terima kasih atas jemputan.

1. Ini boleh didapati di Baidu. Mengembalikan benar jika tarikh semasa lebih besar daripada expireDate objek.

2. Algoritma saya tidak begitu baik Jika terdapat sebarang kesilapan, sila komen: pertimbangkan dahulu sama ada tarikh luput objek adalah teratur. Tertib boleh belajar daripada idea carian binari. Sebagai contoh, dari kecil ke besar, jika objek boleh ditemui, semua objek berikutnya akan kembali benar.

Answer 2

Pertama sekali, anda boleh melihat pelaksanaan dalaman kaedah Date objek compareTo Akan ada operasi clone, yang akan meningkatkan overhed.

1. Fungsi kaedah isExpired adalah untuk menentukan sama ada objek semasa telah tamat tempoh. expireDate

Pada masa ini terdapat sejumlah besar objek snek (seperti susunan objek Snek dengan panjang 1 juta) yang perlu melaksanakan kaedah isExpired

2. Memandangkan ungkapan ini agak samar-samar, saya akan menerangkannya dalam dua situasi:

2.1 Tatasusunan Snek dengan panjang 100W, melintasi dan melaksanakan kaedah
, soalan mungkin memeriksa memori JVM. pengurusan dan mekanisme pengumpulan sampah, kerana program ini akan isExpired secara bersiri melaksanakan kaedah bagi 1 juta objek ini (dengan mengandaikan bahawa kos untuk mencipta objek ini diabaikan), dan setiap kali ia dijalankan, satu isExpired objek akan dibuat, dan Date Secara dalaman, compareTo akan diklon, jadi overhead akan menjadi agak besar; this.expireDate2.2 Dalam tempoh masa tertentu, terdapat sejumlah besar objek Snek
melaksanakan kaedah selari , jadi soalan tertumpu pada Ujian mungkin mengenai pemprosesan serentak tinggi Jika anda juga boleh menyentuh mata pengetahuan 2.1, anda boleh mendapatkan mata tambahan; isExpiredSecara peribadi, saya rasa kebarangkalian 2.2 adalah lebih tinggi.

Bercakap tentang pemahaman pengoptimuman saya tentang kod ini:

1 Gunakan

atau
(apabila keperluan ketepatan tidak tinggi) untuk menyimpan long, jika int2.1expireDate , maka anda boleh menyusun di luar kaedah (dengan mengandaikan bahawa keperluan ketepatan masa tidak terlalu tinggi), dan kemudian dalam kaedah anda hanya perlu membandingkan nilai Date now = new Date() dan isExperied jika ia adalah now.getTime()2.2 expireDate dan aplikasi digunakan dalam persekitaran kluster, maka objek tidak boleh dijana dalam , kerana walaupun terdapat penyegerakan masa antara pelayan, ketidakkonsistenan masa mungkin berlaku, contohnya , mesin A dan Mungkin juga perbezaan antara mesin B dan mesin B ialah 1 saat. Pada masa ini, anda boleh menggunakan penjana masa global, dan kemudian aplikasi memanggil penjana ini untuk mendapatkan masa pelayan semasa untuk perbandingan isExpired2. Sahkan ketepatan masa tamat Date dari perspektif perniagaan; , iaitu [tahun |. Bulan|Hari|Jam|Minit|Kedua|Millisaat]?, strategi penyimpanan dan perbandingan bagi ketepatan yang berbeza juga boleh berbeza.
Tulisan agak bersepah.

Answer 3

Jika terdapat sejumlah besar data, ia akan memakan masa untuk mendapatkan masa bagi setiap satu dalam isExpired().
Memandangkan isExpired() setiap objek dalam tatasusunan dipanggil secara berurutan pada masa yang sama, ia boleh diandaikan bahawa perbandingan dilakukan pada masa yang sama, kemudian tambahkan lebihan isExpired() kepada

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

Anda boleh melakukan ini apabila memanggil

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

Answer 4

Bandingkan masa dengan 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

Tukar tatasusunan menjadi baris gilir keutamaan Setiap kali anda hanya perlu melaksanakan isExpired() pada elemen atas timbunan, prestasi dipertingkatkan daripada O(n) kepada O(1)

Answer 7

Sekarang saya melihat sesuatu yang selari, saya mahu menggunakan API Java 8 baharu, aliran selari, haha, jadi saya hanya mengamalkannya, untuk rujukan sahaja

1. Bandingkan menggunakan kaedah tradisional compareTo of Date

2. Bandingkan menggunakan kaedah System.currentTimeMillis() > expiredDate.getTime() Tarikh

Setiap kaedah perbandingan dilaksanakan 5 kali untuk memudahkan perbandingan Pada masa yang sama, setiap kaedah menggunakan 3 mod untuk pelaksanaan

1. untuk mod pelaksanaan gelung

2. Mod pelaksanaan gelung strim

3. Mod pelaksanaan gelung strim selari

Kod adalah serupa dengan ini:

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

Keputusan pelaksanaan akhir adalah seperti berikut:
1 juta tahap

][2]

Tahap 1000w

Ringkasnya: Saya merasakan bahawa kaedah perbandingan masa perlu diubah atau tidak, berdasarkan kod ujian, ia akan memberi sedikit kesan (ia mungkin juga berkaitan dengan persekitaran sebenar yang khusus). kaedah aliran, kecekapan pelaksanaan sememangnya bertambah baik Apabila mengendalikan sejumlah besar tatasusunan atau koleksi, kaedah aliran selari adalah lebih baik

Answer 8

Terdapat dua titik pengoptimuman
1: Penciptaan objek Tarikh
2 kaedah compareTo()

Answer 9

Dikatakan dalam soalan bahawa "pada masa ini terdapat sejumlah besar objek snek (seperti susunan objek Snek dengan panjang 1 juta) yang perlu melaksanakan kaedah isExpired, dan kecekapan didapati rendah semasa pelaksanaan"

Terdapat dua masalah teras di sini, dan saya tidak tahu yang mana satu untuk diselesaikan.

1. Mahu menyelesaikan sejumlah besar objek?
   2. Untuk menyelesaikan ketidakcekapan pelaksanaan.

Soalan 1,
Kosongkan tatasusunan 10,000 objek. Tidak banyak yang perlu dilakukan.

Soalan 2,
Padamkan kod yang dilaksanakan dalam kaedah isExpire() Kaedah ini tidak melakukan apa-apa dan kecekapan pelaksanaan akan menjadi tinggi.