2015年7月5日 星期日

The C++ Programming Language 國際中文版 第四版 勘誤

其實好幾年前，大約是 Modern C++ Design 讀了一半的時候，我就放棄學習 C++ 進階技術了。倒也不是看不懂，那些技術很巧妙、確實能解決某些其他語言不易解決的實際問題沒錯，但覺得用那些技術寫程式也末免太迂迴。

舉個比較簡單的例子：用 static_assert<> 來檢查 compile time 的問題。compiler 不認得什麼是 static_assert，就乖乖的把 template 展開；視 static_assert 怎麼寫的，展開之後可能發現某 class 有問題或是陣列宣告不合語法，於是吐出一堆 template 具現化失敗的錯誤訊息。

我的意思是說，一個很 high level 的目的(也許是 static_assert，也許是判斷某個 type 是不是繼承另一個 type，或判斷 template 參數的個數……)，但 compiler 不認得，寫的人只好用一堆 low level 的東西湊出那個意圖，叫 compiler 去一堆 header 檔裡找 template 定義、template matching、推導、instantiation，層層疊疊，寫的人辛苦，compiler 也花一堆時間照做，若不小心寫錯，還吐出天書一般的錯誤訊息。整個就是事倍功半。簡直是為了解決一個問題結果製造更多問題。
 (p.s. static_cast 已經在 C++11 成為語言的一部分了)

話雖如此，無論是工作還是自己寫東西自娛，我還是常常用 C++。這陣子越來越常看到有人用新的 C++ 語法，自己也開始用。雖然還不太懂整個 C++11 C++14，但就看到的部分，覺得新的 C++ 修正了許多原本的不足，也有嘗試改善前面我提到的問題。難怪有看到文章說，很多 C++ programmer 因為 C++11 對 C++ 好感度提升了。

最近看到 The C++ Programming Language 第四版的中文版剛出，就買了一本來看，想比較有系統的學學 C++ 的新東西。目前只讀了前幾章導覽的部份，覺得組織得比第三版好(其實很薄弱的印象，畢竟好幾年前讀的了)。作者 Bjarne Stroustrup 也更強調這本不是給初學者的教材，初學者應該讀他寫的另一本 Programming -- Principles and Practice Using C++。(我前陣子忘了這件事，竟然還推薦一個初學者，還好他沒聽我的話 XD)

第四版翻譯的品質沒第三版葉秉哲的那麼好。文句算通順沒問題，有些譯名不習慣還可以接受，但是錯譯不算少。讀到令人困惑之處再找原文比對，通常會發現是翻譯錯誤。整體來說，翻譯得還可以，希望出版社/譯者能花更多工夫確保書籍的正確性。原本讀中文版是想偷懶節省時間，但我查找原文比對，還做了勘誤表向譯者回報問題，最終可能沒省下太多時間 :(

以下是我自己做的勘誤表(若我有空繼續讀的話，會持續更新)
https://docs.google.com/spreadsheets/d/1d3yOOVuhAHSla6LKQLZ9QHdu1hKgGegaXO7Np5PlIV8/edit?usp=sharing
譯者在出版社的書籍網頁最下面有提供勘誤下載(err, 為什麼不是網頁，為什麼是 docx…)，目前好像都是我回報的 :P (不過譯者並沒有100%接受我的建議)
張貼者： 於 4 則留言 :

2015年6月4日 星期四

nonogram 漫談 - 3 TCGA2015

之後約三年多沒再改程式，只是有時會想到一些沒機會實作的點子。今年春假時翻了幾篇最近幾年的論文，發現用 SAT solver 來解 nonogram 有好幾個突出的成果，讓我又冒出一些新想法(結合傳統 solver 跟 SAT solver 的用到的技術)，便考慮今年再次參賽。

再來就是了解現在參賽程式的發展。說到這個我就要抱怨一下。TCGA 及 TAAI 辦的比賽(我是指各項比賽，不只 nonogram)某些資訊不夠公開，譬如有時比賽規則細節從略，有時比賽結果只有名次，沒有比數或棋譜/數據，有幾年甚至連名次都很難找到。(今年的狀況似乎還可以)。雖然比賽後其實有結賽報告，但那只有訂閱期刊才看得到，且限於篇幅沒有完整的資料。我並不認為這是故意隱瞞，但我覺得這部分沒做好，其實是會間接影響這領域的發展的。

想像有個無聊的人(我? :p) 或是有個學生，對某個棋類感到好奇，說不定他本來看一看棋譜發現當下的程式不過爾爾，有為者亦若是寫個更強的，或是覺得某個課題有趣想找這幾年的冠軍討論。但實際上他上網查到的只有殘缺不全的資訊，說不定就澆息他的想法了，覺得那是一個自己玩自己的小圈圈。

也許我比較理想化，我覺得這比賽還算是學術活動，雖然各自的程式不公開，還是要盡量「可重現」(別人用一樣的機器、類似的做法，應該要有辦法做出類似的結果)。但實際上就算報名了比賽，可能還是不知道對方用什麼機器，看不到對方跟別人對弈的棋譜。

扯遠了，回到主題。我去信詢問這次比賽的規則及最近幾次的賽況，了解到今年規則大致上沒有差太多，這幾年 nonogram 的交大第一名的程式自 2011 年後也沒什麼改動。雖然我的程式還沒完成，還是先報名了 :) 畢竟對我而言有個寫程式自娛的機會，還到會場去看看這領域的進展，跟一些朋友、老師聊聊，都很有意思，比賽名次只是附帶的。

我也回頭看了一下我舊的程式，TAAI11 時，程式在第 510 題卡了 81 分鐘(直到比賽結束還沒解出來)，應該是程式有 bug 掉到無窮迴圈，而不是單純算得慢。

這回我的程式計畫是，先重構我舊的程式，實作交大論文的 fully probe, FP2, 還有 search heuristic 當作 baseline，然後再開始試驗結合 SAT solver (其實我有做點小實驗，效果還不錯)。程式檔名就叫 baseline，只是沒想到後來光最佳化 baseline 就用掉了我全部的時間。

照著論文實作的好處是，有數據可以對照知道自己有沒有誤解論文。我發現我大方向是對的，搜尋次數是一樣的，但問題出在算一樣的東西我的就是比較慢。用時間複雜度來說明就是，整個演算法是 O(a * b^n * n^c)，這是指數時間演算法，我的 search heuristic 跟論文相同，其他部分也正確，所以 search node 跟論文一樣多，也就是 b 一樣大。但是我的程式比較慢，也許是選用的基本資料結構不同造成 a 比較大，或是一些實作細節的不同 c 比較大……所以我就一路最佳化我的程式，從大約三倍慢一直改進到慢 40%。

這次的比賽結果，交大第一名，1000 題花了 908 秒, 我拿第二花了 1135 秒，第三名 3737 秒，第四名兩小時解了 232 題。只慢 20% 是因為我稍微調整了 choose weight 的參數(比較小的 b，不過我其實不是很有把握)。也就是說我的程式只有一點參數不同，其他部份其他部分跟第一名的程式沒什麼兩樣，這是比較無趣的地方(理想上大家用不同做法，百花齊放，有趣多了)。
(技術細節我在接下來的文章再談)

這次比賽花了我一個禮拜的休假，加上兩個禮拜下班後的時間。我原本都在 linux 上開發，由於比賽要在 windows 上跑，我在前兩天才開始下載 Visual Studio Express 2013，所以程式還沒有針對 windows/vc++ 作最佳化。在賽後我改用 mingw64-g++ 並調整 compiler 參數，還可以快 15%，也就是說跟第一名只差 5% 左右。所以我可以很阿 Q 的說，只要再一個禮拜就可以贏了 :P (我也試了 Intel system studio 2015 free trial 裡附的 intel c++ compiler 15.0，但沒有比較快，不過我跟 intel c++ compiler 參數也不熟就是了)
張貼者： 於 沒有留言 :
標籤：

2015年6月1日 星期一

nonogram 漫談 - 2

我跟 nonogram 的故事要從國中開始說起 :)

國中時有同學帶了尖瑞出版社的一本 "解題畫冊"(我忘了當時的書名) 來學校玩，那時還不流行數獨，不過就類似那感覺，每一頁就是一題，用紙筆加上邏輯推理，解出謎底的圖案。印象中那時會跟同學抄題目到自己的計算紙上玩。雖然覺得很有趣但好像沒有一直玩下去，現在回想大概是抄題、解題太累了，而且沒有跟同學競技的快感 (那時還會玩三角殺棋(當時我們叫三角棋)，幾A幾B等等)

後來在某一年(可能是 2001)的 IOI 研習營期中考題，就有老師出了一題叫「海島地圖」其實就是 nonogram ，我那時還去幫忙寫 test data 跟參考解答。後來(應該是 2003)我到建中幫忙出校內比賽的題目，就拿一樣的題目來用。當時題目要求輸出全部符合條件的圖形，我對 nonogram 的理解就是 search 題，不過並不要求大家在比賽時限內寫出任何 heuristic，所以 n 給得並不大，只要能正確的 DFS search 就可以拿到超過一半的分數，若 search 時有稍微考慮不跟相臨顏色的條件衝突，差不多就能拿滿分。程式碼約 100~200 行就可以完成。只是印象中大部分的人都拿不到一半的分數。

後來查資料才發現，IOI '92 那年有題 "Islands in the Sea" 相信就是研習營出題的來源。'92 年的測試資料最大  8*8。另外，ICPC '93 年有一題 "Scanner" 應該也算相關的題目，記得 '97 集訓寫考古題時大家都卡住，只有 lckung 學長成功解出。

大學時出現了一系列 logic 遊戲的網站，我還有一些同學有時會玩玩上面的遊戲打發時間。這些遊戲 (Nonogram, Slither Link, Sudoku, Light Up, Bridges, Shikaku, Nurikabe, Dominosa) 有些還有人發表論文研究，有幾項還成為 Computer Olympiad 或其他類似 conference 的比賽項目。 (Computer Olympiad 每年會辦許多電腦棋類比賽(西洋棋、象棋、圍棋甚至橋牌、撲克)，我偶爾會關心一下比賽了解最近發展的狀況。)

我在 2011 年時才發現 nonogram 2010 年開始有辦比賽，也就開始讀相關的論文跟網路資訊，我發現當時網路上已經有幾個很強的 nonogram solver，但是大部分的論文都沒提到這件事(也許是論文發表的時間差，譬如 BGU 2010 年不錯的成果，論文 2012 投稿，2014 才登出來已經晚了；除此之外，我是覺得有些論文，該怎麼說呢，參考價值不高)。

我當時也覺得比賽規則有很大的問題。也許是想增加競爭趣味，比賽方式是雙方互相出題給對方解。但出題是在事先準備好的，沒有資源限制，所以可以隨機產生大量題目，用大量 CPU 把簡單的題目過濾掉，只要有足夠的計算資源，我相信可以做到比賽時限內沒有人可以解出任何一題 ;)

當時我的做法就是這樣：先隨機產生幾百個題目當種子，然後用程式去解，把解得比較快的題目丟掉，解得比較慢的題目隨機改幾個顏色(黑變白或反過來)當作新的題目。然後跟朋友借一些 CPU 來跑(我忘了多少，大概有數十顆)，跑了也許一個禮拜吧。

當時覺得這比賽參賽者可能不是很強(根據前一年的賽後報告)，比賽規則又不是很公平(或說有漏洞)，所以我就報名參賽 TCGA2011 (6月)，程式取名 Naughty，就是說我是來搗蛋的 :) 從程式開始寫到比賽不到兩個禮拜，事實上比網路上抓得到的 solver 還弱，結果拿第一名。

到了年底另一個比賽 (TAAI2011, 11月)，這回我就幫忙修改比賽規則，改回單純的比賽解題速度，可是也比較無趣 (相較於其他棋類你來我往的廝殺)，往後幾年比賽的規則大致上延用。

不過半年不見，交大的隊伍重組，程式演算法大改進，這回就換我被痛宰了 XD (現在回頭看當年的紀錄，我才發現四年前他們用的電腦比今年比賽用的還快 orz 還好近幾年規則改成統一用同一台電腦跑了)

交大 2013 年也發表了一篇 paper 解釋他們的做法，有興趣寫 nonogram solver 的話值得一讀。
張貼者： 於 沒有留言 :
標籤：

2015年1月11日 星期日

OSM vector map - mapsforge

本文介紹 mapsforge 的 map 格式、製作、應用及相關概念。

OSM vector map

在 Android 上 OSM 的 vector map 主要有三個選擇
OSMAnd 雖然 open source 但它的 license 在 GPLv3 之上另外加了限制
Publishing applications using the OsmAnd GPLv3 code to Google Play, Amazon Market or Apple Store should be done with written permission
所以在 app 世界沒有其他人用。

maps.me (以前叫 MapsWithMe)的公司在被併購之後 app 變免費，還宣稱會在 2015 年 open source (公告)。

而 mapsforge 不是 app，它是一個 map engine library (LGPL)，所以幾乎其他支援 vector map 的 app 其實都是用它，像是 OruxMaps、LocusMap 等等。

另外，garmin gps 的地圖檔格式已被研究、公開，也有一些程式或網站可以將 OSM data 轉為 garmin gps 用(教學)。本文不討論 garmin map。

mapsforge

OSM 的資料本來就是點、線座標及文字 tag，已經是「vector」了。只是一般 OSM 資料用的 xml 或 pbf 格式只適合儲存、批次處理，不能 random access, render map。

mapsforge 將 OSM 的資料 preprocess 預先切成一個個 tile (且以 zoom level 區分)，同一個 tile 的資料連續儲存，因此 render 時就能從檔案一次把相關的資料全讀完，省下很多計算(不用考慮資料是不是太遠不用畫；在 low zoom level 的資料也已預先篩選、化簡，也不會資料量太大)。(spec)

不過 tile 裡資料要怎麼呈現、文字的擺放位置，是 render 時才根據 render theme 決定。也就是說，mapsforge 的 data model 是延續 OSM 的設計，mapsforge 並沒有區分什麼是路、房子、河流，它只知道點、線的座標還有 tag，地圖上的顏色、線條樣式都是 theme 裡頭寫的。

不少人會自己製作 map 或 theme 跟人分享，像是
map 檔跟 theme 檔是分開的，但兩者的內容要配對。有的人會兩個一起 share，但也常見使用現有的 map 檔，再依各人用途或喜好修改 theme 檔分享。譬如 tiramisu theme(介紹) 好像受到不少好評。

要測試作出來的 map 跟 theme，除了把檔案傳到 Android 用 map app 看之外，也可以用電腦上的 viewer (譬如 atlas)直接看，會比較有效率。

除了 mapsforge 的 map 格式有分版本(向前相容)，mapsforge library 也有分版本，新的 library 版本除了加功能、修 bug 之外，也會支援新的 render theme feature。只是大部分 app 都沒寫他用的是哪一版的 mapsforge library。依 tiramisu theme 網站的說法，現在只有 oruxmap 6.0 及少數程式用 mapsforge library 0.4 (可以用 svg icon)。2014/12 release 的 0.5 開始支援 render theme V4。

等高線

mapsforge 原先只是設計給 OSM 地圖用，並沒有考慮到等高線。但有人就想到，如果把等高線的座標寫成 OSM 資料格式，「偽裝成一般的 OSM way」，就可以用原有的地圖製作工具作成 map 檔，再修改現有的 theme 加上等高線的定義(可能像是「細黑線，某些高度用粗黑線」)，就可以有等高線地圖了。

至於等高線資料哪裡來？美國 NASA 及各國研究單位合作有免費提供全球的高程模型(Digital Elevation Data) 。DEM 的資料內容很單純，就是把全球切成譬如 90m*90m 的方格，每個方格有一個高度數值。等高線便可以透過程式計算出來。

DEM 資料集

製作 mapsforge 地圖

用到的資料及工具
  • OSM 網站可下載每週最新的 data，但全球的資料一個檔 26G。geofabrik 有提供每天最新的台灣 OSM data extract。
  • osmosis 是 OSM data 的資料處理、轉換工具，支援很多格式，還能寫 plugin。
  • mapsforge 有提供 osmosis plugin MapWriter，可以在 osmosis 讀入 OSM data 之後，輸出成 mapsforge map 檔。
  • phyghtmap 可以把 DEM 資料轉為 OSM 格式等高線。還內建下載  SRTM 跟 viewfinderpanoramas DEM 的功能。
  • 如果手邊的地形資料不是 phyghtmap 能處理的格式，可能可以用 gdal_contour 轉換。gdal 是處理 GIS 資料常用的 library/tool。
詳細的步驟有教學。

若單純只有台灣 OSM data 的話，大概兩三分鐘就跑完了。若是含等高線(每 10m 一條線)，全台灣一個檔(ram mode)大約要 8GB ram 執行 24 小時(估)。另有 hd mode，可以用少一點 ram，我沒試過。

若覺得全台灣的資料量太大，可以先用 osmosis 切成更小的區域。

台灣的地圖

前面提到的 OpenAndroMaps (OAM) 就可以下載台灣的地圖了。

geocaching.com.tw 的 Jing (也就是足跡遍布全台的圖客 JingGeocacher) 結合 ASTER GDEM 及 OSM data 自製 mapsforge 地圖。通常每個月會更新一次。手機 GPS 登山推廣計畫也有寫文章教學如何安裝、設定。

OAM 跟 Jing 的地圖的差異:

  • OAM 的等高線距 20m, Jing 的比較精細到 10m。
  • Jing 的地圖比較大(46mb vs 159mb)
  • Jing 有另外調過 theme，我沒跟其他 theme 比較過。
  • OAM 的歐洲以外的地圖更新頻率好像超過一個月


張貼者： 於 沒有留言 :
標籤：
訂閱： 文章 ( Atom )