Solidity 102 #4: คนนี้อยู่ใน k อันดับแรกของ List มั้ย? ตอบได้ภายใน O(1)

ยินดีตอนรับสู่ตอนที่ 4 ของซีรี่ “Solidity 102”. ในตอนนี้เราก็ยังคงอยู่กับเนื้อหาเกี่ยวกับ data structure และเทคนิคในการเขียนโค้ด solidity อย่างมีประสิทธิภาพบน EVM ซี่รีส์นี้จึงเหมาะกับผู้อ่านที่พอคุ้นเคยกับภาษา solidity และเข้าใจคร่าวๆว่า EVM ทำงานอย่างไร

ความเดิมจากตอนที่แล้ว, จากที่เราได้ทำ List เก็บนักเรียนแล้วก็ทำให้ List นั้นมันเรียงนักเรียนตามคะแนนแบบมากไปหาน้อยได้แล้ว ตอนใกล้จบก็ได้ทิ้งท้ายไว้ว่า เอ๊ะ…ถ้าเราอยากรู้ว่านักเรียนคนนี้อยู่ในอันดับ top-k คนแรกของ List มั้ย จะทำยังไงดีให้ smart contract เรากิน gas น้อยๆ หรือ O(1) ซึ่งหมายความว่าปริมาณ gas ไม่เพิ่มตามแม้ว่าจำนวนนักเรียนใน List เราจะโคตรเยอะ

ภาพตัวอย่าง sorted list ที่มีนักเรียน 10 คน เรียงตามคะแนน , ในที่นี้ top-3 (k เท่ากับ 3) คนแรกได้แก่ สมหมาย, สมพร, สมปอง ถ้าถามว่า มานะ อยู่ใน top-3 คนแรกมั้ย ต้องสามารถตอบได้ว่า “ไม่อยู่” ภายใน O(1)

ในบทความนี้เราก็จะมาต่อกันที่ sorted list จากตอนที่แล้ว เพื่อจะเสริมให้ sorted list ของเรามีฟังก์ชันที่ตอบเราได้อย่างรวดเร็วว่านักเรียนคนนี้อยู่ใน top-k มั้ย

เริ่ม ☃️

วิธีตรงๆ 🛣

ถ้าอยากรู้ว่านักเรียน address นี้อยู่ใน top-k คนมั้ยหรอ … อ้าวก็ไล่หาตั้งแต่คนแรกไปเรื่อยๆสิจนถึงคนที่ k ถ้าเจอก็ตอบไปว่า “เจอ” ถ้าไล่ไปจนถึง k แล้วไม่เจอก็ตอบไปว่า “ไม่เจอ”

แต่วิธีนี้ก็อย่างที่เราเห็นคือ จำนวนการทำงานของเรามันเพิ่มตามค่า k
ซึ่งจากการทดลองของเราด้วย Truffle เราพบว่า

loop 1000 คน ใช้ gas 417685 
loop 2000 คน ใช้ gas 835685 
loop 5000 คน ใช้ gas 2089685 
loop 10000 คน ใช้ gas 4179685 

ซึ่งจริงๆเราน่าจะอาการหนักตั้งแต่ 2พัน คนแล้วแหละ … มากกว่า 2พัน คนแทบจะไม่ไหวละใน Ethereum ปัจจุบัน (แค่ถาม top-2000 อย่างเดียวยังไม่ทันทำอะไรเลย)
เพราะว่า gas ของทั้ง block นั้นอยู่ที่ประมาณ 8ล้าน

วิธี O(1) ✡️

แบ่ง List เก็บนักเรียนออกเป็น 2 Lists

• List แรกเรียก Active List
• List ที่สองเรียก Reserved List

Active List

• เก็บนักเรียนจำนวน k คน ที่มีคะแนนติดอันดับ top-k (อาจจะน้อยกว่า k คนได้ถ้าจำนวนนักเรียนทั้งหมดเลยที่เรามีดันน้อยกว่า k)
• ใน Active List นี้เราจะเรียงจากคะแนนน้อยไปคะแนนมากแทน เพราะว่าเวลาเราจะหาคนที่คะแนนน้อยสุดใน top-k เราก็รู้ได้ทันทีเลยว่าคนนั้นคือคนแรกใน Active List , พอมีคนใน Reserved List ได้คะแนนแซงขึ้นมา เราก็แค่สลับคนแรกใน Active List และคนแรกใน Reserved List (Reserved List จะเรียงจากคะแนนมากไปคะแนนน้อย)

Reserved List

• เก็บนักเรียนคนอื่นที่ไม่ได้อยู่ใน Active List (มีคะแนนน้อยกว่าคนที่คะแนนน้อยสุดใน Active List)
• ถ้ามีนักเรียนคนไหนใน Reserved List ที่ได้คะแนนมากกว่าคนที่มีคะแนนน้อยสุดใน Active List นักเรียนคนนั้นก็จะถูกใส่เข้าไปใน Active List จากนั้นคนที่อยู่ใน Active List ที่คะแนนน้อยสุดก็จะถูกย้ายมาใส่ใน Reserved List แทน
• Reserved List จะเรียงนักเรียนจากคะแนนมากไปคะแนนน้อย เพราะเวลาหาคนที่คะแนนมากสุดก็สามารถรู้ที่ทันทีว่าคือคนแรกของ Reserved List

ให้เราลองพิจารณา 2 Lists นี้ดู

เราจะพบว่ากับความสวยงามว่า ถ้าหากเรานำจุดเริ่มต้น(GUARD) ของ List ทั้งสองมาต่อกัน เราก็จะได้ List ดั้งเดิมก่อนถูกแยกออกเป็น 2 Lists นั่นเอง!

จากตรงนี้เราก็มาลองเขียนโค้ดกันดู

แรกสุดเราก็ประกาศ ตัวแปร , ฟังก์ชันหลัก และ ฟังก์ชันตัวช่วย ที่จำเป็นต้องใช้ออกมาให้หมดก่อน เพื่อที่เราจะได้มองเห็นภาพใหญ่

ภาพ ตัวแปร global ทั้งหมดใน contract ของเรา

ภาพฟังก์ชันหลักทั้งหมด

ภาพฟังก์ชันตัวช่วย (helper function) ทั้งหมด สังเกตุว่าจะใช้ชื่อขึ้นต้นด้วย _

เรามาเริ่มดูแต่ละฟังก์ชันกันได้เลย

ฟังก์ชัน addStudent

เพิ่มนักเรียนใหม่ โดยมีตัวแปร student แทน address ของนักเรียนและ score คือคะแนนตั้งต้นของนักเรียน

• แรกสุดเราไปเช็คก่อนว่ามีนักเรียนคนนี้อยู่แล้วหรือเปล่าด้วยฟังก์ชัน studentExisted ถ้ามีอยู่แล้วก็ revert ถ้าไม่มีอยู่ก็ทำการเพิ่มนักเรียน
• จากนั้นเราไปเซ็ต scores ให้ scores[student] = score
• หาตำแหน่งที่ต้องการจะเพิ่มนักเรียนคนใหม่นี้ด้วยฟังก์ชัน _findIndex
• เพิ่มนักเรียนเข้าไปตรงตำแหน่งที่ index ด้วยฟังก์ชัน _addStudent
• ทำการปรับสมดุลทั้ง 2 Lists ด้วยฟังก์ชัน _rebalanceLists

_rebalanceLists เป็นฟังก์ชันที่ค่อยดูแลให้ Active List นั้นมีนักเรียนอยู่ k คนหลังจากที่มีการ เพิ่มนักเรียน,ลบนักเรียน,อัพเดทคะแนนนักเรียน,เปลี่ยนแปลงค่า k

ฟังก์ชัน _rebalanceLists

• ใน loop แรกนั้น เราตอนการนำนักเรียนจาก Reserved List มาใส่ใน Active List ในกรณีที่ Active List มีนักเรียนน้อยกว่า k คนและใน Reserved List ยังมีนักเรียนเหลืออยู่
  ในแต่ละรอบที่เรา loop เราจะนำนักเรียนคนแรกใน Reserved List ออกจาก Reserved List แล้วเอาไปใส่ใน Active List นักเรียนคนนั้นก็จะกลายเป็นคนแรกใน Active List
• ใน loop ต่อมาก็คือในกรณีที่นักเรียนใน Active List นั้นเยอะเกิน k เราจะนำคนที่คะแนนน้อยสุดใน Active List (คนแรกของ Active List) ไปใส่ใน Reserved List จนกว่า Active List จะเหลือนักเรียน k คน

สำหรับฟังก์ชัน _addStudent นั้นก็แค่เช็คก่อนว่านักเรียนที่จะเพิ่มอยู่ใน Active List หรือ Reserved List จากนั้นก็นำนักเรียนที่จะเพิ่มมาต่อท้าย prevStudent (ตำแหน่งนักเรียนคนอื่นที่อยู่ใน List) เสร็จแล้วก็เพิ่มความยาวให้ List

ฟังก์ชัน _addStudent

ส่วน _removeStudent ก็คล้ายกับ _addStudent นักเรียนคนที่ถูกลบก็ให้ชี้ไปที่ address(0) ส่วนคนก่อนหน้า (prevStudent) ก็ให้ชี้ไปที่คนที่ต่อหลังคนที่ถูกลบ

ฟังก์ชัน _removeStudent

ตอนมาคือฟังก์ชัน _findIndex ซึ่งเป็นฟังก์ชันที่รับคะแนนเข้าไปแล้วจะไปหาตำแหน่งที่เหมาะสมให้ว่าคะแนนเท่านี้ควรอยู่ List ไหนและต่อจาก address ไหน

แต่ก่อนที่เราจะไปหาตำแหน่งที่เหมาะสมนั้นด้วย _findIndex เราต้องมีฟังก์ชันอีกตัวคือ _verifyIndex ที่ใช้เช็คว่าตำแหน่งนั้นเหมาะสมจริงรึเปล่า ซึ่งจะเป็น true ถ้า List ยังเรียงอยู่ และจะเป็น false ถ้า List ไม่เรียง

ฟังก์ชัน _verifyIndex

_verifyIndex จะรับ 4 พารามิเตอร์ได้แก่

1. prevStudent คือนักเรียนคนที่อยู่ข้างหน้า
2. newValue คือคะแนนของนักเรียนคนที่จะมาแทรกระหว่าง prevStudent กับ nextStudent
3. nextStudent คือนักเรียนคนที่ขณะนี้คือคนถัดจาก prevStudent
4. isActive คือ flag ที่เอาไว้บอกว่าตอนนี้เรากับกำลังตรวจสอบของ Active List หรือ Reserved List

ต่อมาก็คือฟังก์ชัน _findIndex

_findIndex เราสามารถแยกออกได้เป็น 3 กรณี

1. กรณีพิเศษ ซึ่งจะเกิดขึ้นเมื่อ newValue อยู่ระหว่าง Active List และ Reserved List ในกรณีนี้เราก็สามารถเพิ่มไปด้านหน้า Active List ได้ถ้ายังขนาดของ Active List ยังไม่ถึง k แต่ถ้าถึง k แล้วเราก็จะไปเพิ่มด้านหน้า Reserved List แทน
2. กรณีที่ newValue ควรอยู่ภาย Active List (newValue มากกว่าตัวแรกสุดของ Reserved List) เราก็ loop ตั้งแต่ตัวแรกของ Active List ไล่ไปแล้วใช้ฟังก์ชัน _verifyIndex ในการตรวจสอบว่าต่อหลังนักเรียนคนนี้เหมาะสมหรือเปล่า ถ้า _verifyIndex บอกว่า true ก็ return address ของนักเรียนที่จะไปต่อหลัง
3. กรณีที่ newValue ควรอยู่ภายใน Reserved List ซึ่งก็จะคล้ายกับกรณีที่ 2

ฟังก์ชัน removeStudent

ลบนักเรียน โดยมีตัวแปร student แทน address ของนักเรียนที่จะถูกลบ

• แรกสุดเราไปเช็คก่อนว่ามีนักเรียนคนนี้อยู่จริงหรือเปล่าด้วยฟังก์ชัน studentExisted ถ้าไม่มีอยู่ก็ revert เพราะถ้าไม่มีจะลบได้ไง …
• จากนั้นเราไปเซ็ต scores ให้ scores[student] = 0
• หานักเรียนคนก่อนหน้า นักเรียนคนที่จะโดนลบด้วยฟังก์ชัน _findPrevStudent
• ลบนักเรียนด้วยฟังก์ชัน _removeStudent
• ทำการปรับสมดุลทั้ง 2 Lists ด้วยฟังก์ชัน _rebalanceLists

เราจะเห็นว่ามีฟังก์ชันหน้าใหม่โผล่มาคือ _findPrevStudent

ฟังก์ชัน _findPrevStudent

ฟังก์ชัน _findPrevStudent จะเช็คว่านักเรียนอยู่ใน top-k มั้ย ถ้าอยู่ก็ไป loop ใน Active List ไล่ตรวจสอบไปเรื่อยๆด้วยฟังก์ชัน _isPrevStudent ถ้าไม่อยู่ก็ไป loop ใน Reserved List แทน

ฟังก์ชัน _isPrevStudent

_isPrevStudent ก็คล้ายๆกับ _verifyIndex โดยจะตรวจสอบว่า prevStudent ชี้ไปที่ student มั้ยแค่นั้น

ฟังก์ชัน updateScore

ใช้ในการอัพเดทคะแนนของนักเรียน

ง่ายๆก็คือเราก็ลบนักเรียนคนนั้นออกไปก่อน … 😀

แล้วเพิ่มนักเรียนคนนั้นเข้าไปใหม่ด้วยคะแนนใหม่ … เย่จบ 🤗

ฟังก์ชัน setAciveMaxSize

เอาไว้สำหรับเปลี่ยนค่า k

ก็คือเราแค่เปลี่ยนขนาดของ Active List

จากนั้นก็ไปเรียก _rebalanceLists

ฟังก์ชัน getTop

สำหรับกรณีที่เราต้องการ addresses ของนักเรียนทุกคนที่อยู่ใน Active List

ที่เราร่ายยาวมาทั้งหมดก็เพื่อ climax ของเรา isInTop ฟังก์ชันที่พอถามว่า นักเรียนคนนี้อยู่ใน k อันดับแรกของ List มั้ย? แล้วตอบได้ภายใน O(1)

ฟังก์ชัน isInTop

เย่จบ 😅

ซึ่งถ้าเราเข้าใจหมดว่าที่ผ่านมามันทำงานยังไง ตรงนี้ก็เข้าใจอยู่แล้วหละ 😉

สรุป

ถ้าใครเคยอ่านบทก่อนๆของซีรี่ย์นี้มา จะรู้ว่าปกติเราจะเขียนแบบ optimized ให้ดูด้วยหลังจากพูดถึงแบบ loop จบไปแล้ว ซึ่งฟังก์ชันแบบ addStudent, removeStudent และ updateStudent ก็สามารถ optimized ให้กลายเป็น O(1) ได้ ไม่ต้องมานั่ง loop ให้เสียเวลา ถ้าหากใครสนใจการ optimize สามารถใช้ไอเดียจากบทความก่อนหน้าได้

อย่างไรก็ตาม List ของเรานำเสนอนี้ยังสามารถปรับปรุงได้อีกมาก ถ้าหากใครมีความคิดเห็นอย่างไร ก็สามารถแสดงความคิดเห็นมาได้เลย

Band Protocol เป็นแพลตฟอร์มที่สนับสนุนให้ทุกคนมีส่วนร่วมในการสร้างข้อมูลที่ถูกต้องเข้าสู่โลก blockchain โดยพวกเราเป็นทีม developer ที่อยากจะเชื่อมต่อโลกความจริงกับโลกของ blockchain เข้าด้วยกัน และถ้าคุณเป็น developer ที่มีความสนใจในด้านนี้และอยากร่วมงานกับเรา ติดต่อเราได้ที่ talent@bandprotocol.com