seke blog: 2008

2008年12月31日星期三

lowly and highly motivated

Keep lowly motivated to see how subtly things can go by themselves;
Keep highly motivated to see how far you can go by yourself.

常無欲以觀其妙;
常有欲以觀其徼.

參考:
1.http://www.shunto.org.hk/DaoDeiJinS/DaoDeiJin003.htm
「徼」有邊界、巡守之意:

2008年12月8日星期一

Evaluation Indices for Information Retrieval


資訊檢索評估指標計算法說明        2005/11/24-2008/12/8
==========================

假設某次查詢q1,資料集60篇中應有10篇相關文章,
  但系統傳回15篇文章中,只有5篇屬相關文章,
  現列出排名由高到低的15篇文章,如下,其中,+表相關,-表不相關,
        d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15
         +, -, +, -, -, +, -, -, -,  +,  -,  -,  -,  -,  +

則就此次q1查詢,可計算如下各項評估指標,

     機Y 機N   .0 60   +1 59   -2 58   +3 57   -4 56   -5 55  +6 54     +15 45
     -------    -----   ----    ----    ----    ----    ----   ----      -----
 人Y  TP  FN    0 10    1  9    1  9    2  8    2  8    2  8   3  7       5  5
 人N  FP  TN    0 50    0 50    1 49    1 49    2 48    3 47   3 47 ...  10 40

a.一次查詢曲線結果
  1.相關召回點準確率,P vs R, P@Rel
    (註: P=TP/(TP+FP), R=TP/(TP+FN),  FP=多進數,  FN=少進數)
        +   -   +   -   -   +   -   -   -   +   -   -   -   -   +
      R=0.1 0.1 0.2 0.2 0.2 0.3 0.3 0.3 0.3 0.4 0.4 0.4 0.4 0.4 0.5
      P=1/1 1/2 2/3 2/4 2/5 3/6 3/7 3/8 3/9 0.4 0.3 0.3 0.3 0.2 0.3

  2.標準11召回點準確率,P vs R (0%,10%,20%,...,100%), P@11Rel
    (註:當標準召回點無值或多值時,可用內插法,採計召回點以上最高準確率)
      R=0   0.1   0.2   0.3    0.4    0.5   0.6   0.7   0.8   0.9   1.0
      P=1   1/1   2/3   3/6    0.4    0.3     0     0     0     0     0

  3.標準3召回點準確率,P vs R (20%,50%,80%), P@3Rel
    (註:當標準召回點無值或多值時,可用內插法,採計召回點以上最高準確率)
      R=0.2       0.5       0.8
      P=2/3       0.3         0

  4.不相關出現點召回率(ROC接收器工作特性曲線),TP_rate vs FP_rate, ROC
    (註:相關正判率 TP_rate=TP/(TP+FN),不相關誤判率 FP_rate=FP/(FP+TN))
              +    -    +    -    -    +    -    -    -    +    -    -    -    -     +
      FP_rate=0/50 1/50 1/50 2/50 3/50 3/50 4/50 5/50 6/50 6/50 7/50 8/50 9/50 10/50 10/50
      TP_rate=1/10 1/10 2/10 2/10 2/10 3/10 3/10 3/10 3/10 4/10 4/10 4/10 4/10 4/10  5/10

  5.判別點準確率(lift chart提昇圖),TP vs subset_size, lift_chart
    (註: subset_size = (TP+FP)/(TP+FP+TN+FN))
                  +    -    +    -    -    +    -    -    -    +     -     -     -     -     +
      subset_size=1/60 2/60 3/60 4/60 5/60 6/60 7/60 8/60 9/60 10/60 11/60 12/60 13/60 14/60 15/60
                P=1    1    2    2    2    3    3    3    3    4     4     4     4     4     5

b.一次查詢單值結果
  6.準確率(P@ALL), P=TP/(TP+NP),NP=多進數,不應進而進
       P@ALL = 5 / (5 + 10)

  7.召回率(R@ALL), R=TP/(TP+FP)=TP_rate,FP=少進數,應進而未進
       R@ALL = 5 / (5 + 5)

  8.相關出現點平均準確率, AveP@Rel
       AveP@Rel = (1/1 + 2/3 + 3/6 + 4/10 + 5/15) / 5

  9.總相關數召回點準確率, R-value, R-precision, P@R-value
       P@R-value = 4/10

  10.最大召回準確率之調和平均數(F measure),F=2/(1/R+1/P), maxF
        +    -    +   -    -    +    -    -    -    +   -    -    -    -    +
      R=0.1  0.1  0.2 0.2  0.2  0.3  0.3  0.3  0.3  0.4 0.4  0.4  0.4  0.4  0.5
      P=1/1  1/2  2/3 2/4  2/5  3/6  3/7  3/8  3/9  0.4 0.3  0.3  0.3  0.2  0.3
      F=0.18 0.16 0.3 0.28 0.26 0.37 0.35 0.33 0.31 0.4 0.38 0.36 0.34 0.33 0.4
      maxF = 0.4

  11.前10名準確率, P@10
      P@10 = 4 / 10

  12.前10名平均準確率, AveP@10,average precision)
      AveP@10 = (1/1 + 1/2 + 2/3 + 2/4 + 2/5 + 3/6 + 3/7 + 3/8 + 3/9 + 4/10) / 10

  13.成功率, (TP+TN) / (TP+FP+TN+FN), SUCCESS_RATE
      SUCCESS_RATE = (5 + 40) / (5 + 10 + 40 + 5)

  14.相關綜合判別率, TP_rate*(1-FP_rate) = TP*TN/(TP+FP)/(FP+TN)
      Rel = 5 * 40 / (5+10) / (10 + 40)


假設有q1,q2,q3共計三次查詢,結果自資料集60篇文章中,
分別得到三次結果,如下,
      應該傳回相關文章數(TP+FN),10,15,20,
      實際傳回相關文章數(TP+FP),15,20,25,
      其中,真正相關文章數(TP),   5, 2, 6,
詳情如下,

  q1, +,-,+,-,-,+,-,-,-,+,-,-,-,-,+
  q2, -,-,-,+,-,-,-,+,-,-,-,-,-,-,-,-,-,-,-,-
  q3, -,+,-,-,+,-,+,-,-,-,+,-,-,-,+,-,-,-,-,-,+,-,-,-,-

       機Y 機N    q1 15 45    q2 20 40      q3 25 35
       -------       -----       -----         -----
  人Y  TP  FN         5  5        2 13          6 14
  人N  FP  TN        10 40       18 27         19 21

c.多次查詢曲線結果
  15.召回點準確率平均圖,MP@Rel
       仿照方法1,針對三次查詢,計算各召回點之準確率,再除以3,求平均

  16.內插標準11召回點平均準確率, MP@11Rel
       仿照方法2,針對三次查詢,計算11召回點之準確率,再除以3,求平均

  17.無內插相關召回點平均準確率(依相關文章召回數及查詢數作平均)
       q1_AveP@Rel = (1/1 + 2/3 + 3/6 + 4/10 + 5/15)/5
       q2_AveP@Rel = (1/4 + 2/8)/2
       q3_AveP@Rel = (1/2 + 2/5 + 3/7 + 4/11 + 5/10 + 6/16)/6
       MAveP@Rel = (q1_AveP@Rel + q2_AveP@Rel + q3_AveP@Rel) / 3

  18.特定相關數召回點平均準確率(前5,10,20,100相關文章召回點之查詢平均準確率)
       q1_P@5R = 5/10
       q2_P@5R = 無
       q3_P@5R = 5/10
       MP@5R = (q1_P@5R + q2_P@5R + q3_P@5R) / 3

  19.總相關數召回點平均準確率(前5,10,20,100相關文章召回點之查詢平均準確率)
       q1_P@R-value = 2/5
       q2_P@R-value = 0/2
       q3_P@R-value = 2/6
       MP@5R = (q1_P@R-value + q2_P@R-value + q3_P@R-value) / 3

d.多次查詢單值結果
  20.微觀平均準確率(micro average precision),依文章數作平均
       map = (5 + 2 + 6) / (15 + 20 + 25)

  21.巨觀平均準確率(macro average precision),依查詢數作平均
       MAP = (5/15 + 2/20 + 6/25) / 3

  22.前10名有正確之查詢比例 robust@10
       q1前10名有正確文章=true
       q1前10名有正確文章=true
       q1前10名有正確文章=true
       robust@10 = (1 + 1 + 1) / 3

  23.總相關數召回點之查詢平均準確率, MP@R-value
       q1總相關數召回點準確率=4/10
       q2總相關數召回點準確率=2/10
       q3總相關數召回點準確率=3/10
       MP@R-value = (4/10 + 2/10 + 3/10) / 3

  24.首相關排名之幾何平均數
       q1首相關排名=1
       q2首相關排名=4
       q3首相關排名=2
       幾何平均數=(1*4*2)^(1/3)

  25.MAP(mean average precision),平均精確率平均
       值介於0~1之間,越高越好,適用於二值相關度場合
       MAP(Q) = 1/|Q| Sum_from_j=1_to_|Q| 1/m_j Sum_from_k=1_to_m_j Precision(R_jk)
        Q:問題集, |Q|:問題數, m_j:問題j之應召回相關文件數,
        R_jk: 問題j排名結果中,由前取到第k份相關文件出現為止的文件集
        Precision(R_jk): 問題j第k份相關文件召回點之精確率
       = 1/3 * [  1/5 * (1/3 + 2/3 + 3/6 + 4/10 + 5/15)
                + 1/2 * (1/4 + 2/8)
                + 1/6 * (1/2 + 2/5 + 3/7 + 4/11 + 5/15 + 6/21)]

  26.NDCG(normalized discounted cumulative gain),前k名累計打折正確率
       值介於0~1之間,越高越好,適用於非二值相關度之機器學習場合
       NDCG(Q,k)=1/|Q| Sum_from_j=1_to_|Q| Zk Sum_from_m=1_to_k [2^R(j,m) - 1]/log(1+m)
        Q:問題集, |Q|:問題數,
        Zk:正規化因子,讓NDCG在完美排名(前k份文件全相關)下,其值為1,
        R(j,m): 問題j和文件m之相關度分數,介於0~1
        若問題j回傳文件數k'小於指定的k,則NDCG(Q,k)就只累計到k'
       例子: NDCG(Q,k=2)
       = 1/3 * {  Z2 * [(2^1-1)/log(1+1) + (2^0-1)/log(1+2)]
                + Z2 * [(2^0-1)/log(1+1) + (2^0-1)/log(1+2)]
                + Z2 * [(2^0-1)/log(1+1) + (2^1-1)/log(1+2)]}
       with Z2 = (2^1-1)/log(1+1) + (2^1-1)/log(1+2)

e.多次查詢表格結果
  25.查詢問題數,所有查詢傳回文章總數
       查詢問題數=3
       所有查詢傳回文章總數=60

  26.所有查詢傳回相關文章總數,所有查詢實際相關文章總數
       所有查詢傳回相關文章總數=15+20+25
       所有查詢實際相關文章總數=5+2+6

參考文獻
1.baezayates-aw-99-modern information retrieval
2.witten-mkp-99-managing gigabytes
3.witten-mkp-00-data mining- practical machine learning tools and techniques
4.manning-cup-08-introduction to information retrieval

2008年12月2日星期二

how to read big5 files in Java


/*
  ReadBig5File.java
  
    read a file in big5 code
  
  > javac ReadBig5File.java
  > java ReadBig5File big5.txt
  Big5編碼文字檔
*/
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class ReadBig5File
{
  public static void main(String args[]) throws
    java.io.FileNotFoundException,
    java.io.UnsupportedEncodingException,
    java.io.IOException
  {
    String file="big5.txt";
    FileInputStream fis = new FileInputStream(new File(file));
     // java.io.FileNotFoundException
    BufferedReader br =new BufferedReader(new InputStreamReader(fis,"BIG5"));
     // java.io.UnsupportedEncodingException
    
    // java.io.IOException
    while(br.ready())
    {
      String line=br.readLine();
      System.out.println(line);
      System.out.flush();
    }
    br.close();
  }
}

how to get unicode/big5 code in java String


/*
  ConvertBig5Unicode.java
  
    print string in big5 and unicode

  >javac ConvertBig5Unicode.java
  >java ConvertBig5Unicode
  查詢字串: 今天天氣很好
  查詢字串的統一碼 : 4eca 5929 5929 6c23 5f88 597d
  查詢字串的大五碼 : a4b5 a4d1 a4d1 aef0 abdc a66e
*/

import java.io.File;

// 如何取得java字串之unicode及big5碼
public class ConvertBig5Unicode
{
  public static void main(String args[]) throws java.io.UnsupportedEncodingException
  {
    String query="今天天氣很好";

    String unicode_query="";
    for(int i=0; i<=query.length()-1;i++)
    {
      if(query.charAt(i)>=0x100)
        unicode_query += Integer.toHexString(query.charAt(i)) + " ";
      else
        unicode_query += query.charAt(i);
    }

    byte [] big5_stream=query.getBytes("big5");
      // java.io.UnsupportedEncodingException

    String  big5_query="";
    for(int i=0; i<=big5_stream.length-1;i++)
    {
      int b1,b2;

      b1 = big5_stream[i];
      b2 = (i+1<=big5_stream.length-1)? big5_stream[i+1] : 0;

      b1 = (b1>=0) ? b1 : 0x100+b1;
      b2 = (b2>=0) ? b2 : 0x100+b2;

    //out.println("b1="+b1+",b2="+b2);

      if((b1 >= 0xa1 && b1 <= 0xf9) && ((b2 >= 0x40 && b2 <= 0x7e) || (b2 >= 0xa1 && b2 <= 0xfe)))
      {
        big5_query += Integer.toHexString(b1) + Integer.toHexString(b2) + " ";
        i++;
      }
      else
        big5_query += (char) big5_stream[i];
    }

    System.out.println("查詢字串: " + query);
    System.out.println("查詢字串的統一碼 : "+unicode_query);
    System.out.println("查詢字串的大五碼 : "+big5_query);
  }
}

2008年11月20日星期四

dataparksearch檢索系統安裝摘要


dataparksearch+mysql安裝摘要  2008.11.20.
----------------------------

http://www.dataparksearch.org/#download
http://www.dataparksearch.org/dpsearch-4.50.tar.bz2
http://www.dataparksearch.org/add-on/TraditionalChinese.freq.gz
http://www.appservnetwork.com/
http://prdownloads.sourceforge.net/appserv/appserv-win32-2.6.0.exe?download

1.解壓編譯佈署
    # 解開壓縮及包裝
    bunzip2 -c dpsearch-4.50.tar.bz2 | tar tvf -

    #產生編譯指令檔Makefile
    cd dpsearch-4.50/
    perl install.pl
      ...
      Enable support for extra charsets? yes
      ...
    或
    ./configure
      --prefix=/home/me/dataparksearch
      --bindir=/usr/local/dpsearch/bin
      --sbindir=/usr/local/dpsearch/sbin
      --sysconfdir=/usr/local/dpsearch/etc
      --localstatedir=/usr/local/dpsearch/var
      --libdir=/usr/local/dpsearch/lib
      --includedir=/usr/local/dpsearch/include
      --mandir=/usr/local/dpsearch/man
      --enable-shared
      --disable-syslog
      --enable-pthreads
      --enable-parser
      --enable-mp3
      --without-aspell
      --with-extra-charsets=all
      --enable-file
      --enable-http
      --enable-ftp
      --enable-htdb
      --enable-news
      --with-mysql=/usr/local/mysql/include

  #產生執行檔indexer,search.cgi等
  dpsearch-4.50/make

  #佈署組態檔.conf及執行檔indexer,search.cgi等
  dpsearch-4.50/make install

  #解壓佈署字典檔
  gunzip TraditionalChinese.freq.gz  #解開壓縮
  cp TraditionalChinese.freq /usr/local/dpsearch/etc/  #安裝中文字典

2.設定索引組態檔
  cd /usr/loca/dpsearch/etc/
  cp indexer.conf-dist indexer.conf #indexer使用
  vi indexer.conf
    DBAddr mysql://username:password@localhost/dpsearch/?dbmode=single
    LocalCharset BIG5    #資料庫字集
    RemoteCharset BIG5   #索引來源網站字集
    LoadChineseList BIG5 TraditionalChinese.freq  #中文字典位置
    #Include langmap.conf #載入太多字集,可能識別錯誤,宜用下行,只載入單一字集
    LangMapFile langmap/zh.big5.lm
    Server site http://your.server.name/path  索引網站下所有網頁
    Server path http://your.server.name/path  索引路徑下所有網頁
    Server page http://your.server.name/path  索引單一網頁

  #cp langmap.conf-dist langmap.conf
  #vi langmap.conf
  #  LangMapFile langmap/zh.big5.lm

  cp search.htm-dist search.htm  #search.cgi使用
  vi search.htm
    DBAddr mysql://user:password@localhost/dpsearch/?dbmode=single
    LocalCharset big5     #資料庫字集
    BrowserCharset big5   #顯示用字集

  cp stopwords.conf-dist stopwords.conf
  cp sections.conf-dist sections.conf

3.建立空白索引資料庫
  #啟動mysql資料庫服務
  service mysql start

  #建立dpsearch資料庫
  /usr/bin/mysqladmin -u root -p create dpsearch
    Enter password:

  #設定dpsearch資料庫供用戶user及密碼password使用
  /usr/bin/mysql -u root -p dpsearch
    Enter password:
    mysql> grant all privileges on dpsearch.* to user@localhost identified by 'password';
    mysql> flush privileges;
    mysql> quit

4.建立索引資料表大綱及內容
  /usr/local/dpsearch/sbin/indexer -Edrop    #清除舊大綱
  /usr/local/dpsearch/sbin/indexer -Ecreate  #建立新大綱
  /usr/local/dpsearch/sbin/indexer -a        #建立索引
  /usr/local/dpsearch/sbin/indexer -S        #索引狀態

5.耙取網頁建立索引資料庫
  /usr/local/dpsearch/sbin/indexer -Edrop    #清除舊大綱
  /usr/local/dpsearch/sbin/indexer -Ecreate  #建立新大綱
  #依據index.conf的Server指示起始位置,耗取網頁,建立索引
  /usr/local/dpsearch/sbin/indexer -a -v 5   #詳細訊息顯示索引過程

6.利用索引資料庫檢索網頁
  #啟動apache網頁伺服器服務
  service http start

  #建立檢索首頁,假設網頁伺服器首頁cgi路徑為/var/www/cgi-bin/
  cp /usr/local/dpsearch/bin/search.cgi /var/www/cgi-bin/

  #利用瀏覽器開啟檢索首頁
  firefox http://localhost/cgi-bin/search.cgi

7.中文索引問題
  a.網頁字集判別錯誤,可依下法知道是否判別錯誤,
     /usr/local/dpsearch/sbin/dpguesser [-n maxhits] < web.htm
 444h 214m       zh      Big5
 58h 235m        zh      GB2312
 118h 235m       es      ISO-8859-1
 136h 235m       ja      UTF-8
     或
     /usr/local/dpsearch/sbin/indexer -v 5
        indexer[16184]: {01} Guesser: Lang: zh, Charset: Big5

     解決法為減少自動識別的字集,最好indexer.conf只用一種字集即可,如下,
       #Include langmap.conf
       LangMapFile langmap/zh.big5.lm

  b.參考http://www.dataparksearch.org/dpsearch-international.en.html


註:
1.以上資料部份參考mikanagi-tku-06-search_engines gais and dataparksearch.ppt
2.dataparksearch計畫來自mnogosearch(www.mnogosearch.org)計畫,兩者差異如下,
   dataparksearch: gpl, sql/cache, linux
   mnogosearch: gpl, sql, windows, shareware

2008年10月13日星期一

dataparksearch安裝摘要


dataparksearch+mysql安裝摘要
----------------------

http://www.dataparksearch.org/#download
http://www.dataparksearch.org/dpsearch-4.50.tar.bz2
http://www.dataparksearch.org/add-on/TraditionalChinese.freq.gz
http://www.appservnetwork.com/
http://prdownloads.sourceforge.net/appserv/appserv-win32-2.6.0.exe?download

安裝
  產生Makefile
    ./install.pl
      Enable support for extra charsets? yes
    或
    ./configure
      --prefix=/home/me/dataparksearch 
      --bindir=/usr/local/dpsearch/bin 
      --sbindir=/usr/local/dpsearch/sbin 
      --sysconfdir=/usr/local/dpsearch/etc
      --localstatedir=/usr/local/dpsearch/var
      --libdir=/usr/local/dpsearch/lib 
      --includedir=/usr/local/dpsearch/include 
      --mandir=/usr/local/dpsearch/man 
      --enable-shared 
      --disable-syslog 
      --enable-pthreads 
      --enable-parser 
      --enable-mp3 
      --without-aspell 
      --with-extra-charsets=all 
      --enable-file 
      --enable-http 
      --enable-ftp 
      --enable-htdb 
      --enable-news 
      --with-mysql=/usr/local/mysql/include
  產生sbin/indexer等執行檔
    make
  佈署執行檔,組態檔
    make install 

建立資料庫
  mysqladmin create search
  /usr/local/dpsearch/sbin/indexer –Ecreate

設定組態檔
  cd /usr/loca/dpsearch
  cp indexer.conf-dist indexer.conf
    DBAddr mysql://foo:bar@localhost/dpsearch/?dbmode=mulit
    LocalCharset BIG5
    LoadChineseList BIG5 TraditionalChinese.freq
    Server http://your.server.name  ### 耙取起始網址
  cp langmap.conf-dist langmap.conf
    LangMapFile langmap/zh.big5.lm
  cp search.htm-dist search.htm
  cp stopword.conf-dist stopword.conf
  cp sections.conf-dist sections.conf

耙取網頁
  將search.cgi放到cgi-bin目錄下
  耙取索引網頁
    /usr/local/dpsearch/sbin/indexer -a

檢索網頁
  http://localhost/cgi-bin/search.cgi

2008年7月13日星期日

remote disk over ssh


http://www.nikhef.nl/~janjust/CifsOverSSH/Howto_Loopback.html
 WindowsXP-KB884020-x86-cht.exe, non 127.0.0.1 loopback patch
 --
 ssh -Llocal_loopback:139:remote_netbios_server:139 remote_ssh_server
 --
 local_loopback:
  ip=10.0.0.1/30
  metric=9999
  netbios over tcpip=disabled
  client for microsoft networks=unchecked
  file and printer sharing for microsoft networks=unchecked

 local_interface:
  netbios over tcpip=disabled
  client for microsoft networks=unchecked

ssh auto login without password

#
# run to get /etc/ssh_config, /etc/sshd_config
ssh-host-config

# run to get ~/.ssh/id_rsa.pub
ssh-user-config

# append id_rsa.pub to remote key store
cat ~/.ssh/id_rsa.pub | ssh user@host "cat >> .ssh/authorized_keys"

2008年5月28日星期三

5 kinds of event handler styles

依處理器所掛的位置,總共有5種寫法,以計時器處理器為例,
A.處理器掛在外部類別下:

 import javax.swing.Timer;
 import java.awt.event.ActionListener;
 import java.awt.event.ActionEvent;
 public class TimerTest1
 {
   public static void main(String args[]) throws Exception
   {
     ActionListener al = new TimerHandler();
     Timer t = new Timer(1000,al);
     t.start();
     Thread.sleep(10000);
     t.stop();
   }
 }
 
class TimerHandler implements ActionListener
 {
   public void actionPerformed(ActionEvent ae)
   {
     System.out.println("執行每次叫醒要作的事1");
   }
 }


B.處理器掛在內部匿名類別下:

 import javax.swing.Timer;
 import java.awt.event.ActionListener;
 import java.awt.event.ActionEvent;
 public class TimerTest2
 {
   public static void main(String args[]) throws Exception
   {
     ActionListener al = new ActionListener()
       {
  public void actionPerformed(ActionEvent ae)
  {
    System.out.println("執行每次叫醒要作的事2");
  }
       };
     Timer t = new Timer(1000,al);
     t.start();
     Thread.sleep(10000);
     t.stop();
   }
 }


C.處理器掛在內部有名類別下:

 import javax.swing.Timer;
 import java.awt.event.ActionListener;
 import java.awt.event.ActionEvent;
 public class TimerTest3
 {
   public static void main(String args[]) throws Exception
   {
     new TimerTest3();
   }

   TimerTest3() throws Exception
   {
     ActionListener al = new TimerHandler();
     Timer t = new Timer(1000,al);
     t.start();
     Thread.sleep(10000);
     t.stop();
   }

   private class TimerHandler implements ActionListener
   {
     public void actionPerformed(ActionEvent ae)
     {
       System.out.println("執行每次叫醒要作的事3");
     }
   }
 }


D.處理器掛在本身類別下:

 import javax.swing.Timer;
 import java.awt.event.ActionListener;
 import java.awt.event.ActionEvent;
 public class TimerTest4 implements ActionListener
 {
   public void actionPerformed(ActionEvent ae)
   {
     System.out.println("執行每次叫醒要作的事4");
   }

   public static void main(String args[]) throws Exception
   {
     ActionListener al = new TimerTest4();
     Timer t = new Timer(1000,al);
     t.start();
     Thread.sleep(10000);
     t.stop();
   }
 }


E.處理器同時掛在內部和外部類別下:

 import javax.swing.Timer;
 import java.awt.event.ActionListener;
 import java.awt.event.ActionEvent;
 public class TimerTest5
 {
   public static void main(String args[]) throws Exception
   {
     ActionListener al = new ActionAdapter()
       {
  public void actionPerformed(ActionEvent ae)
  {
    System.out.println("執行每次叫醒要作的事5x");
  }
       };
     Timer t = new Timer(1000,al);
     t.start();
     Thread.sleep(10000);
     t.stop();
   }
 }

 class ActionAdapter implements ActionListener
 {
   public void actionPerformed(ActionEvent ae)
   {
     System.out.println("執行每次叫醒要作的事5");
   }
 }

2008年5月22日星期四

cisco nat usage


 inside local ip, 內部私有ip
 inside global ip, 內部私有ip之對外公開代表ip
 outside global ip, 外部公開ip
 outside local ip, 外部公開ip之對內私有代表ip
 --
 ilip olip (內) NAT路由器 (外) igip ogip
 --
 nat分一對一,一對多,多對一,多對多轉址
  一對一,靜態,單址對應到單址
  一對多,動態,單址對應到池群,輪流負載平衡
  多對一,動態,清單群對應到單址,埠超載
  多對多,動態,清單群對應到池群,埠超載
  --
  清單群(list number/name)
   基本清單(限定來源),擴張清單(限定來源去處,埠號)
  池群(pool name)
   IP範圍起終點,遮罩
  負載平衡(type rotary)
  埠超載(port overload)
 --
 nat分動態(dynamic)及靜態(static)轉址
  動態只具單向連線性,內可主動連外,外則不可主動連內
  靜態則具雙向連線性,內可主動連外,外也可主動連內
 --
 ip nat inside source 內清單群 外池群/單址
  用於內向外的來源住址轉換,ilip 內->外 igip
  將內部發出之私有來源住址轉成外部公開來源住址
  可保護內部電腦不為外界入侵

 ip nat inside destination 外清單群 內池群/單址
  用於外向內的目的住址轉換,ilip 內<-外 igip
  將外部發出之公開目的住址轉成內部私有目的住址
  可作內部伺服器對外之負載平衡

 ip nat outside source 外清單群 內池群/單址
  用於外向內的來源住址轉換,olip 內<-外 ogip
  將外部發出之公開來源住址轉成內部私有來源住址
  可作對稱式連外路由,或重疊網路間之橋樑,內部有外部公開住址

 ip nat outside destination 內清單群 外池群/單址
  用於內向外的目的住址轉換,olip 內->外 ogip
  將內部發出之私有目的住址轉成外部公開目的住址
  可限制內部對外連線對象

2008年5月21日星期三

strut, glue, rigid area in BoxLayout


盒子排版器(BoxLayout)有3種無互動,純佔面積用之視窗元件可用,
摘要如下,


1.strut (支架)
Component v = Box.createVerticalStrut(h); //新增隱形固定高度h像素之垂直支架
Component h = Box.createHorizontalStrut(w); //新增隱形固定寬度w像素之水平支架

2.glue (黏膠)
Component v = Box.createVerticalGlue(); //新增隱形垂直等間隔黏膠
Component h = Box.createHorizontalGlue(); //新增隱形水平等間隔黏膠
Component g = Box.createGlue(); //新增隱形等間隔黏膠,適用於垂直或水平盒子排版器

3.rigid area (硬塊), 相當於2維支架
Dimension d = new Dimension(h,w);  // 新增寬h,高w尺寸
Component ra = Box.createRigidArea(d); // 依給定尺寸新增隱形硬塊

PS:
deitel-php-05-java how to program 6th ed

2008年4月24日星期四

time complexity for sorting algorithms

時間複雜度             最差        平均
選擇排序              O(n²)       O(n²)
氣泡排序              O(n²)       O(n²)
插入排序              O(n²)       O(n²)
快速排序              O(n²)       O(n*log(n))
樹形排序              O(n²)       O(n*log(n))
合併排序              O(n*log(n))  O(n*log(n))
堆積排序              O(n*log(n))  O(n*log(n))
謝耳排序              O(n^1.5)     O(n^1.25)
數元排序(限整數)      O(n)         O(n)

參考:
1.carrano-pie-05-data abstraction & problem solving with java
2.weiss-pie-04-data structures & problem solving using java
3.budd-awl-00-classic data structures in java

weka.classifiers.rules


weka.classifiers.rules
  ConjunctiveRule, 連言規則
        適用於類別/數值預測
        利用單條連言(and)規則作預測
          若規則未涵蓋新案例,傳回過去案例之類別分佈或平均值
        規則前件成長法:依條件加入前後之資訊增量為指標,留大者
          分類之資訊量為規則涵蓋及未涵蓋案例資訊量之加權平均值
          迴歸之資訊量為規則涵蓋及未涵蓋案例均方差之加權平均值
        規則前件修剪法:
          若長前修剪策略,限定其前件許可之條件數;
          若長後修剪策略,使用縮減錯誤修剪法
            分類之指標為修剪集中,涵蓋與否案例正確率之加權平均值,變大則修剪
            迴歸之指標為修剪集中,涵蓋與否案例均方差之加權平均值,變小則修剪
        參數:
          exclusive: [false] 名目屬性分叉時考慮排他測試條件,例如,某屬性不為某屬性值
          folds: [3] 訓練集分割組數,其中1組保留作縮減錯誤修剪,其餘供長規則用
          minNo: [2.0] 規則最少案例權重數
          numAntds: [-1] 若>=0,表採用長前修剪策略,其許可前件之條件數;
                        若-1,表採用長後修剪策略,使用縮減錯誤修剪法

  DecisionTable, 決策表
        適用於類別/數值預測
        利用最佳優先搜尋法,以交叉驗證錯誤率為指標,找出最佳屬性子集合
        預測時遇決策表未涵蓋新案例,使用k最近鄰居法,或多數決法
        參數:
          crossVal: [1] 交叉驗證切割組數,1表只保留一測試案例,餘供訓練
          maxStale: [5] 放棄搜尋前,能忍受指標無進步之試走步數
          useIBk: [false] 遇未涵蓋新案例,使用k最近鄰居法,否則使用多數決法
        kohavi-ecml-95-the power of decision tables

  JRip,
        適用於類別預測
        實作ripper分裂演算法,具啟發式規則集全域優化功能
          依案例由少到多類別順序,逐一產生各類別規則集,如下
            1.類別C規則集建造階段
              1.1.以2:1比例分割案例集為新成長集及修剪集
              1.2.重複以下前件成長,修剪動作,直到以下任一條件滿足
                a.類別C案例無前件未涵蓋案例剩下
                b.規則集及未涵蓋案例之描述長度
                  比目前為止最小描述長度,還長超過64位元
                c.錯誤率超過0.5
              1.2.1.前件成長期
                    依資訊增量指標,貪婪(局部最佳)添一前件條件,直到正確率100%
                    條件測試形式為"若某屬性為某屬性值"
                    資訊增量=p(log(p/(p+n))-log(P/(P+N)))
              1.2.2.前件修剪期
                    由後往前逐一試修剪規則前件最後一個條件
                    只要修剪後規則價值有提昇,就繼續修剪
                    規則價值=(p+1)/(p+n+2)
            2.類別C規則集優化階段
              2.1.逐一檢視各規則R
              2.1.1.重新2:1分割案例集為新成長集及修剪集
              2.1.2.剔除修剪集已由其他規則涵蓋(前件符合)之案例
              2.1.3.利用成長集案例
                    貪婪添一前件條件,長出新規則R1
                    從無到有產生一條新規則R2
              2.1.4.利用修剪集案例,修剪R1,R2
                    但規則價值=(p+N-n)/(P+N)
              2.1.5.就R,R1,R2三者,挑選描述長度最短者留下,餘刪除
              2.2.優化後若還有未涵蓋案例,回到1.
              2.3.逐一檢視各規則,若加入會增加規則集描述長度,則刪除之
                  自案例集移除由規則集涵蓋之案例
            註:p,n為規則涵蓋之正反案例數;P,N為類別C之正反案例數
        參數:
          checkErrorRate: [true] 利用錯誤率>=0.5作為終止條件
          folds: [3] 訓練集分割組數,其中1組保留作縮減錯誤修剪,其餘供長規則用
          minNo: [2.0] 每條規則最少案例數
          optimizations: [2] 規則集全域優化次數
          usePruning: [true] 縮減錯誤修剪
        cohen-icml-95-fast effective rule induction

  M5Rules
        適用於數值預測
        利用M5P線性模型樹,產生決策清單
        參數:
          buildRegressionTree: [false] 建迴歸樹,否則只有樹根長葉節點模型
          minNumInstances: [4.0] 各葉節點最少案例數
          unpruned: [false] 不修剪
          useUnsmoothed: [false] 預測數值時不平滑化處理
        hall-ajcai-99-generating rule sets from model trees

  Nnge, Nearest Neighbor GEneralization 最佳鄰居一般化
        適用於類別預測
        仿最近鄰居演算法,利用不相互包含之一般化範例(超矩形規則)作預測
        參數:
          numAttemptsOfGeneOption: [5] 一般化嚐試次數
          numFoldersMIOption: [5] 計算相似資訊量之組數
        roy-ucnz-02-nearest neighbor with generalization
        martin-uwnz-95-instance-based learning- nearest neighbor with generalization

  OneR, One Rule 單規則
        適用於類別預測
        只測試單屬性及值,挑選錯誤最小者,形成單規則
        遇數值屬性會自動分割區間離散化,每區間多數類別案例至少minBucketSize個
        holte--93-very simple classification rules perform well on most commonly used datasets". Machine Learning, Vol. 11, pp. 63-91.

  Part, 零件
        適用於類別預測
        利用移開再征服(separate and conquer)策略,產生決策清單
        每回利用c4.5產生部份決策樹,挑最好葉節點轉成規則
        參數:
          binarySplits: [false] 名目屬性作二元分叉
          confidenceFactor: [0.25] 估錯誤率上限之信心水準,愈小修剪愈多
          minNumObj: [2] 規則最少案例數
          numFolds: [3] 訓練集分割組數,其中1組保留作縮減錯誤修剪,其餘供長樹用
          reducedErrorPruning: [false]  縮減誤差修剪法,否則沿用c4.5修剪法
          unpruned: [true] 樹不修剪
        frank-icml-98-generating accurate rule sets without global optimization

  Prism, 稜鏡
        適用於類別預測,名目屬性,無缺值
        不修剪
        cendrowska-ijmms-87-prism- an algorithm for inducing modular rules

  Ridor, RIpple DOwn Rule 漣漪下移規則
        適用於類別預測
        能產生含例外之規則集
        先產生預設規則,再利用累進縮減錯誤修剪,產生錯誤率最低之最佳例外規則集.
          再就每一例外規則產生最佳例外規則集,迭代直到案例變純剩單類別無例外為止.
        參數:
          folds: [3] 訓練集分割組數,其中1組保留作縮減錯誤修剪,其餘供長樹用
          majorityClass: [false] 多數類別為預設值
          minNo: [2.0] 規則最案例權重數
          shuffle: [1] 每條規則產生前所需案例洗牌次數,若>1,將留下其中最準確者
          wholeDataErr: [false] 依全部案例計算規則價值,否則依前件涵蓋案例計算

  ZeroR, Zero Rule 零規則
        適用於類別/數值預測
        以案例集之眾數類別/平均值,預測類別/數值.

weka.classifiers.trees


weka.classifiers.trees
  ADTree, Alternating Decision Tree 交替決策樹
        適用於雙類別預測
        以推進法,累進新增節點長出選項樹,具分叉及預測兩類節點
          典型推進法如LogitBoost套在底層ConjunctiveRule學習器上
        預設推進次數為10,每次推進若無合併,可新增一分叉節點及二預測節點
          推進次數愈多,模型愈複雜,但效果不一定好,要手調適當參數
        擴張路徑方法
                Expand all paths (預設,所有路徑都長,最慢)
                Expand the heaviest path
                Expand the best z-pure path
                Expand a random path
        freund-icml-99-the alternating decision tree learning algorithm

  DecisionStump, 決策樹根
        適用於類別/數值預測,接受缺值(長第3分叉),常作為推進法之底層學習器
        建立單節點雙分叉決策樹,只允許依某屬性為某值與否作二元分叉
        遇缺值可再加一未知值分叉

  Id3,
        適用於類別預測,名目屬性,無缺值
        節點分裂屬性挑法:利用資訊增益比為指標,留大者
                資訊增益比=分裂前後資訊增量/分裂資訊量
        無樹修剪,空案例葉節點會造成無法分類情形
        quinlan-ml-86-induction of decision trees

  J48, 即c4.5
        適用於類別預測
        節點分裂屬性挑法:利用資訊增益比為指標,留大者
        遇數值屬性,限定用二元分叉,分叉點選擇利用資訊增量為指標
        遇缺值,採用案例分解碎片再匯總作法
        修剪策略:長後修剪,從葉至根測試子樹替換或子樹提昇之錯誤率是否下降
          計算錯誤率方法,可採用縮減誤差修剪法,利用保留之修剪案例為之
        參數:
          binarySplits: [false] 名目屬性作二元分叉
          confidenceFactor: [0.25] 估錯誤率上限之信心水準,愈小修剪愈多
          minNumObj: [2] 葉節點最少案例數
          numFolds: [3] 訓練集分割組數,其中1組保留作縮減錯誤修剪,其餘供長樹用
          reducedErrorPruning: [false]  縮減誤差修剪
          subtreeRaising: [false] 子樹提昇修剪,較費時
          unpruned: [true] 樹不修剪
          useLaplace: [false] 輸出葉節點之類別分佈機率時是否平滑化
        quinlan-mkp-93-c4.5: programs for machine learning

  LMT, Logistic Model Tree 邏輯模型樹
        適用於雙/多類別預測
        決策樹葉節點為各類別之線性邏輯模型
        節點分裂屬性挑法:利用推進法殘差(留小者)或資訊增量(留大者)為指標
        利用LogitBoost推進法,套在底層簡單線性迴歸器,
                每次推進,找出一個誤差最小之屬性疊加到線性邏輯模型上
                推進結束時,即得一最大概似率之多元邏輯迴歸模型
        參數:
          convertNominal: [false] 名目屬性轉為多個二值屬性,採二元分叉
          errorOnProbabilities: [false] 交叉驗證指標依機率均方根值,否則依誤判數
          fastRegression: [true] 各節點推進次數統一由一次交叉驗證決定
          minNumInstances: [15] 節點要最少多少案例才考慮分裂
          numBoostingIterations: [-1] 固定推進次數,-1表依各節點交叉驗證決定
          splitOnResiduals: [false] 節點分裂依殘差指標,否則依資訊增量指標
        landwehr-ecml-03-logistic model trees

  M5P, Model 5 Prime 多元線性模型樹
        適用於數值預測
        決策樹葉節點為多元線性模型
        節點分裂屬性挑法:利用案例之標準差降低量sdr為指標,留大者
        分裂屬性時永遠採二元分叉
          遇數值屬性,依數值排序,測試每個分割點,計算sdr取大者
          遇k值名目屬性,先轉為k-1個合成二值屬性,依各合成屬性平均值排序,
                再測試每個分割點,計算sdr取大者
        遇缺值,於訓練選分裂屬性時,依缺值案例佔目前案例之比例,縮小sdr值
                於訓練分配案例時,先算無缺值而歸屬左右分叉之兩案例數值平均值
                  再依缺值案例之數值是否大於兩平均值之平均值,而歸屬適當一方
                  等訓練長樹結束時,所有缺值由其所處葉節點案例平均值取代
                  註:此法為找出最相關屬性作代理分裂(surrogate split)之簡化版
                於測試分配案例時,缺值由同時到達該內部節點之訓練案例平均值取代
        修剪策略:採長後修剪,從葉至根測試子樹替換回葉節點之錯誤率是否下降
          葉節點之線性迴歸模型,其自變數則取自原子樹各內部節點屬性
          葉節點錯誤率為將目前案例之實際減預測的殘差平均值,再作悲觀放大
                放大比例為(n+v)/(n-v),n為訓練案例數,v為悲觀度調整值
          內部節點(即子樹)錯誤率為其左右兩子樹錯誤率之案例數比重加總
        預測數值時,利用樹根到葉節點路徑上之所有模型作平滑化處理
        參數:
          buildRegressionTree: [false] 建迴歸樹,否則只有樹根長葉節點模型
          minNumInstances: [4.0] 各葉節點最少案例數
          unpruned: [false] 不修剪
          useUnsmoothed: [false] 預測數值時不平滑化處理
        wang-ecml-97-induction of model trees for predicting continuous classes
        quinlan-ajcai-92-learning with continuous classes

  NBTree, Naive Bayes Tree 簡單貝氏樹
        適用於類別預測
        混用決策樹及簡單貝氏兩學習器
        決策樹葉節點為簡單貝氏分類器
        利用交叉驗證判別節點要分裂成內部節點,或維持貝氏模型葉節點
        kohavi-ickddm-96-scaling up the accuracy of naive-bayes classifiers- a decision tree hybrid

  RandomForest, 亂數森林
        適用於類別預測
        利用重複取樣聚合法(bagging),建立給定顆亂數樹
        參數:
          numFeatures: [0] 分裂屬性自多少最佳屬性中亂數取一, 0表3
          numTrees: [10] 打算長出幾顆樹
          seed: [1] 挑分裂屬性之亂數種子
        breiman-ml-01-random forests

  RandomTree, 亂數樹
        適用於類別預測
        節點分裂屬性挑法:每回自給定個最佳屬性中亂數取一
        不作節點修剪
        參數:
          KValue: [1] 分裂屬性自多少最佳屬性中亂數取一
          minNum: [1.0] 葉節點最少案例權重數
          seed: [1] 挑分裂屬性之亂數種子

  REPTree, Reduced-Error Pruning Tree 縮減誤差修剪樹
        適用於類別/數值預測
        節點分裂屬性挑法:利用資訊增量/變異數,快速長出決策/迴歸樹,
        修剪策略:長後修剪,利用縮減誤差修剪法
          參數nFolds為訓練集分割組數,其中1組保留作縮減錯誤修剪,其餘供長樹用
        數值屬性只排序一次,以加快學習速度
        遇缺值同c4.5,採用案例分解碎片再匯總作法
        可設定其他參數
          minNum: 葉節點最小案例總權重,預設值2
          minVarianceProp: 案例變異數需佔原始訓練集多少比例以上才作節點分裂
                預設值:0.001,適用於預測對象為數值時
          maxDepth: 長樹最大深度限制,預設值-1,代表無限制,適用於搭配推進法時

  UserClassifier, 用戶分類器
        適用於類別/數值預測
        節點分裂屬性挑法:人工一次挑選任兩屬性之適當2維區間作節點分裂用

2008年4月23日星期三

weka.classifiers.bayes


weka.classifiers.bayes 只適用於分類
  AODE, Averaged, One-Dependence Estimator 平均單相依估算器
      適用於屬性相依
      建立一群允許單對屬性相依之候選貝氏模型,求其平均結果
      webb-ml-05-not so naive bayes- aggregating one-dependence estimators

  BayesNet,貝氏網路
      適用於屬性相依,名目屬性(遇數值會先離散化),無缺值(遇缺值會補值)
      估算貝氏網路條件機率表方法,weka.classifiers.bayes.net.estimate
          BayesNetEstimator
          BMAEstimator
          MultiNominalBMAEstimator
          SimpleEstimator
      搜尋貝氏網路結構方法,weka.classifiers.bayes.net.search.local
          GeneticSearch
          HillClimber
          K2 (預設選項,預設節點最大親節點數為1)
          LocalScoreSearchAlgorithm
          RepeatedHillClimber
          SimulatedAnnealing
          TabuSearch
          TAN
          註:搜尋指標為條件獨立性檢定值
      可利用AD樹資料結構犧牲記憶體,以加快速度

  ComplementNaiveBayes,互補簡單貝氏
      適用於屬性獨立,屬性表示關鍵詞TFIDF值之文件分類
      rennie-aaai-03-tackling the poor assumptions of naive bayes text classifiers

  NaiveBayes,簡單貝氏
      適用於屬性獨立,數值屬性不符合常態分配情形
      數值屬性支援核心密度估算子推估機率及監督式離散化

  NaiveBayesMultinomial,簡單貝氏多項版
      適用於屬性獨立,屬性表示關鍵詞出現次數之文件分類

  NaiveBayesSimple,簡單貝氏簡化版
      適用於屬性獨立,數值屬性符合常態分配情形
      數值屬性採用常態分配模型推估機率

  NaiveBayesUpdateable,簡單貝氏累進版
      適用於累進學習場合
      數值屬性支援核心密度估算子,不支援離散化

2008年4月16日星期三

jpanel.requestFocus on mouseEntered

Java Swing元件中，無法敲字進入JPanel畫板，理由主要在畫板尚未取得鍵盤焦點。一個視窗收到鍵盤事件要送給誰，是由處於鍵盤焦點之元件來決定。這樣的鍵盤焦點一個視窗一次只能存在一個接收元件。故想要畫板隨著滑鼠移入即可接收鍵盤事件，作法為設定畫板監聽mouseEntered事件，一旦發現滑鼠移入，立即利用jpanel.requestFocus()方法，設定畫板自己為鍵盤焦點。範例如下。


/*
  KeyPanel.java
  
    Demo for receiving key events in a jpanel
*/
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class KeyPanel extends JFrame
{
  JPanel centerPanel; // 打算敲字之畫板
  JTextField txtField; // 顯示所敲字之文字盒

  public KeyPanel()
  {
    centerPanel = new JPanel();
    centerPanel.setBackground(Color.pink);
    centerPanel.addKeyListener(new KeyAdapter()
    {
      public void keyTyped(KeyEvent ke)
      {
        char k = ke.getKeyChar();

        txtField.setText("keyTyped=" + k); // 顯示接收鍵盤字元
      }
    });

    centerPanel.addMouseListener(new MouseAdapter()
    {
      public void mouseEntered(MouseEvent me)
      {
        centerPanel.requestFocus(); // 滑鼠移入時自動取得鍵盤焦點
      }
    });

    this.add(centerPanel, BorderLayout.CENTER);

    txtField = new JTextField();
    this.add(txtField, BorderLayout.NORTH);
  }

  public static void main(String args[]) // 主程式
  {
    KeyPanel df = new KeyPanel();
    df.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    df.setSize(600, 400);
    df.setVisible(true);
  }
}

2008年4月14日星期一

inner.java, a sample code for 6 kinds of java classes inside classes/methods

/*

  Inner.java

    Demo for a variety of inner classes which include

1. static nested classes: 類別內具名靜態類別 InClassStaticClass
 no associated outer class instance.

2. inner nested classes: 類別內具名非靜態類別 InClassInstanceClass
 with an associated outer class instance.

3. anonymous classes: 方法內匿名類別 adapted from InMethodUnnamedClass
 unnamed inner class defined in the middle of a method.

4. local classes: 方法內具名類別 InMethodStaticClass, InMethodInstanceClass
 named inner class defined in the middle of a method.

實際展示6種內部類別(inner class)寫法:
 1.類別內具名靜態類別,InClassStaticClass
 2.類別內具名非靜態類別,InClassInstanceClass
 3.類別方法內具名靜態類別,InMethodStaticClass
 4.物件方法內具名非靜態類別,InMethodInstanceClass
 5.類別方法內匿名靜態類別,adapted from InMethodUnnamedClass
 6.物件方法內匿名非靜態類別,adapted from InMethodUnnamedClass

Note:
 1.StaticClass can directly instantiate without an instance.
   An inner InstanceClass can have static and instance members,
   but can only access outer class static members.
   Members include attributes and methods.
   Most classes are named StaticClass.
 2.InstanceClass must instantiate from an instance.
   An inner InstanceClass can only have instance members,
   but can access outer class static and instance members.
 3.Methods provide a non-static context and
   do not allow static declarations inside.
   All intra method inner classes can add
   new instance but not static members.
 4.Unnamed inner classes are adapted inline from known classes,
   and must be in a method, not in a class.
   They can add new instance but not static members and
   access old public but not private members of known classes.

Ref:
  http://www.blogjava.net/blackbat/archive/2006/10/04/73352.html

 執行方法及結果

> javac Inner.java
> java Inner
我是<外部類別OuterClass>物件,擁有
    類別屬性outerStaticAttribute
    物件屬性outerInstanceAttribute
    類別方法outerStaticMethod
    物件方法outerInstanceMethod

1.使用類別內具名靜態類別...
我是<類別內具名靜態類別InClassStaticClass>物件,擁有
    類別屬性innerStaticAttribute
    物件屬性innerInstanceAttribute
    類別方法innerStaticMethod
    物件方法innerInstanceMethod
 從類別方法innerStaticMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 內部類別之類別屬性innerStaticAttribute
  呼叫 外部類別之類別方法outerStaticMethod
 從物件方法innerInstanceMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 內部類別之類別屬性innerStaticAttribute
  存取 內部類別之物件屬性innerInstanceAttribute
  呼叫 外部類別之類別方法outerStaticMethod

2.使用類別內具名非靜態類別...
我是<類別內具名非靜態類別InClassInstanceClass>物件,擁有
    x類別屬性
    物件屬性innerInstanceAttribute
    x類別方法
    物件方法innerInstanceMethod
 從物件方法innerInstanceMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 外部類別之物件屬性outerInstanceAttribute
  存取 內部類別之物件屬性innerInstanceAttribute
  呼叫 外部類別之類別方法outerStaticMethod
  呼叫 外部類別之物件方法outerInstanceMethod

3.使用類別方法內具名靜態類別...
我是<方法內具名靜態類別InMethodStaticClass>物件,擁有
    x類別屬性
    物件屬性innerInstanceAttribute
    x類別方法
    物件方法innerInstanceMethod
 從物件方法innerInstanceMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 內部類別之物件屬性innerInstanceAttribute
  呼叫 外部類別之類別方法outerStaticMethod

4.使用物件方法內具名非靜態類別...
我是<方法內具名非靜態類別InMethodInstanceClass>物件,擁有
    x類別屬性
    物件屬性innerInstanceAttribute
    x類別方法
    物件方法innerInstanceMethod
 從物件方法innerInstanceMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 外部類別之物件屬性outerInstanceAttribute
  存取 內部類別之物件屬性innerInstanceAttribute
  呼叫 外部類別之類別方法outerStaticMethod
  呼叫 外部類別之物件方法outerInstanceMethod

5.使用類別方法內匿名靜態類別...
我是<方法內匿名靜態類別 adapted from InMethodUnnamedClass>物件,擁有
    類別屬性innerStaticAttribute.2
    物件屬性innerInstanceAttribute,2,3
    類別方法innerStaticMethod
    物件方法innerInstanceMethod
 從類別方法innerStaticMethod,我可以:
  存取 私密 內部類別之類別屬性innerStaticAttribute
  存取 公開 內部類別之類別屬性innerStaticAttribute2
 從 覆寫的 物件方法innerInstanceMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 舊有公開 內部類別之類別屬性innerStaticAttribute2
  存取 舊有公開 內部類別之物件屬性innerInstanceAttribute2
  存取 添加私密 內部類別之物件屬性innerInstanceAttribute3
  呼叫 外部類別之類別方法outerStaticMethod

6.使用物件方法內匿名非靜態類別...
我是<方法內匿名非靜態類別 adapted from InMethodUnnamedClass>物件,擁有
    類別屬性innerStaticAttribute,2
    物件屬性innerInstanceAttribute,2,3
    類別方法innerStaticMethod
    物件方法innerInstanceMethod
 從類別方法innerStaticMethod,我可以:
  存取 私密 內部類別之類別屬性innerStaticAttribute
  存取 公開 內部類別之類別屬性innerStaticAttribute2
 從 覆寫的 物件方法innerInstanceMethod,我可以:
  存取 外部類別之類別屬性outerStaticAttribute
  存取 外部類別之物件屬性outerInstanceAttribute
  存取 舊有公開 內部類別之類別屬性innerStaticAttribute2
  存取 舊有公開 內部類別之物件屬性innerInstanceAttribute2
  存取 添加私密 內部類別之物件屬性innerInstanceAttribute3
  呼叫 外部類別之類別方法outerStaticMethod
  呼叫 外部類別之物件方法outerInstanceMethod
*/
class OuterClass {
  private static String outerStaticAttribute = "外部類別之類別屬性outerStaticAttribute";
  private String outerInstanceAttribute = "外部類別之物件屬性outerInstanceAttribute";

  public OuterClass() {
    System.out.println(this);
  }

  public String toString() {
    String text = "";

    text = text + "我是<外部類別OuterClass>物件,擁有\n";
    text = text + "\t類別屬性outerStaticAttribute\n";
    text = text + "\t物件屬性outerInstanceAttribute\n";
    text = text + "\t類別方法outerStaticMethod\n";
    text = text + "\t物件方法outerInstanceMethod";

    return text;
  }

  // 外部類別靜態方法
  public static void outerStaticMethod() {
    System.out.println("  呼叫 外部類別之類別方法outerStaticMethod");
  }

  public static void outerStaticMethod2() {
    class InMethodStaticClass {
      //private static String innerStaticAttribute = "內部類別之類別屬性innerStaticAttribute";
      //  inner classes cannot have static declarations
      private String innerInstanceAttribute = "內部類別之物件屬性innerInstanceAttribute";

      public InMethodStaticClass() {
        System.out.println("我是<方法內具名靜態類別InMethodStaticClass>物件,擁有");
        System.out.println("\tx類別屬性");
        System.out.println("\t物件屬性innerInstanceAttribute");
        System.out.println("\tx類別方法");
        System.out.println("\t物件方法innerInstanceMethod");
      }

      public String toString() {
        return "我是<方法內具名靜態類別>物件";
      }

      //public static void innerStaticMethod()
      //  inner classes cannot have static declarations
      /*
      {
        System.out.println( " 從類別方法innerStaticMethod,我可以:");
        System.out.println( "  存取 " + outerStaticAttribute);
        //System.out.println( "  存取 " + outerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        System.out.println( "  存取 " + innerStaticAttribute);
        //System.out.println( "  存取 " + innerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        outerStaticMethod();
        //outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
      */

      public void innerInstanceMethod() {
        System.out.println(" 從物件方法innerInstanceMethod,我可以:");
        System.out.println("  存取 " + outerStaticAttribute);
        //System.out.println( "  存取 " + outerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        //System.out.println( "  存取 " + innerStaticAttribute);
        //  non-static variable cannot be referenced from a static context
        System.out.println("  存取 " + innerInstanceAttribute);
        outerStaticMethod();
        //outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
    }

    InMethodStaticClass imsc = new InMethodStaticClass();
    //imnic.innerStaticMethod();
    imsc.innerInstanceMethod();
  }

  public static void outerStaticMethod3() {
    InMethodUnnamedClass imuc = new InMethodUnnamedClass() {
      //private static String innerStaticAttribute3 = "內部類別之類別屬性innerStaticAttribute";
      //  inner classes cannot have static declarations
      private String innerInstanceAttribute3 = "內部類別之物件屬性innerInstanceAttribute3";

      public String toString() {
        String text = "";

        text = text + "我是<方法內匿名靜態類別 adapted from InMethodUnnamedClass>物件,擁有\n";
        text = text + "\t類別屬性innerStaticAttribute.2\n";
        text = text + "\t物件屬性innerInstanceAttribute,2,3\n";
        text = text + "\t類別方法innerStaticMethod\n";
        text = text + "\t物件方法innerInstanceMethod";

        return text;
      }

      //cannot overwrite constructor
      //  invalid method declaration; return type required
      //public InMethodUnnamedClass()
      /*{
        System.out.println( "我是<方法內匿名非靜態類別>物件,擁有" );
        System.out.println( "\tx類別屬性" );
        System.out.println( "\t物件屬性innerInstanceAttribute" );
        System.out.println( "\tx類別方法" );
        System.out.println( "\t物件方法innerInstanceMethod" );
      }*/

      //public static void innerStaticMethod()
      //  inner classes cannot have static declarations
      /*
      {
        System.out.println( " 從類別方法innerStaticMethod,我可以:");
        System.out.println( "  存取 " + outerStaticAttribute);
        //System.out.println( "  存取 " + outerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        System.out.println( "  存取 " + innerStaticAttribute);
        //System.out.println( "  存取 " + innerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        outerStaticMethod();
        //outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
      */

      //  overwriting method must exist in prototype class
      public void innerInstanceMethod() {
        System.out.println(" 從 覆寫的 物件方法innerInstanceMethod,我可以:");
        System.out.println("  存取 " + outerStaticAttribute);
        //System.out.println( "  存取 " + outerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        //System.out.println( "  存取 舊有私密 " + innerStaticAttribute);
        //  innerStaticAttribute has private access in InMethodUnnamedClass
        System.out.println("  存取 舊有公開 " + innerStaticAttribute2);
        //System.out.println( "  存取 添加私密 " + innerStaticAttribute3);
        //System.out.println( "  存取 " + innerInstanceAttribute);
        //  innerInstanceAttribute has private access in InMethodUnnamedClass
        System.out.println("  存取 舊有公開 " + innerInstanceAttribute2);
        System.out.println("  存取 添加私密 " + innerInstanceAttribute3);
        outerStaticMethod();
        //outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
    };

    imuc.innerStaticMethod();
    imuc.innerInstanceMethod();
  }

  // 外部類別物件方法
  public void outerInstanceMethod() {
    System.out.println("  呼叫 外部類別之物件方法outerInstanceMethod");
  }

  public void outerInstanceMethod2() {
    class InMethodInstanceClass {
      //private static String innerStaticAttribute = "內部類別之類別屬性innerStaticAttribute";
      //  inner classes cannot have static declarations
      private String innerInstanceAttribute = "內部類別之物件屬性innerInstanceAttribute";

      public InMethodInstanceClass() {
        System.out.println(this.toString());
      }

      public String toString() {
        String text = "";

        text = text + "我是<方法內具名非靜態類別InMethodInstanceClass>物件,擁有\n";
        text = text + "\tx類別屬性\n";
        text = text + "\t物件屬性innerInstanceAttribute\n";
        text = text + "\tx類別方法\n";
        text = text + "\t物件方法innerInstanceMethod";

        return text;
      }

      //public static void innerStaticMethod()
      //  inner classes cannot have static declarations
      /*
      {
        System.out.println( " 從類別方法innerStaticMethod,我可以:");
        System.out.println( "  存取 " + outerStaticAttribute);
        //System.out.println( "  存取 " + outerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        System.out.println( "  存取 " + innerStaticAttribute);
        //System.out.println( "  存取 " + innerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        outerStaticMethod();
        outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
      */

      public void innerInstanceMethod() {
        System.out.println(" 從物件方法innerInstanceMethod,我可以:");
        System.out.println("  存取 " + outerStaticAttribute);
        System.out.println("  存取 " + outerInstanceAttribute);
        //System.out.println( "  存取 " + innerStaticAttribute);
        //  non-static variable cannot be referenced from a static context
        System.out.println("  存取 " + innerInstanceAttribute);
        outerStaticMethod();
        outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
    }

    InMethodInstanceClass imic = new InMethodInstanceClass();
    //imic.innerStaticMethod();
    imic.innerInstanceMethod();
  }

  public void outerInstanceMethod3() {
    InMethodUnnamedClass imuc = new InMethodUnnamedClass() {
      //private static String innerStaticAttribute3 = "內部類別之類別屬性innerStaticAttribute";
      //  inner classes cannot have static declarations
      private String innerInstanceAttribute3 = "內部類別之物件屬性innerInstanceAttribute3";

      public String toString() {
        String text = "";

        text = text + "我是<方法內匿名非靜態類別 adapted from InMethodUnnamedClass>物件,擁有\n";
        text = text + "\t類別屬性innerStaticAttribute,2\n";
        text = text + "\t物件屬性innerInstanceAttribute,2,3\n";
        text = text + "\t類別方法innerStaticMethod\n";
        text = text + "\t物件方法innerInstanceMethod";

        return text;
      }

      //cannot overwrite constructor
      //  invalid method declaration; return type required
      //public InMethodUnnamedClass()
      /*{
        System.out.println( "我是<方法內匿名非靜態類別>物件,擁有" );
        System.out.println( "\tx類別屬性" );
        System.out.println( "\t物件屬性innerInstanceAttribute" );
        System.out.println( "\tx類別方法" );
        System.out.println( "\t物件方法innerInstanceMethod" );
      }*/

      //public static void innerStaticMethod()
      //  inner classes cannot have static declarations
      /*
      {
        System.out.println( " 從類別方法innerStaticMethod,我可以:");
        System.out.println( "  存取 " + outerStaticAttribute);
        //System.out.println( "  存取 " + outerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        System.out.println( "  存取 " + innerStaticAttribute);
        //System.out.println( "  存取 " + innerInstanceAttribute);
        //  non-static variable cannot be referenced from a static context
        outerStaticMethod();
        //outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
      */

      //  overwriting method must exist in prototype class
      public void innerInstanceMethod() {
        System.out.println(" 從 覆寫的 物件方法innerInstanceMethod,我可以:");
        System.out.println("  存取 " + outerStaticAttribute);
        System.out.println("  存取 " + outerInstanceAttribute);
        //System.out.println( "  存取 舊有私密 " + innerStaticAttribute);
        //  innerStaticAttribute has private access in InMethodUnnamedClass
        System.out.println("  存取 舊有公開 " + innerStaticAttribute2);
        //System.out.println( "  存取 添加私密 " + innerStaticAttribute3);
        //System.out.println( "  存取 " + innerInstanceAttribute);
        //  innerInstanceAttribute has private access in InMethodUnnamedClass
        System.out.println("  存取 舊有公開 " + innerInstanceAttribute2);
        System.out.println("  存取 添加私密 " + innerInstanceAttribute3);
        outerStaticMethod();
        outerInstanceMethod();
        //  non-static method cannot be referenced from a static context
      }
    };

    imuc.innerStaticMethod();
    imuc.innerInstanceMethod();
  }

  // 類別內具名靜態類別
  public static class InClassStaticClass {
    private static String innerStaticAttribute = "內部類別之類別屬性innerStaticAttribute";
    private String innerInstanceAttribute = "內部類別之物件屬性innerInstanceAttribute";

    public InClassStaticClass() {
      System.out.println("我是<類別內具名靜態類別InClassStaticClass>物件,擁有");
      System.out.println("\t類別屬性innerStaticAttribute");
      System.out.println("\t物件屬性innerInstanceAttribute");
      System.out.println("\t類別方法innerStaticMethod");
      System.out.println("\t物件方法innerInstanceMethod");
    }

    public static void innerStaticMethod() {
      System.out.println(" 從類別方法innerStaticMethod,我可以:");
      System.out.println("  存取 " + outerStaticAttribute);
      //System.out.println( "  存取 " + outerInstanceAttribute);
      //  non-static variable cannot be referenced from a static context
      System.out.println("  存取 " + innerStaticAttribute);
      //System.out.println( "  存取 " + innerInstanceAttribute);
      //  non-static variable cannot be referenced from a static context
      outerStaticMethod();
      //outerInstanceMethod();
      //  non-static method cannot be referenced from a static context
    }

    public void innerInstanceMethod() {
      System.out.println(" 從物件方法innerInstanceMethod,我可以:");
      System.out.println("  存取 " + outerStaticAttribute);
      //System.out.println( "  存取 " + outerInstanceAttribute);
      //  non-static variable cannot be referenced from a static context
      System.out.println("  存取 " + innerStaticAttribute);
      System.out.println("  存取 " + innerInstanceAttribute);
      outerStaticMethod();
      //outerInstanceMethod();
      //  non-static method cannot be referenced from a static context
    }
  }

  // 類別內具名非靜態類別
  public class InClassInstanceClass {
    //private static String innerStaticAttribute = "內部類別之類別屬性";
    //  inner classes cannot have static declarations
    private String innerInstanceAttribute = "內部類別之物件屬性innerInstanceAttribute";

    public InClassInstanceClass() {
      System.out.println("我是<類別內具名非靜態類別InClassInstanceClass>物件,擁有");
      System.out.println("\tx類別屬性");
      System.out.println("\t物件屬性innerInstanceAttribute");
      System.out.println("\tx類別方法");
      System.out.println("\t物件方法innerInstanceMethod");
    }

    //public static void innerStaticMethod()
    //  inner classes cannot have static declarations
    /*
    {
      System.out.println( "從類別方法,我可以:");
      System.out.println( " 存取 " + outerStaticAttribute);
      //System.out.println( " 存取 " + outerInstanceAttribute);
      //   non-static variable cannot be referenced from a static context
      //System.out.println( " 存取 " + innerStaticAttribute);
      System.out.println( " 存取 " + innerInstanceAttribute);
      outerStaticMethod();
      //outerInstanceMethod();
      //  non-static method cannot be referenced from a static context
    }
    */

    public void innerInstanceMethod() {
      System.out.println(" 從物件方法innerInstanceMethod,我可以:");
      System.out.println("  存取 " + outerStaticAttribute);
      System.out.println("  存取 " + outerInstanceAttribute);
      //System.out.println( "  存取 " + innerStaticAttribute);
      System.out.println("  存取 " + innerInstanceAttribute);
      outerStaticMethod();
      outerInstanceMethod();
    }
  }
}

class InMethodUnnamedClass {
  private static String innerStaticAttribute = "內部類別之類別屬性innerStaticAttribute";
  public static String innerStaticAttribute2 = "內部類別之類別屬性innerStaticAttribute2";
  //  inner classes cannot have static declarations
  private String innerInstanceAttribute = "內部類別之物件屬性innerInstanceAttribute";
  public String innerInstanceAttribute2 = "內部類別之物件屬性innerInstanceAttribute2";

  public InMethodUnnamedClass() {
    System.out.println(this.toString());
  }

  public String toString() {
    String text = "";

    text = text + "我是<方法內匿名類別InMethodUnnamedClass>物件,擁有\n";
    text = text + "\t類別屬性innerStaticAttribute,2\n";
    text = text + "\t物件屬性innerInstanceAttribute,2\n";
    text = text + "\t類別方法innerStaticMethod\n";
    text = text + "\t物件方法innerInstanceMethod";

    return text;
  }

  public static void innerStaticMethod() {
    System.out.println(" 從類別方法innerStaticMethod,我可以:");
    //System.out.println( "  存取 " + outerStaticAttribute);
    //System.out.println( "  存取 " + outerInstanceAttribute);
    //  non-static variable cannot be referenced from a static context
    System.out.println("  存取 私密 " + innerStaticAttribute);
    System.out.println("  存取 公開 " + innerStaticAttribute2);
    //outerStaticMethod();
    //outerInstanceMethod();
    //  non-static method cannot be referenced from a static context
  }

  public void innerInstanceMethod() {
    System.out.println(" 從物件方法innerInstanceMethod,我可以:");
    //System.out.println( "  存取 " + outerStaticAttribute);
    //System.out.println( "  存取 " + outerInstanceAttribute);
    //  non-static variable cannot be referenced from a static context
    System.out.println("  存取 私密 " + innerStaticAttribute);
    System.out.println("  存取 公開 " + innerStaticAttribute2);
    System.out.println("  存取 私密 " + innerInstanceAttribute);
    System.out.println("  存取 公開 " + innerInstanceAttribute2);
    //outerStaticMethod();
    //outerInstanceMethod();
    //  non-static method cannot be referenced from a static context
  }
}

public class Inner {
  public static void main(String args[]) {
    OuterClass oc = new OuterClass();

    // 使用類別內具名靜態類別
    System.out.println("\n1.使用類別內具名靜態類別...");
    // 建立<類別內具名靜態類別>之物件
    OuterClass.InClassStaticClass oc_icsc = new OuterClass.InClassStaticClass();

    OuterClass.InClassStaticClass.innerStaticMethod();
    oc_icsc.innerInstanceMethod();


    // 使用類別內具名非靜態類別
    //   要使用類別內具名靜態類別,需先建立其外部類別之物件
    System.out.println("\n2.使用類別內具名非靜態類別...");
    OuterClass.InClassInstanceClass oc_icic = oc.new InClassInstanceClass();
    //oc_icic.innerStaticMethod();
    oc_icic.innerInstanceMethod();

    // 使用方法內具名類別
    System.out.println("\n3.使用類別方法內具名靜態類別...");
    OuterClass.outerStaticMethod2();

    System.out.println("\n4.使用物件方法內具名非靜態類別...");
    oc.outerInstanceMethod2();

    // 使用方法內具匿名類別
    System.out.println("\n5.使用類別方法內匿名靜態類別...");
    OuterClass.outerStaticMethod3();

    System.out.println("\n6.使用物件方法內匿名非靜態類別...");
    oc.outerInstanceMethod3();
  }
}

2008年3月7日星期五

when will peterson's mutual exclusion algorithm fail?

Silbershatz課本6章同步介紹peterson雙行程演算法前,有提到如下適用但書,
"Because of the way modern computer architectures perform basic machine-language instructions,
such as load and store, there are no guarantees that Peterson's solution will work correctly on such architectures."
到底是什麼現代電腦架構會造成peterson演算法失效?
上網查了一下,有兩種可能性,如下,其中第一種可能性比較大,

1.多CPU且記憶體採弱循序存取模式(weak memory access model)的電腦架構下,

此弱存取模式特徵是和傳統程式師假設的強存取模式不同,
CPU(讀或寫)存取兩記憶體內容之順序,假設先變數X,再變數Y,
實際存取順序卻視快取存在與否,而可能先變數Y,再變數X,
即有關記憶體存取之指令順序(program order)可能和實際資料存取順序(data order)不同.

以peterson演算法來看,其出錯情況如下,
兩者原始指令順序
CPU_A CPU_B
flag[A]=true flag[B]=true
turn=B turn=A
flag[B]==false flag[A]==false
turn==A turn==B

假設
CPU_A正有flag[B]快取為false,但無flag[A],turn快取,
CPU_B正有flag[A]快取為false,但無flag[B],turn快取,
則雙方會在各自認為自己指令結果不衝突之下,
調整資料讀取順序如下,

兩者實際資料順序
CPU_A CPU_B
flag[B]==false flag[A]==false
flag[A]=true flag[B]=true
turn=B turn=A
turn==A turn==B

於是雙方都會認為對方旗標測試為假,而同時進入重要區段.

至於單CPU且記憶體採弱循序存取模式(weak memory access model)的電腦架構下,
peterson演算法有沒有問題,我猜測應該沒有問題,
因為將兩者原始指令作任意組合後,在沒有衝突情況下調整順序,皆似乎不會造成兩者同進.
但這點文獻上尚未獲得佐證.

2.多CPU且記憶體採強循序存取模式(strong memory access model)下
各CPU有獨立快取記憶體,而未作快取一致性管理的電腦架構,

所謂強存取模式特徵是
某一顆CPU(讀或寫)存取兩記憶體內容之順序,假設先變數X,再變數Y,
其他CPU觀察到實際存取順序一定也是先變數X,再變數Y,
即有關記憶體存取之指令順序一定和實際存取順序相同.

以peterson演算法來看,其出錯情況為CPU快取管理出現不一致時,如下,
若CPU A執行A緒欲進入重要區段,分享資源,先設定A使用旗標為真,及輪用者為B緒,
但兩設定皆只寫入A的快取記憶體,尚未反應到實際記憶體;
同時間,CPU B執行B緒,亦欲進入重要區段,分享資源,遂設定B使用旗標為真,及輪用者為A緒,同樣,兩設定亦皆只寫入B的快取記憶體,而尚未反應到實際記憶體;
則接下來A,B雙方測試讀取對方使用旗標時,若其值皆尚未進入快取,而自實際記憶體取得,將得值為假,
雙方就會誤以為只有自己想進入重要區段而同時進入.

故在記憶體採強循序存取模式(strong memory access model),即指令及資料順序相同下
若電腦架構為單CPU,或
雙CPU但共用快取記憶體,或
雙CPU未共用快取但有作快取一致性管理時,peterson演算法就不會失效.

Reference:
1.http://en.wikipedia.org/wiki/Peterson's_algorithm
2.bhattacharya-dcc-02-issues in multiprocessor memory consistency protocol design and verification
3.ridge-springer-07-operatinal reasoning for concurrent caml programs and weak memory models
4.holzmann-iel-07-the design of a multicore extension of the spin model checker
5.higham---implementing sequentially consistent programs on processor consistent platforms
6.http://cis.poly.edu/muller/CS623/weakmemory.htm
Thus any algorithm that is based on a strong ordering assumption may fail in a system that is allowed to reorder memory request, Dijkstra’s and Peterson’s synchronization algorithms fail [1,2,5], for example.
7.http://docs.sun.com/app/docs/doc/801-6659/6i116aqnb?l=zh_TW&a=view
8.http://en.wikipedia.org/wiki/Out-of-order_execution

訂閱：文章 (Atom)

2008年12月31日 星期三

2008年12月8日 星期一

2008年12月2日 星期二

2008年11月20日 星期四

2008年10月13日 星期一

2008年7月13日 星期日

2008年5月28日 星期三

2008年5月22日 星期四

2008年5月21日 星期三

2008年4月24日 星期四

2008年4月23日 星期三

2008年4月16日 星期三

2008年4月14日 星期一

2008年3月7日 星期五