Friday, November 19, 2004

Uncertainty in Hashset

เมื่อวาน บ.ก. Otto ทวงต้นฉบับ TryLinux ภาค 9 ว่าจะเขียนอยู่นี่แหละ แต่เปลี่ยนใจเอาเรื่องสั้นๆคาใจก่อนดีกว่า

ความแน่นอนของโปรแกรม ?

ปกติโปรแกรมคอมพิวเตอร์ ถ้า Input เหมือนกัน จะรันกี่ทีกี่ที ผลจะออกมาเหมือนๆกัน ถึงแม้ในโปรแกรมจะใช้ฟังก์ชั่นสุ่มตัวเลข เช่น rand() ถ้าเราไม่ได้ กำหนดค่าเริ่มต้น srand() ด้วยอะไรที่มีการเปลี่ยนแปลง (เช่น เวลา) มันก็จะสุ่มออกมาตามลำดับเดิมๆทุกครั้งไป

มาติดใจตรงโปรแกรม WhichCoin ที่พูดถึงใน Blog ก่อนหน้านี้ (โปรแกรมแก้ปัญหาชั่ง n เหรียญ) พบว่ารันแต่ละที บางครั้ง ผลมันออกมาไม่เหมือนกัน แต่ก็เป็นผลที่ถูกต้องตามเจตนาของโปรแกรม เช่น เปิดโปรแกรมสองหน้าต่างพร้อมๆกัน ใส่จำนวนเหรียญเป็น 4 ทั้งคู่ แล้วกดปุ่ม คำนวณ ดันได้ผลออกมาแตกต่างกัน !

หรือกดปุ่ม "คำนวณ" ซ้ำอีก ในตัวโปรแกรมนั้น เมื่อกดปุ่มคำนวณ มันจะเรียก GenMap gm = new GenMap() ซึ่งเป็นการสร้างคลาสสำหรับคำนวณขึ้นมาใหม่ทุกครั้ง ไม่มีการใช้ตัวแปร static หรือเอาค่าใดๆจากการคำนวณครั้งที่แล้ว (gm ตัวเก่า) มาใช้เลย โดยโปรแกรมจะหยุดแสดงผลเมื่อเจอคำตอบแรก

ตามความรู้สึกทั่วๆไป จะกด คำนวณ สักกี่ครั้งก็ควรจะได้ผลออกมาเหมือนเดิม (เพราะเป็นคำตอบแรกที่เจอ) จริงอยู่ที่ คำตอบ อาจมีได้หลายคำตอบ แต่ถ้าใช้โปรแกรมเดิม คิดตามลำดับเดิม ผลมันจะแตกต่างได้อย่างไร ?

ไอน์สไตน์ยังเคยพูดว่า "God does not play dice (with the universe)" !

Hashset คือตัวการ

ลองไล่ๆดู รู้สึกว่าจะเป็นเพราะการใช้ Hashset เก็บรูปแบบเหรียญที่เป็นไปได้ แล้วเลือกออกมาลองทีละอันด้วย iterator() ลำดับของรูปแบบที่ออกมาทาง iterator() เนี่ยแหละ มันเปลี่ยนไป ในการเรียกแต่ละครั้ง

ลองทดสอบดูง่ายๆ โดยตัดบางส่วนของโปรแกรมออกมาทำเป็นโปรแกรมทดสอบ สั้นๆ ดังนี้

for(int i=0;i<4;i++)
  (new TestHashset()).test();
โดยใน test() เขียนไว้ว่า
..
    Hashset hs = new Hashset();

    public void test() {
        addlist();
        printlist();
    }

    private void addlist() {
        int count = 2;
        int patcount = (int) (Math.pow(3, count));
        System.out.print("Add: ");
        for (int i = 1; i < patcount; i++) {
            CoinPattern cp = new CoinPattern(count);
            cp.setValue(i);
            hs.add(cp);
            System.out.print(cp+" ");
        }
        System.out.println("");
    }

    private void printlist() {
        System.out.print("Get: ");
        Iterator iter = hs.iterator();
        while (iter.hasNext()) {
            CoinPattern item = (CoinPattern)iter.next();
            System.out.print(item+" ");
        }
        System.out.println("");
        System.out.println("");
    }
ผลที่ได้ออกมาเป็น
Add: L- R- -L LL RL -R LR RR 
Get: -L R- LR RR RL L- -R LL 

Add: L- R- -L LL RL -R LR RR 
Get: R- -L L- RL RR LL LR -R 

Add: L- R- -L LL RL -R LR RR 
Get: -L RR LR R- RL LL L- -R 

Add: L- R- -L LL RL -R LR RR 
Get: LL LR -R RL -L R- L- RR 
คือ Add ลำดับเหมือนเดิมทุกครั้ง แต่ลำดับที่ออกมาแตกต่างกัน

ไม่รู้ข้างใน Hashset เขาเขียนไว้อย่างไร ลำดับใน iterator() จึงเปลี่ยนแปลงไปในการเรียกแต่ละครั้ง (หรือว่าขึ้นกับ เวลา/ตำแหน่งในหน่วยความจำ/ทอยลูกเต๋า ?)

โดยทั่วไป iterator() ก็คงไม่รับประกันลำดับของข้อมูลอยู่แล้ว และโปรแกรมก็ไม่ได้(และไม่ควร)เรียกร้องว่าลำดับต้องเหมือนเดิม กรณีนี้ก็ไม่ถือว่า Hashset ทำงานผิด แต่มันน่าสนใจ

No comments: