de algorismoKratui++
Interpolation search : อยากเร็วก็ต้องเสี่ยง
  • ออเจ้าชอบความเร็วและความเสี่ยงใช่ฤๅไม่
    เช่นนั้นแล้วไซร้ Interpolation search คืออัลกอฯสำหรับออเจ้า

    ความเร็วระดับ O(log(log n)) มันหอมหวานเหลือเกิน แต่ก็มาพร้อมกับความเสี่ยงที่จะเกิดการ degrade เหลือเพียง O(n)

    อัลกอฯนี้พัฒนามาจาก Binary Search อีกทีหนึ่ง โดยแทนที่จะซอยลงที่ละครึ่ง ๆ เราก็ทำการเดาเสียว่าหากค่ากลางมีค่าเท่านี้แล้ว ค่าที่เราต้องการจะอยู่แถว ๆ ไหน (แน่นอนว่าต้องเรียงข้อมูล (sort) เสียก่อน)

    จริง ๆ โค้ดมันแทบจะเป็น Binary Search เลย เพียงแต่เราเปลี่ยนหลักการหาตัวตรงกลางให้เป็นไปตามนี้  แทนที่จะหาร 2 ง่าย ๆ เราจะทำการหาว่าคีย์ของเราเป็นกี่ % ของผลต่างของขอบช่วงค้นหา แล้วนำไปคูณกับขนาดของช่วงค้นหา 

    กำหนดให้

    1. mid คือตำแหน่งที่ใช้ในการเปลี่ยบเทียบค่ากับคีย์ (เสมือนค่ากลางของ Binary Search)
    2. low และ high คือขอบเขตการค้นหา
    3. source คืออาเรย์ (หรือเวกเตอร์) ที่จะค้นหา และ
    4. key คือค่าที่ต้องการค้นหา

    mid = low + ((key - source[low]) * (high - low)) / (source[high] - source[low]);

    1. int interpolationSearch(vector<int> source, int key) {
    2. int low = 0, high = source.size()-1, mid;

    3.   while (source[low] <= key and source[high] >= key) {
    4. mid = low +
    5. ((key - source[low]) * (high - low)) /
    6. (source[high] - source[low]);

    7. if(source[mid] < key)
    8. low = mid + 1;
    9. else if (source[mid] > key)
    10. high = mid - 1;
    11. else
    12. return mid;
    13. }
    14.  
    15. if(source[low] == key)
    16. return low;
    17. else
    18. return -1;
    19. }

    จากวิธีค้นหาแบบนี้แล้ว การค้นหาแบบนี้จะได้ผลที่ดีที่สุดเมื่อข้อมูลมีการกระจายตัวสม่ำเสมอ เช่น

    1, 2, 4, 5, 6, 9, 12, 15

    แต่จะแย่มากในการค้นหาชุดข้อมูลที่ไม่สม่ำเสมอ ซึ่งในกรณีนี้การใช้ Binary Search จะให้ผลที่ดีว่า เช่น

    1, 14, 66, 67, 102, 231, 541, 1098

    ฉะนั้นจงเลือกใช้ให้เหมาะกับประเภทข้อมูล ความเสี่ยงนั้นไม่ได้เกิดจากตัวอัลกอฯ
    แต่เกิดจากการที่เราไม่รู้ว่าเราทำอะไรอยู่

    Risk comes from not knowing what you are doing
    - Warren Buffett

Views

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

Log in