ผู้ใช้:Aworachate

ข้อมูลส่วนตัว เทพ รักบำรุง

ภูมิลำเนา 74 หมู่ที่ 4 บ้านวังเจ้า ตำบลบ้านนา อำเภอบ้านนาเดิม จังหวัดสุราษฎร์ธานี

การศึกษาขั้นพื้นฐาน

            ระดับชั้นประถมศึกษาตอนต้น          โรงเรียนบ้านทรายทอง       จังหวัดสุราษฎร์ธานี
            ระดับชั้นประถมศึกษาตอนปลาย       โรงเรียนบ้านนา                จังหวัดสุราษฎร์ธานี
            ระดับชั้นมัธยมศึกษาตอนต้น           โรงเรียนบ้านนาวิทยาคม     จังหวัดสุราษฎร์ธานี
            ระดับชั้นมัธยมศึกษาตอนปลาย        โรงเรียนบ้านนาสาร           จังหวัดสุราษฎร์ธานี

การศึกษาการอุดมศึกษา

            ด้านดนตรี                                   ดนตรีศึกษา                    โรงเรียนดนตรีสยามกลการ  
            ปริญญาตรี                                  คบ.วิชาเอกสังคมศึกษา    วิทยาลัยครูสุราษฎร์ธานี
            บัณฑิตศึกษา                              การบริหารการศึกษา          มหาวิทยาลัยราชภัฏสุราษฎร์ธานี
            การศึกษามหาบัณฑิต                   (กำลังศึกษา)         มหาวิทยาลัยราชภัฏสุราษฎร์ธานี

กิจกรรมจิตอาสาและช่วยเหลือสังคม

            ปี พ.ศ.2517 - ประธานนักเรียนโรงเรียนบ้านนา
            ปี พ.ศ.2521 - ประธานนักเรียนโรงเรียนบ้านนาวิทยาคม
            ปี พ.ศ.2523 - ประธานนักเรียนโรงเรียนบ้านนาสาร
            ปี พ.ศ.2527 - นายกองค์การนักศึกษาวิทยาลัยครูสุราษฎร์ธานี
            ปี พ.ศ.2528 - ประธานสมาพันธ์นักศึกษาภาคใต้ตอนบน
            ปี พ.ศ.2528 - ตัวแทนนักศึกษายื่นเสนอให้จัดตั้งมหาวิทยาลัยในจังหวัดสุราษฎร์ธานี
            ปี พ.ศ.2530 - ประธานข้าราชการครูจังหวัดชายแดนภาคใต้ (ศอ.บต.)

ผลงานรางวัลเกียรติยศ

การค้นหาแบบทวิภาคอย่างมีเอกรูป (Uniform Binary Search) เป็นการลดขนาดการทำงานของการค้นหาแบบทวิภาคแบบธรรมดาลง ซึ่งขั้นตอนวิธีนี้ได้ถูกคิดค้นขึ้นโดยท่าน Donald Knuth และได้เขียนแนวคิดและการพิสูจน์ประสิทธิภาพไว้ในหนังสือThe Art of Computer Programming ,Volume 3.

แนวคิด

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

ตัวอย่างการเขียนโค้ด การค้นหาแบบทวิภาคอย่างมีเอกรูป

สำหรับขั้นตอนวิธีในการทำงานของการค้นหาแบบทวิภาคอย่างมีเอกรูป เริ่มต้นจากการสร้าง อาเรย์สำรวจ ขึ้นมาไว้เก็บดันชีที่จะใช้กระโดดไปพิจารณาในอาเรย์ข้อมูลของเรา โดยตั้งค่าเริ่มต้นให้เป็น 0 ทั้งหมด จากนั้นเราจะสร้างฟังก์ชันขึ้นมา ซึ่งฟังก์ชั่นนี้จะมีหน้าที่ในการเติมค่าดัชนีลงในอาเรย์สำรวจ เพื่อเป็นการบอกระยะของตำแหน่งที่จะพิจารณาถัดไปเมื่อเทียบกับตำแหน่งปัจจุบัน โดยจะมีวิธีการเติมค่าของอาเรย์สำรวจ ตามตัวอย่างโค้ดภาษา C ด้านล่าง

1  void make_delta(int n)
2  {
3	int power =1;
4	int i=0;
5	do{
6		int half = power;
7		power<<=1;
8		delta[i]=(n+half)/power;	 // delta[] คือ อาเรย์สำรวจ
9	      }while(delta[i++]!=0);
10  }

อธิบายการทำงานของฟังก์ชันได้ดังนี้ power เป็นตัวแปรไว้เก็บค่า 2^n โดยกำหนดตัวแปร n ให้เริ่มที 0 ส่วนตัวแปร i เป็น ดันชีชี้ตำแหน่งของ อาเรย์สำรวจ และภายในวงวนจะทำการเติมค่าใน อาเรย์สำรวจ ไปเรื่อยๆ จนกว่าจะเติมด้วยเลข 0 จึงหยุดวงวน (ซึ่งแสดงว่าระยะกระโดดเพื่อไปยังตำแหน่งอื่นเป็น 0 ก็หมายถึงไม่ต้องกระโดแล้ว) ส่วนวิธีเติมเลขลงไปใน อาเรย์สำรวจ นั้นได้มาจากทางสูตรคณิตศาสตร์ที่อยู่ในหนังสือ the art of computer programming หน้า 415 สูตรที่ 6 ซึ่งได้มาจากการพิสูจน์และสรุปผลทางคณิตศาสตร์ เพื่อประกันว่าการกระโดดแบบนี้จะพิจารณาข้อมูลภายในอาเรย์ข้อมูลของเราได้อย่างครบถ้วนแล้ว

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

1  int unisearch(int *a,int key)
2    {
3         int i = delta[0]-1;  // จะเริ่มค้นหาที่ตำแหน่งกึ่งกลางของ อาเรย์ข้อมูล เสมอ
4         int d=0;
5         while(1)
6             {
7                  if(key==a[i])
8	              return i;
9                  else if (delta[d]==0)
10	              return -1;
11                else
12	           {
13	                if(key<a[i])
14		             i-=delta[++d];
15	                else
16		             i+=delta[++d];
17                    }
18               } 
19    }

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

การวิเคราะห์ประสิทธิภาพเชิงเวลา

ลักษณะการทำงานโดยรวมของการค้นหาแบบทวิภาคอย่างมีเอกรูป จะคล้ายๆกับการค้นหาแบบทวิภาคแบบธรรมดา แต่จะต่างกันที่การเลือกจุดพิจารณาว่าจะคิดจากตัวแปร และการที่การค้นหาแบบทวิภาคอย่างมีเอกรูป ได้ทำการคำนวณค่า ที่จะพิจารณาไว้ก่อนค้นหานั้น จะทำให้ความเร็วในการทำงานเพิ่มขึ้นโดยเฉลี่ยประมาณ 17% เทียบกับการค้นหาแบบทวิภาคแบบธรรมดา แต่ประสิทธิภาพเชิงเวลาที่คำนวณได้จะมีค่าเท่ากันกับ ประสิทธิภาพเชิงเวลาของการค้นหาแบบทวิภาพแบบธรรมดา นั่นคือ O(log n) ดังนั้นขั้นตอนวิธีแบบการค้นหาแบบทวิภาคอย่างมีเอกรูป จึงไม่ค่อยได้ถูกนำไปใช้กันมากนัก ทั้งนี้อาจเกิดจากการเขียนโค้ดที่ยุ้งยากกว่า แต่ได้ประสิทธิภาพเชิงเวลาเท่ากับการค้นหาแบบทวิภาพแบบธรรมดา

อ้างอิง

• Knuth. The Art of Computer Programming, Volume 3. Page 412, Algorithm C.