日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > 互聯網 > [Java 8] Lambda表達式對遞歸的優化(下) - 使用備忘錄模式(Memoization Pattern)

[Java 8] Lambda表達式對遞歸的優化(下) - 使用備忘錄模式(Memoization Pattern)

來源:程序員人生   發布時間:2014-11-17 08:24:43 閱讀次數:3613次

使用備忘錄模式(Memoization Pattern)提高性能

這個模式說白了,就是將需要進行大量計算的結果緩存起來,然后在下次需要的時候直接獲得就行了。因此,底層只需要使用1個Map就夠了。

但是需要注意的是,只有1組參數對應得到的是同1個值時,該模式才有用武之地。

在很多算法中,典型的比如分治法,動態計劃(Dynamic Programming)等算法中,這個模式應用的10分廣泛。 以動態計劃來講,動態計劃在求最優解的進程中,會將原有任務分解成若干個子任務,而這些子任務必將還會將本身分解成更小的任務。因此,從整體而言會有相當多的重復的小任務需要被求解。明顯,當輸入的參數相同時,1個任務只需要被求解1次就行了,求解以后將結果保存起來。待下次需要求解這個任務時,會首先查詢這個任務是不是已被解決了,如果答案是肯定的,那末只需要直接返回結果就好了。

就是這么1個簡單的優化措施,常常能夠將代碼的時間復雜度從指數級的變成線性級。

以1個經典的桿切割問題(Rod Cutting Problem)(或這里也有更加正式的定義:維基百科)為例,來討論1下如何結合Lambda表達式來實現備忘錄模式。

首先,簡單交代1下這個問題的背景。

1個公司會批發1些桿(Rod),然后對它們進行零售。但是隨著桿的長度不同,能夠賣出的價格也是不同的。所以該公司為了將利潤最大化,需要結合長度價格信息來決定應當將桿切割成甚么長度,才能實現利潤最大化。

比如,下面的代碼:

final List<Integer> priceValues = Arrays.asList(2, 1, 1, 2, 2, 2, 1, 8, 9, 15);

表達的意思是:長度為1的桿能夠賣2元,長度為2的桿能夠賣1元,以此類推,長度為10的桿能夠賣15元。

當需要被切割的桿長度為5時,存在的切割方法多達16種(2^(5 - 1))。以下所示:


針對這個問題,在不斟酌使用備忘錄模式的情況下,可使用動態計劃算法實現以下:

public int maxProfit(final int length) { int profit = (length <= prices.size()) ? prices.get(length - 1) : 0; for(int i = 1; i < length; i++) { int priceWhenCut = maxProfit(i) + maxProfit(length - i); if(profit < priceWhenCut) profit = priceWhenCut; } return profit; }

而從上面的程序可以發現,有很多重復的子問題。對這些重復的子問題進行不斷糾結,損失了很多沒必要要的性能。分別取桿長為5和22時,得到的運行時間分別為:0.001秒和34.612秒。可見當桿的長度增加時,性能的降落時非常非常顯著的。

由于備忘錄模式的原理10分簡單,因此實現起來也很簡單,只需要在以上maxProfit方法的頭部加上Map的讀取操作并判斷結果就能夠了。但是這樣做的話,代碼的復用性會不太好。每一個需要使用備忘錄模式的地方,都需要單獨寫判斷邏輯,那末有無1種通用的辦法呢?答案是肯定的,通過借助Lambda表達式的氣力可以輕易辦到,以下代碼我們假定有1個靜態方法callMemoized用來通過傳入1個策略和輸入值,來求出最優解:

public int maxProfit(final int rodLenth) { return callMemoized( (final Function<Integer, Integer> func, final Integer length) -> { int profit = (length <= prices.size()) ? prices.get(length - 1) : 0; for(int i = 1; i < length; i++) { int priceWhenCut = func.apply(i) + func.apply(length - i); if(profit < priceWhenCut) profit = priceWhenCut; } return profit; }, rodLenth); }

讓我們仔細分析1下這段代碼的意圖。首先callMemoized方法接受的參數類型是這樣的:

public static <T, R> R callMemoized(final BiFunction<Function<T,R>, T, R> function, final T input)

BiFunction類型的參數function實際上封裝了1個策略,其中有3個部份:

  1. Function:通過傳入參數T,來得到解答R。這1點從代碼int priceWhenCut = func.apply(i) + func.apply(length - i)很明顯的就可以夠看出來。可以把它想象成1個備忘錄的入口。
  2. T:代表求解問題時需要的參數T。
  3. R:代表問題的答案R。

以上的T和R都是指的類型。

下面我們看看callMemoized方法的實現:

public class Memoizer { public static <T, R> R callMemoized(final BiFunction<Function<T,R>, T, R> function, final T input) { Function<T, R> memoized = new Function<T, R>() { private final Map<T, R> store = new HashMap<>(); public R apply(final T input) { return store.computeIfAbsent(input, key -> function.apply(this, key)); } }; return memoized.apply(input); } }

在該方法中,首先聲明了1個匿名Function函數接口的實現。其中定義了備忘錄模式的核心---Map結構。 然后在它的apply方法中,會借助Java 8中為Map接口新添加的1個computeIfAbsent方法來完成下面的邏輯:

  1. 通過傳入的key檢查(在以上代碼中是input)對應的值是不是存在于備忘錄的底層Map中
  2. 如果存在,跳轉到步驟4
  3. 如果不存在,根據computeIfAbsent的第2個參數(是1個Lambda表達式)來計算得到key對應的value
  4. 返回得到的value

具體到該方法的源碼:

default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { Objects.requireNonNull(mappingFunction); V v; if ((v = get(key)) == null) { V newValue; if ((newValue = mappingFunction.apply(key)) != null) { put(key, newValue); return newValue; } } return v; }

也能夠很清晰地看出以上的幾個步驟是如何體現在代碼中的。

關鍵的地方就在于第3步,如果不存在對應的value,那末需要調用傳入的Lambda表達式進行求解。以上代碼傳入的是key -> function.apply(this, key),這里的this使用的10分奇妙,它實際上指向的就是這個用于容納Map結構的匿名Function實例。它作為第1個參數傳入到算法策略中,同時需要求解的key被當作第2個參數傳入到算法策略。這里所謂的算法策略,實際上就是在調用callMemoized方法時,傳入的情勢為BiFunction<Function<T,R>, T, R>的參數。

因此,所有的子問題僅僅會被求解1次。在得到子問題的答案以后,答案會被放到Map數據結構中,以便將來的使用。這就是借助Lambda表示實現備忘錄模式的方法。

以上的代碼可能會顯得有些奇異,這很正常。在你反復瀏覽它們后,并且經過自己的思考能夠重寫它們時,也就是你對Lambda表達式具有更深理解之時。

使用備忘錄模式后,桿長依然取5和22時,得到的運行時間分別為:0.050秒和0.092秒。可見當桿的長度增加時,性能并沒有如之前那樣降落的很利害。這完全是得益于備忘錄模式,此時所有的任務都只會被運行1次。

生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 精品成人一区二区 | 九九在线视频 | 美女视频黄是免费 | 国产成人精品在线观看 | 夜间av免费看精品 | 精品一区欧美 | 99精品九九 | 欧美中文字幕一区二区三区亚洲 | 久久日本片精品aaaaa国产 | 污视频网站在线免费观看 | 国产传媒在线播放 | 最近的中文字幕在线看 | 色婷婷狠狠| 欧美xxxx视频 | 永久av免费 | 香蕉成人在线 | 精品一区精品二区 | 欧美日韩精品一区二区三区 | 免费a v在线 | 国产成人精品视频在线 | 久久一日本道色综合久久大香 | 国产精品视频免费在线观看 | 精品久久99| 国产精品一区二区三区在线 | 一区二区在线视频 | 国产黄色免费网站 | www.嫩草| h片在线免费观看 | 精品福利在线观看 | 亚洲性无码av在线 | 在线一区二区三区 | 黄色片在线看 | 午夜精品久久久久久99热 | 国产黄页在线观看 | 91精品观看| 91视频欧美 | 国产欧美日韩一区 | 日韩欧美电影在线观看 | 亚洲第一性理论片 | 国产精品免费一区二区三区四区 | 欧美性一区二区三区 |