One Definition Rule – class type

最近在幫忙debug看到一段有意思的程式碼

我把出問題程式核心概念抽出來碼簡化改寫如下

//common.h
#pragma once

class C1
{
public:
	virtual ~C1()
	{

	}
};
//class2.h
#pragma once
#include "common.h"
#include <memory>

class Class2C1 : public C1
{
};

class Class2
{
	std::shared_ptr<Class2C1> p;
public:
	Class2();
	void run();	
};
//class2.cpp
#include "class2.h"
#include <iostream>

class ClassC2 : public Class2C1
{
public:
	ClassC2()
	{
		std::cout << "class2" << std::endl;
	}
};

void Class2::run()
{
	ClassC2* p2 = dynamic_cast<ClassC2*>(p.get());
	std::cout << "Class2 " <<  p2 << std::endl;
}

Class2::Class2()
{		
	p.reset(new ClassC2);
}
//class1.h
#pragma once
#include "common.h"
#include <memory>

class Class1C1 : public C1
{
};

class Class1
{
	std::shared_ptr<Class1C1> p;
public:		
	Class1();
        void run();
};
//class1.cpp
class ClassC2 : public Class1C1
{
public:
	ClassC2()
	{
		std::cout << "class1" << std::endl;
	}	
};

Class1::Class1()
{
	p.reset(new ClassC2);
}

void Class1::run()
{
	Class1C1* pp = p.get();
	ClassC2* p2 = dynamic_cast<ClassC2*>(pp);
	std::cout << "Class1 " << p2 << std::endl;
}
//main.cpp
#include "class1.h"
#include "class2.h"

int main()
{
	Class1* p1 = new Class1;
	Class2* p2 = new Class2;		
	p1->run();
	p2->run();
        return 0;
}

以上程式碼在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 type)

以下節錄 C++03 3.2 One definition rule
3.2.1 No translation unit shall contain more than one definition of any variable, function, class type, enumeration type or template. <– 這個是針對同一個translation unit
3.2.5 There can be more than one definition of a class type, enumeration type, … in a program provided that each definition appears in a different translation unit, and provided the definitions satisfy the following requirements — each definition of D shall consist of the same sequence of tokens; and …

重複定義在不同的translation unit是有限制的,例如允許class type、enumeration type。但是function呢? 在C++03 標準中的3.2.3 就有明確提到non-inline function只能存在一份定義在entire program

順帶一提, 一般來說declaration is definition,除了一些例外情況(在C++03 3.1.2 有明確提到 A declaration is a definition unless …),有關class definition 的sample 可參考C++03標準 3.1.3的範例

struct S { int a; int b; }; // defines S, S::a, and S::b
struct X { // defines X
int x; // defines nonstatic data member x
static int y; // declares static data member y
X(): x(0) { } // defines a constructor of X
};

可以看到上面範例struct S,定義了 class type,struct X也定義了 class type(雖然有static member 是declare),因此平常我們在header file寫的class 其實是 「定義」,也就是cpp在include header file時,會存在多份class type定義在不同的translation unit,但標準有提到只要 same sequence of tokens就沒有問題

那平常我們寫class時,不是還會分class.h和 class.cpp嗎?

這邊需區分class definition和member function declaration的概念,可參考C++03標準 9.3 Member functions的部分,9.3.2 A member function may be defined (8.4) in its class definition, in which case it is an inline member function (7.1.2), or it may be defined outside of its class definition if it has already been declared but not defined in its class definition

簡單說 member function是否inline 不影響class的定義

再回到原來的問題,範例程式碼中在class1.cpp class2.cpp都定義了ClassC2 但是內容卻不同,按照標準,這會導致undefined behavior

可是如果只看class2.cpp,在class2.cpp new ClassC2 再dynamic_cast 看到的應該同樣ClassC2才對,也就是class2.cpp內定義的ClassC2才對? 但是dynamic_cast回傳nullptr,顯然代表轉型失敗了,也就是runtime RTTI判斷並非同一個繼承樹

事實上如果看construtor的內容 class2.cpp new ClassC2是call class1.cpp的實作,因此推測dynamic_cast比對到不同版本的ClassC2 (同樣的code在g++ 不是nullptr,這部分跟實現有關)

再追下去,看class2.cpp assembly

__RTDynamicCast : https://docs.microsoft.com/en-us/cpp/c-runtime-library/rtdynamiccast?view=msvc-140

我們可以看到SrcType是Class2C1, TargetType是ClassC2 (但這個ClassC2是class11.cpp定義的)

__RTDynamicCast 的實作可以在C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\crt\src\vcruntime\rtti.cpp 看到,這邊會轉失敗的原因應該是在__RTDynamicCast裡走到FindSITargetTypeInstance 會再比對SrcType和TargetType的關係導致return nullptr (這一段是直接從source code推敲的,實際情況還需要另外debug trace)

在不同cpp中出現相同的class name看起來是很誇張的錯誤,但是其實不是不可能發生,例如在一個project中不同的開發者分別在不同的cpp中想到相同的名稱,也有可能是剪剪貼貼忘記改掉名稱,這些一旦出現問題時常常很難debug,特別是dynamic_cast是runtime的行為,例如在command pattern,從command queue取出來的command在一般會做down cast轉型,在這種情況下,不一定每次都會轉到有問題的command type

當然,一旦轉錯時,就會出現nullptr,如果又沒有特別檢查可能就會object call method時 nullptr access而crash,或是被nullptr check默默地屏蔽掉,又增加debug的困難度,但總結來說,dynamic_cast fail就是在型別轉換上失敗,有可能是不在同一個繼承樹,也有可能是同一顆繼承樹,但是private 繼承等原因,這個就需要根據實際情況推敲判斷了

像上面提到class definition多分的問題,因為是各自不會互相使用到,除了可以將class name改掉,另外一種做法是用unamed namespace

namespace的機制對於多人共同開發的project非常有用,避免重複名稱可以利用類似Java的做法,限定namespace + directory structure + class對應檔案名稱來解決,即便是想到相同的class name,但是因為在不同namespace,所以不會違反one definition rule,而如果在相同的namespace想到相同的名稱,那代表會存在相同的cpp路徑,在多人合作時,就會發現衝突

而如果是限制在單一個內部使用,建議可以使用file scope的作法 – unamed namespace,避免內部使用的名稱被外部(linker)看到

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可參考

概念上跟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

var express = require("express");
var bodyParser = require("body-parser");
var { JSONRPCServer } = require("json-rpc-2.0");
var server = new JSONRPCServer();

server.addMethod("is_even", function(n){
  return n % 2 == 0;
});

var app = express();
app.use(bodyParser.json());

app.post("/jsonrpc", async function(req, res){
  let jreq = req.body;
  let jresp = await server.receive(jreq);
  if(jresp){
    res.json(jresp);
  }else{
    res.sendStatus(204);
  }
});

app.listen(8091);
import requests
import json

def main():
    url = "http://localhost:8091/jsonrpc"
    payload = {
        "method": "is_even",
        "params": [100],
        "jsonrpc": "2.0",
        "id": 0,
    }
    response = requests.post(url, json=payload).json()
    print(response)
if __name__ == "__main__":
    main()

輸入100 回傳結果如下

{u'jsonrpc': u'2.0', u'id': 0, u'result': True}

使用起來簡單直覺,python 可以再利用語言本身的proxy機制,讓呼叫起來比較簡潔

以下整理json rpc 1.0 spec

其中提到 To invoke a remote method, a request is sent. Unless the request is a notification it must be replied to with a response. 在一般情形下,request response模式,但也可以單向client notify server

request body有 method, params, id,其中method 就是method name和xml rpc相同,params就是function parameter,id則是用來識別request / response,id不要求型態類別,可以是sequence id or uuid之類的,spec特別提到 The request id. This can be of any type. It is used to match the response with the request that it is replying to.

Notification: spec: A notification is a special request which does not have a response (並且 id = null)

response body有 result, error, id,其中在error發生時,result為null (spec: This must be null in case there was an error invoking the method. )

在底層的transport,spec分別說明了JSON-RPC over stream connections和JSON-RPC over HTTP的行為

因為HTTP本質是client server的架構,如果要做peer to peer,比較簡單的作法是兩個peer都開http port,分別當server,也當client,在spec中是採用另外一種作法: client會持續的polling (with HTTP POST),server要發request,或是client要回應server來的request,就是透過下一次的HTTP POST夾帶

顯然以spec描述的json rpc over HTTP的方式沒有效率,也因此在spec中說: The use of TCP/IP socket streams is encouraged

v1 spec 第3段 JSON Class hinting主要是描述type的擴展,原因是JSON type就那幾個type,這邊提供了一個擴充機制,這邊必須要接收端和發送端都對type有一致的理解,這就又回到serialization怎麼定的問題了,看起來和單純直接轉成string serialization是沒太多差異

第四段描述communication examples, 比較值得注意的是他的multiple request responses範例 (節錄自spec v1.0)

...

--> {"method": "postMessage", "params": ["Hello all!"], "id": 99}
<-- {"result": 1, "error": null, "id": 99}
<-- {"method": "handleMessage", "params": ["user1", "we were just talking"], "id":
null}
<-- {"method": "handleMessage", "params": ["user3", "sorry, gotta go now, ttyl"], "id":
null}
--> {"method": "postMessage", "params": ["I have a question:"], "id": 101}
<-- {"method": "userLeft", "params": ["user3"], "id": null}
<-- {"result": 1, "error": null, "id": 101}
...

我們可以看到 json rpc的設計概念上是雙向且asynchronous

因為asynchronous,所以需要用message id來mapping,第一筆postMessage 馬上就有response回來,但不一定如此,在最下面倒數第3筆的postMessage,後面還插入一筆notification (userLeft),然後才是id: 101的response

json rpc 2.0 大約在2010年左右,在1.0的基礎上做了擴展,但spec不要求實作相容1.0,並且在特定詞彙用字上根據RFC 2119的語意,另外以下點出幾個比較重要的差異

jsonrpc field

多了 jsonrpc field,帶版本資訊 “jsonrpc”: “2.0” ,這個方便未來版本相容性處理

params field

支援named parameter,1.0只支援positional parameter

在1.0的spec: params是An Array of objects to pass as arguments to the method., 在2.0中是A Structured value that holds the parameter values to be used during the invocation of the method. 在4.2 Parameter Structures 有更詳細的描述,如果params是array,就如同1.0是按照順序傳入(positional parameter),如果是object,代表是key value,key為parameter name (named parameter)

id field

notification 在1.0 id = null, 2.0 直接拿掉id (注意這邊指的是request id),對於response id來說,是REQUIRED

2.0 spec也提到 If there was an error in detecting the id in the Request object (e.g. Parse error/Invalid Request), it MUST be Null. 所以在response message中id: null是可能的

error、result field

2.0中有error就沒有result,有result就沒有error,在1.0中是要求兩個field都存在,但值可以是null

error object

這是在2.0新定義的,包含code、message、data,code要求為integer,並且spec中參考了  http://xmlrpc-epi.sourceforge.net/specs/rfc.fault_codes.php (Specification for Fault Code Interoperability, version 20010516) 的設計

batch request

這是在2.0新定義的,直接將多個request合併在一個array中

整體來說 json rpc 2.0 spec還是保持簡要的風格(相較於W3C的SOAP)
,作為一個簡單的protocol spec設計文件,其spec內容文件的大小大概是一個人日可以做得出來的範圍,值得作為啟發與參考

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

<?xml version="1.0"?>
<methodCall>
    <methodName>is_even</methodName>
    <params>
        <param>
            <value>
                <int>3</int>
            </value>
         </param>
    </params>
</methodCall>

在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 specified and must be correct. )

POST / HTTP/1.1
User-Agent: NodeJS XML-RPC Client
Content-Type: text/xml
Accept: text/xml
Accept-Charset: UTF8
Connection: Keep-Alive
Content-Length: 137
Host: 127.0.0.1:8090

在URL的endpoint,沒有特別規定,方便整進http server,這樣一台http server就可以同時提供不同類型的服務,範例中是使用 / 來做處理

The <methodCall> must contain a <methodName> sub-item 其中的methodName有要求charset: The string may only contain identifier characters, upper and lower-case A-Z, the numeric characters, 0-9, underscore, dot, colon and slash. It’s entirely up to the server to decide how to interpret the characters in a methodName.

這邊說明,methodName的字元集限制,以及server端可以自行決定如何解釋 methodName,這邊指的自行決定是指server端背後的實作(如何進行背後的function call),從介面的角度來看,並不影響client-server的相容性,只要server提供出他有哪些methodName以及需要的parameters即可

在params的定義,包含了參數型別,scalar value type不包含參數名

<i4> <int>:	four-byte signed integer
<boolean> 0 (false) or 1 (true)	
<string>
<double> double-precision signed floating point number
<dateTime.iso8601>	date/time	19980717T14:08:55
<base64>
<params>
    <param>
        <value>
            <int>3</int>
        </value>
     </param>
</params>

可以看到上面 3本身就只有描述param, value, int

因為是remote procedure call,所以概念上基本上可以用程式語言裡的function call來理解,在function call param中,arguments是帶有型別的(即使是Javascript,雖然是dynamic typing,但argument還是有type)

在描述複雜結構,xmlrpc定義了struct / array,struct可理解為JSON的object: key value pair,array即是array of <value>, An <array> contains a single <data> element, which can contain any number of <value>s.

可以參考下面的範例

<?xml version="1.0"?>
<methodCall>
<methodName>test</methodName>
<params>
<param>
    <value>
        <struct>
        <member><name>a</name><value><int>1</int></value></member>
        <member><name>b</name><value><string>2</string></value></member>
        <member>
            <name>c</name>
            <value>
            <array>
            <data>
            <value><double>3.3</double></value>
            <value><string>hello</string></value>
            <value><boolean>1</boolean></value>
            </data>
            </array>
            </value>
        </member>
        </struct>
    </value>
</param>
</params>
</methodCall>

上面的範例用JSON表示如下

{
    "a": 1,
    "b": "2",
    "c": [3.3, "hello", true]
}

其中可以看到 a, b, c在xml的struct member中, 型態分別是int, string,c的型態則是array,array中包含了3個value,分別是double, string, boolean型態。我們也可以發現JSON表示法相較於XML簡潔許多,甚至更human readable

另外,從設計的角度dateTime.iso8601 & base64都可以視為string的一種擴展,這有點像是JSON vs BSON,BSON基於JSON之上定義了許多型態擴展,像是binary data, date, regex, undefined, objectId等。當然所有的型態,最終都可以表示成string (serialization),定義哪些基本型別是牽涉到設計的哲學和藝術

再來看xmlrpc response,以下是 is_even的response,body的內容規則和request很像,差別只是methodResponse,以及error case的判斷,正常情況回傳<params>,錯誤發生時回傳<fault>

<?xml version='1.0'?>
<methodResponse>
<params>
<param>
<value><boolean>1</boolean></value>
</param>
</params>
</methodResponse>

另外我故意傳入錯誤的參數型態,產生<fault> 和 faultString

<?xml version='1.0'?>
<methodResponse>
<fault>
<value><struct>
<member>
<name>faultString</name>
<value><string><class 'TypeError'>:unsupported operand type(s) for %: 'dict' and 'int'</string></value>
</member>
<member>
<name>faultCode</name>
<value><int>1</int></value>
</member>
</struct></value>
</fault>
</methodResponse>

上面的fault用JSON表示

{
    "faultString": "<class 'TypeError'>:unsupported operand type(s) for %: 'dict' and 'int'",
    "faultCode": 1
}

在spec中提到 Unless there’s a lower-level error, always return 200 OK. 這邊指的是 例如404, 500這種server context error response,否則一律回應200,錯誤的解析則由xml body parse處理

以上就是xmlrpc的介紹,後續有機會再整理JSON-RPC

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

# from https://docs.python.org/3/library/xmlrpc.client.html
from xmlrpc.server import SimpleXMLRPCServer

def is_even(n):
    return n % 2 == 0

server = SimpleXMLRPCServer(("localhost", 8090))
print("Listening on port 8090...")
server.register_function(is_even, "is_even")
server.serve_forever()

python文件中有client side example

import xmlrpc.client

with xmlrpc.client.ServerProxy("http://localhost:8000/") as proxy:
    print("3 is even: %s" % str(proxy.is_even(3)))
    print("100 is even: %s" % str(proxy.is_even(100)))

不過為了展示interop,我另外用nodejs寫了一個範例

var xmlrpc = require('xmlrpc')
function TestClient(ep){
    let client = xmlrpc.createClient(ep);
    this.isEven = function(val){
      return new Promise(function(resolve, reject){
          client.methodCall('is_even', [val], function (err, data) {
            if(err) return reject(err);
            resolve(data);
          })
      });
    }
}
async function  main(){
  let testClient = new TestClient('http://127.0.0.1:8090/');
  console.log('3 is even?', await testClient.isEven(3));
  console.log('100 is even?', await testClient.isEven(100));
}
main().catch(console.log);

看起來js的實現很冗長,主要的原因再methodCall要傳入 method name和argument,javascript ES6有Proxy物件,可以動態攔截function call

var xmlrpc = require('xmlrpc')
function TestClient(ep){
    let client = xmlrpc.createClient(ep);
    let smartClient = new Proxy({}, {
        get: function( target, prop, receiver) {
            if(prop in target) return target[prop];
            return function() {
              let args = [].slice.call(arguments);
              return new Promise(function(resolve, reject){
                  client.methodCall(prop, args, function (err, data){
                    if(err) return reject(err);
                    resolve(data);
                  })
              });
            }

        }
    });
    Object.setPrototypeOf(this, smartClient);
}
//上面與rpc method name無關

async function  main(){
  let testClient = new TestClient('http://127.0.0.1:8090/');
  console.log('3 is even?', await testClient.is_even(3));
  console.log('100 is even?', await testClient.is_even(100));
}
main().catch(console.log);

利用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/ 的思路來實現

std::string lps(const std::string& s)
{
  int len = s.size();
  int N = 2 * len + 1; //with delimiter
  std::vector<int> dp(N);
  int C = 1; //current center
  int R = 1; //palindrome right index of current center
  int maxLen = 1; // max palindrome radius (inclusive)
  int maxI = 0; //center index of max palindrome length 
  for(int i = 1; i < N; i++)
  {
    int mirrorI = C - (i-C);
    int delta = R - i;
    if(delta>0)
    {
      //based on previous information, calculate current palindromic string radius
      //also need to take account of information which is out of bound
      dp[i] = std::min(dp[mirrorI], delta);
    }
    while(( i + dp[i] < N - 1) &&
          ( i - dp[i] > 0) &&
          ( ((i + dp[i] + 1) % 2 == 0) ||
            (s[(i+dp[i]+1)/2] == s[(i-dp[i]-1) / 2])))
    {
      dp[i]++;
    }
    //update max radius
    if(dp[i] > maxLen)
    {
       maxLen = dp[i];
       maxI = i;
    }
    //update center
    if(i + dp[i] > R)
    {
      C = i;
      R = i + dp[i];
    }
  }
  int index = (maxI - maxLen)/2;
  return s.substr(index, maxLen);
}

先理解一下dp內代表的意義

dp中存了走訪的資訊,代表該index [i-j, i+j] 是以該index為中心,最長的palindrome,可以看到圖中的 a dp = 9,代表 該字元 a 往右邊9個與往左邊9個皆相同,也可以發現這個數字對應原來沒有delimiter的字串,剛好以a為中心整個palindrome長度就是9

如果我們可以得到整個dp的值,基本上答案就出來了

首先看一個範例,以下圖的箭頭處為例,該處字元a 對應的dp值應該是多少呢?

最簡單的想法就是往右走往左走,看看能比對到最長的長度,這樣就要O(n),n個字元就要O(n^2),Manacher的算法說,可以省略一些步驟,方框處是以c為中心點找到最長的palindrome,左右7 chars都對稱,這裡面隱含了一些可利用的資訊

如何找出隱含的資訊,仔細觀察在虛線c的位置,已經找到左右7個對稱,代表在某種程度,左邊看到的世界和右邊看到的世界是相同的, 圖中藍色的數字是已經算好的dp值,下排紅色的數字是從mirror看到的數字,因為對稱,代表在c的方圓內,可以保證兩方在碰到藍色框之內是相同的,藍色框外的世界不知道,這裡我們可以看到至少? 地方的longest match = 3(因為3仍然在方框內)

方框外的資訊就不知道,但是至少我們可以從方框外開始比

也就是直接跳了3步,直接從j = 4開始比,透過比較完可以知道方框往右可以延伸的地方,必要時更新new center,和new radius

看起來很繁瑣,但是只要掌握住基本的概念,利用可利用的資訊,超出邊界的不能用,邊界外的資訊再另外算的原則,就可以比較好理解

我們再來看圖中?處的值應該是多少,看mirror,應該是7,但是如果仔細看,其實對應的位置走七步是超出藍框邊界的(下圖中綠色框處),因此必須做調整,只能保證到藍框處,也就是5,接著直接從5開始比,比失敗就設定dp = 5

關於time complexity,乍看之下,上面的作法是省略了一些比較,但真的能把n^2降到n嗎?關鍵在於藍框處,會需要做超過一步的比較就代表以新的點為中心,沒有藍框以內的資訊可以用,因此新的比較是從藍框外開始比,如果有比到代表會擴展藍色框的右邊,而藍色框是一路往右的,因此整體的time complexity是O(n)

test case: 這個test case長度約一千多,如果使用一般的做法n^2約做1 million steps

實測step數 Manacher算法對上面的字串 len =1450, steps = 2897

順便附上中心點展開法的一個參考解答(來自於leetcode其他人的submission)

std::string lps(const std::string& s)
{
  if (s.size() <= 1) return s;
    int maxIdx = 0;
    int maxLen = 1;
    int i = 0;
    while (i < s.size()) {
        int start = i;
        int end = i;
        // expand the window from the end if it's an even palindrome
        while (end + 1 < s.size() && s[end] == s[end + 1]) {
           end++;
        }
        i = end + 1;
        // expand the window from both sides until it's not longer a palindrome
        while (start - 1 >= 0 && end + 1 < s.size() && s[start - 1] == s[end + 1]) {
            start--, end++;
        }
        int currLen = end - start + 1;
        if (currLen > maxLen) {
            maxIdx = start;
            maxLen = currLen;
        }
    }
    return s.substr(maxIdx, maxLen);
}

以上面test case測試,len = 1450,steps = 524902

另外也放上根據wiki 參考,直接使用delimiter作法的實現,和最一開始的實作差別是直接使用加工過的string做計算,不用額外處理index

std::string lps(const std::string& s)
{
  int len = s.size();
  int N = 2 * len + 1;
  std::vector<int> dp(N);
  std::string s2(1, '|');
  for(auto c: s)
  {
    s2.push_back(c);
    s2.push_back('|');
  }
  int C = 0;
  int R = 0;
  for(int i = 1; i < N; i++)
  {
    if(i > R)
    {
      C = i;
      R = i;
    }
    else
    {
      int mirrorI = C - (i - C);
      dp[i] = std::min(dp[mirrorI], R - i);
    }
    int j = dp[i] + 1;
    while((i-j >= 0) && (i+j < N) && (s2[i-j] == s2[i+j]))
    {
      j++;
    }
    dp[i] = j - 1;
    if(i + dp[i] > R)
    {
      C = i;
      R = i + dp[i];
    }
  }
  auto it = std::max_element(dp.begin(), dp.end());
  int maxLen = *it;
  int index = it - dp.begin();
  return s.substr((index - maxLen) / 2, maxLen);
}

總結來說,Manacher算法的核心在如何重複利用先前發掘的dp資訊,並且需要標定藍框的位置,藍框是使得Manacher可以將步數降到O(n)的關鍵,對應程式碼就是C, R變數(center, radius)

Manacher算法其實理解了後並不難,不過理解本身需要沉下心來花一點時間,不能抱著速成心態看。

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

int search(const std::string& target, const std::string& p)
{
  if(target.size() < p.size()) return -1;
  std::vector<int> v(p.size(), -1);
  int i = 1;
  int j = 0;
  //build failure function stage
  while(i < p.size())
  {
    if(p[i] == p[j]) //matched, update failure function
    {
      v[i] = j;
      i++;
      j++;
    }
    else if(j == 0) //j = 0,不用往前看prefix string,直接放棄比對
    {
      i++;
    }
    else //更新比對基準
    {
      j = v[j-1] + 1;
    }
  }
  i = 0;
  j = 0;
  //compare target string stage
  while(i < target.size())
  {
    if(target[i] == p[j])
    {
      i++;
      j++;
    }
    else if(j == 0)
    {
      i++;
    }
    else
    {
      j = v[j-1] + 1;
    }
    if(j == p.size())
    {
      return i - j;
    }
  }
  return -1;
}

字串的算法看起來很短,但是對於初學者來說非常不容易記憶或理解,主要的原因是死記一定容易忘記,並且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),例如 對aaabaaabaaab 搜尋 aaaa

//brute-force
int search(const std::string& target, const std::string& p)
{
  if(target.size() < p.size()) return -1;
  for(int i = 0; i <= target.size() - p.size(); i++)
  {
    for(int j = 0; j < p.size(); j++)
    {
      if(target[i+j] != p[j]) break;
      if(j == p.size() - 1) return i;
    }
  }
  return -1;
}

worse case就是比對到最後fail又要重新開始,雖然在一般情況下,target和pattern的關係不會這麼極端,大部分情況都會early return,在wiki上也有描述到如果是random隨機的情況下,target和pattern要match到n 個字的機率是 26^n(假設charset 是small capital alphabet),這樣time complexity平均來說就是O(n) 但是這是隨機情形,random也是很極端的case

而Knuth–Morris–Pratt字串搜尋算法可以將worst case降到 O(n),有些文章寫O(n+m),不過不影響,主要還是看target string length,另外pattern string length也不大於target string length,如果大於就直接放棄搜尋了

那麼KMP算法是如何將worse case time complexity壓到O(n)呢,最主要就是preprocess pattern string,原始的brute force solution每次fail就pattern match從頭開始,KMP則是可以利用pattern內的資訊,跳過不需重複比較的部分

以 target = ABCDABABCDABD, pattern = ABCDABD為例

比到index = 6( 0-index),A對到pattern中的D發現不合,在brute force時此處代表是從index = 0的A起始的,所以會跳到 index = 1的B重新開始比對

但是如果仔細看pattern string,假如已經比到index = 6的D代表target字串從index = 1到index = 5的資訊也已知並且等同於pattern的index 1~5,KMP即是巧妙的利用此信息來去除掉不必要的搜尋步驟,brute force的作法,會移動target index = next,pattern index = 0,而KMP則是只移動pattern index,以上面的例子看就是從紅->藍->綠,乍看之下好像KMP對單一個字元進行了多次pattern跳轉比對,但事實上,因為跳轉是往前跳最多就當前比對pattern位置J的次數,而如果J的數字大,代表I也走了J步才遇到failure,這時候再怎麼跳也頂多跳J步,而此時I的位置不變,所以整個搜尋過程跳轉最多也就是n步

KMP裡面紀錄如何跳轉的資訊用了類似dynamic programming的做法,記錄一個failure function array,那麼failure function如何產生呢,先理解failure function的數字的意義

pattern: ABABABABABABABAA

搜尋的target字串為 ABABABABABABABAC

failure function存的資訊即是: pattern中的第J個字元,往前的字串可以找到最長的pattern prefix,suffix = longest pattern prefix

以圖中為例,pattern index = 14 橘線的地方可以找到紫色虛線相同prefix ( index =0 ~ 12)

在比較target string, 從紅色虛線框index = 0開始比,比到index = 15時發現不對,此時代表0-14都是一樣的,而failure function說: index 14往前看和 index 0-12是一樣的,所以C可以直接從index 12 + 1 => index 13開始比(綠色虛線),如果不一樣就再看failure function,此時target字串雖然不match index=13,但是仍然代表對於pattern match index 0-12是相同的

failure function又說 index 12往前看 跟index0-10是相同的

所以比較可以從pattern index 11開始比,即綠色虛線指向處,如此一直重複,直到比對到pattern index = 0,此時退化為原始的判斷,如果連index = 0都不match當然就只能跳過目前的target string char,往後比較了,pattern index = 0也就是重比了

我們可以看到比較的過程,failure function是往前一格查詢,因為當前的字元不match,只能往前一格去找前一格成功比對match的字串,跟pattern字串最長的prefix match,這邊要注意target prefix match比對的起始點不是從頭算,因為我們知道重頭算(前面圖index = 0)紅框處沒辦法match整個pattern,所以要從pattern index = 1之後找prefix match的起始點

以上圖為例,index = 12的A,prefix match是match 從index = 2的字元開始 (index = 2 – 12),比對pattern prefix(index = 0 – 10)

所以target char != pattern char時就是 J – 1找尋pattern prefix string last index,再從該index + 1繼續比對

前面提到: failure function存的資訊即是: pattern中的第J個字元,往前的字串可以找到最長的pattern prefix,-1代表no match

以上面的例子,index = 0,為A,第一眼看起來好像有prefix match,但是注意前面提到pattern prefix match起始點不是從開頭算,所以此格 = -1

第二個index = 1字元為B,找不到跟pattern 共通prefix,= -1 (AB = AB步算)

第三個index = 2 字元為A, 往前的string 有 BA, A,A跟index = 0 A match,match的prefix string last index = 0,failure function value = 0

index = 4的字元為A,往前的string有BABA、ABA,match pattern prefix ABA,matched prefix last index = 2,failure function value = 2

仔細發現failure function建立的過程,其實就是pattern 中的char和自己比,前面提到的target比pattern的方法可以拿來用到pattern比自己,差別是pattern自己比完還要更新failure function

碰到not match char,就找最長prefix,再更新j,如果match,就更新failure function

整個實現的細節可以參考最開頭的程式碼

總結來說: 理解 KMP算法的關鍵是

  • 查找字串 動pattern index J,不動target index I
  • failure function 代表的意義(這篇文章使用的概念是 current suffix = pattern prefix )
  • 如何利用failure function減少不必要的比對(如何使用failure function)
  • 如何建立failure function

重複利用已知資訊常常是字串算法優化的關鍵,類似的還有Longest palindromic substring,一般brute force 兩個for loop檢查是否為palindrome的作法O(n^3),好一點的作法是中心點展開也要O(n^2),但是Manacher’s algorithm可以做到O(n),有機會再來整理此算法

Posted in Algorithm | Leave a comment

return 0 for std::string type

看到一段有問題的code,簡化如下

#include <string>

std::string test()
{
  return 0;
}

int main()
{
  test();
  return 0;
}

這樣子會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 a prvalue of type std::nullptr_t. A null pointer constant can be converted to a pointer type

C++11 § 4.10 Pointer conversions

所以結果就是 std::string constructor看到null pointer,根據 C++11 21.4.2.9,描述

basic_string(const charT* s, const Allocator& a = Allocator());

Requires: s shall not be a null pointer.

C++11 § 21.4.2.9

標準要求,不可以傳null pointer進去,否則可能是直接abort,可能是exception,結果為UB

Posted in C++ Language | Leave a comment

stringstream使用

寫一個parser簡單的parse input,可以利用stringstream簡單做tokenizer

std::string expression = "(2+3)*4";
std::stringstream ss(expression);
while(ss)
{
  ....
}

上面這個寫法看起來沒問題,檢查stringstream的state,如果fail就跳出迴圈,但其實這個寫法並不完全安全

我們再來看另一個範例

#include <sstream>
#include <iostream>

int main()
{
  std::string s = "123456";
  std::stringstream ss(s);
  while(ss)
  {
    char c = ss.peek();
    std::cout << c << ", " << (int)c << " , EOF = " << ss.eof() << std::endl;
    ss.get();
  }
  return 0;
}

一般可能會預期就是印出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 does not extract the current input character.
Returns: traits::eof() if good() is false. Otherwise, returns rdbuf()->sgetc().

C++11 27.7.2.3

而sgetc()的行為則是在C++11 27.7.2.1裡有描述

If rdbuf()->sbumpc() or rdbuf()->sgetc() returns traits::eof(), then the input function, except as explicitly noted otherwise, completes its actions and does setstate(eofbit), which may throw ios_- base::failure (27.5.5.4), before returning.

C++11 27.7.2.1

亦即 peek()本身會透過 sgetc()觸發eof bit set

網路上有一篇討論也值得參考,不過需注意的是該篇時間比較久,所以有些資訊的描述不一定跟上較新的標準

https://comp.lang.cpp.moderated.narkive.com/vwstw4Un/std-stringstream-and-eof-strangeness

Posted in C++ Language | Leave a comment

bits/stdc++.h

https://stackoverflow.com/questions/25311011/how-does-include-bits-stdc-h-work-in-c

有時候會看到一些範例使用

#include <bits/stdc++.h>

特別是在一些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 ~ 100N
find ~ 50N (N以walk為倍數基準)

#include <iostream>
#include "Timer.h"
#include "Util.h"
#include <unordered_set>

int main()
{
  std::vector<int> v = generateShuffleVector(1000000);
  Timer timer;
  std::vector<int> loop = {100, 1000, 10000, 100000, 1000000};
  std::vector<int> walkt;
  std::vector<int> insertt;
  std::vector<int> findt;
  std::vector<int> eraset;

  for(auto k: loop)
  {
    int ms = 0;
    std::unordered_set<int> s1;
    //s1.rehash(1000000);
    timer.start();
    for(int i = 0; i < k; i++)
    {
      v[i];
    }
    ms = timer.stop();
    walkt.push_back(ms);

    timer.start();
    for(int i = 0; i < k; i++)
    {
      s1.insert(v[i]);
    }
    ms = timer.stop();
    insertt.push_back(ms);

    timer.start();
    for(int i = 0; i < k; i++)
    {
      s1.find(v[i]);
    }
    ms = timer.stop();
    findt.push_back(ms);

    timer.start();
    for(int i = 0; i < k; i++)
    {
      s1.erase(v[i]);
    }
    ms = timer.stop();
    eraset.push_back(ms);
    //μs
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "walk: " << walkt[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "insert: " << insertt[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "find: " << findt[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "erase: " << eraset[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  return 0;
}

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: 3057 μs (10000)
insert: 31091 μs (100000)
insert: 344995 μs (1000000)

find: 8 μs (100)
find: 88 μs (1000)
find: 1014 μs (10000)
find: 11328 μs (100000)
find: 130589 μs (1000000)
erase: 17 μs (100)
erase: 174 μs (1000)
erase: 1843 μs (10000)
erase: 20141 μs (100000)
erase: 202869 μs (1000000)

preallocate

walk: 0 μs (100)
walk: 2 μs (1000)
walk: 19 μs (10000)
walk: 196 μs (100000)
walk: 2032 μs (1000000)
insert: 26 μs (100)
insert: 216 μs (1000)
insert: 2147 μs (10000)
insert: 22046 μs (100000)
insert: 230671 μs (1000000)

find: 7 μs (100)
find: 71 μs (1000)
find: 842 μs (10000)
find: 9229 μs (100000)
find: 101268 μs (1000000)
erase: 16 μs (100)
erase: 129 μs (1000)
erase: 1374 μs (10000)
erase: 14663 μs (100000)
erase: 168957 μs (1000000)

上面比較可以發現preallocate bucket insert需要的時間較少,主要的原因是減少了rehash的時間,以下列出insert過程中, bucket count的變化

1:rehashed from 1 to 2
2:rehashed from 2 to 5
5:rehashed from 5 to 11
11:rehashed from 11 to 23
23:rehashed from 23 to 47
47:rehashed from 47 to 97
97:rehashed from 97 to 199
199:rehashed from 199 to 409
409:rehashed from 409 to 823
823:rehashed from 823 to 1741
1741:rehashed from 1741 to 3739
3739:rehashed from 3739 to 7517
7517:rehashed from 7517 to 15173
15173:rehashed from 15173 to 30727
30727:rehashed from 30727 to 62233
62233:rehashed from 62233 to 126271
126271:rehashed from 126271 to 256279
256279:rehashed from 256279 to 520241
520241:rehashed from 520241 to 1056323

可以看出bucket count 每次增加都是倍增 F(m+1)= 2F(m) + 1,這種方式類似vector的運作,insert rehash amortized time complexity會平均到O(n)

順便比較一下 <set>的實作,值得注意的是find那邊的time complexity,跟預期的nlogn有落差,這邊推測主要的原因是因為底層實作如果是用RB tree, 不會完全balance,因此高度不能用最小的nlogn來算,但理論上使用RB tree還是nlogn 只是會有一個constant factor

walk: 0 μs (100)
walk: 1 μs (1000)
walk: 19 μs (10000)
walk: 196 μs (100000)
walk: 1991 μs (1000000)
insert: 36 μs (100)
insert: 427 μs (1000)
insert: 4870 μs (10000)
insert: 60547 μs (100000)
insert: 934594 μs (1000000)
find: 19 μs (100)
find: 269 μs (1000) [ 14.16x ] , expect 15.00x
find: 3582 μs (10000) [ 13.32x ] , expect 13.33x
find: 47652 μs (100000) [ 13.30x ] , expect 12.50x
find: 855063 μs (1000000) [ 17.94x ] , expect 12.00x

erase: 37 μs (100)
erase: 430 μs (1000)
erase: 5532 μs (10000)
erase: 68321 μs (100000)
erase: 1124433 μs (1000000)


Posted in C Language | Leave a comment