學校課程/計算型智慧

論文選讀 Building optimal regression tree by ant colony system ...

前文

課程 計算型智慧 報告，這是一門碩班課程，因此聽了許多學長的報告，雖然有難有易，牽扯的領域相當繁雜且艱深，例如影像分析、電機、醫學領域 … 等，很多都是有聽沒有懂，但是多少能明白一些些道理，即使後來挑選幾個進行實作，發現自己根本沒有理解，或者只是單純實作能力不足。

其中最常見到的報告內容是 B*-tree with floor plan，對於電子電路的配置擺放，要求最小化面積的操作。當然其中也有幾個跟我報告的預測性有關。對於影響分析就不多述了，其中也有幾個電費電流調控也挺有意思的，總之報告內容相當多元。

報告的時候，教授就在台下緊盯，而我剛好是在教授開會的時候報告，這學期僅我一個在教授不在的情況下報告。

  • One Exam: 30%
    只有一次期中考，而且還是人腦仿電腦考試，但是題目沒有講清楚，考炸了不少，題目理解上把常數搞錯意思，但是這不影響廣義型算法，希望助教給點分！例如：在基因算法中交配的兩兩交配，難道就不能與自己交配嗎？而在粒子算法中，只給兩個參數，難道就不能只模仿全局最佳點和自己嗎？如果只有兩個參數，而且加總為一，您叫我如何模仿鄰居和自己，看來只能二選一。
  • Homework: 40% (3 programs)
  • Presentation: 30%
    教授不在的情況下仍可以報告，所以成績是由助教評定嗎？
  • Questions: 3
    本課程一定要問三個問題，否則視如無效修課，但是問題我總是在課堂中發問，對於學長報告的內容有點作噁不明白。

論文挑選為「Building optimal regression tree by ant colony system – genetic algorithm Application to modeling of melting points」這是一篇化學期刊上的運用，不是在計算機領域的論文。

開始

從一個最簡單的應用開始

在二十個問題內，能猜出心中想的目標角色。這一類的遊戲相當多，在很多遊戲或者是心理測驗中都會用到，用來預測你大概會是哪一種類型的人、或者正在想什麼。
http://en.akinator.com/

決策樹

決策樹的分類

  • Classification Tree：分類樹
    分類，輸出 “類型”
  • Regression Tree：回歸樹
    關係程度，輸出 “數值”
  • CART (Classification And Regression Tree) 即上述兩個的總稱

關於 CART

  • 大量數據可以快速算出結果
  • 易於理解 和 解釋
  • 可以用統計數據驗證模型
  • 最優 CART 是 NP 問題。
  • 能力有限，只能對有限數據屬性操作
  • 機器學習 Machine Learning 領域常用

論文實驗資料

  • 4173 種化合物，分類屬性有 202 種描述方式。在 4173 種化合物中，3000 種用來訓練，1173 種用來驗證。
  • 與另外一組經由 277 種藥物進行熔點預測的 CART 相比。(另外一篇論文做的結果)
  • 目標預測更加準確。

CART–ACS–GA 理論

  • 將 ACS – GA 算法，套用在 CART 的建造上。
  • 先說說 ACS – GA 算法運作

ACS-GA

ACS–GA 算法 (蟻群遺傳混合算法)，基於 ACS 的缺點 – 收斂慢，加入 GA 算法來加快。

  • 為什麼不單純使用 GA 算法就好？
  • 對問題編碼的困難 (轉 DNA 的問題)，突變效果可能不好

螞蟻基因也有好壞問題

  • 如何反應基因好壞
  • 對費洛蒙決策的方式
  • 對費洛蒙的敏感度 … 等

換句話說，將螞蟻的能力也各自數據化，對於產生較好解的螞蟻，繁殖、交配、突變，接著談論如何運用在 CART！

CART 建造

假解亂做前，如何隨機？CART 是一棵二分樹
How we do ?

  • 基於深度優先的方式，直到某個葉節點的分類種數 < 30 或深度大於某個值，就退回。
  • 每一層必須決定 “依據哪個屬性分類” Age ? Gender ? Last R ?
  • 分類時，又要按照什麼 數值 進行分割。< 30 ? > 30 ? = 30 ?

假設 CART 有 m 個節點，n 個分類描述。在此篇中，化合物有 202 種描述，即 n = 202。

  • 為了表示螞蟻的判斷能力，到達某個節點 i 時，採用下一個分類方式 k 的費洛蒙 M[i][k]
    i < m, k < n
  • 這樣可以決定分類方式。對於某個節點 i，i 可以是目前累計完成的節點個數，或者是其他。

上面決定了分類方式，但沒決定分割點 ( cut point ) 的選擇方式。

  • 假設用 10 種決策方式，來對應分類到節點內有的所有項目屬性，進行統計分類。
    • 決策方式 1：平均、眾數、權重、 ID3、C4.5 (熵理論和訊息增益) … 等分割策略
    • 決策方式 2 : 用 10 個常數對於屬性最大最小值 f(min, max) = x0 * min + x1 * max + x2 * min * max
    • 決策方式 3：最大最小值之間切 10 等分。
  • 費洛蒙將會有 10 × n × m，即 M[10][n][m]。

關於適應函數

對於葉節點

Partial least squares method 不同於 “最小平方法”

  • 多因變數 對 多自變數 的回歸建模方法
  • 對於每一個葉節點的所有資料分別做偏最小二乘法，會得到分類的相聯性，也就是 相關係數 (correlation coefficient)
  • 相關係數總和大小 與 適應力高低 成正比，用 驗證集 找到相關係數。

結論

  • 對於下次迭代，偏向於好的切割屬性
  • 對於切割屬性，可以得到好的分割點
  • 排除單一分割策略的形式
Read More +
學校課程/作業系統

向 NachOS 4.0 作業進發 (2)

接續

接續上一篇的 向 NachOS 4.0 作業進發 (1)，我們繼續完成排程處理，在原始的 NachOS 4.0 中，基礎排程是 Round-robin，它的運作方式藉由定時呼叫 threads/alarm.h 中的 Alarm::CallBack()，而呼叫的時脈來源設定為 machine/stats.h 中的 const int TimerTicks = 100; 決定，數值越小表示呼叫頻率越高，置換的次數就會上升。

目標 Scheduler

  • FIFO (FCFS) 先來先服務
  • SJF 最短工作優先
  • Priority 最小優先權優先
  • RR (Round-robin)
  • multi-level queue 最後的大魔王

開始

第一步 - 測試

先來說說怎麼測試自己的寫的代碼正確性，不然怎麼寫都只是理論腦補，雖然會動，但是不知道是否寫對。

  • 第一種方式為下達 

    $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個

    這樣必須自己設置優先權、Burst Time，這方面撰寫方式有兩種，其一是來亂，其二是較為正式，而在 Burst Time 的計算又分成兩種，一是執行前已知、二是執行時猜測。

    • 其一來亂寫法，

      $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個

      不改變原本的的執行方式，直接在代碼中決策 thread fork 出來時所擁有的優先權和 Burst Time。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      static int testPriority = 0;
      void 
      Thread::Fork(VoidFunctionPtr func, void *arg)
      {
      // morris add
          testPriority++;
          if(testPriority == 1)
              setPriority(64);
          else if(testPriority == 2)
              setPriority(128);
          else
              setPriority(64);
      // end morris add

      因此，您可能會寫出以上的代碼，當然我不建議這麼寫，雖然是一種測試方式，但這並不好，一開始就這麼錯得相當離譜。

    • 其二寫法，增加下達參數，不過這些參數格式要去查閱一下他們的參數傳遞建造，我想會寫成大概的樣子為

      $ ./nachos -e ../test/test1 -pw 64 -e ../test/test2  -pw 128 ...

      多個為了不增加工作量，這裡就沒有親自去實作。某方面來說，可能要寫很多 small program 進行測試，並且撰寫時還要預測會跑多久，這難度會稍微提高。

  • 第二種方式按照軟工的寫法
    來寫 test code 吧！如果細心一點，就會看到相關的 Class::SelfTest() 在很多 class 都有的，因此我們需要把 test code 寫到 SelfTest 中被呼叫。因此，不需要有實體的 process 運行，只是單純地測試我們寫的 scheduler 的排程順序是否正確。

    threads/thread.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void
    threadBody() {
        Thread *thread = kernel->currentThread;
        while (thread->getBurstTime() > 0) {
            thread->setBurstTime(thread->getBurstTime() - 1);
            kernel->interrupt->OneTick();
            printf("%s: remaining %d\n", kernel->currentThread->getName(), kernel->currentThread->getBurstTime());
        }
    }
    void
    Thread::SchedulingTest()
    {
        const int thread_num = 4;
        char *name[thread_num] = {"A", "B", "C", "D"};
        int thread_priority[thread_num] = {5, 1, 3, 2};
        int thread_burst[thread_num] = {3, 9, 7, 3};
        
        Thread *t;
        for (int i = 0; i < thread_num; i ++) {
            t = new Thread(name[i]);
            t->setPriority(thread_priority[i]);
            t->setBurstTime(thread_burst[i]);
            t->Fork((VoidFunctionPtr) threadBody, (void *)NULL);
        }
        kernel->currentThread->Yield();
    }

    請自行在 class Thread 增加 setPriority(), setBurstTime(), SchedulingTest() … 等 method header and body。
    threads/thread.h
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Thread {
      private:
       ...
      public:
       ...
        // morris add
        void setBurstTime(int t)	{burstTime = t;}
        int getBurstTime()		{return burstTime;}
        void setStartTime(int t)	{startTime = t;}
        int getStartTime()		{return startTime;}
        void setPriority(int t)	{execPriority = t;}
        int getPriority()		{return execPriority;}
        static void SchedulingTest();
      private:
        // some of the private data for this class is listed above
        // morris add
        int burstTime;	// predicted burst time
        int startTime;	// the start time of the thread
        int execPriority;	// the execute priority of the thread
        ...
    };

    接著是需要 call testcode 加入到 ThreadedKernel 中。
    threads/kernel.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void
    ThreadedKernel::SelfTest() {
       Semaphore *semaphore;
       SynchList<int> *synchList;
       
       LibSelfTest();		// test library routines
       
       currentThread->SelfTest();	// test thread switching
       Thread::SchedulingTest();   
       				// test semaphore operation
       semaphore = new Semaphore("test", 0);
        ...
    }

    因此我們可以利用單一 module 就能進行檢查。

    $ cd code/threads
$ ./nachos

    但是這種方式，並沒有決定我們要測試哪一種類型的 scheduler，額外需要設定參數，讓其選擇建造哪一種的 readyList(Thread*)

    $ cd code/threads
$ ./nachos FCFS
$ ./nachos SJF
$ ./nachos Priority
$ ./nachos RR

    預計要修成如上述的測試方式。

    threads/main.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int
    main(int argc, char **argv)
    {
        ...
        debug = new Debug(debugArg);
        
        DEBUG(dbgThread, "Entering main");
    //
        SchedulerType type = RR;
        if(strcmp(argv[1], "FCFS") == 0) {
        type = FIFO;
        } else if (strcmp(argv[1], "SJF") == 0) {
        type = SJF;
        } else if (strcmp(argv[1], "PRIORITY") == 0) {
        type = Priority;
        } else if (strcmp(argv[1], "RR") == 0) {
        type = RR;
        }
    //
        kernel = new KernelType(argc, argv);
        kernel->Initialize(type);
        
        CallOnUserAbort(Cleanup);		// if user hits ctl-C
        kernel->SelfTest();
        kernel->Run();
        
        return 0;
    }

第一步測試撰寫就這麼結束，比起撰寫新的 code，不會進行測試也是徒勞。

雖然這麼說，實際運作也是先寫 code 再寫 test code，因為當時還不太懂這些，所以如果已經先寫了一些也不用難過，大家都是這麼走過來的。

如果不知道怎麼執行，哪還有什麼撰寫的欲望，如果不知道怎麼測試，那就是在黑暗中漫步。

第二步 - 撰寫

在撰寫開始前，如果使用走第一種測試方式的人，需要將實體記憶體用大一點，否則需要實作虛擬記憶體的 context-swith。

machine/machine.h
1
2
3
const unsigned int NumPhysPages = 64;  // morris modify, old value=32
const int MemorySize = (NumPhysPages * PageSize);
const int TLBSize = 4;			// if there is a TLB, make it small

若完成以上的修改，在 /userprog 下，執行

1
$ ./nachos -e ../test/test1 -e ../test/test2 -e ../test/test1

就不會跑出 segment fault 。

threads/scheduler.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
enum SchedulerType {
        RR,     // Round Robin
        SJF,
        Priority,
        FIFO
};
...
class Scheduler {
  public:
    Scheduler();
    Scheduler(SchedulerType type);		// Initialize list of ready threads 
    ...
    	// morris add
    SchedulerType getSchedulerType() {return schedulerType;}
    void setSchedulerType(SchedulerType t) {schedulerType = t;}
  private:
    ...
};

如果有機會查閱其他代碼，很常見會把 List<Thread *> *readyList; 改成 SortedList<Thread *> *readyList; 但是其實不用的，可以利用多形來完成，畢竟 SortedList 繼承 List。因此是不需要更動的。

接著，我們使用多形，在建構子中決定要用哪一種類型的排程，並且宣告相對應的 compare function，參照如下。

threads/scheduler.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int SJFCompare(Thread *a, Thread *b) {
    if(a->getBurstTime() == b->getBurstTime())
        return 0;
    return a->getBurstTime() > b->getBurstTime() ? 1 : -1;
}
int PriorityCompare(Thread *a, Thread *b) {
    if(a->getPriority() == b->getPriority())
        return 0;
    return a->getPriority() > b->getPriority() ? 1 : -1;
}
int FIFOCompare(Thread *a, Thread *b) {
    return 1;
}
//----------------------------------------------------------------------
// Scheduler::Scheduler
// 	Initialize the list of ready but not running threads.
//	Initially, no ready threads.
//----------------------------------------------------------------------
Scheduler::Scheduler() {
    Scheduler(RR);
}
Scheduler::Scheduler(SchedulerType type)
{
    schedulerType = type;
    switch(schedulerType) {
    case RR:
        readyList = new List<Thread *>;
        break;
    case SJF:
        readyList = new SortedList<Thread *>(SJFCompare);
        break;
    case Priority:
        readyList = new SortedList<Thread *>(PriorityCompare);
        break;
    case FIFO:
        readyList = new SortedList<Thread *>(FIFOCompare);
    }
    toBeDestroyed = NULL;
}

上述的寫法是因為沒有辦法宣告 default argument value for class。

如果需要搶先 (Preemptive) 設計，則在 Alarm::CallBack() 決定是否要呼叫 interrupt->YieldOnReturn() 查看是否有更需要優先的 process 要執行。

threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void 
Alarm::CallBack() 
{
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    kernel->currentThread->setPriority(kernel->currentThread->getPriority() - 1);
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
        timer->Disable();	// turn off the timer
    }
    } else {			// there's someone to preempt
    if(kernel->scheduler->getSchedulerType() == RR ||
        kernel->scheduler->getSchedulerType() == Priority ) {
//		interrupt->YieldOnReturn();
        cout << "=== interrupt->YieldOnReturn ===" << endl;
        interrupt->YieldOnReturn();
        }
    }
}

在 Burst Time 計算上，如果採用運行時估計，可以在以下代碼中進行計算。kernel->stats->userTicks 是執行 user program 的時間累加器 (也存有一個 system program 的時間累加器，運行 thread context-free, thread scheduling … 等時間用途。)

threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
void 
Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    // burst time
    int worktime = kernel->stats->userTicks - t->getStartTime();
    t->setBurstTime(t->getBurstTime() + worktime);
    t->setStartTime(kernel->stats->userTicks);
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}

其實到這裡已經完成，接下來就放幾張測試結果。

multi-programming

FCFS(1)
FCFS(2)

RR(1)
RR(2)

SJF(1)
SJF(2)

Priority(1)
Priority(1)

最後

如果在

1
2
$ cd code
$ make

編譯時發生錯誤，想必是兩個地方的 Initialize() 發生錯誤，所以請參照以下代碼進行修改。這問題是發生於我們在 /threads 下修改 main.cc 的關係，所以必須在每一個 kernel 宣告地方都給一個決定 scheduler 類型的參數。

其一,

userprog/userkernel.h
1
2
3
4
5
6
7
8
9
#include "../threads/scheduler.h"
class SynchDisk;
class UserProgKernel : public ThreadedKernel {
  public:
  	...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType type);
    ...

其二,
userprog/userkernel.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
UserProgKernel::Initialize()
{
    Initialize(RR);
}
void
UserProgKernel::Initialize(SchedulerType type)
{
    ThreadedKernel::Initialize(type);	// init multithreading
    machine = new Machine(debugUserProg);
    fileSystem = new FileSystem();
#ifdef FILESYS
    synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}

其三,
network/netkernel.h
1
2
3
4
5
6
7
8
9
10
11
#include "../threads/scheduler.h"
class PostOfficeInput;
class PostOfficeOutput;
class NetKernel : public UserProgKernel {
  public:
    ...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType);
    ...

其四,
network/netkernel.cc
1
2
3
4
5
6
7
8
9
10
11
12
void 
NetKernel::Initialize() {
    Initialize(RR);
}
void
NetKernel::Initialize(SchedulerType type)
{
    UserProgKernel::Initialize(type);	// init other kernel data structs
    postOfficeIn = new PostOfficeInput(10);
    postOfficeOut = new PostOfficeOutput(reliability, 10);
}

致網路資源

感謝網路上前人們所遺留的遺產。雖然在看不懂的文字中摸索，但仍抓到了一點線索。

我一無所有，直到見到了你們。

Read More +
學校課程/作業系統

作業系統 multiprocess & multithread 作業

A 班程式要求

請使用所熟悉的程式開發環境設計單一行程產生子行程 ( Child Process ) 與 多執行緒 ( Multi-Thread) 的程式，意即完成下列傳統 for loop 之列印工作，將其改寫成多行程與多執行緒，由不同的行程與執行緒列印不同 i 值。

1
2
for (int i = 0; i < 10; i++)
    printf("output i = %d\n", i);

注意事項

  • 嚴禁從網路抄襲作業 。每份程式作業將被程式比對軟體檢查，一旦發現抄襲，該份作業以零分計，並且這學期作業系統作業成績以零分計。
  • 後略

這種作業不抄來抄去也難。但是作業格式不清楚，所以也有不同理解方式就是了。

開始動手

對於將 for 迴圈改寫，我們必須認知到幾項

  • 是否要按照順序輸出？
  • 平台 M$, Linux, or Max OS？

此篇假設目標是一模一樣的輸出

multiprocess

child process 屬於 multiprocess 中的一種方式。為什麼這麼說呢？multiprocess 只是要求一個 CPU 中有多個工作同時在進行，藉由排程器去進行工作分配。

先不管這些，要實作 child process 看起來只有走向 fork() 一途。而之前 inker 大神則是走非 child process 使用類似 ./nachos -e ../test/test1 -e ../test/test1 的方式去運行。

為了實作按照順序輸出，我們需要 process 共同擁有的 shared memory，這個 shared memory 將要紀錄原本 for 裡面的 i 值和一個 sem_t，來保證 process 和 process 之間不會同時搶先動作，sem_t 也許是不需要的，這裡留給實驗者去測試。

為了使輸出一致，在 fork() 完之後，使用 wait() 來等待所有子程序結束。這樣會造成當 for loop 需要跑 n 次，就會總共 n 個 process，也就是一整條鏈下去。

  • 思考 wait() 和 sem_t 都不是這麼必要？// 這個要看寫法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <semaphore.h>
#ifndef  MAP_ANONYMOUS
#ifdef  MAP_ANON
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif
static int *glob_var;
static int n = 32;
int main(void)
{
    glob_var = (int *)mmap(NULL, sizeof *glob_var, PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, -1, 0);
    
    sem_t *sema = (sem_t *)mmap(NULL, sizeof(sema),
                       PROT_READ |PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,
                       -1, 0);
    sem_init(sema, 1, 0);
    *glob_var = 0;
    while (*glob_var < n) {
        sem_wait(sema);
        int pid = fork();
        int output = (*glob_var)++;
        if (output < n)
            printf("%d, pid = %d\n", output, pid);
        sem_post(sema);
        int wpid, status = 0;
        while ((wpid = wait(&status)) > 0)
        {
            //printf("Exit status of %d was %d (%s)\n", (int)wpid, status, (status > 0) ? "accept" : "reject");
        }
    }
    munmap(glob_var, sizeof *glob_var);
    return 0;
}

multithread

Thread 就相當簡單，因為它們是共用同一個記憶體區段，因此沒有 share memory 的問題。
雖然使用 sem_wait(&sem) 和 sem_post(&sem) 來保證區域內的代碼不會同時有多個 thread 在運行，但仍遇到 i = 0 同時在多個 Thread 噴出的情況，這一點百思不得其解，為了解決這一切問題，使用課本提到的 Producer–consumer problem 寫法。

希望能從代碼中看懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
#include <pthread.h>
int i = 0, n = 16;
int count = 0;
sem_t sem;
const int MAX_THREAD = 4;
void *Producer(void *arg) {
    for(int i = 0; i < n;) {
        sem_wait(&sem);
        if(count == 1) {
            sem_post(&sem);
            continue;
        }
        count++;
        // printf("\nProducer is :%d\n", count);
        sem_post(&sem);
        i++;
    }
    pthread_exit(NULL);
}
void *runPrint(void *arg) {
    int id = *((int *) arg);
    for (; i < n ;) {
        sem_wait(&sem);
        if (count == 0) {
            sem_post(&sem);
            continue;
        }
        count--;
        i++;
        printf("loop i = %d, thread id %d\n", i, id);
        sem_post(&sem);
    }
    pthread_exit(NULL);
}
int main() {
    pthread_t *threads;
    sem_init(&sem, 0, 0);
    threads = (pthread_t *) malloc(MAX_THREAD * sizeof(pthread_t));
    for (int i = 0; i < MAX_THREAD; i++) {
        int *p = (int *) malloc(sizeof(int));
        *p = i;
        pthread_create(&threads[i], NULL, runPrint, (void *)(p));
    }
    pthread_t producer;
    int *p = (int *) malloc(sizeof(int));
    *p = -1;
    pthread_create(&producer, NULL, Producer, (void *)(p));
    for (i = 0; i < MAX_THREAD; i++) {
        pthread_join(threads[i], NULL);
    }
    sem_destroy(&sem);
    return 0;
}

後記

代碼沒有寫得很完整，也就是能達到輸出相同且用符合需求，這一點是有很多漏洞的，前人也是鑽漏洞交作業的。相較之下，我們 B 班的作業略顯兇殘，但是網路上資料還真是少呢，雖然還是找地方抄和理解。

測試的時候，為了保證輸出是穩定的，記得得多測試幾次，並且把數字範圍作變調，當然能不能讓一個 create thread 跑完整個迴圈呢？畢竟加上 main thread 就算是 multithread？haha

執行

編譯

  • Mac OSX

    $ clang -pthread x.cpp -o x

  • Linux

    $ gcc -lpthread x.cpp -o x

    運行

  • Linux & Max OSX

    $ ./x

Mac 運行問題

1
2
3
4
5
#ifndef  MAP_ANONYMOUS
#ifdef  MAP_ANON
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif

不知道為什麼 clang 中沒有定義 MAP_ANONYMOUS，增加上述代碼後正確運行。

其他作業

B 班程式作業 1
B 班程式作業 2

Read More +
學校課程/通識課程

當代消費文化與社會 (2)

母親節篇

  1. 請簡述母親節與消費文化的關聯性 ?
    母親節與消費文化原本是扯不上邊的，後來商人們藉由這些推銷的活動，給予不知道母親節要怎麼犒勞養育辛勞的兒女們一項消費選擇，因此提供了相關的優惠活動方便消費者，母親節就逐漸跟情人節送禮一樣的氣氛。
  2. 舉例說明母親節有哪些消費現象 ?
    相關女性用品優惠，對於餐飲業而言就是雙人、多人套餐，而觀光景點就是帶著母親出遊享優惠 … 等等。
  3. 您決定購買什麼禮物送媽媽及其理由 ?
    身為一個程序猿，買禮物卻沒有思路，寫卡片卻沒有語言，在這樣的情況下，按照自己最常做的事情下手設計，但最近還有其他程序要趕，大概是趕不上這個母親節專案了。

血色月灣

Youtube

在這場被隱藏的殺戮中，繼上次壽司造成的魚類問題，沒想到日本又在海洋造成了更大的傷害，不管是不是海豚，也許有人會因為海豚可愛而在這一次的血色海灣而保護它，在我們不喜歡的動物上，說不定也有類似的問題。

最令人訝異的是，即使在國際會議中，也有隱瞞事實的大人物在，果然要執行某些事情，不是會議或者是組織所為，而是來自個人的發起。這句話有額外的啟發，為了背後國民的飯碗或支持，這些代表人物不得不說謊的情境，假使一開始錯了，他們便會一直錯下去，這樣的情況令人相當惋惜。

海豚的確很有靈性，在他們受到如此的遭遇，難免會感受到如新世界中，那些因為外表被看成不同種的情況，而受到摧殘的可能，對於靈性的動物，在受到傷害，我們給予同情，在其他情況下則沒有這麼強烈的反應。

消費型科技商品

現在出門一定有 GPS 衛星導航的裝置，才能穿梭於大街小巷，這些裝置給我們相當大的便利，不用攜帶大量的地圖資訊出門，不會迷路、不用煩惱就可以輕鬆出門。

科技所帶來的便利，使得停下來思考的機會少了，也不會看看四周的景色，追求更快速地抵達目的地，目的地以外的機緣就越來越少了。比起問人，問機器更來得有信任感，這也表示著相信別人給的知識也不是那麼重要。根據新聞的研究報導，也許我們正在改變記憶方式，開始不擅長記繁瑣的事物，而開始擅長去哪裡找資料、如何使用資料。

因此，也常發生因衛星導航所造成的交通事故，被引導到錯誤地方或者是進入不合適的地點。這也反應使用者即使發現了不合理之處，最後仍相信訊息給的答案。假使衛星給了錯誤訊息，或者被惡意修改成錯誤訊息，很容易造就嚴重事故，我們已經被訓練得無法自己處理這些資訊。

也許老師會問我「那你認為到底要不要買衛星導航？」這一點還真的是要看需求，身為宅的人們不喜歡出門呢。

Read More +
學校課程/作業系統

向 NachOS 4.0 作業進發 (1)

關於 NachOS 4.0

作為教學用作業系統，需要實現簡單並且儘量縮小與實際作業系統之間的差距，所以我們採用 Nachos 作為作業系統課程的教學實踐平臺。Nachos 是美國加州大學伯克萊分校在作業系統課程中已多次使用的作業系統課程設計平臺，在美國很多大學中得到了應用，它在作業系統教學方面具有一下幾個突出的優點：

  • 採用通用虛擬機器
  • 簡單而易於擴展
  • 物件導向性
  • … 略

簡單地來說，就是一個模擬作業系統的軟體

安裝

課程頁面：http://networklab.csie.ncu.edu.tw/2014_os/osweb.html#download

  • Platform: Linux or Linux over VMware 
    RedHat Linux 9.0
    在 Ubuntu 上面運行無法
  • Install steps
    • Get NachOS-4.0
      wget ../nachos-4.0.tar.gz
    • Get Cross Compiler
      wget ../mips-decstation.linux-xgcc.tgz
    • Move Cross Compiler to /
      mv ./mips-decstation.linux-xgcc.tgz /
    • Untar Cross Compiler
      tar zxvf ./mips-decstation.linux-xgcc.tgz
    • Untar NachOS-4.0
      tar zxvf ./nachos-4.0.tar.gz
    • Make NachOS-4.0
      cd ./nachos-4.0/code
make
    • Test if installation is succeeded
      cd ./userprog
./nachos -e ../test/test1
./nachos -e ../test/test2

預期運行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Total threads number is 1
Thread ../test/test1 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:6
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
                                                                                
Ticks: total 200, idle 66, system 40, user 94
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Total threads number is 1
Thread ../test/test2 is executing.
Print integer:20
Print integer:21
Print integer:22
Print integer:23
Print integer:24
Print integer:25
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
Ticks: total 200, idle 32, system 40, user 128
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

作業階段

Multiprogramming

執行下述指令

1
./nachos –e ../test/test1 –e ../test/test2

test1.c
1
2
3
4
5
6
#include "syscall.h"
main() {
    int n;
    for (n=9;n>5;n--)
        PrintInt(n);
}
test2.c
1
2
3
4
5
6
7
#include "syscall.h"
main() {
    int n;
    for (n=20;n<=25;n++)
        PrintInt(n);
}

在開始動工前，發現在 Multithread 操作會有錯誤，test1 程序會遞減輸出，而 test2 程序會遞增輸出，但是根據運行結果，兩個程式都會遞增輸出。

目標運行結果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Total threads number is 2
Thread ../test/test1 is executing.
Thread ../test/test2 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:20
Print integer:21
Print integer:22
Print integer:23
Print integer:24
Print integer:6
return value:0
Print integer:25
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
 
Ticks: total 300, idle 8, system 70, user 222
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

  • 為什麼兩個程式都會遞增輸出？
    明顯地是兩個程式匯入時，操作到相同區域的 code segment。如果發現各別遞增和遞減，但是輸出 n 的結果錯誤，則可以想到是 context-switch 上發生問題。

解決

需要為 physical address 做標記，這個 physical address 就是在 main memory 裡面的位置。而每一個 process 都會有一個 AddrSpace，然後紀錄 logical address 所對應在 physical address，也就是 pageTable 對應到 pageTable[i].physicalPage。

也就是說，當要執行 process 某一頁的程序，則將會去找 pageTable 所對應的 physicalPage，然後去運行。在作業一開始給的代碼中，會發現所有程序的 physicalPage 都共用，如此一來當然會執行到同一份 code。

首先，我們需要一個全局的標記，來記錄 main memory page 的情況。

usrprog/addrspace.h
1
2
3
4
5
6
7
class AddrSpace {
  public:
    ...
    static bool usedPhyPage[NumPhysPages];
  private:
    ...
};

接著，在 addrspace.cc 宣告實體，並且初始化是 0，表示全部都還沒有用過。

usrprog/addrspace.cc
1
2
3
4
5
6
7
8
#include "copyright.h"
#include "main.h"
#include "addrspace.h"
#include "machine.h"
#include "noff.h"
    ...
bool AddrSpace::usedPhyPage[NumPhysPages] = {0};
    ...

當 process 執行成功後，將會釋放資源。此時將要把標記使用的 page 設回未使用。

usrprog/addrspace.cc
1
2
3
4
5
6
AddrSpace::~AddrSpace()
{
    for(int i = 0; i < numPages; i++)
        AddrSpace::usedPhyPage[pageTable[i].physicalPage] = false;
   delete pageTable;
}

最後，就是稍微麻煩的地方，當將程序載入記憶體時，要去填入 pageTable[] 對應的 physicalPage，這裡使用線性時間去搜索第一個未使用的 page 進行填入。

載入確定後，便要開始執行，執行的時候要去算程序進入點，進入點的位置即是 main memory address。

mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]

首先算出第幾頁，然後乘上 PageSize 就是 page base，而 page offset 則是 code.address mod PageSize。

最後，page base + page offset 就是我們所需要的程序進入點。

usrprog/addrspace.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
bool AddrSpace::Load(char *fileName) {
    OpenFile *executable = kernel->fileSystem->Open(fileName);
    NoffHeader noffH;
    unsigned int size;
    if (executable == NULL) {
    cerr << "Unable to open file " << fileName << "\n";
    return FALSE;
    }
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
        (WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);
// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
            + UserStackSize;	// we need to increase the size
                        // to leave room for the stack
    numPages = divRoundUp(size, PageSize);
//	cout << "number of pages of " << fileName<< " is "<< numPages << endl;
// morris add
    pageTable = new TranslationEntry[numPages];
    for(unsigned int i = 0, j = 0; i < numPages; i++) {
        pageTable[i].virtualPage = i;
        while(j < NumPhysPages && AddrSpace::usedPhyPage[j] == true)
            j++;
        AddrSpace::usedPhyPage[j] = true;
        pageTable[i].physicalPage = j;
        pageTable[i].valid = true;
        pageTable[i].use = false;
        pageTable[i].dirty = false;
        pageTable[i].readOnly = false;
    }
// end morris add
    size = numPages * PageSize;
    ASSERT(numPages <= NumPhysPages);		// check we're not trying
                        // to run anything too big --
                        // at least until we have
                        // virtual memory
    DEBUG(dbgAddr, "Initializing address space: " << numPages << ", " << size);
// then, copy in the code and data segments into memory
    if (noffH.code.size > 0) {
        DEBUG(dbgAddr, "Initializing code segment.");
    DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);
// morris add
        	executable->ReadAt(
        &(kernel->machine->mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]), 
            noffH.code.size, noffH.code.inFileAddr);
// end morris add
    }
    if (noffH.initData.size > 0) {
        DEBUG(dbgAddr, "Initializing data segment.");
    DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
// morris add
        executable->ReadAt(
        &(kernel->machine->mainMemory[pageTable[noffH.initData.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]),
            noffH.initData.size, noffH.initData.inFileAddr);
// end morris add
    }
    delete executable;			// close file
    return TRUE;			// success
}

Sleep() System call

撰寫自己的 Sleep function，將該 Thread 進入休眠。

測試檔案

與一開始的 test1.c 很像，這裡先做個簡單測試。

/code/test/sleep.c
1
2
3
4
5
6
7
8
9
#include "syscall.h"
main() {
    int i;
    for(i = 0; i < 5; i++) {
        Sleep(10000000);
        PrintInt(50);
    }
    return 0;
}

因為整個測試檔案是要能在 nachOS 上面跑，所以不能使用一般的編譯方式？所以把這些訊息寫入 Makefile 中，之後下 $ make 產出 sleep 即可。
/code/test/Makefile
1
2
3
4
5
6
7
...
all: halt shell matmult sort test1 test2 sleep
...
sleep: sleep.o start.o
    <span>$(LD)$</span><!-- Has MathJax -->(LDFLAGS) start.o sleep.o -o sleep.coff
    ../bin/coff2noff sleep.coff sleep
...

如果無法在 /code/test 下 $ make 順利產出，則請參照 其他指令 ，將原本下載的 mips-decstation.linux-xgcc.gz 解壓縮產生的 /usr 移動到正確位置。

解決

首先，要模仿 PrintInt()，找到切入的宣告位置。努力地尾隨前人。

/code/userprog/syscall.h
1
2
3
4
5
6
7
...
#define SC_PrintInt	11
#define SC_Sleep	12
...
void PrintInt(int number);	//my System Call
void Sleep(int number);         // morris add
...

接著，找一下 ASM。
以下部分就不得而知了，為什麼會出現在 /code/test 目錄下。

/code/test/start.s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    ...
PrintInt:
    addiu   <span>$2,$</span><!-- Has MathJax -->0,SC_PrintInt
    syscall
    j       $31
    .end    PrintInt
    .globl  Sleep
    .ent	Sleep
Sleep:
    addiu   <span>$2,$</span><!-- Has MathJax -->0,SC_Sleep
    syscall
    j	$31
    .end	Sleep
    ...

最後，確定 nachOS 會處理我們的例外操作。

/code/userprog/exception.cc
1
2
3
4
5
6
7
8
9
10
11
    ...
case SC_PrintInt:
    val=kernel->machine->ReadRegister(4);
    cout << "Print integer:" << val << endl;
    return;
case SC_Sleep:
    val=kernel->machine->ReadRegister(4);
    cout << "Sleep Time " << val << "(ms) " << endl;
    kernel->alarm->WaitUntil(val);
    return;
    ...

到這裡需要喘口氣，剛找了一陣子的代碼。接著才是重頭戲，因為你看到了 kernel->alarm->WaitUntil(val); 出現了。沒錯！我們需要撰寫那邊的代碼。

既然 kernel 存有 alarm，也就是說每隔固定一段間，就會呼叫 Alarm::CallBack()，因此，對於這個鬧鐘來個累加器 Bedroom::_current_interrupt，全局去記數，當作毫秒 (ms) 看待就可以，每加一次就相當於過了 1 毫秒 (ms)。

假設現在某一個 time = _current_interrupt 呼叫 Sleep(x) 後，將 (Thread address, _current_interrupt + x) 丟入 List，則期望在 _current_interrupt + x 的時候甦醒。因此，每當 _current_interrupt++ 就去檢查 List 中，誰的預期時間小於 _current_interrupt，就將其從 List 中清除。

這裡先不考慮 _current_interrupt Overflow 的問題，根據電腦效率，可能在 5 ~ 10 秒內就發生一次，此時會造成所有 Thread 沉眠很久。若察覺 Sleep 太久，則是發生 Overflow。

  • 當有程序呼叫 Sleep() 時，會呼叫 WaitUntil()，然後將其丟入 Bedroom 安眠。
  • 然後在 CallBlack() 被呼叫時，來去 Bedroom 檢查誰該醒來了。
/code/threads/alarm.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "copyright.h"
#include "utility.h"
#include "callback.h"
#include "timer.h"
#include <list>
#include "thread.h"
class Bedroom {
    public:
        Bedroom():_current_interrupt(0) {};
        void PutToBed(Thread *t, int x);
    bool MorningCall();
    bool IsEmpty();
    private:
        class Bed {
            public:
                Bed(Thread* t, int x):
                    sleeper(t), when(x) {};
                Thread* sleeper;
                int when;
        };
    
    int _current_interrupt;
    std::list<Bed> _beds;
};
// The following class defines a software alarm clock. 
class Alarm : public CallBackObj {
  public:
    Alarm(bool doRandomYield);	// Initialize the timer, and callback 
                // to "toCall" every time slice.
    ~Alarm() { delete timer; }
    
    void WaitUntil(int x);	// suspend execution until time > now + x
  private:
    Timer *timer;		// the hardware timer device
    Bedroom _bedroom;
    void CallBack();		// called when the hardware
                // timer generates an interrupt
};

確定有哪些 method 就可以開始實作了。

/code/threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void Alarm::CallBack() {
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
        timer->Disable();	// turn off the timer
    }
    } else {			// there's someone to preempt
    interrupt->YieldOnReturn();
    }
}
void Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}
bool Bedroom::IsEmpty() {
    return _beds.size() == 0;
}
void Bedroom::PutToBed(Thread*t, int x) {
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    _beds.push_back(Bed(t, _current_interrupt + x));
    t->Sleep(false);
}
bool Bedroom::MorningCall() {
    bool woken = false;
    _current_interrupt ++;
    for(std::list<Bed>::iterator it = _beds.begin(); 
        it != _beds.end(); ) {
        if(_current_interrupt >= it->when) {
            woken = true;
            cout << "Bedroom::MorningCall Thread woken" << endl;
            kernel->scheduler->ReadyToRun(it->sleeper);
            it = _beds.erase(it);
        } else {
            it++;
        }
    }
    return woken;
}

到這裡我們就完成 Sleep() 製作。

在下一階段，將要加入排程的製作。

Scheduling

目標完成 SJF, RR, FIFO。
請參閱 “向 NachOS 4.0 作業進發 (2)”

其他指令

  • 打包轉移 // 交作業前，將檔案包出傳送，此指令不是壓縮用途

    1
    $ tar cvf FileName.tar DirName

  • 複製資料夾 // 將 nachos gcc library 搬移至 /usr/local/nachos ...

    1
    $ cp -a DirName TARGET_PATH

  • 轉移至 root 權限 // 如果指令權限不夠，需要下達此指令。

    1
    $ su

備忘

  • 網路上有幾個 Java 版本的 NachOS，架構稍微不同，如果發現文章說明有點怪怪的，請看一下他是用 JAVA 版本還是 C++ 版本。
  • 至於怎麼將檔案從 Red Hat，這有點惱人，可以想辦法安裝其他瀏覽器，然後開 e-mail 送出，或者使用 terminal 上的 wget 安裝 … 一堆辦法。最後我自己用 nodejs 寫一個簡單的 upload server 傳出來。

代碼下載

Github

Read More +
學校課程/計算型智慧

計算型智慧 程式作業

Computational Intelligence 計算型智慧

本課程將會有三階段程式，將三個算法依序加入程式中，為了要實作這些算法，必須先作出模擬器。

Lv. 0 模擬器

在一個 2D 平面中，以一個圓形當作車子，道路為線段的方式進行描述。為了在隨後的擴充，將地圖內容物分成可行區域多邊形和障礙物多邊形。

  • 要支持車子下一秒的擺角，並且按下推動鍵會根據方程式進行移動。
  • 可以將車子兩側的感測器進行角度調整，並且可以根據感測器角度進行距離計算。
  • 並且在呈現 2D 平面時，附加顯示座標軸的比例。

完成圖

由於私心，有一些額外產物。

  • 完成可以自動置中的設定
  • 提供地圖縮放和讀取操作
  • 製作地圖產生器 (other project)
  • 模擬器的彈木遊戲番外篇 (other project)
  • 提供運行欄位的縮起

Lv. 1 模糊系統

車子運行公式

運行公式

其中 Φ(t) 是模型車與水平軸的角度，b 是模型車的長度，x 與 y 是模型車的座標位置， Θ(t) 是模型車方向盤所打的角度，我們對模擬的輸入輸出變數限制如下：

-40 deg <= Θ(t) <= 40 deg

寫一個程式使用模糊系統、理論模擬車子行徑，並且想辦法最佳化。

  • 考慮擴充性，以後車子的運行公式可能會替換，因此建造一個 Engine class。
  • 模糊系統的幾個特性拆分成數個 method，並且使用不同的數學計算採用繼承關係。
  • 最困難得地方在於計算函數交集，採用離散取點是最後的手段

函數實驗

  1. 經過實驗，三個感測器分別坐落於前方 (90度)、左右各偏轉 50 度左右的夾角比左右 90 度更好。用以應付多變的轉角彎度，防止模稜兩可的擺動。
  2. 不管哪裡種去模糊化系統，由於題目限制擺角於 [-40, 40] 度之間，因此很容易在加權平均、質心、離散化而導致邊界擺角的機率甚低，當越多函數則稀釋程度越高。因此函數定義可以超過限制擺角，只需要在去模糊化時，約束至條件內即可。
  3. 設計函數時，要討論向其中一個方向偏轉，也就是不能設計過於對稱的圖形，否則將會在死胡同裡打轉。

函數設計

d1 為前方感測器，d2 為右方感測器，d3 為左方感測器。

  1. d1 歸屬函數為
    d1 歸屬函數
    d2, d3 歸屬函數為
    d2, d3 歸屬函數
  2. 函數式加權平均
    If d3 large, θ = 55
If d2 large, θ = -55
If d2 medium, θ = -40
If d3 medium, θ = 40
If d1 large and d2 small, θ = -30
If d1 large and d3 small, θ = 30
If d1 small, θ = -60
    規則如上述七條，以最簡單的常數關係。測試結果還算不錯。
    if condition, then statement，statement 中的變數不存在於 condition 去做調整，後來發現由於太複雜去討論而一直失敗。

  3. 重心法、最大平均法、修正型最大平均法、中心平均法
    為了方便計算連續函數，採用離散取點，間隔 0.1 抓取 [-60, 60] 之間的點座標。對於以下四種方法討論於簡單彎道的過程記錄：
    If d3 large
    If d3 large
    If d2 large
    If d2 large
    If d2 medium
    If d2 medium
    If d3 medium
    If d3 medium
    If d1 large and d2 small
    If d1 large and d2 small
    If d1 large and d3 small
    If d1 large and d3 small
    If d1 small, θ = -60
    If d1 small

    • 重心法
      當中表現最為穩健，而且路徑平滑。
    • 最大平均法
      由於定義的函數較為簡單，而且大多都是以梯形的方式存在，雖然能在機率高的情況下走完全程，路徑中會呈現左右擺盪情況。並且大多都已極值的方式出現。
    • 修正型最大平均法
      情況會稍微好一些，但是對於並沒有向重心法一樣的圓滑曲線，仍是因為原先的函數設計所惹的問題。

    對於某一種方法而去定義相關的函數進行測較好，而在最大平均法的部分，必須使用較具有變化性的曲線，否則很容易在極值狀況下擺動。

Lv 2. GA

RBF

「放射狀基底函數網路 RBF」，基本上，其網路架構如圖1所示，為兩層的網路；假設輸入維度是p ，以及隱藏層類神經元的數目是J ，那麼網路的輸入可以表示成：

其中選用高斯型基底函數：

其中 x = (x1,x2,…,xp) 、mj = (mj1,mj2,…,mjp) 、|| || 代表向量絕對值
適應函數為：

請用實數型基因演算法，找出wj , mj , σj，在不同的數字J下，最好的基因向量 (例如J為9、輸入x為3維向量，則表示基因向量是1+9+3x9+9=46維度的向量，請注意這裡不是指族群數；又例如J為7、輸入x為3維向量，則表示基因向量是1+7+3x7+7=36維度的向量)下，評估函數E(式1)為越小越好。其中基因向量維度公式為 1+J + pJ+J = (p+2)J+1維向量( ,w1 , w2 ,.., wJ , m11, m12,.., m1p, m21, m22,.., m2p,.., mJ1, mJ2,…, mJp, σ1, σ2, …, σJ)。

參數說明 :

  • N 作業1產生的N筆成功到達目的訓練資料(換不同起始點)
  • yn 表示訓練資料的方向盤期望輸出值 P.s.如果配合wj值的範圍為0~1之間，在此則必須把yn由-40~+40度正規化到 0~1之間；如果不想正規化 就必須把 wj的值範圍調整到 -40~40之間 範圍為0~1之間
  • Wj 範圍為 0~1 (或是-40~40)之間 P.s.此需配合訓練集的yn跟F(n)值範圍，所以皆需正規化到0~1之間；若不正規化，wj的值範圍為 -40~40之間
  • mj 範圍跟X範圍一樣，如以提供的範例檔則為 0~30
  • σj 範圍為0~10之間；也可以設定更大的範圍做探討。

實作概要 ：
把參數編碼成 DNA，使用 GA 算法改變 DNA，然後用之前的模糊系統的結果，讓 RBF 接近之前定義的模糊系統。需要拿模糊系統的一些測資當作訓練資料，收集之後餵給 GA 做訓練。

實驗方法

  1. 核心代碼，對於每次迭代，著手適應、選擇、交配、突變。
  2. 細部 “交配” 代碼，採用實數型的分離和聚集兩種情況。
  3. 細部 “突變” 代碼，採用微量雜訊，唯一不同的地方在於，這個微量雜訊會根據當前數值的比例有關，為了避免大數字對於微量雜訊的干擾不夠強烈。

實驗結果

  1. 運行結果 J = 3, p = 3
    ( ,w1 , w2 ,.., wJ , m11, m12,.., m1p, m21, m22,.., m2p,.., mJ1, mJ2,…, mJp, σ1, σ2, …, σJ) = (0.163568 0.851471 1.594151 1.379580 13.092824 0.000505 12.611789 30.000000 0.000368 18.715240 0.000850 2.708967 30.000000 6.307677 7.584529 10.000000)
  2. 訓練數據為 “map2” 走一圈的訓練資訊，約為 500 筆。因為 “map0” (即本次作業給的地圖) 的複雜度不夠以至於無法充分表達原本設計的模糊系統。也就是根據當初模糊系統設計，收集的數據的多樣性和連續性不足。

實驗分析

根據 RBF 的神經元，這裡可以越少越好，在程式中，神經元個數(J) 設置 3 個。運行時採用輪盤式選擇，讓適應能力好的，具有較高的機會繁殖，採用一個隨機變數去挑選。而在基因方面使用實數型基因的形式。

  1. 運行時，突變機率和突變比例相當重要，由於相同適應能力好的物種量很多，只保留其中一部分即可，因此可以將突變機率0.5 左右，太低則會造成進化速度太慢，太高則容易失去原本適應好的物種，導致整體適應度的震盪。
  2. 另外設置突變的比例，也就是該段實數值上下調整的比例。
    g.getDNA()[i] = g.getDNA()[i] + ratio * Math.random() * g.getDNA()[i];
    藉由上述的式子，將 ratio 設置成一個調變比例，來製造爆炸效應的規模。而在運行時，突變效果還能接受。
  3. 原本運行時，只將 DNA 片段的值任意放置，並且約束在不會超出函數的定義域，在收斂速度上有明顯加速。但為了符合作業需求，將每個參數約束在指定範圍內，在收斂速度慢了一截，在預期結果並沒有很好。
  4. 在不同地圖收集的預期資訊，會針對不同車子感測器的角度有所差異，因此不能拿不同型的感測數據，訓練出來的 RBF 不能給另外一台車子來使用，除非使用的感測器角度相當接近。
  5. 對於死路的轉彎，在神經元個數(J) 等於 2 的時候，運行結果較為不佳，但是在本次作業中，並不會有這種數據的出現，也不用考慮這種情況。但是當神經元個數少時，GA 算法的運行速度是相當快的。

Lv. 3 PSO

請利用Particle swarm optimization替換掉 GA 部分。

  • AgentNum(粒子數)
  • IterationNum(疊代數),
  • MaxV(最大速度),
  • MaxX(最大值範圍),
  • Weights(兩個權重),
  • Convergent_Error(停止條件)
  • 並畫出 fitness function 曲線變化 (每一次疊代的最佳fitness值)，最後訓練完成的F(x)當作規則 請跑出車子軌跡。

實驗分析

一開始參數為

1
2
3
4
5
6
public int sandSize = 512;
public double maxVelocity = 0.5;
public double maxXposition = 0.5;
public double weightOfCognition = 0.5;
public double weightOfSocial = 0.5;
public double nearRatio = 0.5;

PSO 1

PSO 2

  • 基本上 maxXposition 沒有用到，調整其他比例可以發現端倪。

  • 從圖 PSO 2 中可以發現到，PSO 與 GA 最大的不同在於，如果 GA 調用部分突變的情況下，很高的機率會發現適應曲線是嚴格遞減的，但是在 PSO 由於會飛來飛去，有可能會來回震盪。

  • 當所有粒子逼近最佳解時，仍會以原本的速度繼續飛行，而原本屬於最佳位置的點也會開始模仿其他粒子飛行，如此一來就會造成震盪。

PSO 3

  • 其震盪的高低決定於鄰近模仿的權重，如果鄰近的粒子效果不好，模仿的權重高的時候，會導致整個最佳解有嚴重的偏離。由 PSO 3 中可以驗證這個震盪問題。

  • 如果對於全局模仿權重調高，很容易造成處於群聚粒子不容易分離，也就是很難在早到其他的區域最佳解，會在很快的時間內進入某一個區域最佳解，從這一點中可以發現 PSO 真的具有快速收斂的性質。

  • 設定 maxVelocity 是將整個向量長度 (歐幾里得距離) 壓縮，這將可以控制查找的精密度，如果設定太小會導致收斂速度明顯下降。將 maxVelocity = 10 時，適應函數看起來會有比較高的進展，由於會將每個參數約束，只要速度不是太小影響就不大。

  • 當速度上限增加時，粒子碰到牆的機會也會上升，由於搜索範圍的可能性涵蓋邊界的情況增加，如果最佳解在邊界，在這樣的情況就會更好。

  • 在代碼中，鄰近的定義為最近粒子中排名前 20% 的最佳解。如果採用對於常數長度，這種情況上不容易觀察，也就是說不能直接找到鄰近模仿的規模該定義在何處。

  • 運行結果 J = 3, p = 3
    ( ,w1 , w2 ,.., wJ , m11, m12,.., m1p, m21, m22,.., m2p,.., mJ1, mJ2,…, mJp, σ1, σ2, …, σJ) = (0.117271 1.270048 0.000000 0.805823 15.845525 0.000000 21.613452 13.509075 0.000000 0.000000 30.000000 0.000000 10.505934 10.000000 10.000000 5.238101)

Github Download

Download

Blog

Read More +
學校課程/作業系統

作業系統 Thread 程式作業

C++ Thread 練習

作業要求

作業一:應用 Thread 撰寫任意程式(語言不限)，繳交方式 FTP:140.115.155.192(選擇自己學號的資料夾上傳) 帳:os2014 密碼不知道者請再問助教，檔案名稱: “作業一學號姓名_第幾版” ex:”作業一10252200x林大乖_v1” 繳交內容:壓縮檔(報告word 以及 程式碼,執行檔)，截止日期:2014/05/25(日)23:59

程式功能

兩個 n*n 矩陣相乘，在最基礎的 O(n^3) 效能上，使用 Thread 等相關技巧使其加速。

運行

  • Mac OSX

    $ clang -pthread x.cpp -o x

  • Linux

    $ gcc -lpthread x.cpp -o x

測試效率

  • Mac OSX and Linux
    $ time ./a.out

測試結果

測試環境為 2013 Mac Air 1.3 GHz Intel Core i5 上對 1024 x 1024 的矩陣進行相乘的統計結果。

  • matrix.cpp
    最原始的一般寫法，直接使用 O(n^3) 。運行時間約在 20 秒左右完成。
  • matrix[v2].cpp
    使用轉置矩陣後，在進行運算，這種方式是加快作業系統中的快取層，速度提升至約在 4 秒左右完成。
  • matrix[v3].cpp
    建立在 matrix[v2].cpp 的基礎上，使用 4 條 thread，分別對處理的 column 進行分割操作，速度約在 2 秒內完成。
  • matrix[v4].cpp
    與 matrix[v3].cpp 類似，調整 thread 的數量，查看效率變化，但是速度沒有更快的趨勢。

結論

Thread 多不代表會比較快，而是該程式佔有 CPU 的機會比較高，使用的資源就會比較多。在整個作業系統中，Thread 多上下文切換的次數就會上升，對於作業系統整體效率是下降的，但是又不能沒有 Thread，看起來像是所有程式同時在運行，也要防止落入死機無法動彈的情況。

而在 thread 上面會發現，當數量達到一定程度後，速度就不會上升，有一部分是因為 CPU 超頻運作。

超頻（英語：Overclocking）是把一個電子配件的時脈速度提升至高於廠方所定的速度運作，從而提升性能的方法，但此舉有可能導致該配件穩定性下降。

可能是長時間閒置的 CPU 發現有大規模的工作運行，把時脈速度升起。

代碼

matrix.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define MAX_N 1024
double A[MAX_N][MAX_N];
double B[MAX_N][MAX_N];
double C[MAX_N][MAX_N];
void multiply(double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            double sum = 0;
            for (int k = 0; k < MAX_N; k++) {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
}
int main(void) {
    //clock_t start, finish;
    //start = clock(); // start time clock
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            A[i][j] = i;
            B[i][j] = j;
        }
    }
    multiply(A, B, C);
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

matrix[v2].cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
using namespace std;
#define MAX_N 1024
double A[MAX_N][MAX_N];
double B[MAX_N][MAX_N];
double C[MAX_N][MAX_N];
void trans(double A[][MAX_N]) {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = i+1; j < MAX_N; j++) {
            swap(A[i][j], A[j][i]);
        }
    }
}
void multiply(double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) {
    trans(B);
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            double sum = 0;
            for (int k = 0; k < MAX_N; k++) {
                sum += A[i][k] * B[j][k];
            }
            C[i][j] = sum;
        }
    }
}
int main(void) {
    //clock_t start, finish;
    //start = clock(); // start time clock
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            A[i][j] = i;
            B[i][j] = j;
        }
    }
    multiply(A, B, C);
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

matrix[v3].c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#define MAX_N 1024
double A[MAX_N][MAX_N];
double B[MAX_N][MAX_N];
double C[MAX_N][MAX_N];
void trans(double A[][MAX_N]) {
    double x;
    int i, j;
    for (i = 0; i < MAX_N; i++) {
        for (j = i+1; j < MAX_N; j++) {
            x = A[i][j];
            A[i][j] = A[j][i];
            A[j][i] = x;
        }
    }
}
#define MAX_THREAD 4
void *multiply(void *arg) {
    int id = *((int *)arg);
    int st = id * MAX_N / MAX_THREAD;
    int ed = (id + 1) * MAX_N / MAX_THREAD - 1;
    int i, j, k;
    for (i = st; i <= ed; i++) {
        for (j = 0; j < MAX_N; j++) {
            double sum = 0;
            for (k = 0; k < MAX_N; k++) {
                sum += A[i][k] * B[j][k];
            }
            C[i][j] = sum;
        }
    }
    return NULL;
}
int main(void) {
    puts("Thread version");
    //clock_t start, finish;
    //start = clock(); // start time clock
    int i, j;
    for (i = 0; i < MAX_N; i++) {
        for (j = 0; j < MAX_N; j++) {
            A[i][j] = i;
            B[i][j] = j;
        }
    }
    trans(B);
    
    pthread_t *threads;
    threads = (pthread_t *) malloc(MAX_THREAD * sizeof(pthread_t));
    
    for (int i = 0; i < MAX_THREAD; i++) {
        int *p = (int *) malloc(sizeof(int));
        *p = i;
        pthread_create(&threads[i], NULL, multiply, (void *)(p));
    }
    for (i = 0; i < MAX_THREAD; i++) {
        pthread_join(threads[i], NULL);
    }
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

其他

雖然作業可以有其他語言的相關 Thread，在 Java 作品方面可以查看 Github。

Read More +
學校課程/敏捷方法

論文選讀 Agile Development and User Experience Design ...

課程論文心得

首先，所讀這一篇的論文名稱為『Agile Development and User Experience Design Integration as an Ongoing Achievement in Practice』 所以著重點在于用戶體驗設計要怎麼融入敏捷開發的探討。

什麼是用戶體驗？先說說 UX Designer 做些什麼嗎

第一次轉UX Designer就上手（上）

第一次轉UX Designer就上手（下）

看完內容後，總之 UX Designer 算是一種設計師，與理工背景的開發人員可是天差地遠，

他們比起宅宅開發者來說，要與用戶產生關係，繪畫、表達、心理學、與現實溝通，開發人員擁有技術並且完成目標，但是行為卻不是一般使用者，最簡單的說法是『為什麼做出來的軟體只有開發者會用？』如果在軟體的需求面向是開發者們的話，這也許還不是問題，但是要做出給一般人使用的軟體，這樣是行不同的。但是開發者的邏輯古怪到自己都不明白的機率是挺高的，因此會有 UX Designer。

借由 UX design，軟體將會有耐用性、易上手、輕便化 … 等，這讓我突然想到總是會開發出根本用不著的功能，或者是相當難操作的功能。

但是要把 UX design 完全融入是有困難的，因為邏輯思維不同的人，是很難協調的，又或者會互相侵蝕。

開始談談論文的內容

這一篇論文，主要是 觀察 ，也沒有觀察到所有目前的運行方式。換句話說，不會存在唯一一個好的開發方式，根據組織的規模和文化背景，所適用的運行方式也會有所不同，在理論上百分之百照抄別人的做法運用在自己的發開方式，但是可以藉由論文中觀察的幾點來學習我們的開發方式大概需要的是哪些面向需求。

而當開發人員是怎麼樣類型的人，就可能需要運用哪些方式，這些都是需要去探討的。外國也許按照它們的方式走成功，但並不代表按照一樣的作法一樣會成功，這就所謂 新方法論 。新方法論沒有絕對的方法，說來有點玄，也就是沒有固定方法就是方法！

由於組織規模不同，彼此部門又要互相協調，在設計與開發之間的不同在於時間的週期不同，工作類型的方式不同，如果是大規模組織，『提高內聚力，降低耦合度』因此專業分工的類型將會在 Study 1 中被提及，這麼考量是有它的原因在的。

而文藝復興時期的全才－達文西類型，則可以在 Study 2 中被提及，每一個人都必須學習一點別人的領域的項目，這樣可以互相考量、共同承擔，來分散思考風險。但這樣對於一般人是相當困難的，如果是菁英組織的運行，大概就是長得這樣。

在最後的 Study 3 中，雖然使用傳統的瀑布式開發，這種神祕的設計大於開發組合相當異常，但也許是一種新的導向。在往後的時代中，當技術相對成熟穩定時，面對的將會是設計需求大於開發需求。

RESEARCH METHOD

這裡提供三種 Ethnography (社會學的一種寫作文本，中文翻譯：民族誌) 來探討敏捷開發人員和用戶體驗設計師的配置方式。

A. In the field

(田野調查的區域，民族誌運用田野工作來提供人類社會學的描述研究)

總共有三個組織中，四個團隊參與本次研究，參與研究的團隊中正在進行 UX 設計，而我們主要的工作是觀察他們的工作運行情況。

共計在三種情況進行觀察。

  • Study 1: 觀察時間為兩個星期
  • Study 2: 觀察時間為六天
  • Study 3: 觀察時間為兩天

其中 Study 1, 2 過程中會涵蓋 Sprint 會議，而 Study 3 則只有涵蓋開發人員和設計師共處一室。

B. Thematic analysis

(專題分析)

C. Study participants

(研究參與者)

ACCOUNTS OF THE DAY-TO-DAY INTEGARTION WORK

Study 1

這項研究在 14 位 developer 和 2 位 UX designer，這兩位 UX designer 並不屬於 developer team，而是屬於該公司的 UX design team，因此他們並沒有參與 Sprint meeting、Standup、Retrospective，當然開發人員也沒有參與 design meeting，developer team 和 design team 在不同樓層工作。

開發人員描述道『將 UX design 與 agile develop 分開，是基於管理層面。』這很大的原因在於要將 UX 創造力發揮到極限，不能讓軟體工程的問題阻擋他們思考。

而在 Sprint meeting 中觀察到，UX designer 會提供一個 UX design 在 sprint meeting 前送達。但在隨後的 UX design 版本則是偶爾送到 developer 手上，直到 sprint 的最後一天仍持續修改，這表示著 developer 無法依靠 UX design 考慮相關的實作項目，所以大多數的關於 UX 工作將會分配在最後幾個小時來完成。

然而如果詢問 UX designer 是否已經意識到自己時間分配所造成的影響，則他們會回答說『沒有』。但事實上，在發送 UX design 時就已經造成相當多的問題。

[UX designer]: “That was never explicitly said to me … I thinks there was and still is visibility issues to do with what they’re doing and what their timeline are.”
這表示 UX designer 從來不知道這些事情，也從來沒有直接地被告知這項問題，也是因為不知道 developer 的運行工作和時程表。

當要澄清或者是修改 UX design 時，develop 會將問題寫下，並且要求 UX designer 在他們的 feedback meeting 中討論。

[senior UX designer]: “The visual designs are pretty much parallel to the wireframes … what kind of feedback do you want to give ?”
資深 UX designer 表示道：所有的視覺設計都是在線框 (wireframe) 的基礎上完成的，能有什麼樣的反饋？

developer 並不完全了解 UX design，只能依靠 UX designer 的批准和重構，這 “批准” 主要是對於敏捷開發中的維護和支持的組成用途，但是當 developer 向 designer 發問時，往往是溝通失敗的。

2pm: There is some problem with the visual design from UX [hadn’t arrived yet]. Project manager’s been trying to get in touch with the interaction designer, however can not get in contact - mobile switched off. Project manager has heard that UX are moving desks (not all the visual designs have been delivered since the developer feedback session).

上述內容看得不明白，難道是就是單純 PM 得不到完整的 visual design，因此也就不能向互動工程師聯繫嗎？

Study 2

小型手機軟件開發的公司，這一間公司有兩支團隊，每一隊有 5 名 developer 和 1 名 UX designer。其中 UX designer 設計非功能性描述和 screen mock-ups，這幾個項目將可以幫助 developer 參考進行開發。

mock-ups 相當於一種 prototype 可以支持動作的描述，通常會帶有基礎的 action code，關於 mock-ups 的相關工具有很多，但是通常價格不菲，邊設計還能自動幫忙產生代碼是不容易的工作。網路上找不到相關的解釋，就先這樣頂替了，相較於一般手繪製圖和文件描述，這樣的方式更為容易了解。

在他們會議中，每一個角色(QA, scrum master, product owner, UX designer, developer) 都參與討論會議，創造共同意識和共享決策責任。

9:30 [developer]: How should tabs appear, is ad always right-most tab ? … UX designer tells the developer what whould happen: As new chats come in ad tab moves over to right-most tab.

開發人員: 分頁到底該如何呈現，而廣告要固定在最右側的分頁嗎？ … UX designer 告訴我們應該「當新的聊天訊息進來時，廣告要移動到最右邊的分頁嗎？」

[Product owner]: Still waiting on response for some questions from the client.

Product owner: 這仍然在等待顧客的回報訊息

[QA]: Kind of hard to do QA if we don’t have the answer … wayry of starting stories without behaviours which means we might have to change thins and that wastes time.

QA: 這件事情很難做確認，如果我們沒有接收到回報，做的任何修改也許只是浪費時間，無法確定品質。

[UX designer]: Do them anyway, they might need to go through a number of iterations before they agree this is what they want … it’s better of they see something working as soon as posssible.

UX designer: 先把這問題放一旁，這需要多次迭代才能確定這是他們想要的 … 如果他們需要高效工作，則這個方式可能比較好。

[QA]: What if an ad coes in at exactly the same time as a chat ?

QA: 那如果廣告作為一個新的聊天訊息出場的話呢？

[UX designer]: That’s extreme edge case and probably very hard to test. So leave it. QA agrees.

UX designer: 這是一個相當極端的方式，非常難測試，所以先不要管這個。

這些對話通常在每一天的工作中進行，詢問另外一個團隊問題，而另外的團隊注意這些問題。

[UX designer]: “… if developers come up with issues, these are discussed on a case-by-case basis as they come up … There are lots of small things which are easily worked out on a day-to-day basis”

UX designer: 如果 developer 在每一個 case 基礎上想出了問題，這些小問題很容易在每日解決。

從會議過程中，主要，我們可以發現的每一個角色都參與了 UX design，同時也在職權外貢獻了他們的想法 - 例如 UX designer 建議在極端情況忽略 QA testing，而在 QA 沒有指責 UX designer 所做的 QA 決策，他們接受這項意見並沒有發出任何評論。其次，在這個 UX design 討論議題中也一起討論了 non-UX 的問題(如這個 QA testing 問題)。

這次的會議的下一步行動，包括實現解決方案和傳達問題給客戶。所有的角色參與討論導致決策同時考慮的設計價值和技術考量。

而在會議中，有 developer 向其他人簡單說明，他在網路空間上有一些之前專案製作時替換視覺設計的文件可以參考，這可以讓 UI designer 可以接受這些更改的項目，增加信服力。

[UX designer]: Sometimes the developers’ decisions are better, as they are much closer to the implementation. 有時候開發者的決策會更好，因為他們更接近實作。

Study 3

在非常小的公司進行，有 1 名 developer 和 2 名 UX designer，他們擅長瀑布形式的開發，在開發過程中 developer 和 UX designer 在同一間辦公室工作，目標是使得設計和開發更接近。正如 Study 1 的時候，發現 developer 會根據 UX designer 設計的線框 (wireframe) 和 visual design 努力地工作。

觀察兩天後的結果如下:

在一般的情況下，UX designer 通常和 developer 在不同樓層工作，developer 也表示他們很少去找 designer 討論遭遇的問題。

[developer]: We often find things that don’t work, but we don’t go back to design. We just do our best. 我們常發現很多事情並不會 work，但是並沒有回去檢討設計，單純盡力而為。

在這種共同工作的情況下，designer 給予了一些回應。

[UX designer]: This style of working means we can collaborate in order to get our points across, rather than dictate because there’s no communication going on. 這種工作方式可以讓我們的觀點交換，而不是因為沒有通通合作的命令。

[Head of UX]: And when we first met with the client, the first thing they did was to present to us the findings of that initial research. So we can then go and propose what would bee the next step, which is quite different from any other type of work we’ve been invited to get involved in.

在大多數的情況，不確定性，設計師在現場談話的記錄:

[visual designer]: I just feel like I’m not getting any-where.

[IA]: I also feel that way.

但是對於另一個情況下

[developer]: Just cover the site map.

developer 和 designer 共同工作

  • 可以相互討論跟顧客對談時的內容 (當時在場的感受不同)
  • 目標計劃做些什麼，訊息可以提前知道。(想要做第二個版本)
  • 「這個設計會不會很難實作？」這些問題將會很快被反應出來。

[developer]: It would probably be just as easy.

THEME FOR ACHIEVING INTEGRATION

A. Integration as expectations about acceptable behaviour

在 Study 1 中可以發現，如果將兩者隔離，很容易造成規劃的浪費和開發者在最後期限前超時工作。UX designer 同時跨越多個專案進行設計，丟出設計之後就沒有可接收開發者的反饋，只有等到 sprint meeting 的反應才重新設計，這時可能已經為期已晚。

在 Study 2 中可以發現，頻繁確保兩者之間有相互支持，並且在 UX design 和代碼之間可以互相溝通，相較于 Study 1 上，溝通性有上升，但這些遭遇的問題將會在每個人參與討論會議的過程中的一部份。

在 Study 3 中，每一個成員都有機會被其他角色問到自己領域的問題，同時也可以在與客戶討論中的觀察，在隨後討論。這都歸因于他們在同一間辦公室工作。

B. Integration as mutual awareness

相對于 Study 1 中，Study 2, 3 擁有了共同享有決策的責任，同時提高了互動上的認識。

Read More +
學校課程/編譯器

編譯器 Compiler CFG LL(1)

序文

相較於其他技術而言，編譯器的確不是什麼有趣的課程，在這一門領域專研的人也變少了，所以專精的人越少，將會越有機會。易見地，也越來越少大學開設這門編譯器的課程，不過在一些公司，編譯器的技術將成為私囊秘寶，如何將代碼更加地優化快速，這就是相當令人感到為之一驚的地方。

DFA, NFA, Regular expression

在討論所有語法前，要明白正規表達式 ( Regular expression = RegExp ) 的運作，RegExp 運作上涵蓋的語法集合是最小的，對於一個 RegExp 來說，可以轉換成具有 n 個狀態的 NFA，而這台 NFA 可以轉換成 2n 狀態的 DFA。

NFA 和 DFA 最大的不同在於轉移狀態時，考慮的路徑情況，NFA 可以在不考慮輸入進行轉移，或者在相同情況下可以有很多轉移選擇。 DFA 則必須在一個輸入唯一一個轉移情況下運作。

如上圖 DFA 所示，邊上的內容就是根據輸入的情況進行轉移。

如上圖 NFA 所示，會發現狀態 p 對於輸入 1 有 2 種轉移可能 (p->p or p->q)。

最後可以得到一個 RegExp 一定會有一台 DFA 辨識它。而一台 DFA 也一定會有一個 RegExp，這句話的含意將可以在 計算理論 這門課中學到如何藉由類似 Floyd Algorithm 內點性質依序推出 DFA 對應的 RegExp。

CFG (Context-free grammar)

A context-free grammar is a formal system that describes a language by specifying how any legal string (i.e., sequence of tokens) can be derived from a start symbol. It consists of a set of productions, each of which states that a given symbol can be replaced by a given sequence of symbols.

另一個類似的語言是 Context-sensitive grammar，等價性質的兄弟是 Chomsky normal form。

  • CFG G = (Vt, Vn, S, P)

    • Vt: 有限的 terminal 字符集
    • Vn: 有限的 nonterminal 字符集
    • S: 一開始出發的 start symbol
    • P: 轉換的規則 (production)

    • 來個例子

      LHS (left-hand side) -> RHS (right-hand side)

<E>         -> <Prefix> ( <E> )
<E>         -> V <Tail>
<Prefix>    -> F
<Prefix>    -> l
<Tail>      -> + <E>
<Tail>      -> l

      明顯地

      • Vt = {(, ), V, F, l, +}
      • Vn = {<E>, <Prefix>, <Tail>}
      • S = <E>
      • P 就是給定那六條規規則
  • 名詞
    • Sentential form
      If S =>* β, β then is said to be sentential form of the CFG
      簡單來說，所有從 start symbol 過程中替換出來的句子都稱為 sentential form。
    • Handle of a sentential form
      The handle of a sentential form is the left-most simple phrase.
      img
      簡單來說，就是將一個 nonterminal 根據 production 轉換成 RHS (right-hand side) 的一個步驟。
  • 什麼是 CFG (上下文無關語法)？
    簡單來說，還真的是上下文無關，例如 S -> AB 可以見到 S 轉換時，不會因為前文或後文是什麼內容而影響，而在 Context-sensitive grammar (上下文敏感) 可以見到 aSb -> AB 會因為前面跟後面所受到的影響。

這裡使用大寫為 nontermainl，其他字符為 terminal。

First Set

  • First(A)
    • The set of all the terminal symbols that can begin a sentential form derivable from A. A =>* aB
      First(A) = {
    a in Vt | A =>* aB, and
    Λ in Vt | A =>* Λ
}
    • 簡單地說，從這個 nonterminal 開始，第一個不能被替換的 terminal 就會在 First set 中。
  • 計算 First(A) 前，必須先建出這個 nonterminal 有沒有可能推出 Λ，即 A =>* Λ。
    這邊相當有意思，使用迭代更新，如果發現 B =>* Λ 和 C =>* Λ 則對於 Production A => BC 來說，可以得到 A =>* Λ 就這麼依序推出所有情況，時間複雜度應該在 O(n^2)。
  • 計算 First(A) 時，掃描規則 LHS => RHS，找到 First(RHS) 並且 First(LHS).insert(First(RHS))，依樣使用迭代更新推出所有情況，時間複雜度應該在 O(n^2)。

Follow Set

  • Follow(A)
    • A is any nonterminal
    • Follow(A) is the set of terminals that may follow A in some sentential form. S =>* ... Aabc ...follow set。
      Follow(A) = {
    a in Vt | S =>* ... Aa ..., and
    Λ in Vt | S =>* aA
}
    • 請切記，一定要從 start symbol 開始替換的所有句子，而在這個 nonterminal 隨後可能跟著的 termainl 就會屬於它的。
  • 計算 Follow(A) 前，請先把 First set 都算完，接著也是用迭代更新，掃描規則 A -> a B b
    對於 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    if Λ not in First(b)
        Follow(B).insert(First(b))
    else
        Follow(B).insert(First(b) - Λ)
        Follow(B).insert(Follow(A))
    ``` 
    ## Predict Set ##
    * Given the productions
    * During a (leftmost) derivation, Deciding which production to match, Using lookahead symbols
    * 相較於 First set 和 Follow set，Predict Set 是根據 Production 產生的，也就是說一條 production 會有一個對應的 predict set，而 First set 和 Follow set 都是根據 nonterminal 產生一對一對應的集合，用來預測這一條規則的第一個 terminal 會有哪些。
    對於 production : `A -> X1 X2 ... Xm`

if Λ in First(X1 X2 … Xm)
Predict(A -> X1 X2 … Xm).insert(First(X1 X2 … Xm) - Λ);
Predict(A -> X1 X2 … Xm).insert(Follow(A));
else
Predict(A -> X1 X2 … Xm).insert(First(X1 X2 … Xm));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
對於第一判斷情況在于 `... AE = ... X1 X2 ... Xm E`，明顯地可以從 `Follow(A)` 得到第一個字符為何。
## LL(1) Table ##
> 尚未撰寫
C++ code
=====
## 資料規格 ##
以下代碼實作 CFG 的 First Set, Follow Set, Predict Set 和 LL(1) Table。
用字符 `l` 代替 lambda
## 資料範例 ##
* 本課程簡易範例輸入

S->aSe
S->B
B->bBe
B->C
C->cCe
C->d

A->BaAb
A->cC
B->d
B->l
C->eA
C->l

A->aAd
A->B
B->bBd
B->C
C->cCd
C->l

E->TX
X->+E
X->#
T->(E)
T->intY
Y->*T
Y->#

E->P(E)
E->vT
P->f
P->l
T->+E
T->l

S->aSe
S->B
B->bBe
B->C
C->cCe
C->d

S->ABc
A->a
A->l
B->b
B->l

1
2
* 本課程簡易範例輸出

B:b,c,d
C:c,d
S:a,b,c,d
a:a
b:b
c:c
d:d
e:e
A:a,c,d
B:d,l
C:e,l
a:a
b:b
c:c
d:d
e:e
A:a,b,c,l
B:b,c,l
C:c,l
a:a
b:b
c:c
d:d

#:#
(:(
):)
:
+:+
E:(,i
T:(,i
X:#,+
Y:#,*
i:i
n:n
t:t
(:(
):)
+:+
E:(,f,v
P:f,l
T:+,l
f:f
v:v
B:b,c,d
C:c,d
S:a,b,c,d
a:a
b:b
c:c
d:d
e:e
A:a,l
B:b,l
S:a,b,c
a:a
b:b
c:c

1
2
3
4
- - - - -
* HTML 格式範例輸入

-> begin end
->
->
-> l
-> ID := ;
-> read ( ) ;
-> write ( ) ;
-> ID
-> , ID
-> l
->
-> ,
-> l
->
->
-> l
-> ( )
-> ID
-> INTLIT
-> +
-> -
-> $

begin ID := ID - INTLIT + ID ; end $

1
* HTML 格式範例輸出

+—————-+—– First set —–+
|$ | { $ }
|( | { ( }
|) | { ) }
|+ | { + }
|, | { , }
|- | { - }
|:= | { := }
|; | { ; }
| | { + - }
| | { ( ID INTLIT }
| | { , l }
| | { ( ID INTLIT }
| | { ID }
| | { , l }
| | { ( ID INTLIT }
| | { + - l }
| | { begin }
| | { ID read write }
|| { ID read write }
|| { ID l read write }
| | { begin }
|ID | { ID }
|INTLIT | { INTLIT }
|begin | { begin }
|end | { end }
|read | { read }
|write | { write }
+—————-+———————+

+—————-+—– Follow set —–+
| | { ( ID INTLIT }
| | { ) }
| | { ) }
| | { ) , ; }
| | { ) }
| | { ) }
| | { ) + , - ; }
| | { ) , ; }
| | { $ }
| | { ID end read write }
|| { end }
|| { end }
| | { l }
+—————-+———————+

+—————-+—– LL(1) table —–+
| | $| (| )| +| ,| -| :=| ;| ID|INTLIT| begin| end| read| write|
| | | | | 20| | 21| | | | | | | | |
| | | 11| | | | | | | 11| 11| | | | |
| | | | 13| | 12| | | | | | | | | |
| | | 14| | | | | | | 14| 14| | | | |
| | | | | | | | | | 8| | | | | |
| | | | 10| | 9| | | | | | | | | |
| | | 17| | | | | | | 18| 19| | | | |
| | | | 16| 15| 16| 15| | 16| | | | | | |
| | | | | | | | | | | | 1| | | |
| | | | | | | | | | 5| | | | 6| 7|
|| | | | | | | | | 2| | | | 2| 2|
|| | | | | | | | | 3| | | 4| 3| 3|
| | | | | | | | | | | | 22| | | |
+—————-+———————+

Process syntax accept

```

代碼

2014/6/1 修正 parsing 時的 lambda 問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctype.h>
#include <assert.h>
using namespace std;
#define HTMLProduction
class Production {
    public:
        string 			LHS;
        vector<string> 	RHS;
        int 			label;
        
        Production(string L = "", vector<string> R = vector<string>()) {
            LHS = L;
            RHS = R;
        }
        
        void print() {
            printf("%s -> ", LHS.c_str());
            for(size_t i = 0; i < RHS.size(); i++)
                printf("%s", RHS[i].c_str());
        }
};
class Grammar {
    public:
        static const string 		lambda;
        string 						start_symbol;
        vector<Production> 			rules;
        map<string, set<string> > 	first_set;
        map<string, set<string> > 	follow_set;
        map<string, bool> 			derives_lambda;
        map<string, map<string, Production> >	lltable;
        
        map<string, bool> mark_lambda();
        void fill_first_set();
        void fill_follow_set();
        bool isNonterminal(string token);
        set<string> compute_first(vector<string> rhs);
        set<string> get_predict_set(Production p);
        void fill_lltable();
        void lldriver(queue<string> tokens);
};
const string Grammar::lambda("l");
set<string> Grammar::compute_first(vector<string> rhs) {
    set<string> result;
    size_t i;
    
    if(rhs.size() == 0 || rhs[0] == Grammar::lambda) {
        result.insert(Grammar::lambda);
    } else {
        result = first_set[rhs[0]];
        for(i = 1; i < rhs.size() && 
            first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end(); i++) {
            set<string> f = first_set[rhs[i]];
            f.erase(Grammar::lambda);
            result.insert(f.begin(), f.end());	
        }
        if(i == rhs.size() 
            && first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end()) {
            result.insert(Grammar::lambda);
        } else {
            result.erase(Grammar::lambda);
        }
    }
    
    return result;
} 
/*
 * please call get_predict_set() after fill_follow_set() and fill_first_set()
 */
set<string> Grammar::get_predict_set(Production p) {
    set<string> result;
    set<string> rfirst;
    
    rfirst = compute_first(p.RHS);
    if(rfirst.find(Grammar::lambda) != rfirst.end()) {
        rfirst.erase(Grammar::lambda);
        result.insert(rfirst.begin(), rfirst.end());
        rfirst = follow_set[p.LHS];
        result.insert(rfirst.begin(), rfirst.end());
    } else {
        result.insert(rfirst.begin(), rfirst.end());
    }
    
    return result;
}
/*
 * 
 */
void Grammar::fill_lltable() {
    string		A; // nonterminal
    Production 	p;
    
    for(size_t i = 0; i < rules.size(); i++) {
        p = rules[i];
        A = p.LHS;
        set<string> predict_set = get_predict_set(p);
        
        for(set<string>::iterator it = predict_set.begin();
            it != predict_set.end(); it++) {
            assert(lltable[A].find(*it) == lltable[A].end());
            lltable[A][*it] = p;
        }
    }
    
}
bool Grammar::isNonterminal(string token) {
#ifdef HTMLProduction
    if(token == Grammar::lambda)
        return false;
    if(token[0] == '<' && token[token.length() - 1] == '>')
        return true;
    return false;
#else
    if(token == Grammar::lambda)
        return false;
    for(size_t i = 0; i < token.length(); i++) {
        if(isupper(token[i]))
            return true;
    }
    return false;
#endif
}
map<string, bool> Grammar::mark_lambda() {
    bool 				rhs_derives_lambda;
    bool 				changes;
    Production 			p;
    
    derives_lambda.clear();
    
    /* initially, nothing is marked. */
    for(size_t i = 0; i < rules.size(); i++) {
        derives_lambda[rules[i].LHS] = false;
    }
    do {
        changes = false;
        for(size_t i = 0; i < rules.size(); i++) {
            p = rules[i];
            if(!derives_lambda[p.LHS]) {
                if(p.RHS.size() == 0 || p.RHS[0] == Grammar::lambda) {
                    changes = derives_lambda[p.LHS] = true;
                    continue;
                }
                /* does each part of RHS derive lambda ? */
                rhs_derives_lambda = derives_lambda[string(p.RHS[0])];
                for(size_t j = 1; j < p.RHS.size(); j++) {
                    rhs_derives_lambda &= derives_lambda[p.RHS[j]];
                }
                if(rhs_derives_lambda) {
                    changes = true;
                    derives_lambda[p.LHS] = true;
                }
            }
        }
    } while(changes);
    return derives_lambda;
}
void Grammar::fill_first_set() {
    
    string 		A; // nonterminal
    string 		a; // terminal
    Production 	p;
    bool 		changes;
        
    mark_lambda();
    first_set.clear();
    
    for(size_t i = 0; i < rules.size(); i++) {
        A = rules[i].LHS;
        if(derives_lambda[A])
            first_set[A].insert(Grammar::lambda);
    }
    
    for(size_t i = 0; i < rules.size(); i++) {
        for(size_t j = 0; j < rules[i].RHS.size(); j++) {
            a = rules[i].RHS[j];
            if(!isNonterminal(a)) {
                if(a != Grammar::lambda)
                    first_set[a].insert(a);
                if(j == 0) { // A -> aXX
                    first_set[rules[i].LHS].insert(a);
                }
            }
        }
    }
    
    do {
        changes = false;
        for(size_t i = 0; i < rules.size(); i++) {
            p = rules[i];
            set<string> rfirst = compute_first(p.RHS);
            size_t oldsize = first_set[p.LHS].size();
            first_set[p.LHS].insert(rfirst.begin(), rfirst.end());
            size_t newsize = first_set[p.LHS].size();
            if(oldsize != newsize)
                changes = true;
        }
    } while(changes);
} 
void Grammar::fill_follow_set() {
    string 	A, B; // nonterminal
    Production 	p;
    bool 	changes;
    
    for(size_t i = 0; i < rules.size(); i++) {
        A = rules[i].LHS;
        follow_set[A].clear();
    }
    
    follow_set[start_symbol].insert(Grammar::lambda);
        
    do {
        changes = false;
        for(size_t i = 0; i < rules.size(); i++) {
            /* A -> a B b
			 * I.e. for each production and each occurrence
			 * of a nonterminal in its right-hand side. 
			 */
            p = rules[i];
            A = p.LHS;
            for(size_t j = 0; j < p.RHS.size(); j++) {
                B = p.RHS[j];
                if(isNonterminal(B)) {
                    vector<string> beta(p.RHS.begin() + j + 1, p.RHS.end());
                    set<string> rfirst = compute_first(beta);
                    size_t oldsize = follow_set[B].size();
                    
                    if(rfirst.find(Grammar::lambda) == rfirst.end()) {
                        follow_set[B].insert(rfirst.begin(), rfirst.end());	
                    } else {
                        rfirst.erase(Grammar::lambda);
                        follow_set[B].insert(rfirst.begin(), rfirst.end());	
                        rfirst = follow_set[A];
                        follow_set[B].insert(rfirst.begin(), rfirst.end());
                    }
                    size_t newsize = follow_set[B].size();			
                    if(oldsize != newsize)
                        changes = true;
                }
            }
        }
    } while(changes);
}
void Grammar::lldriver(queue<string> tokens) {
    stack<string> 	stk;
    string 			X;
    string			a;
    Production		p;
    /* Push the Start Symbol onto an empty stack */
    stk.push(start_symbol);
    
    while(!stk.empty() && !tokens.empty()) {
        X = stk.top();
        a = tokens.front();
        // cout << X << " " << a << endl;
        if(isNonterminal(X) && lltable[X].find(a) != lltable[X].end()) {
            p = lltable[X][a];
            stk.pop();
            for(int i = p.RHS.size() - 1; i >= 0; i--) {
                if(p.RHS[i] == Grammar::lambda)
                    continue;
                stk.push(p.RHS[i]);
            }
        } else if(X == a) {
            stk.pop();
            tokens.pop();
        } else if(lltable[X].find(Grammar::lambda) != lltable[X].end()) {
            stk.pop();
        } else {
            /* Process syntax error. */
            puts("Bad!");
            return;
        }
    }
    while(!stk.empty()) {
        X = stk.top();
        if(lltable[X].find(Grammar::lambda) != lltable[X].end())
            stk.pop();
        else
            break;
    }
    if(tokens.size() == 0 && stk.size() == 0)
        puts("Good");
    else
        puts("Bad!");
    return;
}
queue<string> getTokens(char s[]) {
    stringstream 	sin(s);
    queue<string> 	tokens;
    string			token;
    while(sin >> token)
        tokens.push(token);
    return tokens;
}
void parsingProduction(string r, Grammar &g) {
#ifdef HTMLProduction
    static int 		production_label = 0;
    stringstream 	sin(r);
    string 			lhs, foo;
    vector<string> 	tokens;
    sin >> lhs >> foo;
    while(sin >> foo)
        tokens.push_back(foo);
    Production p(lhs, tokens);
    p.label = ++production_label;
    g.rules.push_back(p);
#else
    string div("->");
    size_t found = r.find(div);
    if(found != std::string::npos) {
        string rhs = r.substr(found + div.length());
        vector<string> tokens;
        for(size_t i = 0; i < rhs.size(); i++)
            tokens.push_back(rhs.substr(i, 1));
        Production p(r.substr(0, found), tokens);
        g.rules.push_back(p);
    }
#endif
} 
int main() {
    
    //freopen("input.txt", "r+t", stdin);
    //freopen("output.txt", "w+t", stdout); 
    
    char in[1024];
    while(gets(in)) {
        Grammar g;
        parsingProduction(in, g);
        while(gets(in) && in[0] != '\0') {
            parsingProduction(in, g);
        }
        
#ifdef HTMLProduction
        g.start_symbol = "<system_goal>";
#else
        g.start_symbol = "S";
#endif
        
        g.fill_first_set();
        g.fill_follow_set();
        g.fill_lltable();
        
        puts("+----------------+----- First set -----+");
        for(map<string, set<string> >::iterator it = g.first_set.begin();
            it != g.first_set.end(); it++) {
            printf("|%-16s| {", it->first.c_str());
            for(set<string>::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                cout << " " << *jt;
            }
            puts(" }");
        }
        puts("+----------------+---------------------+\n");
        puts("+----------------+----- Follow set -----+");
        for(map<string, set<string> >::iterator it = g.follow_set.begin();
            it != g.follow_set.end(); it++) {
            printf("|%-16s| {", it->first.c_str());
            for(set<string>::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                cout << " " << *jt;
            }
            puts(" }");
        }
        puts("+----------------+---------------------+\n");
        puts("+----------------+----- LL(1) table -----+");
        printf("|%-16s|", "");			
        for(map<string, set<string> >::iterator jt = g.first_set.begin();
                jt != g.first_set.end(); jt++) {
            string A = jt->first;
            if(g.isNonterminal(A))
                continue;
            printf("%6s|", A.c_str());
        }
        puts("");
        for(map<string, map<string, Production> >::iterator it = g.lltable.begin();
            it != g.lltable.end(); it++) {
            printf("|%-16s|", it->first.c_str());
            for(map<string, set<string> >::iterator jt = g.first_set.begin();
                jt != g.first_set.end(); jt++) {
                string A = jt->first;
                if(g.isNonterminal(A))
                    continue;
                if(it->second.find(A) == it->second.end()) 
                    printf("%6s|", "");
                else
                    printf("%6d|", it->second[A].label);
            }
            puts("");
        }
        puts("+----------------+---------------------+\n");
#ifdef HTMLProduction
        gets(in);
        g.lldriver(getTokens(in));
#endif
    }
    return 0;
}

備註

要學會更多，請修 計算理論 這門課程。

Read More +
學校課程/敏捷方法

軟體開發方法論(翻譯部分內容)

長篇大論

只求軟體開發的工程方法，最近上敏捷方法，教授開始講到了始祖 …

於是上演了輪番翻譯的戲碼，讓各種同學參與這份大型工程，關於翻譯的同時，深刻地理解到這也是為什麼無法接觸國外的最新資訊啊，曲解、誤解、亂解 …

我的語言記憶體如此小，卻搭載世界最複雜的語言。

序

In the past few years there’s been a blossoming of a new style of software methodology - referred to as agile methods. Alternatively characterized as an antidote to bureaucracy or a license to hack they’ve stirred up interest all over the software landscape. In this essay I explore the reasons for agile methods, focusing not so much on their weight but on their adaptive nature and their people-first orientation.

Probably the most noticeable change to software process thinking in the last few years has been the appearance of the word ‘agile’. We talk of agile software methods, of how to introduce agility into a development team, or of how to resist the impending storm of agilists determined to change well-established practices.

也許在這過去幾年最引人注目對軟件過程的思考的改變 - “敏捷 agile” 一詞的出現。我們將談論如何將敏捷軟體方法(agile software method)引入到開發團隊，或者如何抗拒即將到來的敏捷提倡者所帶來的風暴，這風暴將改變原先建立的好的業界實踐方法。

This new movement grew out of the efforts of various people who dealt with software process in the 1990s, found them wanting, and looked for a new approach to software process. Most of the ideas were not new, indeed many people believed that much successful software had been built that way for a long time. There was, however, a view that these ideas had been stifled and not been treated seriously enough, particularly by people interested in software process.

這新運動來自于 1990 年起不同人對於軟體程序的努力，他們發現和找到一個新的軟體程序。大多數敏捷方法的想法並不新，大多數人認為很多成功的軟件本來就有內置這種方式很久了，的確是有的，然而有一觀點指出，這些想法對於對軟體過程感興趣的人眼中並沒有受到重視，甚至被受到抑制。

This essay was originally part of this movement. I originally published it in July 2000. I wrote it, like most of my essays, as part of trying to understand the topic. At that time I’d used Extreme Programming for several years after I was lucky enough to work with Kent Beck, Ron Jeffries, Don Wells, and above all the rest of the Chrysler C3 team in 1996. I had since had conversations and read books from other people who had similar ideas about software process, but had not necessarily wanted to take the same path as Extreme Programming. So in the essay I wanted to explore what were the similarities and differences between these methodologies.

這篇文章也是新運動的起源一部份，最初發表于 2000 年 7 月。作為嘗試了解這文章一部份，您必須知曉這篇文章的風格如同其他大多數我寫的文章。在很幸運地與 Kent Beck, Ron Jeffries, Don Wells 共事後，我已經使用極限編程 (Extreme Programming) 好幾年。從 1996 年的 Chrysler C3 team 那時。我有機會與別人互相交流資訊和書籍來得到他們對於軟體過程中的類似想法，但即使是極限編程 (Extreme Programming) 也沒有一定要採用一樣的走法，所以在這篇文章中，我想要探索這些方法間的異同。

My conclusion then, which I still believe now, is that there were some fundamental principles that united these methodologies, and these principles were a notable contrast from the assumptions of the established methodologies.

以我的話來說，我至今仍相信那些方法一定有一些共同的基本原則，這些原則可能會從原本既有的(主流)方法假設中有明顯地對比。

This essay has continued to be one of the most popular essays on my website, which means I feel somewhat bidden to keep it up to date. In its original form the essay both explored these differences in principles and provided a survey of agile methods as I then understood them. Too much has happened with agile methods since for me to keep up with the survey part, although I do provide some links to continue your explorations. The differences in principles still remain, and this discussion I’ve kept.

這篇文章將會一直是一篇這個網站最熱門的文章，也意味者我會感到使命去保持這篇文章的更新。在文章原始架構中，會探討我所了解的這些原則的差異和提供敏捷方法的調查。當我在調查的同時，敏捷方法已經發生了變動，但仍我也提供一些鏈結供您探索，這些原則的差異和討論內容仍會保留在這篇文章中。

Most software development is a chaotic activity, often characterized by the phrase “code and fix”. The software is written without much of an underlying plan, and the design of the system is cobbled together from many short term decisions. This actually works pretty well as the system is small, but as the system grows it becomes increasingly difficult to add new features to the system. Furthermore bugs become increasingly prevalent and increasingly difficult to fix. A typical sign of such a system is a long test phase after the system is “feature complete”. Such a long test phase plays havoc with schedules as testing and debugging is impossible to schedule.

大多數軟體開發是一個混亂的開始，常常以一句話代以概括 ”撰寫！修復！“，這些軟體在撰寫時不用事先有基礎的計劃，也不用系統架構，將由短期項目討論就可以拼湊起來。這確切在系統很小時可以運作，但當系統越大時將會變得相當困難去增加新的功能。此外，BUG 也會越來越普遍見到，且越來越難除錯。這典型系統是在功能齊備後，才經由長時間的測試階段。這麼長時間的測試階段將嚴重破壞測試和除錯的行程，使得行程根本無法安排。試階段起著嚴重破壞的時間表為測試和調試是不可能的安排。

The original movement to try to change this introduced the notion of methodology. These methodologies impose a disciplined process upon software development with the aim of making software development more predictable and more efficient. They do this by developing a detailed process with a strong emphasis on planning inspired by other engineering disciplines - which is why I like to refer to them as engineering methodologies (another widely used term for them is plan-driven methodologies).

起源運動將要改變這種方法的概念，這些方法論所施加的紀律，將協助軟體開發變得更可預測和更有效率。他們將透過製定詳細的過程，這些過程特別強調設計，靈感來自于其他工程學門- 這就是為什麼我喜歡稱呼它們為 ”工程方法 enginerring methodologies“ (對於他們來說，另一個廣泛使用的術語為 “計劃驅動方法 plan-driven methodologies”)

Engineering methodologies have been around for a long time. They’ve not been noticeable for being terribly successful. They are even less noted for being popular. The most frequent criticism of these methodologies is that they are bureaucratic. There’s so much stuff to do to follow the methodology that the whole pace of development slows down.

工程方法已經存有一段歷史，它們都沒有被注目那背後可怕的成功，它們相當少被認為是受流行的，常見的批評為 ”它們是官僚政治的“ // 相當死板的 ？ 。有相當多的項目都遵循這套方法論使用緩慢的發展步伐。

Agile methodologies developed as a reaction to these methodologies. For many people the appeal of these agile methodologies is their reaction to the bureaucracy of the engineering methodologies. These new methods attempt a useful compromise between no process and too much process, providing just enough process to gain a reasonable payoff.

敏捷方法的發展就是反映這些工程方法論，對于大多數的人而言，敏捷方法的吸引力是反映出工程方法的官僚主義，這些新方法是在沒有進展和太多進展中的折衷妥協方案，提供一種恰當的過程來獲得合理回饋。

The result of all of this is that agile methods have some significant changes in emphasis from engineering methods. The most immediate difference is that they are less document-oriented, usually emphasizing a smaller amount of documentation for a given task. In many ways they are rather code-oriented: following a route that says that the key part of documentation is source code.

這一切的結過是，敏捷方法從工程方法中有顯的改變。最明顯的差異是少寫文件(文件導向)，通常強調少量文件的工作，在許多說法上，它們更偏向代碼導向(code-oriented: 文件的關鍵部分是源代碼 source code)

糟透的軟體開發

在土木工程中，建造一個橋來說，通常在設計草圖完成後，即使換了別的公司繼續接按下去做，一樣能按照這個設計草圖完成。如果在施工過程中遇到問題，通常問題也不會太難，而且非常容易被解決。

在了解這些設計草圖後，可以發現勞心者和勞力者的工作是分開的，設計由專家耗費心力完成，而實作能由工人來按照草圖，因此這些設計草圖是確保工人們能看得懂，但是在軟體工程中，大部分都是勞心者和勞力者集一人之中。

施工是一個相當耗費成本的工作，在早期的軟體工程開發專家，希望能將土木工程的方法轉移到軟體工程上。讓專家進行設計，再讓低成本的工作人員來完成實作，設計費用通常比實作費用來的低，工程師仍有高低薪之分，新一代的低薪工程師呢！

專家寫出來的設計草圖，要讓 programmer 看得懂，通常是非常困難的。即使是 UML 圖，雖然在紙(草圖)上看起來相當不錯，但是實作上的問題卻相當多，土木工程的設計圖可以經過數學模型去測試，但是軟體工程的設計圖只能由人腦去找到邏輯BUG，即使是設計熟練的專家，要設計出不會有實作問題的草圖也是常發生的。

接續著剛剛討論的造橋問題，設計費用只占了全部花費的十分之一，按照草圖寫 code 是相當簡單的，根據 McConnell 調查大型專案，只有 15% 的成本進行程式撰寫和測試(這裡我們需要勞力成本比例越高越好)。即使把其他成本混在一起，設計仍占了 50% 的成本比例。軟體工程只是工程分枝中之一，這其中一定有蹊蹺。

結論

  • 軟體的建造相當便宜，甚至於免費(只淤需要電腦和編譯器，沒有實體。)
  • 軟體受設計影響，因此需要有創造力和有天賦的人。
  • 俱有創新的程序不容易去規劃，可預測的性質甚至變成不可能。
  • 我們需要不同於傳統工程的方法，來解決這詭異的軟體工程的開發程序。

常常有開發者收到客戶不斷地改變需求，但是改變需求是常態，但是對於開發者而言卻是想不透的謎。這表示當初需求並沒有弄完整，但是也不能說像客戶簽訂契約——表示在軟體完成前，需求都不會改變。需求改變是很正常的，這客戶來說這個契約反而不合理。

按需求收費，加什麼功能要多少錢？估算收費也是不好量化，也會根據產品使用的方式和使用者有關，因此品質的水準與費用是不好預估。客戶以為“軟”體容易修改，但並不是每個需求都容易修改，通常會耗費大量的時間去滿足客戶的需求。

如果需求不穩定，就得不到可預測的計劃去完成軟體。

真的不可預測？

在 NASA 太空軟體開發中，他們的計劃是可以預測的，但這也只是一個特別的例子，主要原因是長期時間，龐大的團隊，穩定的需求。

更可怕的是，如果客戶需求不穩定，卻告知有可預測的計劃，這樣自欺欺人的行為相當令人詬病。

”可預測“是令人相當渴望的，這導致一開始擬定的計劃越飄越遠，最後計劃將會分崩離析。

按照方法論運行總是美好的，但是在軟體開發上必須要捨棄掉，但這樣的舉動相當困難，要捨棄一直以來處理事情的方式，但也並不是讓事情處理變得無法控制的混沌，捨棄“預測”吧！

控制 “不可預測”程序

使用迭代方式，並且將計劃越短越好，看起來就是多方面失敗的開始，但卻有機會看來進步的地方，當計劃越短，就能越早知道反饋(feedback)。

文件可以隱藏缺失，沒有經過測試將會有更多的缺失。

XP 一周或兩周，SCRUM 一個月之類的，越熟練則會越短時間。

=====

並不是每個工程師都像零件，換個人就可以繼續運行。

不可更換的人零件都跑了，也就是最有創意的人力都走了，可更換的人卻留下了。

Programmer 是有責任的專業人員？

早期是工廠的運行模式，希望能讓工人多做一點事情，來讓成本降低。

每個 programmer 是獨特的，產出的代碼也都不同，每一個人的創意不同，把人當資源就錯了。

施工和設計能不能分開？施工只是由編譯器來，因此軟體全是文創業，算是設計類型的職業。

Read More +