บทความ IT เจ๋งๆ

ในบทความนี้เราจะพูดถึงวิธีทำให้ Code ของคุณเร็วขึ้นด้วย Sets ของ JavaScript ซึ่งโดยทั่วไปแล้วมี Crossover หลายอย่างระหว่างสิ่งที่ Array สามารถทำได้และสิ่งที่ Set สามารถทำได้ แต่การใช้ Set โดยรวมแล้วจะเกิดผลลัพธ์ด้านดีต่อ Runtime ขณะที่ Array ไม่สามารถทำได้ ในบทความนี้จะมีรายละเอียดในเรื่องนี้

Sets มีข้อแตกอย่างอย่างไรบ้าง

ข้อแตกต่างพื้นฐานเลยก็คือ Array เป็น Indexed Collection นั่นหมายถึง ค่าของข้อมูลใน Array นั้น จะถูกจัดเรียงตาม Index

ในทางตรงกันข้าม Sets เป็น Keyed Collection โดยในการจัดเรียงลำดับ Sets กลับใช้ Keys แทนที่จะใช้ Index ส่วน Element ของ Set สามารถทำงานวนแบบซ้ำ ๆ ได้ (Iterable) ตามลำดับของการแทรก (Insertion) และไม่สามารถมีข้อมูลที่ซ้ำซ้อน (Duplicate) กันได้ กล่าวอีกนัยก็คือ ทุก Item ใน Set จะต้องไม่มีการซ้ำกัน (Unique)

- ข้อดีหลัก ๆ มีอะไรบ้าง

หากเปรียบเทียบกันตรง ๆ Sets มีข้อดีหลายอย่างเหนือ Array โดยเฉพาะอย่างยิ่งเมื่อมันมี Run-Time ที่เร็วยิ่งขึ้น:

• Search for an Item : ใช้ indexOf() หรือ include() เพื่อตรวจสอบว่า Item ที่อยู่ใน Array นั้นช้าหรือไม่
• Deleting an Item : ใน Set คุณสามารถ Delete Item ด้วยใช้ค่าของมันได้เลย หากเปรียบเทียบกับ Array มันก็เหมือนกับการใช้ splice() ขึ้นอยู่กับ Index ของ Element
• Insert an Item : การ Add Item ใน Set เร็วกว่าการ Add Item ไปยัง Array โดยใช้ push(), unshift() หรือ Method ใดก็ตามที่คล้ายกัน
• Storing NaN : คุณไม่สามารถใช้ indexOf() หรือ include() เพื่อหาค่า NaN ได้ ในขณะที่ Set สามารถเก็บค่านี้ได้
• Removing Duplicates : Set objects สามารถเก็บค่าที่เป็น Unique เท่านั้น หากคุณต้องการหลีกเลี่ยงการเก็บข้อมูลที่ Duplicate ซึ่งนี่ถือเป็นข้อได้เปรียบสำคัญที่อยู่เหนือ Array ที่จำเป็นต้องใช้การ Code เพิ่มเติมเข้าไปเพื่อที่จะจัดการกับข้อมูล Duplicate

หมายเหตุ: คุณสามารถดู List ทั้งหมดของ In-built Set Methods ได้ที่ MDN Web Docs

- เกี่ยวกับ Time Complexity

โดยทั่วไป Methods ที่ Array ใช้ในการ Search Item มี Time Complexity เป็นแบบ Linear ซึ่งคือ O(N) กล่าวอีกนัยหนึ่ง ก็คือ Rum-Time จะเพิ่มมากขึ้นในอัตราเดียวกันกับขนาดของข้อมูลที่เพิ่มขึ้น

ในทางตรงกันข้าม Methods ที่ Sets ใช้ในการ Search, Delete และ Insert Item ทั้งหมดมี Time Complexity เป็น O(1) นั่นหมายความว่า ขนาดของข้อมูลแทบไม่มีผลต่อ Rum-Time ของ Method เหล่านี้!

หมายเหตุ: หากคุณต้องการเรียนรู้เพิ่มขึ้นเกี่ยวกับ Time Complexity สามารถลองอ่านเพิ่มเติมได้ที่ บทความเกี่ยวกับ Big O Notation

- Sets เร็วกว่ามากน้อยแค่ไหน

แม้ว่า Rum-Time อาจจะแตกต่างกันกันไปขึ้นอยู่กับ System ที่ใช้, ขนาดของข้อมูล และตัวแปรอื่น ๆ แต่หวังว่าผลการ Test เหล่านี้จะแสดงให้เห็นว่า Sets เร็วกว่าแค่ไหน ลองดูการ Test ใน 3 ตัวอย่างนี้รวมทั้งผลที่ได้:

- เตรียมการ Test

ก่อนที่จะดำเนินการ Test ใด ๆ ให้ทำการสร้าง Array และ Set ให้มีข้อมูลอย่างละ 1,000,000 ข้อมูล โดยเพื่อให้มันง่าย จะเริ่มต้นที่ 0 ไปจนถึง 999,999

Test 1: การ Search Item

ก่อนอื่น ทำการ Search หาหมายเลข 123123

Array: 0.173 ms, Set: 0.023 ms

จะเห็นว่า Set ทำได้เร็วกว่า 7.54 เท่า

Test 2: การ Add Item

คราวนี้ มา Add Item ใหม่เข้าไปในแต่ละ Collection

Array: 0.018 ms, Set: 0.003 ms

จะเห็นว่า Set ทำได้เร็วกว่า 6.73 เท่า

Test 3: การ Delete Item

สุดท้าย ทำการ Delete Item ออกจากแต่ละ Collection (เราสามารถใช้ Item ที่เราเพิ่ง Add เข้าไปก็ได้) เราจะไม่ใช้ In-Built Array Method ในการดำเนินการนี้ ดังนั้น เราจึงสร้าง Function ตัวช่วย ขึ้นมาเพื่อให้ทุกอย่างเท่าเทียมกัน:

และนี่คือ Code สำหรับการ Test:

Array: 1.122 ms, Set: 0.015 ms

ในตัวอย่างนี้ จะเห็นว่า Set ทำได้เร็วกว่าถึง 74.13 เท่า

โดยรวมแล้ว เราจะเห็นว่าการ Improvement ใน Run-Time สามารถทำได้โดยใช้ Set แทนที่จะใช้ Array คราวนี้เรามาดูตัวอย่างในทางปฏิบัติที่เราสามารถจะใช้ประโยชร์จาก Set กัน

Case 1: การ Remove Duplicate Values จาก Array

หากคุณต้องการ Remove Duplicate Values ออกจาก Array อย่างรวดเร็ว คุณสามารถ Convert มันไปเป็น Set ได้ นี่เป็นวิธีที่สั้นกระชับที่สุดในการ Filer ค่าที่เป็น Unique:

Case 2: คำถามสัมภาษณ์งานของ Google

ในบทความหนึ่ง เป็นการ Discuss เกี่ยวกับ 4  Solutions ในการตอบคำถามสัมภาษณ์งานของ Google การสัมภาษณ์จะเน้นการถามในภาษา C++ แต่ถ้าใน JavaScript แล้ว Set จะเป็นส่วนที่จำเป็นในการแก้ปัญหาขั้นสุดท้าย

หากคุณต้องการดู Solution ในเชิงลึกยิ่งขึ้น ก็ขอแนะนำให้อ่านจากบทความข้างต้น แต่นี่คือ สรุปโดยย่อของวิธีแก้ปัญหาขั้นสุดท้าย

• Question

กำหนด Array ของ Integer แบบไม่เรียงลำดับ และผลรวม มาให้ โดยที่ หากมี 2 รายการใด ๆ ที่ถูกเพิ่มเข้าไปแล้วมีค่าเท่ากับผลรวม ให้ Return ค่า True นอกนั้นให้ Return ค่า False

กรณีที่เรามี Array [3, 5, 1, 4] และค่า 9 ดังนั้น Function ของเราควรจะ Return ค่า True กลับมาให้ เนื่องจาก 4 + 5 = 9

• Solution

วิธีการที่เหมาะสมสำหรับคำถามนี้ ก็คือ การใช้วิธี Iterate (วนซ้ำ ๆ ) ผ่าน Array, จากนั้นสร้าง Set of compliments

ลองประยุกต์ใช้ความคิดนี้กับตัวอย่างด้านบน เมื่อเราพบเลข 3 เราก็สามารถเพิ่ม 6 เข้าไปใน Set of compliments ของเราเพราะเรารู้ว่าต้องการหาผลรวมให้ได้เท่ากับ 9 จากนั้นทุกครั้งที่เราเจอกับค่าใหม่ใน Array เราสามารถตรวจสอบเพื่อดูว่ามันอยู่ใน Set of compliments ของเราหรือไม่ เมื่อเราไปถึง 5 เราก็จะเพิ่ม 4 ใน Set of compliments ของเรา จากนั้นเมื่อเราพบ 4 ในที่สุดเราก็จะพบมันใน Set ของเราและเพื่อให้เราสามารถ Return ค่า True กลับมา

นี่คือหน้าตาของ Solution ที่น่าจะเป็น:

และนี่เป็น Version ที่ที่สั้นกระชับยิ่งกว่าเดิม:

เนื่องจาก Set.prototype.has() มี Time Complexity เพียง O(1) การใช้ Set เพื่อเก็บ Compliments แทน Array จะช่วยให้ Solution โดยรวมของเรามี Linear Run-Time ของ O(N)

ถ้าเราพึ่งพา Array.prototype.indexOf() หรือ Array.prototype.includes() แทน ซึ่งทั้งคู่มี Time Complexity เป็น O(N), Run-Time โดยรวมน่าจะเป็น O(N²) ซึ่งมันช้ามาก!

ที่มา:  https://medium.com/