筆記677號

2012年11月2日星期五

Trace code in Linux - cscope

嘛，總之有了追code的需求
自然得去找出一些工具

看看這cscope+vim的組合在linux下好像還滿主流的
就try try 看囉

官網
http://cscope.sourceforge.net/

在ubuntu12.04下
安裝
sudo apt-get install cscope

使用上第一步是要創立"cscope的資料庫"
大概分成兩種case
1.簡單的情況
在project的跟目錄下直接下 cscope -R 就直接將所有的檔案建立資料
2.但是，有些時候我們並不需要所有的file
這時候就要先建立一個list，讓cscope只對裡面的檔案建立資料
如果我們只要目錄中的java檔時，就使用 find . -name '*.java' > cscope.files
再 cscope -b -q -k 就可以建立資料
在複雜的project中可以藉由更複雜則filter來減少我們的目標(如linux kernel)

接著就可以使用 cscope -d 進入cscope的世界(?)了
想要找什麼definition、function...的就隨心所欲了
啊然後上下畫面的些換是用tab
一開始傻傻地把鍵盤上的按鍵都摸了一遍orz

不過這樣其實還是麻煩
因為看完後想到要找什麼得跳出來再找
這點就要靠vim了
再ubuntu12.04裡的vim預設就有支援cscope
可以直接在vim底下輸入 :cs XXXXX 就可以使用cscope了
不知道指令的話只輸入 :cs 就說明得很清楚了

但是這樣其實還是很麻煩
查什麼都要打一大堆字
這時我們就需要vim的cscope plugin
直接從官網上抓下來用就OK了
在 ~/.vim/plugin 下輸入 wget http://cscope.sourceforge.net/cscope_maps.vim
(plugin的路徑和vim但設置有關)
那就支援一票(?)快捷鍵了

http://rickey-nctu.blogspot.tw/2009/02/vim-srcexpl.html
Ctrl+\ s "s表Symbol，列出所有參考到游標所在字串的地方，包含定義和呼叫。
ctrl+\ g "g表Global，與ctags的Ctrl+]相同。
ctrl+\ c "c表Call，列出所有以游標所在字串當函數名的地方。
ctrl+\ t "t表Text，列出專案中所有出現游標所在字串的地方。
ctrl+\ f "f表File，以游標所在字串當檔名，開啟之。
ctrl+\ i "i表Include，以游標所在字串當檔名，列出所有include此檔的檔案。
ctrl+\ d "d表calleD，以游標所在字串當函式名，列出所有此函式呼叫的函式。

安裝了plugin後可能會有一些錯誤訊息或是快捷鍵不work的狀況(都遇到了囧)
就需要透過修改一些設定來解決
http://linux.chinaunix.net/techdoc/desktop/2009/03/29/1106223.shtml

大概是這樣
工具裝好了就上工吧~

2012年8月8日星期三

[ACM] 193 : Graph Coloring

難得解個題
做個筆記

給定一張圖
點可以塗黑或塗白，黑色不相鄰
求最多可以塗多少黑點

一開始自以為greedy的直覺
"既然要塗最多黑色，那就把連結數最少的點塗黑吧，然後一路塗完..."
都說是自以為了，理所當然是錯的
google "ACM 193" 前幾個連結就有在討論這個，也有人提出了反例

所以只好乖乖暴力法了
暴力法的想法
"一個點非黑即白所以只要把一個點塗黑繼續塗完整張圖，
或者塗白繼續塗完整張圖"
就可以找到所有結果

擺明可以遞迴，所以就遞迴求解

遞回函式的想法大概是
1. 選定還沒塗色的點，塗黑，並把相鄰點塗白剩下的點遞迴求解
2. 把剛剛這個點塗白，遞迴求解
3. 整張圖都塗色了，判斷是否為最大值

code :

#include 
int n,k;
int graph[101][101];
int max;
int maxList[101];
int color[101];

void draw(){
 int finish = 1;
 int current[101];

 for(int i = 1; i <= n; ++i){
  current[i] = color[i];
 }
 for(int i = 1; i <= n; ++i){
  if(color[i] == 0){
   finish = 0;
   
   color[i] = 2; 
   for(int j = 1; j <= n; ++j){
    if(graph[i][j] == 1 && color[j] == 0){
     color[j] = 1;
     
    }
   }
   draw();
   color[i] = 1;
   for(int j = 1; j <= n; ++j){
    color[j] = current[j];
   }
   color[i] = 1;
   
  }
 }
 
 if(finish == 1){
  int count = 0;
  for(int i = 1; i <= n; ++i){
   if(color[i] == 2){
    ++count;
   }
  }
 
  if(count > max){
   max = count;
   count = 0;
   for(int i = 1; i <= n; ++i){
    if(color[i] == 2)
     maxList[count ++] = i;
   }
  }
 }
}

int main(){
    int c;

    scanf("%d", &c);

    for(int i = 0; i < c; ++i){
   
  max = 0;
  for(int x = 1 ; x < 101; ++x){
   maxList[x] = 0;
   color[x] = 0;
   for(int y = 1 ; y < 101; ++y)
    graph[x][y] = 0;
  }

        scanf("%d%d", &n, &k);

        for(int j = 0; j < k; ++j){
            int to , from;
            scanf("%d%d", &to, &from);

            graph[to][from] = 1;
            graph[from][to] = 1;
        }
  draw();
  
  printf("%d\n", max);
  printf("%d", maxList[0]);
  for(int i = 1; i < max; ++i)
   printf(" %d", maxList[i]);
  printf("\n");
 }
}

2012年3月13日星期二

[Java] String兩三事

String是個非常常用的一個class
不過有些細節今天上課才知道0.0

String物件在被建立之後就是不可變的
重新assign值給他其實就是砍掉重練
append字串這個動作亦同
基本上就是會先產生一個StringBuffer來進行append再轉回String

因為這個緣故，當在一個迴圈中連續的append字串的話
直接使用最直覺的"str1 += str2;" 就會造成很嚴重的系統負擔
因為每一次動作都要先新建立一個StringBuffer然後收回
剛剛實測了一下執行時間大概差到了100倍

所以比較好的寫法應該是要先建立一個StringBuffer
進行完多次append後再將其存回String

另外有關substring的實作
再進行這個動作後，這個新的字串並沒有複製出來
而是指向原本String的位置

這種設計的立意應該是為了節省資源使用
不過在某些狀況反而會造成更大的系統負擔
像是要連續多次從不同的大字串中提取小字串
在這個狀況下，因為有被指向，所以大字串的記憶體空間不回被釋放
可能就會造成記憶體不足

要解決這種狀況就是要記得new出一個新的字串
String smallStr = new String(largeStr.substring(2, 5));

良葛格這篇其實就很清楚了@@
http://caterpillar.onlyfun.net/Gossip/JavaGossip-V1/ImmutableString.htm

2012年2月10日星期五

[javascript] 使用javascript達成檔案上傳

網頁中檔案上傳最簡單的方法就是直接用表單POST
然後在處理的那個頁面用$_FILES來處理
不過人生總有幾回要用些不同的方法
既然遇到了就把他記下來吧

基本原理就是用FileReader讀入使用者上傳的檔案
然後再利用XMLHttpRequest將他post給後台


Upload File:

這樣就會將收到的檔案以binary post給指定的程式
而後台的做法就是將收到的資料寫入檔案中
我是以一個php做處理

對他來說這是一個post raw data
可以直接把讀為一個字串再寫入檔案
而raw data 和php://input這招其實還是不太懂，有空再來研究

2011年11月20日星期日

[mySQL][php] 中文(utf8)亂碼

每次寫php+mysql的程式時都會被中文資料搞一陣子
記起來方便以後想找030

從資料庫讀出要加入

    mysql_query("SET NAMES 'utf8'");

強制所有與mysql的交流都是utf8編碼

理論上就能搞定所有狀況

但是寫入也要記得先轉成utf8
用iconv函式

    $utf8name = iconv("big5","UTF-8",$name);

2011年10月18日星期二

[隨手] google places api

簡介

Google places API為google map api之一環，結合地點及商家資訊，以提供使用者指定地點附近之資訊。

申請

由google api console取得key： https://code.google.com/apis/console/

這裡需要有一個google帳號。第一次使用要先申請(填個資料、接受服務條款)。

啟動

登入google api consle後，要先創建一個新project，然後再去enable各項服務。從service找到Places API：

點on/off的圖案就可以去啟動或停止服務。

而在API Access的部分就會看到你的API key：

使用

places api目前提供五種功能，一是查詢指定地點附近之資訊(places serach)、二是根據一所查詢的結果取得更詳細資料(places detail)、三是自動完成(places auto compelete)。另外還有check-in和reports功能。

詳細可以直接至http://code.google.com/intl/en/apis/maps/documentation/places/

看完整使用說明，這邊只說明如何使用places search。(這部分中文文件沒更新，有錯誤)

基本上，這一組API的使用就是一個URL request， places search的樣式： https://maps.googleapis.com/maps/api/place/search/output?parameters

Output可以選擇以json或xml之格式回傳，parameter的部分主要為：

location：一組座標

radius：一個距離，就是方圓幾公尺的範圍

sensor：是否是從GPS裝置發出的requset

key：你的金鑰

另外，還可以放入其他參數，我認為比較重要的就是：

types：選取所要的地標類型

有提供的詳細類型可以至http://code.google.com/intl/zh-TW/apis/maps/documentation/places/supported_types.html

查看。

如：https://maps.googleapis.com/maps/api/place/search/json?location=24.790864,121.004105&radius=500&types=food&sensor=false&key=XXXXXXXXXXXXXXXXX

就會以json的形式回傳交大方圓500公尺內所有關食物的地點(當然key要換上你自己的w)

而回傳的詳細格式可以自行去doc查閱。

---
只是把剛剛交出去的小報告拿來湊版面不然都沒寫w

2012年11月2日 星期五