發表新討論
#36992: LCS 省記憶體的作法


liaoweichen1024@gmail.com (M_SQRT)

a133. 10066 - The Twin Towers -- UVa 10066 | From: [118.166.132.219] | 發表日期: 2023-08-19 07:59
如果你還不會「LCS最長共同子序列」，請先上網學習，確保足夠熟悉了再來讀這一篇文章。
 
 
從正常的lcs寫法，我做了3次記憶體簡化
 
1. lcs2d[n][n] → lcs[n] + backup[n]
  在進行lcs填表時，我們可以發現，從頭到尾我們只會存取到lcs2d[i]列與lcs2d[i-1]列，其餘的空間是不需要的，我們可以將lcs2d[i-1]的內容存放於backup[n]中，並且對lcs[n]進行填表，最後再執行swap即可。
 
程式碼參考:
// a[], b[] 為輸入的兩個陣列
for(i=0; i<N1; i++) {
    swap(lcs, bac);
    for(j=0; j<N2; j++)
        if(a[i]==b[j]) lcs[j+1] = bac[j]+1;
        else lcs[j+1] = max(lcs[j+1], lcs[j]);
}
 
2. lcs[n] + backup[n] → lcs[n] + t + c
  目標是把backup[]也省下來。當我們在更新lcs[j+1]時，會需要backup[j]的資料，這是舊的lcs[j]， 所以我們可以在前一次迴圈就先把lcs[j]的資料存下來。
for(i=0; i<N1; i++) {
    swap(lcs, bac);
    for(j=0; j<N2; j++) {
        if(a[i]==b[j]) lcs[j+1] = t+1;
        else lcs[j+1] = max(lcs[j+1], lcs[j]);
        t = lcs[j+1];
    }
}
但是這樣寫，t存的依舊是更新過的lcs[j+1]，若是將t=lcs[j+1]寫在if之前，又會將接下來需要的t值覆蓋掉。
  解決這個問題也很簡單，就像基礎的兩數交換一樣，先存在另一個空間就好
for(i=0; i<N1; i++) {
    swap(lcs, bac);
    for(j=0; j<N2; j++) {
        c = lcs[j+1];
        if(a[i]==b[j]) lcs[j+1] = t+1;
        else lcs[j+1] = max(lcs[j+1], lcs[j]);
        t = c;
    }
}
因為Java在變數指派上跟C++有些許不同，所以可以不需要變數c，具體作法結尾再介紹。
 
3. a[] + b[] → a[]
  內層迴圈中的a[i]，從頭到尾都不會變，離開迴圈後就不會再用到了，所以我們沒有必要用陣列把它存下來，需要時再接收輸入就行了，這個部分就交給你自己寫囉~
 
對了，微不足道的優化
內層迴圈內的j+1比j還要多，所以我把迴圈改成這樣
for(j=0; j++<N2;) ...
這樣就能把j+1改成j，j改成j-1了
 
 
Java變數指派的特性
先從兩數交換談起，你知道java能一行做完兩數交換嗎?
a = b + (b=a)*0;
因為java會嚴格由左至右運算，所以可以利用這個算式達到兩數交換(這個算式在C++無法達到我們要的效果，因為C++會先算(b=a))
當然同樣的邏輯也可以寫成
a = b | (b=a)&0;
各種寫法都行，只要確保未更新的b先出現，後面多一個0，並且在這個0中將b更新(此時的a絕對還沒被更新)
 
根據這個概念，java可以將內層迴圈的算式改成:
for(j=0; j<N2; j++)
    t = lcs[j+1] | 0&(
        a[i]==b[j] ? t+1 : Math.max(lcs[j+1], lcs[j])
    );
 
希望這篇解題報告能幫助到你^_^
#41488: Re: LCS 省記憶體的作法


seancai78@gmail.com (風月春秋)

a133. 10066 - The Twin Towers -- UVa 10066 | From: [118.166.33.18] | 發表日期: 2024-07-31 11:23
        if(a[i]==b[j]) lcs[j+1] = bac[j]+1;

        else lcs[j+1] = max(lcs[j+1], lcs[j]);

老兄，你max的地方應該是 lcs[j], bac[j+1]吧，害我差點懷疑自己的印象
還是感謝所有講解的解題報告，好人一生平安

ZeroJudge Forum