Author Archives: Enrico

One Definition Rule – class type

最近在幫忙debug看到一段有意思的程式碼 我把出問題程式核心概念抽出來碼簡化改寫如下 以上程式碼在VC++2015環境下執行 class2.cpp dynamic_cast fail! 如果單純只看class2.cpp ClassC2* p2 = dynamic_cast(p.get()); std::cout << “Class2 ” << p2 << std::endl; 看起來沒有什麼問題,shared_ptr<Class2C1> p 被assign new ClassC2 , 再取出來做dynamic_cast轉回ClassC2 dynamic_cast失敗所以return nullptr,但是shared_ptr p 裡頭存的不是ClassC2 pointer嗎? 應該要能夠down cast成功 如果仔細看,會發現ClassC2同時在class1.cpp, class2.cpp被定義了! 為什麼compile時沒報任何錯呢? 例如redefinition,原因是compile是針對translation unit,在同一個translation unit不能有重複定義,但是在不同的translation unit,標準允許可以重複定義(class … Continue reading

Posted in C++ Language | Leave a comment

json-rpc整理(JSON remote procedure call)

json rpc 類似xml rpc,透過HTTP的方式進行資料交換來達成remote procedure call,最大的差別在data serialization改成JSON,另外json rpc的規範大約在2005-2010年左右,在底層的傳輸協定也不要求使用HTTP,可以是TCP/IP stream。 spec可參考 1.0 https://www.jsonrpc.org/specification_v1 2.0 https://www.jsonrpc.org/specification 概念上跟xml rpc相同,但是將client server的角色模糊了,採用對等peer的概念,當然如果以功能來看,我們可以將make function call那端看成client,function execution那端看成client,只是在json rpc中的連線概念是採用對等,任何一端可能是client,也可能是server,為了清楚的對比xml rpc文章中的範例,以下我將xml rpc中is_even改成在json rpc裡實現,用Node.js當server,python當client 輸入100 回傳結果如下 使用起來簡單直覺,python 可以再利用語言本身的proxy機制,讓呼叫起來比較簡潔 以下整理json rpc 1.0 spec 其中提到 To invoke a remote method, a request … Continue reading

Posted in Network | Leave a comment

xml-rpc整理 (XML remote procedure call) – spec

這篇整理的spec是以 http://xmlrpc.com/spec.md 為參考 在一開始spec說明xml-rpc是Remote Procedure Calling protocol,可以理解成call – return的communication pattern,而HTTP本身的protocol就是request – response,可以非常直覺地直接對應到procedure call的pattern。 spec主要就是在這樣的通訊架構下,定義資料傳輸的交換格式,並且以xml為資料格式的基底。 以前一篇is_even的例子來看 client送出的xml 在http部分 採用POST (送出xml body),spec要求User-Agent、Host  header field must be required. 值得注意的是 header Host 在HTTP/1.1是required,在HTTP/1.0則沒有要求,nodejs client送出的header sample如下,其中Content-Length是通過計算xml body size得到(在nodejs中,如果不先算好content-length,使用stream write,會導致chunked mode transfer,這部分可能會導致server不相容,因為spec中有寫到: The Content-Length must be … Continue reading

Posted in Network | Leave a comment

xml-rpc整理 (XML remote procedure call) – introduction

在跨process或是跨機器溝通上的IPC有許多方式,以http為基底的也有如SOAP、REST相關的實現,並且也發展的滿成熟的。相較之下,xml-rpc比較像是整個過程中的一個開端或是過渡的解決方案, 這篇整理會著重在背景介紹、spec的一些想法 xml-rpc發展的年代大約在1998年,這個時間點是Web開始蓬勃發展的年代,網路的通信普及也使得跨機器的溝通越來越重要,在這之前或同一個時期,其實已經有不少跨機器通信的標準或實現,例如COBRA、Sun RPC等等,在TCP/IP的環境中,加上資料的傳輸格式的定義(marshaling),其實就可以實現了,因為不難,所以有很多其他像是COBRA、Java RMI、DCOM,都是不同團體或陣營提出的解決方案。xml-rpc就是在當時環境下的一個產物,一方面XML剛出現沒多久,作為一個資料交換的格式,XML的設計在當時跟其他的資料交換格式,更強調human readable以及machine readable,在當時常見的資料交換作法如ASN.1 + DER,常見於其他protocol (如SNMP、LDAP)。將網路+XML作為rpc的想法很自然就出現了。使用XML的代價就是 not compact,資料的大小會膨脹許多,這個對於網路頻寬資源有限的時代或是環境而言,就不是那麼受歡迎。 跨機器通信,其中有一個重點是heterogeneous platforms,因為在1998年時,很多rpc類的protocol是特定陣營提出或使用的,例如DCOM本身基本上只在Windows實現,其他的平台要實作可能會遇到很多瓶頸,例如poor implementation,或是可能架構上已經跟系統的某些元件coupling,所以完整實現很困難。COBRA則是因為本身設計的太完整、太複雜,導致無論是使用或者實現完整都有一定的難度,這個現象在很多系統發展或是標準制定都會看到,當一個設計越想要comprehensive, 想要一個解決方案涵蓋所有的問題時,常常最後會因為過度複雜,導致開發者沒辦法完全掌握。 xml-rpc的spec可以參考: http://xmlrpc.com/spec.md 我們先從實際程式範例來看xml-rpc可以做的事情 server side example: adapted from https://docs.python.org/3/library/xmlrpc.client.html python文件中有client side example 不過為了展示interop,我另外用nodejs寫了一個範例 看起來js的實現很冗長,主要的原因再methodCall要傳入 method name和argument,javascript ES6有Proxy物件,可以動態攔截function call 利用Javascript的Proxy可以讓整個api call變得非常簡潔,很可惜在C++這樣static typing的語言中沒有這樣的機制,因此在C++比較常見的作法是定義interface,再用code generator產生proxy stub

Posted in Network | Leave a comment

longest palindromic substring 演算法整理 (Manacher’s algorithm)

palindrome是指一個字串的 string = reverse(string) 而longest palindromic substring則是指找出一個字串中,substring是palindrome的最長substring 這個問題brute force不難想,就是把所有的substring 列出來,檢查是不是palindrome,但是這樣worse case會是O(n^3),因為substring有O(n^2)個,檢查palindrom要O(n) 比較常見的做法是中心點展開法,也就是選取一個點,然後展開看最大可以展到多少長度 這樣的time complexity為O(n^2),共n個字元做展開,每個字元展開worst case O(n), total O(n^2) 事實上,有更好的方法Manacher’s algorithm time complexity是O(n),可以參考wiki上的說明 https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher’s_algorithm 但是Wiki上的說明實在是太難理解了,所以這邊做個整理說明,並給出一些可能的實現 Manacher’s algorithm中文又有人叫馬拉車算法,本質上還是中心點展開法,但是差異在Manacher算法中會把之前走過的展開的資訊做個紀錄,在後面的展開中直接略去從頭開始展開的步驟,直接將整個演算法步數降到O(n) 在處理palindrome時,為了要避免分開處理奇數長度palindrome 或是偶數長度palindrome,一個常見的處理方式是在字串中插入delimeter 用什麼delimiter都可以,只要不要跟原始string的char衝突就好,加了delimiter後,整個字串的長度一定是奇數,且palindrome也一定是奇數,所以不用擔心要特別偵測偶數的palindrome(偶數palidrome是偵測s[i] == s[i+1],再以i, i+1往兩側展開) 為什麼加了delimiter就保證奇數呢?可以這樣想: N個字元的字串,有N+1個空間,插入delimeter就是N+N+1 = 2N+1 保證奇數,並且觀察以上abba, aba兩個字串的palindrome,可以發現delimeter本身是對稱的,所以也是符合把palindrome空隙插滿,亦即2m+1的情況,因此也是奇數 這邊先看一下其中一個實現方式,此方法參考了 https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/ … Continue reading

Posted in Algorithm | Leave a comment

string search算法整理 (Knuth–Morris–Pratt algorithm)

這邊列出一個字串算法Knuth–Morris–Pratt algorithm的一個實現,這邊使用的failure function value指最長prefix的最後一個字元的index,-1代表 no prefix match 字串的算法看起來很短,但是對於初學者來說非常不容易記憶或理解,主要的原因是死記一定容易忘記,並且failure function value有不同版本的詮釋,如果死記可能會看到不同版本的解法而混亂記憶,理解其中的核心概念非常重要 整個KMP算法的核心思想可以簡單用一句話描述: 比對target string suffix = pattern string prefix,比失敗則退而求其次(再找target string suffix = 次短的pattern string prefix) 在下面的說明中,I代表target string index to compare,J代表pattern string index to compare KMP的算法可參考 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm 原始的字串搜尋算法就是很直觀的將pattern和target一一比對,但是這樣一來worse case就是 O(n * m),例如 … Continue reading

Posted in Algorithm | Leave a comment

return 0 for std::string type

看到一段有問題的code,簡化如下 這樣子會compile過嗎? 答案是可以,此範例是可以通過compile。但是0是integer,integer和string應該不相容吧? 的確是不相容,其他的integer會compile不過,剛好 0 例外,在 C++11 4.10描述了 null pointer constant可以被轉成 null pointer 答案是可以,原因就在 std::string 接收 implicit construct from char pointer A null pointer constant is an integral constant expression (5.19) prvalue of integer type that evaluates to zero or … Continue reading

Posted in C++ Language | Leave a comment

stringstream使用

寫一個parser簡單的parse input,可以利用stringstream簡單做tokenizer 上面這個寫法看起來沒問題,檢查stringstream的state,如果fail就跳出迴圈,但其實這個寫法並不完全安全 我們再來看另一個範例 一般可能會預期就是印出1, 2, 3, 4, 5, 6的ascii int,但其實還多了一個-1 ,也就是說,在讀完6之後ss 的state還不是eof,等到做了peek()操作後,eof bit就會set了 因此在處理stringstream讀取時,此部分要特別小心,不能假設ss valid代表後面的讀操作就 會正確,還需要在讀操作後做一些檢查 以peek來說,C++11標準中描述的行為 int_type peek(); Effects: Behaves as an unformatted input function (as described in 27.7.2.3, paragraph 1). After constructing a sentry object, reads but … Continue reading

Posted in C++ Language | Leave a comment

bits/stdc++.h

https://stackoverflow.com/questions/25311011/how-does-include-bits-stdc-h-work-in-c 有時候會看到一些範例使用 特別是在一些competitive programming中使用到,這個header基本上就是把所有的C++ header include進來,不用再特別去個別include 也可參考 https://gcc.gnu.org/onlinedocs/gcc-4.8.5/libstdc++/api/a01235_source.html 看起來省了好多include header的工,不過需要注意的是,這個header不是standard,所以使用上可能會有portable的issue 另可參考 https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h 這邊提出了一些pros and cons

Posted in C++ Language | Leave a comment

C++11 unordered_set benchmark

結論: insert, erase, find: O(n)insert ~ 100Nfind ~ 50N (N以walk為倍數基準) compare with preallocate 1M bucket rehash(1000000) No preallocate walk: 0 μs (100)walk: 2 μs (1000)walk: 19 μs (10000)walk: 196 μs (100000)walk: 1988 μs (1000000)insert: 40 μs (100)insert: 309 μs (1000)insert: … Continue reading

Posted in C Language | Leave a comment