Roman To Integer

01-26

這是leetcode上的一道題目。

鏈接

Roman to Integer | LeetCode OJ

題目

將羅馬數字轉換為整形，輸入範圍是1-3999

釋義

1-3999的羅馬數，用到的符號和對應的十進位數如下：

I → 1
V → 5
X → 10
L → 50
C → 100
D → 500
M → 1000

書寫規則大致如下，按照十進位的每一位數來描述

若該位為基準數（如1、10、100）的1-3倍，則通過連續書寫表示相加，如III表示3
若為四倍，則改為書寫一次，再加書寫更高級的一個數，表示5-1，如4=5-1=IV
若為6-9倍，則先書寫5的倍數，剩餘數字按照1-4倍在後方追加書寫。如8=5+3=VIII

補充描述

這題的解法，有三種：

查表法，將上述七個羅馬數符號打表，然後依次遍歷，查錶轉換為整形；
switch-case法，其實就是把查表法展開成代碼。

性能上，兩者本質相同，查表法是通過下標進行數據定址。switch-case是通過switch內容進行代碼定址。

性能分析

此段可以先不看，後續版本優化中看不懂了再倒回來看

但需注意——現代CPU，具有流水線、分支預測、亂序執行等高性能流程，具體原理可以分別查詢相關辭彙的維基百科，我們在常規代碼優化中，只需要注意這兩點：

避免條件判斷，解釋見後。
避免代碼跳轉，解釋見後。
避免堆棧出入，如調用函數，進出{}語句塊，這個為什麼會有性能損耗應該不用解釋了。

現代CPU在執行指令過程中，會通過流水線進行。

在執行當條指令同時，就會把後面的幾條指令順序讀取進寄存器，以便後續工作。更喪病的情況下，會把後續指令的操作數也提前讀取進來準備執行。

如果前後兩條指令的數據沒有相互依賴，那麼就會在流水線里並行執行，也就是亂序執行。而條件判斷則會打斷這個提前讀取，因為在判斷成功之前，無法確定後續工作分支。

不過現代CPU大多具有分支預測技術，也就是如果同一個分支多次執行（如for裡面的if），之前幾次走的都是true，那麼下一次就會按照true來提前處理，如果實際為false則回滾，實際為true則會繼續，這樣就避免了指令預處理、流水線等操作被條件語句打斷。

而在實際場合中，分支預測成功率高達八成——也就是說，如果我們在for裡面有if，那麼只要這個if語句絕大部分情況下結果都相同（同為true或同為false），CPU分支預測技術就可以很大程度的避免了條件跳轉帶來的性能損失。而如果我們的if語句，true和false的成功率差異並不明顯，那麼這個多次執行的if，會顯著拖慢執行效率，有時慢上一個數量級都不奇怪。

而代碼跳轉，如goto、switch-case，也會帶來一定的性能損失，原因就和if判斷之後的跳轉相同。

擴展閱讀：CPU 的分支預測器是怎樣工作的？

所以，在一開始提到的查表法和switch-case法中，一般來說查表法性能會更高，因為不需要進行代碼跳轉。

那麼，就開始編程吧！

版本一

這一道題，解題思路上，可以打草稿來模擬計算，我用III(3)、IV(4)和VI(6)來進行推理。

從右往左數，最右邊一個肯定是初始值。
往前逐一數過去，最簡單的就是依次加上去，如III，就是1+1+1得到3，沒毛病。
遇到不同的數，就要判斷下了。從V到I(IV)，之前一步(V)是5，後一步(I)應該減掉。從I到V(VI)則相反。

於是就有了下面的代碼：

class Solution {public: int romanToInt(string s) { unordered_map<char, int> romanMap = { { I, 1 }, { V, 5 }, { X, 10 }, { L, 50 }, { C, 100 }, { D, 500 }, { M, 1000 } }; int num = romanMap.at(s.back()); for(int i=s.length()-2;i>=0;--i) { if(romanMap.at(s.at(i)) < romanMap.at(s.at(i+1))) num -= romanMap.at(s.at(i)); else num += romanMap.at(s.at(i)); } return num; }};

在這裡，我通過unordered_map創建了一張hash表，hash表的好處在於查詢接近於常量級，效率極為接近數組下標定址。

leetcode里，代碼驗證時的輸入數據量好像不大，所以多次執行代碼耗時波動很大。提交後點「more details」可以看耗時在所有答案里的排行。多數情況會穩定在一個較快的值，但也有許多時候會掉下去。

這個版本，多次執行後，比較穩定的快速數值，是超過了53.92%的人。

版本二

我們注意到，在上個版本里，romanMap.at(s.at(i))這段代碼出現了三次。也就是，出現了六次at定址，但這六次的值其實是完全一樣的。

於是，可以用一個變數來代替這段代碼——int cur = romanMap.at(s.at(i));

而romanMap.at(s.at(i+1))這段，看似只出現了一次，但這一次其實是來自於上一次執行的cur，所以也可以把它優化掉，在循環結尾使用變數`prev = cur`來將其緩存。

於是有了下面的版本：

class Solution {public: int romanToInt(string s) { unordered_map<char, int> romanMap = { { I, 1 }, { V, 5 }, { X, 10 }, { L, 50 }, { C, 100 }, { D, 500 }, { M, 1000 } }; int num = romanMap.at(s.back()); int prev = num; for(int i=s.length()-2;i>=0;--i) { int cur = romanMap.at(s.at(i)); if(cur < prev) num -= cur; else num += cur; prev = cur; } return num; }};

運行通過了，效率打敗了55.88%對手。

這裡把romanMap.at(s.at(i+1))替換為prev，究竟是賺是虧我沒細細思考過，但cur變數顯然是賺的，然而效率提升並不明顯，也許prev變數略虧了一點？

版本三（好孩子可以學

版本二已經可以作為比較完美的答案提交了，在執行效率和代碼易讀性上做到了平衡。

如果是在工作環境里，版本二是最完美的！

接下來，為了壓榨性能的極限（畢竟這就是oj的目的），我們可以選擇放棄代碼可讀性來提升性能。這一點在工作環境中極度不推薦，除非是底層的執行超級頻繁，對性能影響很明顯的核心代碼。需牢記——不要過度優化。

class Solution {public: int romanToInt(string s) { unordered_map<char, int> romanMap = { { I, 1 }, { V, 5 }, { X, 10 }, { L, 50 }, { C, 100 }, { D, 500 }, { M, 1000 } }; int num = romanMap.at(s.back()); int prev = num; for(int i=s.length()-2;i>=0;--i) { int cur = romanMap.at(s.at(i)); int curLargerThanPrev = cur >= prev; num += (2 * curLargerThanPrev - 1) * cur; prev = cur; } return num; }};

在這裡，我把if語句弄沒了……

循環體內，多次執行的if語句是萬惡之源，對性能的影響非常嚴重。這題還好，if內的代碼塊里，就一行代碼，運算量很小。如果代碼塊里的運算比較複雜的話，if帶來的性能損失就很嚴重了。

我這裡用了個trick，沒去細查標準——bool其實是個單位元組整形，它的true一般是1，false一般是0。具體的得去查c++規範了，我沒具體驗證過，但在常見編譯器上是這樣的。

於是，我們就能把這個if判斷的判斷條件，保存為一個整形值。然後把這個1/0的整形值，和if-else內的計算揉在一起，合併成一個東西。

具體思路是這樣的:

result = isTrue * ...true expression... + (1 - isTrue) * ...false expression...

參照這個寫法，合併一下多項式，提取一下係數，就得到了上面的代碼。

這版代碼，效率提升沒想像中明顯，執行了多次後，穩定速度是打敗了59.85%對手，偶爾可以蹦到60%甚至70%。

不過在我目前工作的項目中，核心演算法里有許多地方用到了這樣的trick，效率提升很明顯。

最終版（好孩子不要學

/** 以下碎碎念可以忽略

其實，我大學是水過去的，大四做畢設才先學的Qt做GUI，結果還是沒學會，答辯時用Qt Designer畫了個ui截圖寫進論文……

還好我們大學的軟體是中期答辯時演示，之後就只需要論文了。中期那會兒我還可以借口說界面還沒做好來推脫，然後我把界面原型和純命令行的核心功能代碼分別演示了下，老師很大度的讓我過了……

畢業工作後，才開始好好的學C++和Qt，並且因為一開始就入了Qt坑，導致我到現在工作三年多了，對boost都只是一知半解，STL也是從半年前才開始好好學的……

至於ACM、OJ這些東西，那更是離我很遠，我現在是用身為TL的工作經驗，高屋建瓴的逆推這些知識……

而這個領域裡，著重於演算法，所以C++和面向對象其實用處不大，核心還是C的那一套。

而當我知道了打表法的存在時，簡直是毀三觀了，覺得這完全是作弊……但反過來一想，工程領域不就是滿滿的將就和湊合么，在可以接受的精度或其他損失範圍內，能夠提高N個數量級完成工作的方法，就是最完美的方法，比如打表法。

這裡貼一個我見過的最喪心病狂的打表法，Qt的演算法庫里，沒寫到document里的一個函數——qFastSin。

**/

像這題，最直觀的其實應該是switch-case，但最快的卻是打表法。

但打表法的最高境界，是數組，而且是寫在棧上的數組，而不是new出來的堆數組（我都不提ACM里，通過預編譯指令把棧擴容到幾十幾百兆然後全程在棧上寫演算法的奇技淫巧了……）。而這裡用的只不過是unordered_map，雖然hash理論查詢性能是O(1)，但比起真正O(1)的數組下標訪問，還是有那麼點常數上的差距的。

於是，有了最終版的代碼，喪心病狂的打表。如果看不懂的話，可以看一下I、V、X、L、C、D、M的ASCII碼，你就懂了。

最終代碼

class Solution {public: int romanToInt(string s) { int romanMap[X+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100, 500, 0, 0, 0, 0, 1, 0, 0, 50, 1000, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 10 }; int num = romanMap[s.back()]; int prev = num; for(int i=s.length()-2;i>=0;--i) { int cur = romanMap[s.at(i)]; int curLargerThanPrev = cur >= prev; num += (2 * curLargerThanPrev - 1) * cur; prev = cur; } return num; }};

這個版本，平均性能在60-80%，最高打敗了97.73%的對手。

沒毛病！

終極解法（大霧

做一張3999長度的map，key是羅馬數字的1-3999，value是對應的整形數，O(1)時間效率，真·打表法·進化·究極·完全體（逃

後記

可惜leetcode不支持rust，不然我覺得，rust的pattern match，也許是最快的。

github上有個多語言性能的benchmark項目，其中有個test case是實現一個簡易的js解釋器。

這個題目里，ruby等對於字元串處理有喪心病狂的優化的動態語言，性能甚至超過了用switch-case的C/C++——要知道，在其他題目里，C/C++相比動態語言都有著最少一個數量級的碾壓優勢。

然而rust用接近一個數量級的差距碾壓了這些對手……用的就是pattern match，代碼極度簡潔優雅。

可惜我一直沒空學rust……

在知乎上看到一個c++學習群，同時還開了githubwoniu/learnprogram組織刷題，這道題就是在這個群里一起刷的，所以就打個小廣告吧。

（群里有個猛人用LL(1)實現了，隨便跑了下就是打敗92.78%的性能，簡直兇殘，我大學編譯原理是水過去的，現在僅限於能看懂這幾個辭彙，江湖派野路子妥妥的給學術派跪了。他那個答案同樣在github上提交pull request了）

http://weixin.qq.com/r/ZDlocCPE5H6brWcT92x2 (二維碼自動識別)