久久精品国产一区二区电影,久久精品国产亚洲av瑜伽,精品无人区一码卡二卡三,久草热8精品视频在线观看 ,久久99精品久久久久麻豆

最近的Java面試中，我準(zhǔn)備了一個反轉(zhuǎn)不可變列表的問題。結(jié)果發(fā)現(xiàn)，對于大多數(shù)候選人而言，問題并不像想象中那么簡單。因此決定在這里分享一下。

問題

實現(xiàn)下面的接口實現(xiàn)反轉(zhuǎn)輸入的列表：

public interface Reverser {
  List<Integer> reverseList(List<Integer> list);
}

期望結(jié)果：

輸入: 1, 2, 3
輸出: 3, 2, 1

唯一的要求是輸入的list是不可變的。

實現(xiàn)如下：

public List<Integer> reverseList(List<Integer> list) {
  final int size = list.size();
  List<Integer> reversedList = new ArrayList<>();

  for (int i = 0; i < size; i++) {
    // 把元素i添加到位置0
    reversedList.add(0, list.get(i));
  }

  return reversedList;
}

這個解決方案能達(dá)到預(yù)期結(jié)果。但是從性能角度來看還有問題，你能找出來嗎？

能不能用其他方式實現(xiàn)？

通常認(rèn)為，訪問輸入列表中指定索引的元素耗費的時間是常數(shù)。

作為基準(zhǔn)測試，在Intel Core i7-7700（3.6 GHz）上使用Oracle JDK 9，輸入100萬個元素列表執(zhí)行的響應(yīng)時間如下：

problem avgt 403.000 us/op

可能的解決方案

迭代模式

首先看一下輸入列表迭代的幾種方式。眾所周知，有許多經(jīng)典方式可供選擇。

從Java 5開始，可以使用for-each循環(huán)：

for (int i : list) {

  reversedList.add(0, i);

}

這么做真的更快嗎？在Effective Java中，Joshua Block談到：

在某些情況下，[for-each循環(huán)]與普通的for循環(huán)相比可能會具有一些性能上的優(yōu)勢，因為前者只計算一次數(shù)組索引的極限。盡管可以手動計算，但程序員并不總是這樣做。

換句話說，如果已經(jīng)預(yù)先計算了列表大?。ň拖裨谧畛醯膶崿F(xiàn)中所做的那樣），那么與經(jīng)典版本相比不會有任何差別。

Java 8提供了另一個選項，使用Stream API：

list
  .stream()
  .forEach(e -> reversedList.add(0, e));

同樣，這么做沒有帶來任何明顯的性能提升。使用for-each和Stream運行基準(zhǔn)測試得到的結(jié)果幾乎相同：

problem          avgt     403.000 us/op
for-each         avgt     403.000 us/op
stream           avgt     403.000 us/op

分配ArrayList

ArrayList數(shù)組大小可以調(diào)整。背后的實現(xiàn)包含capacity變量，用來存儲數(shù)組大小。

每種ArrayList實現(xiàn)都有自己的擴(kuò)容策略，根據(jù)JDK的版本不同擴(kuò)容策略也不同（例如，數(shù)組填滿時容量遞增50％）。

要取消這種動態(tài)增長，可以指定初始容量初始化ArrayList。由于我們已經(jīng)知道輸出列表的大小，因此可以做到這一點。

實現(xiàn)如下：

ArrayList<Integer> reversedList = new ArrayList<>(size);

運行結(jié)果：

problem          avgt     403.000 us/op
initial-capacity     avgt     403.000 us/op

結(jié)果并沒有發(fā)生變化。如何解釋呢？

JIT編譯器提供的運行時優(yōu)化讓人們相信，設(shè)置初始容量并不重要。如果禁用預(yù)熱時間，就能看到兩個測試響應(yīng)時間之間的差異。

元素移位

讓我們仔細(xì)看看生成結(jié)果ArrayList插入元素方式：

reversedList.add(0, elem);

這個簡單的表達(dá)式時間復(fù)雜度是線性的，不是恒定的常量。實際上，在ArrayList位置0插入元素需要把所有元素右移。

這是上面實現(xiàn)中存在的主要問題。那么還有什么其他選擇嗎？

第一種，使用操作時間為常量的數(shù)據(jù)結(jié)構(gòu)在位0插入元素。在Java中，可以使用LinkedList來管理指向第一個元素的指針。

調(diào)用addFirst()在第一個位置插入元素：

public List<Integer> reverseList(List<Integer> list) {
  final int size = list.size();
  LinkedList<Integer> reversedList = new LinkedList<>();

  for (int i = 0; i < size; i++) {
    // Add element i to the first position
    reversedList.addFirst(list.get(i));
  }

  return reversedList;
}

效果有沒有明顯提升？

problem          avgt     403.000 us/op
linked-list         avgt         541 us/op

結(jié)果好多了！ 

第二種方法，保留ArrayList結(jié)構(gòu)，在末尾插入元素（這樣操作的時間復(fù)雜度是常數(shù)）。

必須對列表倒序迭代，如下所示：

public List<Integer> reverseList(List<Integer> list) {
  final int size = list.size();
  List<Integer> reversedList = new ArrayList<>(size);

  for (int i = size - 1; i >= 0; i--) {
    // Add element i to the last position
    reversedList.add(list.get(i));
  }

  return reversedList;
}

problem       avgt     403.000 us/op
linked-list      avgt         541 us/op
insert-last-pos  avgt         281 us/op

響應(yīng)時間甚至比LinkedList方案還要短。

實際上，由于LinkedList會動態(tài)分配內(nèi)存（每個元素都包裝為一個節(jié)點對象），使用時會增加少量內(nèi)存開銷。因此，如果已經(jīng)知道結(jié)構(gòu)大小，那么使用像ArrayList這樣的數(shù)據(jù)結(jié)構(gòu)顯然會更快。

內(nèi)部數(shù)組拷貝

ArrayList的底層實現(xiàn)是數(shù)組。如果我們試著復(fù)制內(nèi)部數(shù)組并對副本直接進(jìn)行反轉(zhuǎn)會怎么樣？

public List<Integer> reverseList(List<Integer> list) {
  final int size = list.size();
  final Integer[] array = list.toArray(new Integer[0]); // Copy array

  for (int i = 0; i < size / 2; i++) {
    swap(array, i, size - i - 1); // Swap elements
  }

  return Arrays.asList(array);
}

swap()函數(shù)只交換兩個索引對應(yīng)的數(shù)組元素。

這樣能不能帶來性能提升？

problem          avgt     403.000 us/op
linked-list         avgt         541 us/op
insert-last-pos     avgt         281 us/op
copy-swap-array   avgt         254 us/op

有趣的是，這種方案甚至比之前的解決方案更快。一些可能的解釋：

• 數(shù)組副本由System.arraycopy()管理，這是一個優(yōu)化過的本地方法。

• 這種代碼對CPU緩存更友好。

視圖

最后一種解決方案借助了輸入列表的不可變性。因此，可以繼承AbstractList創(chuàng)建一個新列表：

public List<Integer> reverseList(List<Integer> list) {
  return new AbstractList<Integer>() {
    @Override
    public Integer get(int index) {
      return list.get(list.size() - 1 - index);
    }

    @Override
    public int size() {
      return list.size();
    }
  };
}

顯然，在這種情況下與基準(zhǔn)測試比較reverseList()性能是不合適的，因為輸出結(jié)果在調(diào)用時才生成：

problem          avgt     403.000 us/op
linked-list         avgt         541 us/op
insert-last-pos     avgt         281 us/op
copy-swap-array   avgt         254 us/op
view             avgt       0,002 us/op

需要處理list.size()-1-index時，調(diào)用get()產(chǎn)生開銷很小。實際編程中，如何使用列表值得仔細(xì)考慮。如果訪問列表非常頻繁，則最好使用副本。

最后，有些人過于強(qiáng)調(diào)函數(shù)式編程和不變性對性能始終帶來負(fù)面影響。實際上不能一概而論。

以本文討論的面試題為例，最好的解決方案往往取決于問題本身的約束條件。