Skip to content

ทำ Ranking/Leaderboard ด้วย Redis #2

โพสต์ที่แล้ว “ทำ Ranking/Leaderboard ด้วย Redis #1” แล้วผมทำ ranking แบบอันดับซ้ำกันและข้ามอันดับได้ คราวนี้ลองมาทำอีกแบบคืออันดับซ้ำกันและไม่มีการข้ามอันดับดูบ้าง  ranking ที่เราคาดหวังจะเป็นแบบนี้

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

สิ่งที่เรามีคือ 1) ข้อมูลที่เรียงลำดับตาม score ไว้แล้ว 2) ranking มันก็เรียงกันอยู่เหมือนกัน ดังนั้นนอกจากจากมี list ของผู้เล่นแล้ว ผมเลยตัดสินใจแยกอีก list นึง เป็น list ของ score เรียงลำดับด้วย score เพื่อใช้เป็น lookup table แบบนี้ ตั้งชื่อ key ของ sorted set ว่า scores ก็แล้วกัน

สมมุติว่าเราต้องการ rank ของ user03 ขั้นตอนการทำงานเป็นดังนี้ครับ

  1. หา score ของ user03 โดย zscore ranking user03  ซึ่งจะได้ score 900
  2. เอา score ที่ได้จากข้อ 1 ไปหาใน lookup table zrank scores 900 จะได้ rank ออกมาคือ 1 (index เริ่มด้วย 0)
  3. เอาผลจากข้อ 2 บวกด้วย 1 ก็จะได้ rank ของ user03 นั่นก็คือ 2

ส่วนตัวผมคิดว่าการ ranking แบบ non-skipped ranking ง่ายกว่าแบบแรก skipped ranking ประสิทธิภาพคงไม่ต่างกันมากเพราะใช้ O(1) และ O(log N) เหมือนกัน แต่ก็มี trade-off เพราะใช้ space เพิ่มขึ้นเพราะต้องมี list ของ scores เพิ่มขึ้นมาอีก

ส่วนวิธีหา upper/lower rank ก็คล้ายกันครับ เปลี่ยนแค่วิธีในการคำนวณ current rank เป็นอัลกอริทึมข้างบนแทนเท่านั้นเอง

ง่ายๆ เนอะ data structure นี่ก็สนุกดีนะ

Be First to Comment

Leave a Reply

Your email address will not be published.