主管：「把你前面的座位給整理一下，不要堆那麼多東西，看起來就像是垃圾堆一樣！」
Kradark：「桌面是L1 cache，抽屜是L2 cache，書櫃是主記憶體，我是在實作記憶體階層管理，表面上看起來是亂的，實際上卻大大的提升Access的效能啊！」
主管：「好吧，那我現在呼叫你這個API，進行garbage collection。」
Kradark：「......！」
2011/9/30
資訊學院的30堂課-密碼學
crypto1是悠遊卡所使用的加密演算法則，居然在維基百科就有連結，而且開宗明義說，幾乎是沒有保護狀態。原來讀取我們的悠遊卡，跟讀取我們數位相機拍出來的照片一樣，幾乎是完全沒有保護狀態("the security of this cipher is ... close to zero")。到底crypto1演算法哪裡錯了？或者我們教的密碼學哪裡錯了？
資訊學院的30堂課-資料結構 Data Structure
Data Structure說是資訊學院的精華所在，如果有人反對，應該不是唸CS的吧。長官又指定一個其他組員搞不定的工作過來了，任務是因應組織調整，變動人事資料表，但是資料來源是LDAP，沒有開發大量讀取的權限，最棘手的是，資料來源不是常見的關聯式資料，如Oracle或Informix，不單單是搞定ODBC Driver就ok了，那該怎麼辦呢?
--
Data Structure說是資訊學院的精華所在，如果有人反對，應該不是唸Computer Science的吧。鏈結串列、Binary Tree、B-Tree、in-order、pre-order、post-order、recursive，等等不但是程式設計的延伸，還必須承接後續高年級課程，如人工智慧要用到決策樹，不但是計算機概論常出考古題的所在，在考研究所或國家考試時，也常是必選科目。
長官指定一個其他組員搞不定的工作過來了，任務是因應組織調整，變動人事資料表，但是資料來源是LDAP，沒有開放大量讀取的權限，一次只能抓一筆，最棘手的是，資料來源不是常見的關聯式資料，如Oracle或Informix，不單單是搞定ODBC Driver就ok了，那該怎麼辦呢?
我先到書局罰站了一下，帶回了一本Visual C++的書，然後我引入ladp的dll，連上ldap主機，先抓取一筆人員資料看一下，我所要的姓名、組織代碼，年齡，電話甚至學歷都有，另外再抓取一筆單位資料，發現了裏頭有上層組織的代碼，這不就是樹狀結構，這時候，求學時代所學的Data Structure就派上用場，要dump出來有兩個做法，一個是先深(DFS)，一個是先淺(BFS)，我比較懶惰，不想去寫queue或是找STL，我就利用遞迴呼叫就是一種堆疊的觀念，實作先深尋訪，抓出了六個分公司當root，呼叫完遞迴後，就成功的完成了這個專案，再排入這個AP後，後來的組織整併，就與我們沒有關係了，因為都自動處理好了。
昨天在PTT的Soft_Job板上爬文，看到有人抱怨，上104找來的面試的人，DFS與BFS都搞不清楚，還好至少我還記得修課時教什麼，因為期中考考過BFS。
--
Data Structure說是資訊學院的精華所在，如果有人反對，應該不是唸Computer Science的吧。鏈結串列、Binary Tree、B-Tree、in-order、pre-order、post-order、recursive，等等不但是程式設計的延伸，還必須承接後續高年級課程，如人工智慧要用到決策樹，不但是計算機概論常出考古題的所在，在考研究所或國家考試時，也常是必選科目。
長官指定一個其他組員搞不定的工作過來了，任務是因應組織調整，變動人事資料表，但是資料來源是LDAP，沒有開放大量讀取的權限，一次只能抓一筆，最棘手的是，資料來源不是常見的關聯式資料，如Oracle或Informix，不單單是搞定ODBC Driver就ok了，那該怎麼辦呢?
我先到書局罰站了一下，帶回了一本Visual C++的書，然後我引入ladp的dll，連上ldap主機，先抓取一筆人員資料看一下，我所要的姓名、組織代碼，年齡，電話甚至學歷都有，另外再抓取一筆單位資料，發現了裏頭有上層組織的代碼，這不就是樹狀結構，這時候，求學時代所學的Data Structure就派上用場，要dump出來有兩個做法，一個是先深(DFS)，一個是先淺(BFS)，我比較懶惰，不想去寫queue或是找STL，我就利用遞迴呼叫就是一種堆疊的觀念，實作先深尋訪，抓出了六個分公司當root，呼叫完遞迴後，就成功的完成了這個專案，再排入這個AP後，後來的組織整併，就與我們沒有關係了，因為都自動處理好了。
昨天在PTT的Soft_Job板上爬文，看到有人抱怨，上104找來的面試的人，DFS與BFS都搞不清楚，還好至少我還記得修課時教什麼，因為期中考考過BFS。
資訊學院的30堂課-資料庫管理 DataBase
之前開發一套車輛管理系統，車籍資料超過80個欄位了，資深的長官指示車籍資料分成會異動的一個表格，不會變動的另外一個表格，當時剛到公司的被稱為小朋友，長官說甚麼，就只好幹甚麼，這卻是災難的開始。
資料庫管理系統，課程主要精神就是在教EDR與正規化，正規化很重要，一個系統的效能在於適當地切割資料表，沒有正規化的資料庫，很容易發生資料不匹配的問題，而導致於coding時事倍工半。修課當時，也只是照著課本做，其實對於如何合適地使用SQL語法，是上班之後的事了，不過我覺得對於語法效能最有幫助的課反而是Data Structure，order by就不用說了，排序最少是O(N*logN)當我下了一個group by或者union，腦袋瓜要馬上閃過，這樣子在實際上執行時，花費的時間複雜度是否可以接受。另外，偶而會幫忙同事turning語法，新手最容易犯的錯誤，就是查詢網頁時，資料看不到，原因就在於inner join與left join的不同。
再來是索引的運作，大部分的所以都是使用B-Tree結構來節省查詢的時間，樹狀結構可以把線性搜詢所需要的O(n)時間，reduce到O(logN)，如果資料結構B-Tree的那個章節有認真學的話，使用B-Tree的好壞處很快就可以理解，自然也知道最適合加入索引的時間。
之前開發一套車輛管理系統，車籍資料超過80個欄位了，資深的長官指示車籍資料分成會異動的一個表格，不會變動的另外一個表格，當時剛出社會時，被年長20歲的前輩，稱為小朋友，長官說甚麼，就只好幹甚麼，這卻是災難的開始。這樣設計的下場是甚麼呢，就是超級慢的查詢速度，車籍資料有4000筆，兩個表格進行join後，產生4000*4000這麼大的笛卡耳積，先不論資料庫系統進行的什麼優化，或者有設定索引，光就時間複雜度的觀點，就慢了4000倍，這80欄的車籍資料，在大部分的頁面，都需要讀取兩個表格，後來跟我同組的同事討論後，決定合併這兩個表格，結果速度就馬上有明顯的提升，因為長官這一個決策錯誤，全部的code翻起來review一次。
不知道CS哪一門課，教把會變動的資料與不會變動的資料，分開來存放的，是！有的，剛好我們大學開了一門很冷門的課課，叫做檔案結構，不是資料結構喔，這樣存放的確可以減少讀取到記憶體的資料量，但是我們系統的最終儲存目的地是資料庫，而不是自己維護的檔案，所以長官應該是沒有修過資料庫管理系統，甚至於資料結構，經後來他的談話之後，還真的耶，他的開發經驗就是C語言加檔案結構，後來他就沒有再插手系統設計的部分了，只安排了我們做什麼工作，什麼時候交出來而已。
資料庫管理系統，課程主要精神就是在教EDR與正規化，正規化很重要，一個系統的效能在於適當地切割資料表，沒有正規化的資料庫，很容易發生資料不匹配的問題，而導致於coding時事倍工半。修課當時，也只是照著課本做，其實對於如何合適地使用SQL語法，是上班之後的事了，不過我覺得對於語法效能最有幫助的課反而是Data Structure，order by就不用說了，排序最少是O(N*logN)當我下了一個group by或者union，腦袋瓜要馬上閃過，這樣子在實際上執行時，花費的時間複雜度是否可以接受。另外，偶而會幫忙同事turning語法，新手最容易犯的錯誤，就是查詢網頁時，資料看不到，原因就在於inner join與left join的不同。
再來是索引的運作，大部分的所以都是使用B-Tree結構來節省查詢的時間，樹狀結構可以把線性搜詢所需要的O(n)時間，reduce到O(logN)，如果資料結構B-Tree的那個章節有認真學的話，使用B-Tree的好壞處很快就可以理解，自然也知道最適合加入索引的時間。
之前開發一套車輛管理系統，車籍資料超過80個欄位了，資深的長官指示車籍資料分成會異動的一個表格，不會變動的另外一個表格，當時剛出社會時，被年長20歲的前輩，稱為小朋友，長官說甚麼，就只好幹甚麼，這卻是災難的開始。這樣設計的下場是甚麼呢，就是超級慢的查詢速度，車籍資料有4000筆，兩個表格進行join後，產生4000*4000這麼大的笛卡耳積，先不論資料庫系統進行的什麼優化，或者有設定索引，光就時間複雜度的觀點，就慢了4000倍，這80欄的車籍資料，在大部分的頁面，都需要讀取兩個表格，後來跟我同組的同事討論後，決定合併這兩個表格，結果速度就馬上有明顯的提升，因為長官這一個決策錯誤，全部的code翻起來review一次。
不知道CS哪一門課，教把會變動的資料與不會變動的資料，分開來存放的，是！有的，剛好我們大學開了一門很冷門的課課，叫做檔案結構，不是資料結構喔，這樣存放的確可以減少讀取到記憶體的資料量，但是我們系統的最終儲存目的地是資料庫，而不是自己維護的檔案，所以長官應該是沒有修過資料庫管理系統，甚至於資料結構，經後來他的談話之後，還真的耶，他的開發經驗就是C語言加檔案結構，後來他就沒有再插手系統設計的部分了，只安排了我們做什麼工作，什麼時候交出來而已。
crapto1.c
/* crapto1.c
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, US$
Copyright (C) 2008-2008 bla <blapost@gmail.com>
*/
#include "crapto1.h"
#include <stdlib.h>
#if !defined LOWMEM && defined __GNUC__
static uint8_t filterlut[1 << 20];
static void __attribute__((constructor)) fill_lut()
{
uint32_t i;
for(i = 0; i < 1 << 20; ++i)
filterlut[i] = filter(i);
}
#define filter(x) (filterlut[(x) & 0xfffff])
訂閱：
文章 (Atom)