การค้นหาโดยการประมาณช่วง

จากวิกิพีเดีย สารานุกรมเสรี

การค้นโดยการประมาณช่วง (อังกฤษ: Interpolation search) หรือในบางครั้งเรียกว่า การค้นโดยการคาดการณ์ (อังกฤษ: Predictive search, Extrapolation search) เป็นขั้นตอนวิธี (algorithm) สำหรับค้นหาค่าของคำหลัก (key value) ที่ได้รับ(อาจได้รับจากการพิมพ์) โดยทำการค้นหาจาก ดัชนีแถวลำดับหนึ่งๆที่ถูกจัดเรียงอย่างมีระเบียบแบบแผนแล้ว ซึ่งวิธีนี้คล้ายกับวิธีที่เราค้นหา รายชื่อในสมุดโทรศัพท์ของโทรศัพท์มือถือ

ในการค้นหาแต่ละขั้นตอนจะมีการคำนวณหรือ คาดการณ์ว่าสิ่งที่ค้นหานั้น น่าจะอยู่ที่ไหนของช่วงการค้นหาที่เหลือ แม้เทคนิคนี้จะมีลักษณะคล้ายกับการค้นแบบทวิภาค (Binary search) แต่ก็ไม่ใช่เสียทีเดียว ยกตัวอย่างเช่น การค้นหาหมายเลขโทรศัพท์ของนายสมชาย จะไม่ไปหาที่ตรงกลางของสมุดโทรศัพท์ แต่จะไปหายังตำแหน่งที่เริ่มต้นด้วยตัว “ส” โดยการประมาณว่าอยู่ที่ตรงหน้าที่เท่าไรของสมุดโทรศัพท์ แล้วค่อย ๆ เลือกหน้าต่อไปที่ใกล้เคียงที่สุดจนกว่าจะพบ ดังนั้น แทนที่จะใช้การค้นแบบทวิภาค (Binary search) ที่เริ่มต้นตรงกลางเสมอ ก็เปลี่ยนมาใช้การค้นโดยการประมาณช่วง (Interpolation Search) ซึ่งเป็นการค้นหาตำแหน่งโดยการประมาณ

ขั้นตอนวิธี[แก้]

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

กำหนดให้

  • low หมายถึง ค่าขอบล่าง
  • mid หมายถึง ค่ากึ่งกลาง
  • high หมายถึง ค่าขอบบน
  • Array[low] หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งขอบล่าง
  • Array[mid] หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งตามค่ากึ่งกลาง
  • Array[high] หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งขอบบน
  • toFind หมายถึง ค่าที่ต้องการค้นหา

โดยมีขั้นตอนการทำงานดังนี้

  1. เริ่มต้นให้ low = 0 และ high = ขนาดของแถวลำดับ  -1
  2. เริ่มการทำงานแบบวงวนด้วยเงื่อนไข Array[low] \le toFind และ Array[high] \ge tofind
  3. หาค่า mid จาก mid = low + \left( \frac{\left(toFind-Array[low]\right) \times \left(high-low\right)}{Array[high]-Array[low]} \right)
  4. เริ่มต้นเช็คเงื่อนไขภายในวงวนเพื่อปรับค่า low หรือ high
    1. ถ้า Array[mid] < toFind (ถ้าไม่ใช่ ข้ามไปทำข้อ 2.) ปรับค่า low เป็น low = mid+1
    2. ถ้า Array[mid] > toFind (ถ้าไม่ใช่ ข้ามไปทำข้อ 3.) ปรับค่า high เป็น high = mid-1
    3. ได้ค้นพบตำแหน่งของค่าที่ต้องการค้นหา ในแถวลำดับนี้แล้ว ทำการคืนค่ากลับ นั้นก็คือ คืนค่า mid กลับไป
  5. ขั้นตอนนี้หมายถึงปรับค่า low และ high ไปเรื่อยๆจนหลุดจากวงวนแล้วยังไม่พบ ตำแหน่งที่ต้องการค้นหาดังกล่าว ให้ทำการตรวจเงื่อนไขว่า ถ้า Array[low] = toFind (ถ้าไม่ใช่ ข้ามไปทำข้อ 6.) ถ้าใช่ หมายถึงค่า low คือค่าตำแหน่งของค่าที่ต้องการค้นหานั้นเอง ทำการคืนค่ากลับ คือ คืนค่า low กลับไป
  6. ขั้นตอนนี้หมายถึง ไม่สามารถหาตำแหน่งของค่าที่ต้องการค้นหาได้ ทำการคืนค่า  -1 กลับไป

รหัสเทียม[แก้]

 function interpolationSearch(int[] sortedArray, int toFind){
      // กำหนดให้ฟังก์ชันนี้ มีการรับค่าพารามิเตอร์เป็น แถวลำดับที่จะทำการค้นหา และ ค่าที่ต้องการค้นหา
      // และคืนค่าเป็นตำแหน่งของแถวลำดับที่เก็บค่า ตรงกับ ค่าของ tofind  ส่วนกรณีที่หาไม่พบจะคืน -1
 
  int low = 0;
  int high = sortedArray.length - 1;
  int mid;
 
  while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
    mid = low +
         ((toFind - sortedArray[low]) * (high - low)) /
         (sortedArray[high] - sortedArray[low]);
 
    if(sortedArray[mid] < toFind)
       low = mid + 1;
    else if (sortedArray[mid] > toFind)
       high = mid - 1;
    else
       return mid;
  }
 
  if(sortedArray[low] == toFind)
     return low;
  else
     return -1;  // กรณีที่หาไม่พบ จะคืนค่า -1
 }

ประสิทธิภาพการทำงาน[แก้]

การค้นโดยการประมาณช่วง (interpolation search) ในกรณีเฉลี่ยการค้นลักษณะนี้จะมีประสิทธิภาพเท่ากับ O\left(\log \log n\right) ซึ่งดีกว่าการค้นแบบทวิภาค (Binary search) ที่มีประสิทธิภาพเท่ากับ O\left(\log n\right) แต่ในกรณีโชคร้ายคือข้อมูลมีการกระจายไม่สม่ำเสมอเลย เช่น (1,2,4,8,16,..) การค้นหาลักษณะนี้จะมีประสิทธิภาพแย่ที่สุด ซึ่งจะกลายเป็นแบบการค้นแบบเชิงเส้น (Linear search) มีประสิทธิภาพเท่ากับ O\left(n\right) ดังนั้นการค้นโดยการประมาณช่วง (interpolation search) จะมีประสิทธิภาพดีเมื่อใช้กับข้อมูลที่ค่าของคำหลัก (key value) มีกระจายที่ค่อนข้างสม่ำเสมอ เช่น (1,3,4,5,7,9,10,…) และจะมีประสิทธิภาพดีที่สุดเมื่อใช้กับข้อมูลที่ค่าของคำหลัก (key value) มีกระจายอย่างสม่ำเสมอ (Uniformly Distributed) เช่น (1,2,4,6,8,10,..)

การนำไปประยุกต์ใช้งาน[แก้]

การประยุกต์ใช้งานของขั้นตอนวิธี การค้นโดยการประมาณช่วง (Interpolation Search) ที่เราพบเห็นกันบ่อยในชีวิตประจำวัน เช่น การค้นหารายชื่อในสมุดโทรศัพท์ของโทรศัพท์มือถือ การค้นหาคำในพจนานุกรมอิเลกทรอนิกส์ หรือในพจนานุกรมออนไลน์ การค้นหารายชื่อหนังสือผ่านระบบสารสนเทศ ของร้านหนังสือ ฯลฯ โดยบางครั้งก็มีการนำไปประยุกต์ใช้งานร่วมกับขั้นตอนวิธีอื่นๆเพื่อให้มีประสิทธิภาพมากขึ้นด้วย

ศึกษาเพิ่มเติม[แก้]

อ้างอิง[แก้]

  • Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison Wesley
  • Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.
  • Sedgewick, Robert (1990), Algorithms in C, Addison-Wesley
  • การค้นหาข้อมูล