Solidity 102 #3: จัดการ List อย่างไรให้ List เรียงถูกต้องอยู่เสมอ

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

จากบทความที่แล้วเราได้พูดถึงโครงสร้างข้อมูลที่สามารถ เพิ่ม/ลบ/ถามว่าข้อมูลนี้อยู่หรือไม่อยู่ ได้อย่างรวดเร็ว ( O(1) ) คราวนี้เราจะมาพูดเพิ่มเติมจากครั้งที่แล้ว ซึ่งก็คือทำอย่างไรให้ข้อมูลเหล่านั้นถูกเรียงอยู่ตลอดเวลาด้วยแม้ว่าจะโดน เพิ่ม/ลบ สมาชิก ในบทความนี้เราก็จะค่อยๆอธิบายทีละฟังก์ชันไปเรื่อยๆ โอเค ถ้าพร้อมแล้วไปลุยกัน!!

โจทย์ตัวอย่าง

เราต้องการสร้าง smart contract “School” (อีกละหรอ …) แต่ว่าวันนี้เราไม่ได้แค่จะถามว่า address ของคนนี้อยู่ใน List ของนักเรียนหรือเปล่า แต่เรายังอยากจะเรียงลำดับนักเรียนภายใน List ตามคะแนนของนักเรียนอีกด้วย โดยครูสามารถลดหรือเพิ่มคะแนนของนักเรียนคนไหนก็ได้และเราสามารถการันตีได้เลยว่าไม่ว่ายังไง List ของนักเรียนก็จะยังเรียงตามคะแนนอยู่ตลอดเวลา และสุดท้ายเรายังสามารถแจกแจงนักเรียนที่มีคะแนนสูง k (k คือจำนวนนับใดๆเช่น 1,2,3,…) อันดับแรกออกมาได้อีกด้วย ซึ่งสามารถทำให้เราแจกรางวัลให้นักเรียนตัวท๊อป k คนนั้นแบบ on-chain ได้อย่างง่ายดาย

โอเคจากที่เล่ามาข้างต้น มีฟังก์ชั่นที่ต้องเขียนทั้งหมด 5 ฟังก์ชัน ได้แก่

1. เพิ่มนักเรียนใหม่เข้าไปใน List พร้อมกับใส่คะแนนตั้งต้นให้นักเรียนคนนั้น
2. เพิ่มคะแนนของนักเรียนคนไหนก็ได้ที่อยู่ใน List
3. ลดคะแนนของนักเรียนคนไหนก็ได้ที่อยู่ใน List
4. ลบนักเรียนออกจาก List
5. ถามได้ว่านักเรียนที่คะแนนท๊อป k คนแรกมีใครบ้าง

ทีนี้ก่อนที่เราจะเริ่มเขียนแต่ละฟังก์ชัน เราต้องเลือกโครงสร้างข้อมูลตั้งต้นก่อนว่าจะใช้อะไร (เช่น Array, List, ArrayList, Map, etc)
ในกรณีนี้เราขอเริ่มที่ Iterable Map จาก บทความที่แล้ว เริ่มจากสร้าง mapping ใน solidity เพื่อเอาไว้เก็บ score และขึ้นโครงของแต่ฟังก์ชัน 5 ฟังก์ชันนั้นรอไว้ได้เลย หน้าตาก็จะออกมาประมาณภาพด้านล่าง

function ทั้งหมดที่เราต้องการใช้

** GUARD หมายถึงจุดเริ่มต้นหรือ header ของ List **

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

มาเริ่มกันที่ฟังก์ชันแรก สังเกตุว่ามีจุดที่แตกต่างกับ Iterable Map ปกติ นั่นก็คือของที่เราจะใส่เข้าไปนั้น เราต้องใส่ให้ถูกตำแหน่ง เพราะว่า List ต้องเรียงอยู่เสมอในขณะที่ Iterable Map ปกติ เวลาเราจะเพิ่มข้อมูลเราแค่เอาข้อมูลใหม่ไปต่อหน้าสุดของ List เท่านั้น ไม่จำเป็นต้องสนใจตำแหน่ง

List ในภาพเรียงจากมากไปน้อยเพิ่มให้ง่ายต่อการหานักเรียนท๊อป k คนแรก ภาพนี้แสดงการใส่นักเรียนคนใหม่ (Dave) ซึ่งมีคะแนน 37 นั้นต้องใส่ให้ถูกตำแหน่งที่ควรจะอยู่เรียงตามคะแนน

ต่อมาเพิ่มให้การเขียนโค้ดสะดวกขึ้นเราก็สร้างฟังก์ชันตัวช่วย (helper function) ขึ้นมา 2 ฟังก์ชัน อันนึงเพื่อหาตำแหน่ง อีกอันเอาไว้ตรวจสอบความถูกต้องของตำแหน่ง

1. _verifyIndex คือฟังก์ชันที่ใช้ตรวจสอบว่า คะแนนของนักเรียนใหม่ที่ใส่เข้ามานั้นน้อยกว่าหรือเท่ากับคะแนนของนักเรียนคนก่อนหน้าและมากกว่าคะแนนของนักเรียนคนถัดไป ฟังก์ชันจะ return true ถ้า left_value ≥ new_value > right_value (การที่เราบอกว่าน้อยกว่าเท่ากับคะแนนคนก่อนหน้าเพราะว่า ถ้าเกิดนักเรียนคะแนนเท่ากันเราจะเอาคนที่มาที่หลังไปต่อคนที่มาก่อน)

2. _findIndex เป็นฟังก์ชันรับคะแนนของนักเรียนแล้วจะช่วยหาว่าคะแนนเท่านี้ต้องไปต่อหลังนักเรียนคนไหน โดยจะ return มาเป็น address นักเรียน
เราก็แค่เริ่ม loop จาก GUARD (จุดตั้งต้นของ List) ไปเรื่อยๆเพื่อหา index ที่เหมาะสม ซึ่งในแต่ละ loop เราก็จะไปถามฟังก์ชัน _verifyIndex

addStudent จะสามารถเพิ่มนักเรียนได้ตามลำดับที่ถูกต้องจากนั้นอัพเดทคะแนนและขยายขนาดของ List ตามไปด้วย

ฟังก์ชัน removeStudent : ลบนักเรียนออกจาก List

removeStudent นั้นเขียนโค้ดเหมือนกับบทความก่อนหน้าได้เลย เพราะว่าการลบข้อมูลออกจาก List ที่เรียงแล้วนั้นเราสามารถบอกได้เลยว่า List ก็ยังคงเรียงอยู่โดยใช้สมบัติการถ่ายทอด (transitive property) ที่ว่า ถ้า a ≥ b ≥ c แล้ว a ≥ c เพราะฉนั้น List ของเราก็เลยยังเรียงอยู่แม้จะลบ b ออกไปจาก List แล้ว

ภาพแสดงการลบ Bob ผู้มีคะแนนเท่ากับ 40 ออกจาก List

สร้างฟังก์ชันตัวช่วยมาอีก 2 ฟังก์ชัน _isPrevStudent และ _findPrevStudent

จากนั้นเขียน removeStudent เหมือนในบทความที่แล้ว จากนั้นเพิ่มการเคลียร์ mapping ของ scores

ฟังก์ชัน increaseScore และ reduceScore: เพื่ออัพเดท(เพิ่ม/ลด)คะแนนนักเรียน

increaseScore และ reduceScore นั้นสามารถเขียนโดยใช้หลักคิดเดียวกันได้เลย คือ ต้องการจะอัพเดทหรอ? ก็ลบของเก่าออกจาก List สิ จากนั้นใส่ของใหม่เข้าไปแทน นี่ไงอัพเดทแล้ว
แนวคิดนี้ยังมีข้อดีอีกอย่างคือเราสามารถ reuse ฟังก์ชัน addStudent และ removeStudent ได้ด้วย

** เราสามารถตรวจสอบก่อนได้ด้วยว่า คะแนนใหม่ที่อัพเดทในนักเรียนคนนี้เนี่ย มันทำให้นักเรียนคนนี้เปลี่ยนตำแหน่งมั้ย ถ้าไม่เปลี่ยนเราก็แค่อัพเดทคะแนนจบ ไม่ต้องไป add/remove อะไรให้เปลือง gas (optimization นี้ช่วยให้ประหยัดไปประมาณ 1000 gas) **

พอเรามีฟังก์ชัน updateScore แล้ว ชีวิตง่ายขึ้นเพราะสามารถเขียน increaseScore และ reduceScore ได้ใน 1 บรรทัด

ฟังก์ชัน getTop : เพื่อเอา List ของนักเรียนที่ได้คะแนนสูงสุดจำนวน k คนแรก

ก็ไม่มีอะไรแฟนซี เราก็แค่ใส่ k เป็นพารามิเตอร์ของฟังก์ชัน เพื่อบอกว่าจะเอาที่คน และในฟังก์ชันก็ loop ตั้งแต่จุดเริ่มต้นของ List ไปเรื่อยๆ k ครั้ง แต่ละครั้งจะจับ address นักเรียนใส่ List ที่เป็น memory พอ loop เสร็จก็ return List ก้อนนั้นออกไป

สามารถเข้าไปดูโค้ดได้ที่นี่

โบนัส สำหรับการหา index ที่ดีขึ้น

ถ้าหากว่าเรา loop หา index แบบ on-chain ก็จะทำให้ gas นั้นเพิ่มตามความยาวของ List

วิธีแก้คือเราก็แค่ส่ง address ของคนที่เราจะไปต่อท้ายเข้าไปด้วยเลย ที่เหลือ on-chain ก็แค่ verify ว่าที่เราส่งมานั้นมันถูกต้อง ไม่เห็นต้องไปนั่ง loop หาแบบ on-chain เลยนี่นา (สำหรับการอัพเดทคะแนนของนักเรียนนั้นเราต้องเพิ่ม address ไป 2 addresses คือจะลบตรง address ไหน ต่อมาคือจะไปเพิ่มต่อท้าย address ไหน) และเราก็สามารถใช้ฟังก์ชัน _verifyIndex ในการตรวจสอบได้เลย นี่คือสาเหตุที่ทำไมเราแยก _verifyIndex ออกมาเป็นฟังก์ชันตัวช่วย
โอเคลองไปดูโค้ดกัน

addStudent

เราเพิ่ม require มา 2 requires
อันแรกคือตรวจสอบว่า candidateStudent นั้นมีอยู่ใน List จริงมั้ย
อันที่สองคือตรวจสอบว่านักเรียนใหม่ที่ใส่เข้ามานั้นคะแนนต้องต่อจาก candidateStudent

removeStudent

ตรวจสอบนักเรียนที่จะลบกับนักเรียนคนก่อนหน้าด้วยฟังก์ชัน _isPrevStudent ก่อนที่จะลบนักเรียนคนนั้นออกจาก List

updateScore

สำหรับ updateScore ในกรณีที่อัพเดทแล้วนักเรียนคนนั้นยังอยู่ตำแหน่งเดิม เราก็ตรวจสอบแบบเดียวกับ removeStudent จากนั้นก็ตรวจสอบว่าคะแนนใหม่ที่อัพเดทมานั้นยังทำให้ตำแหน่งนั้นเหมือนเดิม

ดูโค้ดฉบับเต็มได้ที่นี่

สรุป

ในบทความนี้เราก็ได้อธิบายการทำงาน + เขียนโค้ดของ Sorted List ซึ่งเป็นโครงสร้างข้อมูลที่เพิ่มเติมต่อจาก Iterable Map เพื่อที่จะทำให้ List แบบ on-chain ของเรานั้นเรียงตาม value ที่เราเป็นคนกำหนด (ในกรณีตัวอย่างคือเรียงตามคะแนนนักเรียน) โดยที่เราสามารถ เพิ่ม/ลบ ข้อมูล รวมถึงอัพเดท value ของข้อมูลใน List นอกจากนี้เรายังพูดถึงการ optimize เพิ่มประหยัด gasในการหาตำแหน่งของนักเรียน (ไม่ต้อง loop บน chain)
ในบทความถัดไปเราจะมาพูดต่อจาก Sorted List นี้อีก โดยเราจะดัดแปลงมันให้สามารถตอบเราได้ว่านักเรียนคนนี้(address นี้) อยู่ในกลุ่มที่มีคะแนนเป็นอันดับท๊อป k คนแรกมั้ย? ภายใน O(1)!
โอเคหวังว่าบทความของเราจะเป็นประโยชน์กับผู้อ่านที่ท่าน หากมีคอมเม้นอะไรก็สามารถคอมเม้นมาได้เลย แล้วเจอกันในบทความหน้าครับ

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