ดาวไม่ได้ใช้งานดาวไม่ได้ใช้งานดาวไม่ได้ใช้งานดาวไม่ได้ใช้งานดาวไม่ได้ใช้งาน
 

Quadratic probing  หมายถึงอะไร ? 

กระบวนการค้นหาแบบ Quadratic probing

 

Quadratic probing คือวิธีแก้ปัญหาความล่าช้าของวิธี linear probing จึงมีการเลือก Collision Resolution Function เพื่อลดความล่าช้าในการหาตำเเหน่งใหม่หลังจากเกิด Collision ฟังก์ชันที่ใช้ก็อยู่ในรูปแบบเดียวกับ linear probing ก็คือ F(i) = i2 โดยที่ i แทนครั้งที่หา (Probe)

การหาตำเเหน่งใหม่ครั้งเเรก สามารถคำนวณจาก 

ตำเเหน่งใหม่ (1) = h(31) + 12 = 31% 11+1  = 10%11 = 10 

 

หากมีการชนกันอัก ก็จะหาตำเเหน่งใหม่ (ครั้งที่ 2 และ 3) จาก

 

ตำเเหน่งใหม่ (2) = h(31) + 22 = 31% 11+4  = 13%11 = 2

ตำเเหน่งใหม่ (3) = h(31) + 32 = 31% 11+9  = 10%11 = 7

 

โดยจะทำเช่นนี้เรื่อย ๆ จนกว่าจะเจอตำเเหน่งว่างที่สามารถบรรจุข้อมูลลงไป จะเห็นว่า วิธีนี้สามารถใช้หลักกระโดดทีละหลาย ๆ ตำเเหน่ง โดยจะเริ่มจาก 1,4,9 เป็นต้นไปเเล้วหวังว่าจะไม่เกิดการชนเช่น วิธี linear probing ซึ่งจะขยับทีละตำเเหน่ง ทำให้มีโอกาสเกิด การชนกันกับข้อมูลอื่นสูง แต่ในทางปฏิบัติกลับไม่เกิดผลดีเท่าที่ควร เนื่องจากการกระโดดจะทำให้เกิดการข้ามตำเเหน่งในระยะคงที่เสมอ คือ 1,4,9 ตำเเหน่งเช่นนี้เรื่อย ๆ ไป 

 

ในการ Implement จริง ฟังก์ชัน F(i) จะทำงานล่าช้า จึงมีการหาวิธีลัดเพื่อให้เพิ่มประสิทธิภาพของการคำนวณ hash function ที่รวดเร็วและสิ้นเปลืองน้อยที่สุด โดยจะเห็นว่าจากวิธีข้างต้นนั้น ค่าของ collision resolution function หรือ F(i) ที่คำนวณมาได้คือ 1,4,9,16 และ 25 วิธีลัดก็อการเลี่ยงการยกกำลัง แต่จะอาศัยการคูณ และการบวก จากความสัมพันธ์ 

 

F(i) = F(i-1) + 2*i - 1 

โดย F(0) เมื่อแทนค่าในสมการความสัมพันธ์แล้ว

F(1) = F(0) + 2*1 - 1 = 1 

F(2) = F(1) + 2*2 - 1 =4

F(3) = F(2) + 2*3 - 1 = 9 

 

ซึ่งการคูณจำนวนใด ๆ ด้วยสองในระดับฮาร์ดแวร์คือการ shift  bit ของจำนวนที่ต้องการคูณสองไปทางซ้าย 1 ครั้ง ทำให้การคูณค่าของ F(i) สามารถกระทำได้อย่างรวดเร็ว เพราะ operations ที่ใช้คือค่าเก่าเพียงค่าเก่าของ F(i) (คือ F(i)) การ shift bit และการลบหนึ่ง เท่านั้น 

 

สรุป Quadratic probing เป็นวิธีที่ 2 ของ Open addressing ซึ่งถูกออกแบบมาในการแก้ปัญหาความล่าช้าของ linear probing โดยจะเลือกใช้ Collision Resolution Function เพื่อลดความล่าช้าในการหาตำแหน่งใหม่หลังจากที่เกิด Collision ฟังก์ชันที่ใช้อยู่ในรูปแบบเดียวกัน 

 

ช่องทางการศึกษาเพิ่มเติมข่าวสารที่น่าสนใจเกี่ยวกับ : ความหมายคำ คืออะไร

กระทู้ล่าสุดจากเว็บบอร์ด
หัวข้อกระทู้
ตอบ
เปิดดู
ล่าสุด
เจอปัญหา Forbidden You don't have permission to access /index.php on this server. Additionally, a 403 Forbidden error
โดย mindphp อ 22 ก.ย. 2020 12:58 am บอร์ด Programming - PHP
1
139
อ 22 ก.ย. 2020 7:44 pm โดย mindphp
มาแล้ว!!! MDSMS component สำหรับส่งข้อความผ่านทาง SMS บน Joomla
โดย bolue จ 21 ก.ย. 2020 5:17 pm บอร์ด MindPHP News & Feedback
0
63
จ 21 ก.ย. 2020 5:17 pm โดย bolue
สอบถามเรื่องการอ่านค่าสีสถานะของปุ่ม
โดย blebee90 จ 21 ก.ย. 2020 2:03 pm บอร์ด Programming - C/C++ & java & Python
1
35
จ 21 ก.ย. 2020 3:10 pm โดย mindphp
ต้องการกำหนดรุปแบบของช่องกรอกให้เป็นเเพทเทิร์นของเบอร์โทร เเต่ไม่ต้องการให้กรอกตัวหนังสือ
โดย thatsawan พฤ 17 ก.ย. 2020 3:18 pm บอร์ด JavaScript & Jquery Ajax
5
1147
พ 23 ก.ย. 2020 2:54 pm โดย thatsawan
สถานที่จัดงานแต่งงานชิคๆ แบบไม่ง้อโรงแรม
โดย Anonymous พฤ 17 ก.ย. 2020 2:10 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
48
พฤ 17 ก.ย. 2020 2:10 pm โดย บุคคลทั่วไป
วิธีแก้ ean13 ปัญหาที่เจอคืออะไร แก้ยังไง
โดย bolue พ 16 ก.ย. 2020 6:38 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
45
พ 16 ก.ย. 2020 6:38 pm โดย bolue
สอบวิธีการ check user ว่าเราใช้ user ไหนอยู่ตอนนี้ ได้มั้ยครับ ใน command บน Ubuntu
โดย jirawoot พ 16 ก.ย. 2020 11:25 am บอร์ด Programming - C/C++ & java & Python
3
84
พ 16 ก.ย. 2020 11:52 am โดย mindphp
หน้าเว็บ phpBB เจอปัญหาโหลด 404 บ้างครั้งไม่รู้ว่าเป็นเพราะอะไรได้บ้าง
โดย thatsawan พ 16 ก.ย. 2020 11:17 am บอร์ด Programming - PHP
5
78
อ 22 ก.ย. 2020 1:00 am โดย mindphp
phpBB เป็นโปรแกรมประเภทไหนมาดูกัน
โดย Udomsak2539 อ 15 ก.ย. 2020 6:25 pm บอร์ด phpBB user Guide Knowledge
0
60
อ 15 ก.ย. 2020 6:25 pm โดย Udomsak2539
รวบรวมข้อมูลเบื้องต้น phpBB คืออะไร ฟีเจอร์ และประวัติ
โดย fhakun อ 15 ก.ย. 2020 6:14 pm บอร์ด PHP Knowledge
0
58
อ 15 ก.ย. 2020 6:14 pm โดย fhakun
สอบถาม วิธีเปิดแจ้งเตือน skype ค่ะ
โดย fhakun อ 15 ก.ย. 2020 6:07 pm บอร์ด ถาม - ตอบ คอมพิวเตอร์
0
67
อ 15 ก.ย. 2020 6:07 pm โดย fhakun
ฟีเจอร์พื้นฐานของ phpBB
โดย fhakun อ 15 ก.ย. 2020 5:33 pm บอร์ด PHP Knowledge
0
62
อ 15 ก.ย. 2020 5:33 pm โดย fhakun
สอบถาม วิธีแทรกลิ้งค์ให้ข้อความค่ะ
โดย fhakun อ 15 ก.ย. 2020 4:42 pm บอร์ด ปัญหาการใช้ phpBB3, SMF, Joomla, Wordpress, CMS, CRM
5
130
อ 15 ก.ย. 2020 5:05 pm โดย fhakun
สอบถาม วิธีติดตั้ง kazaam ใน ubantu ค่ะ
โดย fhakun อ 15 ก.ย. 2020 3:26 pm บอร์ด ถาม - ตอบ คอมพิวเตอร์
7
109
อ 15 ก.ย. 2020 4:38 pm โดย mindphp
ไม่ทราบว่า viewtopic ทำยังไง
โดย Udomsak2539 จ 14 ก.ย. 2020 6:47 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
2
65
อ 15 ก.ย. 2020 10:06 am โดย Udomsak2539
แนะนำโปรแกรม ibis paint และเครื่องมือตัดต่อง่ายๆใน 1 นาที สำหรับมือใหม่
โดย fhakun จ 14 ก.ย. 2020 6:45 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
71
จ 14 ก.ย. 2020 6:45 pm โดย fhakun
รวมวิธี การเดินจาก สงขลา มา กทม.
โดย Udomsak2539 จ 14 ก.ย. 2020 5:10 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
1
90
อ 15 ก.ย. 2020 12:14 pm โดย mindphp
ความแตกต่างระหว่างภาษาอังกฤษและภาษาฝรั่งเศส
โดย fhakun จ 14 ก.ย. 2020 5:03 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
47
จ 14 ก.ย. 2020 5:03 pm โดย fhakun
วิธีเดินทางจากเมืองทองมาเกษตร
โดย fhakun จ 14 ก.ย. 2020 3:03 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
60
จ 14 ก.ย. 2020 3:03 pm โดย fhakun
พิมพ์ข้อความเว็บบอร์ด แล้วกดไปโดยเว็บบอร์ดที่โชว์ในรูปแบบโทรศัพท์ทำยังไง
โดย Udomsak2539 จ 14 ก.ย. 2020 2:59 pm บอร์ด ถาม - ตอบ คอมพิวเตอร์
1
65
จ 14 ก.ย. 2020 3:05 pm โดย tsukasaz