computer

scanf 102

ในการเขียนโปรแกรมแนวคอมโอ เมื่อเขียนด้วยภาษา C จะมีโจทย์บางแบบ ที่ถ้าเรา scanf ดีๆ แล้วจะทำให้ชีวิตง่ายขึ้นมาก เพราะถ้าเราเอา C มาจัดการ string ชีวิตจะเศร้าลงทันที

วันนี้ผมนั่งทำโจทย์ Tree summing ใน uva แล้วหาวิธีการ scanf แนวที่ให้มัน check คล้ายๆ regular expression แล้วก็ไม่เจอข้อมูลเป็นชิ้นเป็นอัน (หรือหาไม่ดีเองหว่า?)  เลยพยายามนั่งทำแล้วรวบรวมมาให้ครับ ถือเป็นวิชา scanf 102 ต่อจากวิชา 101 พื้นฐานที่เราใช้รับเลข รับ string กันเป็นอยู่แล้ว

  • scanf(“%[ABC]”,str)
    • คือ scan ไปเรื่อยๆ ตราบที่ยังเจอเฉพาะ A,B,C แล้วเอาใส่ str
  • scanf(“%[^ABC]”,str)
    • คือ scan ไปเรื่อยๆ ตราบที่ “ไม่เจอ” แต่ A,B,C แล้วเอาใส่ str
    • scan ครั้งต่อไปจะเจอ A เป็นตัวแรก
  • การมี * อยู่หน้า [] คือการ scan อะไรที่เข้าเงื่อนไข ทิ้ง
  • ตัวอักษรที่ไม่ได้อยู่ตาม % ก็คือทิ้งเหมือนกัน เจอตัวอะไรก็ ทิ้งตัวนั้น 1 ตัว
  • scanf(“%*[^(]”)
    • คือ ทิ้งทุกตัวจนกว่าจะเจอ วงเล็บเปิด ‘(‘
    • ก่อนหน้านี้ลอง ทิ้งตัวที่อาจจะเจอ เช่น scanf(“%*[\n ]”); แล้วปรากฏว่าไม่ชัวร์เท่าวิธีนี้ครับ
  • scanf(“(%[-0-9]”,str)
    • แปลว่า เอาเครื่องหมาย – และตัวเลข 0-9
    • ความหมายเดียวกับ scanf(“%[-1234567890]”,str);
  • result = scanf(“(%[-1234567890]”,str);  ควรมีตัวแปรเก็บค่า return
    • อาการที่เหมือนว่ามัน scan เอาค่าเดิมเข้าไป (เช่น print ตัวแปรที่รับค่านั้นออกมาซ้ำ) จริงๆ แล้วคือ มัน scan ไม่เข้า
    • อาการนี่ check ได้โดยการ if(result==0) ถ้าเป็น 0 ชัวร์ได้เลยว่า ตัวแปรจะไม่รับค่าใหม่ใดๆ

ตัวอย่าง code นี้จะสามารถอ่าน tree ในแบบในโจทย์ออกมาได้เลย เมื่อเรียก gentree(0) เช่น

input = (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
output = num[0]=5 num[1]=4 num[3]=11 num[7]=7 num[8]=2 num[2]=8 num[5]=13 num[6]=4 num[14]=1

void gentree(int where){
    int num;
    int result;
    scanf("%*[^(]");
    result = scanf("(%d",&num);
    if(result!=0){
        printf("num[%d]=%d ",where,num);
        gentree(where*2+1);
        gentree(where*2+2);
    }
    scanf("%*[^)])");
}

Tree Summing

ผล NSC 2009 : ผิดหวังแต่ไม่เสียใจ

งาน NSC ผ่านไป
พร้อมไม่เข้าใจ
เมื่อมือว่างเปล่ากลับมา

พินิจพิจารณา
เพื่อนเพื่อนบอกว่า
เพราะใจ”เขา”ไม่ตรงกัน

ในสิ่งเราเห็นสำคัญ
อาจกลับกลายพลัน
เป็นความเบาหวิวเหลือทน

เมื่อประสบการณ์ของคน
มองไม่เห็นผล
สำคัญชุมชนออนไลน์

หรืออาจบางทีเหตุใหญ่
เราเองอ่อนไป
เข้าใจว่าตัวมีดี

อย่างไรไม่คิดเสียที
สำเร็จงานนี้
ผิดหวังแต่ไม่เสียใจ

หนึ่งคือเชื่อมั่นข้างใน
สิ่งที่ทำไป
คงสร้างผลงามตามฝัน

สองคือความรู้สารพัน
ประสบการณ์อัน
ล้ำค่าใช้ต่อหลายปี

ขอบคุณ @rtsp
อีก @kaewgb
ร่วมแรงสร้างสรรค์กันมา

อยากบอกให้ได้รู้ว่า
ประทับตรึงตรา
ครั้งหนึ่งร่วมอดหลับสบาย

และ thx ผู้จุดประกาย
ความคิดต้นสาย
โปรแกรมมิ่งดอทไอเอ็น

สุดท้าย @jittat ผู้เป็น
เจ้าภาพมื้อเย็น
แสนอร่อยแสนสุขสำราญ

ปล. ยังไงก็ตาม
จะพยายาม
“แชร์เล่น”สมบูรณ์ปิดเทอม

acm-icpc 2008 @malaysia #1

การแข่ง acm-icpc เป็นการแข่งขันเขียนโปรแกรมระดับภูมิภาคในรอบแรกและระดับโลกในรอบถัดไป แนวโจทย์เป็นแนวโอลิมปิกหรือแนว problem solving แข่งเป็นทีม ทีมละ 3 คน สำหรับทีมผมมีพี่ต้น แก้วและผม  เวลาในการทำโจทย์จะให้เวลา 5 ชม.  ให้โจทย์ประมาณ 7-12 ข้อ  แต่มีคอมพิวเตอร์ให้เพียงเครื่องเดียว  จุดเด่นของการแข่งขันนี้(ซึ่งด้วยโลโกของงานก็สื่อออกมาเป็นอย่างดี) นั้นคือทีมไหนที่แก้โจทย์ได้จะได้ลูกโป่งมาผูกไว้ที่โต๊ะเพื่อไซโคทีมข้างๆ

ก่อนไปแข่งขัน พี่ต้น แก้วและผม เตรียมตัวก่อนไปโดยทุกวันเสาร์จะมานั่งซ้อมทำโจทย์เก่าของ acm-icpc นี้   ตอนแรกผมเองทำไม่ค่อยได้เท่าไหร่ ห่างหายไปนานครับ ต่างจากพี่ต้นที่คล่องมาก ได้ซ้อมกันอยู่ประมาณ 5 ครั้ง ก็รู้สึกว่าช่วยทำให้เขียนโปรแกรมคล่องมากขึ้น (แม้จะไม่เท่าตอนอยู่ค่ายโอก็ตาม) และตีโจทย์ได้ชัดเจนขึ้น (อันนี้เหนือว่าตอนอยู่ค่ายโอ เพราะประสบการณ์จากการได้อ่าน paper theory และได้เรียน algo อะไรมาอีกรอบ)

ในการแข่งขันนั้น เราได้เตรียม template ของ code ที่คิดว่าน่าจะได้ใช้ เพื่อให้เวลาเข้าไปทำแล้วจะได้ลอก code ได้เลย แล้วก็พยายามแบ่งน่าที่กันให้ชัดเจน หน้าที่ที่ได้จะประมาณ พี่ต้นเป็นคนเขียน code หลักเพราะว่าพี่ต้นเขียน code algo พวก shortest path หรือ max flow ได้แบบไม่ต้องคิดเท่าไหร่แล้ว แล้วก็ด้วยประสบกาณร์การทำโจยท์มหาศาลทำให้เขียนแล้ว bug น้อยมาก  ส่วนแก้วจะทำหน้าที่อ่านโจทย์แล้วแปลเพราะว่าอ่านได้เร็วที่สุด(ผมเองตกใจมากว่าทำไมแก้วอ่านได้เร็วแบบนี้ เวลาแข่งผมจะไม่มีสมาธิในการอ่านภาษาอื่น แล้วมันจะอ่านซ้ำไปซ้ำมาไม่ได้ความเท่าไหร่) เวลาที่ว่างก็ให้แก้วมาช่วยคิด  สำหรับผมเองนั้นรับหน้าที่คิดแก้โจทย์ครับ เพราะว่าอ่านก็ไม่เก่ง เขียนก็bug แต่ผมก็มีความถนัดเลขและอัลกออยู่เหมือนกัน

ที่จริงก่อนวันแข่งขันหนึ่งวัน จะมีโจทย์ให้ทดสอบเครื่องเรียกว่า mock test  ตอนนั้นถือเป็นเวลาแห่งความประสบความสำเร็จประจำ trip ครั้งนี้ครับ เพราะว่าพอได้โจทย์มา 2 โจทย์แรกง่ายมากขนาดที่พี่ต้น เขียนแบบไม่ต้องหยุดเลย  แล้วโจทย์ที่ 3 เป็นโจทย์เลข ระหว่างที่พี่ต้นเขียนจะเสร็จ ผมก็คิดวิธีออกและ make sure กับแก้ว ทำให้พี่ต้นเขียนข้อ 3 ต่อได้ทันทีแล้วก็ส่ง ได้เป็นที่หนึ่งไปเลย! (แม้เวลาสุดท้ายจะตกมาอยู่ที่ 3 เพราะว่ามีครั้งนึงที่ส่งผิดไป แล้วทำให้โดน time panalty ไป 20 นาที  ทีมอื่นๆ ที่ทำช้ากว่าถ้าไม่ผิดพอเค้าส่งมาครบเราเลยโดนแซง)

มาพูดถึงช่วงการแข่งขันเลยกันดีกว่า สำหรับผมบรรยากาศในการแข่งนั้นธรรมดามาก จากตอนแรกที่คิดว่าจะโดนไซโคจากลูกโป่งของคนอื่นก็ไม่รู้สึก ไม่ตื่นเต้นเท่าตอนสอบคัดตัวค่ายโอเลยด้วยซ้ำ ผมคิดว่าเป็นเพราะว่าโต๊ะที่นั่งของแต่ละทีมนั้นห่างกันจนไม่ได้ยินเสียงพิมพ์ดีดและไม่รู้สึกกดดันอะไร  แต่ผมขอสปอยล์เลยว่า ทีมเราได้ที่ 18 จาก 60  (อันดับนี้คืออันดับร่วมของทีมที่ทำได้ 3 ข้อ จาก 11 เหมือนกันหมด – -” ฉะนั้นได้จัดกันตามเวลาด้วย เราก็จะต้องตกอันดับลงมาอีก)

เหตุผลอะไรที่ทำให้ได้แค่นี้  ผมต้องขอไม่ถ่อมตัวคนในทีมว่าไม่ใช่เพราะความสามารถในการแก้โจทย์ไม่ถึงแน่ๆ ครับ ผมแน่ใจว่าถ้าพี่ต้นมาทำคนเดียวจะได้มากกว่า 3 ข้อด้วยซ้ำ หรือถ้าเป็นผมหรือแก้วทำก็ห้าสิบห้าสิบว่าจะได้มากกว่า 3 ข้อ  ยังไงก็ตาม ผมจะขอยกไปเขียนลงอีก entry หนึ่งเลยละกันครับว่า หลักการ/ข้อผิดพลาด จากการแบ่งกันเขียนโปรแกรม 3 คนแต่มีคอม 1 เครื่องที่ผมได้เรียนรู้หลังแข่งขันครั้งนี้คืออะไรบ้าง

intel blogger day 2008

เมื่อวันที่ 11 ต.ค. 50 ได้มีโอกาสไปงาน intel blogger day 2008 มาครับ

ผมไม่แน่ใจนัก แต่คิดว่าน่าจะเป็นครั้งแรกในไทยหล่ะที่บริษัทใหญ่ๆ สนใจที่จะมาสื่อสารกับ blogger บ้าง แทนที่จะแถลงข่าวกับนักข่าวอย่างเดียว  ผมว่านี่สะท้อนว่า blogger ในไทยเรา เริ่มจะเป็นที่เห็นชัดมากขึ้นแล้วหล่ะว่ามีอิทธิพลต่อการเลือกซื้อ  (ในต่างประเทศมีงานคุยกับ blogger แบบนี้เยอะแยะ — intel เค้าบอกมาเอง– เรายังไกลจากต่างประเทศเยอะ)

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

พูดถึงคำว่าสถาปัตย์ แต่ก่อนผมจะคิดแค่ว่ามันคือ ศาสตร์แห่งการออกแบบให้แจ่มๆ หล่อๆ เพราะนึกถึงคณะสถาปัตย์บ้านเรา  แต่หลังจากได้เรียนวิชา computer architecture  หรือได้อ่านบทความเกี่ยวกับ architecture จากที่ต่างๆ ผมว่าผมเก็ตความหมายของสถาปัตย์ได้ลึกขึ้น ซึ่งน่าจะทำให้ไปออกแบบอะไรได้ตรงจุดมากขึ้น

ผมว่า สถาปัตย์คือศาสตร์การหาจุดสมดุลของ trade-off ที่มีอยู่ ให้มันตอบจุดประสงค์ของเราได้..แก่นของออกแบบก็คือความสมดุลนั้นเอง

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

สิ่งที่เราต้องทำนั้น ก็คือหาจุดสมดุล “ของเวลานั้นๆ” ให้เจอ  mp3 เป็นตัวอย่างหนึ่งที่ดีที่สามารถ take over ตลาดได้หมด  ด้วยความที่มีขนาดเล็กมาก ในขณะที่ยังมีคุณภาพที่พอรับได้อยู่

ต่อไปจะขอพูดถึงความรู้ที่ผมได้หลังจากฟัง intel พูดและถามเพื่อนๆ โดยเฉพาะจั้ม(อาจจะเป็นเรื่องพื้นๆ อะนะครับ เพราะผมมันไม่ค่อยมีความรู้) และจะพยายามไม่เขียนซ้ำกับ blog ที่เพื่อนๆ ได้เขียนถึงไปแล้วนะครับ

  • การที่ผลิต CMOS ได้ขนาดเล็กลงนั้น(เช่นจาก 65nm เป็น 45nm) เดิมดูเหมือนว่าเป็นสุดยอด solution เพราะจะทำให้ผลิตได้เยอะขึ้น และความร้อนยังน้อยลงอีก  พอความร้อนน้อยก็ทำให้เร่ง clock speed ได้มากขึ้น(ช่วง 2-3 ปีมานี้ CPU เพิ่มความเร็ว clock ไม่ได้แล้วเพราะความร้อนจัด)

    แต่ปรากฏว่า การที่ชิบเล็กลง เวลาที่ไฟฟ้าเปลี่ยนสถานะศูนย์หนึ่งไปมานั้น กลับเพิ่มอัตรารั่วของอิเล็กตรอนมากขึ้น ซึ่งนี้เป็นสิ่งที่ทำให้ความร้อนสูงขึ้นอีก  ทีนี้ intel เค้าบอกมาว่าด้วยเทคโนโลยี hi-k metal gate นั้นจะทำให้อิเล็กตรอนรั่วน้อยลง ฉะนั้นชิบ intel เลยเร็วได้สุดๆ

  • ผมเพิ่งได้รู้จักกับคำว่า hypertransport ของ AMD และ quickpath ของ intel ก็หลังจากมางานนี้  คือแต่เดิมนั้น CPU จะติดต่อทุกๆ อย่างผ่าน FSB(Front Side Bus) ไม่ว่าจะ mem หรือ I/O ก็ตาม  ซึ่งมันก็เรื่องที่ดีนะ ตามหลัก hierachy of memory

    แต่ทีนี้พอเทคโนโลยี multi-core มันเกิดขึ้น quickpath เลยมีประโยชน์มาก ก่อนอื่นอธิบายโครงสร้างหลักๆ ของมันก็คือ การรวม memory controller เข้ามาใน CPU ทำให้เวลา CPU แต่ละตัวจะ access mem แล้วไม่ต้องแย่งกัน access ผ่าน BUS ซึ่งจะทำให้เกิดคอขวดขึ้นหน่ะครับ  อีกอย่างหนึ่งคือการเพิ่มเส้นทางการคุยกันเองระหว่าง CPU (ไม่ผ่าน BUS) ทำให้คุยกันได้เร็วมาก

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

  • google ผลิต server เองครับ ไม่ได้ซื้อของคนอื่น ซึ่งปรากฎว่าประหยัดไฟมากๆ
  • ประโยคเด็ดจากพี่ javaboom สิ่งใดๆ ก็ตามที่ไม่สามารถทำให้รับรายได้ได้นั้น มันจะค่อยๆ ตายลงไปช้าๆ   …นี้มันโคตรจริงเลยนะเนี่ยครับ (พี่เค้ายกตัวอย่างเช่น Grid computing)
  • ที่จริงมีเรื่อง cloud computing ที่พี่ javaboom ได้พูดถึงไว้ และทำให้ผมชัดเจนขึ้นมากแต่ใน blog ของพี่เค้าไ้ด้อธิบายไว้อย่างดีมากแล้วครับ

ที่จริงมีเรื่อง wimax อีกนิดหน่อย แต่ผมไม่ค่อยสนใจหน่ะครับ แต่ยังไงก็ตามก็ตามก็ต้องขอบคุณ intel ที่จัดงานดีๆ แบบนี้ให้นะครับ หวังว่าบริษัทอื่นๆ จะทำแบบนี้บ้างจัง

ผู้อ่านสามารถอ่านความรู้จากงานนี้ได้จากที่อื่นด้วย