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

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 ฟังก์ชันที่ใช้อยู่ในรูปแบบเดียวกัน 

 

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

กระทู้ล่าสุดจากเว็บบอร์ด
หัวข้อกระทู้
ตอบ
เปิดดู
ล่าสุด
กองทุนประกันสังคม มีผู้ประกันตนกี่ประเภท ??
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 5:53 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
3
พฤ 04 มิ.ย. 2020 5:53 pm โดย natthanit.r2538
สรุปความเข้าใจ เกี่ยวกับการตั้งกระทู้
โดย bolue พฤ 04 มิ.ย. 2020 5:16 pm บอร์ด M104 - สุภาภรณ์ อินกรรไกร
0
9
พฤ 04 มิ.ย. 2020 5:16 pm โดย bolue
วิธีการ ลงเวลา โดย Python
โดย bolue พฤ 04 มิ.ย. 2020 4:09 pm บอร์ด Python Knowledge
0
22
พฤ 04 มิ.ย. 2020 4:09 pm โดย bolue
การยื่นแบบ ภ.ง.ด. 53 ออนไลน์ สอนวิธีการยื่นแบบออนไล์ ทำได้ด้วยตัวเอง
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 3:51 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
1
11
พฤ 04 มิ.ย. 2020 4:16 pm โดย natthanit.r2538
วิธีการ โชว์ข้อมูลด้วยการ Format วันที่ โดย Python
โดย bolue พฤ 04 มิ.ย. 2020 3:38 pm บอร์ด Python Knowledge
0
23
พฤ 04 มิ.ย. 2020 3:38 pm โดย bolue
การยื่นแบบ ภ.ง.ด. 3 ออนไลน์ สรุปขั้นตอนยื่นแบบภาษี ออนไล์
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 2:54 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
1
16
พฤ 04 มิ.ย. 2020 3:08 pm โดย natthanit.r2538
วิธีการเดินทางจาก ปทุมธานี มา กรุงเทพฯ
โดย bolue พฤ 04 มิ.ย. 2020 1:59 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
9
พฤ 04 มิ.ย. 2020 1:59 pm โดย bolue
วิธีการ Search database แบบพื้นฐานๆ โดย Python
โดย bolue พฤ 04 มิ.ย. 2020 1:55 pm บอร์ด Python Knowledge
0
24
พฤ 04 มิ.ย. 2020 1:55 pm โดย bolue
การยื่นแบบ ภ.ง.ด.1 ออนไลน์ ขั้นตอนการยืนแบบออนไลน์
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 12:35 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
2
14
พฤ 04 มิ.ย. 2020 1:40 pm โดย natthanit.r2538
สอบถามเรื่องการแนบรูปในกระทู้ค่ะ
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 12:34 pm บอร์ด ปัญหาการใช้ phpBB3, SMF, Joomla, Wordpress, CMS, CRM
2
19
พฤ 04 มิ.ย. 2020 2:31 pm โดย natthanit.r2538
สรุปขั้นตอนการเขียนบทความ และการตั้งกระทู้(จากวีดีโอ)
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 11:26 am บอร์ด M103 - ณัฐนิตย์ ร่มบ้านโหล๊ะ
0
8
พฤ 04 มิ.ย. 2020 11:26 am โดย natthanit.r2538
สรุปเรื่องที่เรียนตอนเช้า
โดย bolue พฤ 04 มิ.ย. 2020 11:10 am บอร์ด M104 - สุภาภรณ์ อินกรรไกร
0
9
พฤ 04 มิ.ย. 2020 11:10 am โดย bolue
งานประจำวันที่ 4 มิถุนายน 2563
โดย bolue พฤ 04 มิ.ย. 2020 10:32 am บอร์ด M104 - สุภาภรณ์ อินกรรไกร
4
23
พฤ 04 มิ.ย. 2020 7:00 pm โดย bolue
note
โดย bolue พฤ 04 มิ.ย. 2020 10:31 am บอร์ด M104 - สุภาภรณ์ อินกรรไกร
0
2
พฤ 04 มิ.ย. 2020 10:31 am โดย bolue
list ความรู้ที่มี ว่าเคยเรียน หรือ เคยทำอะไรมาบ้าง
โดย bolue พฤ 04 มิ.ย. 2020 10:30 am บอร์ด M104 - สุภาภรณ์ อินกรรไกร
4
24
พฤ 04 มิ.ย. 2020 3:43 pm โดย bolue
Work's on Hand สุภาภรณ์ อินกรรไกร M104
โดย bolue พฤ 04 มิ.ย. 2020 10:29 am บอร์ด M104 - สุภาภรณ์ อินกรรไกร
0
3
พฤ 04 มิ.ย. 2020 10:29 am โดย bolue
งานประจำวันที่ 4 มิถุนายน 2563
โดย natthanit.r2538 พฤ 04 มิ.ย. 2020 9:57 am บอร์ด M103 - ณัฐนิตย์ ร่มบ้านโหล๊ะ
3
33
พฤ 04 มิ.ย. 2020 7:43 pm โดย thatsawan
งานประจำวันที่ 2 มิถุนายน 2563
โดย natthanit.r2538 อ 02 มิ.ย. 2020 10:11 am บอร์ด M103 - ณัฐนิตย์ ร่มบ้านโหล๊ะ
4
40
อ 02 มิ.ย. 2020 7:42 pm โดย natthanit.r2538
มารู้จักจังหวัดสงขลา เมืองสองทะเลกันค่ะ
โดย natthanit.r2538 อ 02 มิ.ย. 2020 4:27 pm บอร์ด M103 - ณัฐนิตย์ ร่มบ้านโหล๊ะ
0
7
อ 02 มิ.ย. 2020 4:27 pm โดย natthanit.r2538
ระบบบัญชีคืออะไร มีความสำคัญอย่างไร และจะทำอย่างไรหากต้องการวางระบบบัญชี
โดย natthanit.r2538 อ 02 มิ.ย. 2020 2:13 pm บอร์ด M103 - ณัฐนิตย์ ร่มบ้านโหล๊ะ
0
6
อ 02 มิ.ย. 2020 2:13 pm โดย natthanit.r2538