โครงสร้างข้อมูลประสิทธิภาพสูง: Set กับ Map

การปรับแต่งโค้ดใน Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

การนำ space/time complexity ไปใช้

ตอนนี้เรารู้จัก space complexity และ time complexity แล้ว!

จะนำความเข้าใจนี้ไปเขียนโค้ดให้มีประสิทธิภาพยิ่งขึ้นได้อย่างไร?

ด้วยการเลือกโครงสร้างข้อมูลที่เหมาะสม!

การปรับแต่งโค้ดใน Java

ระบบจัดการผู้ใช้

  • กำลังสร้างระบบจัดการผู้ใช้

  • ต้องตรวจสอบว่าชื่อผู้ใช้ที่กำหนด มีอยู่จริง หรือไม่

  • ใช้ list: ความซับซ้อน $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}
การปรับแต่งโค้ดใน Java

Set

  • คอลเลกชันของสมาชิกที่ไม่ซ้ำกัน ค้นหาได้รวดเร็ว
  • ความซับซ้อนเฉลี่ย $O(1)$ สำหรับการเพิ่ม ลบ และตรวจสอบว่ามีสมาชิกอยู่หรือไม่

โซลูชันระบบจัดการผู้ใช้ที่ปรับปรุงแล้ว:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}
การปรับแต่งโค้ดใน Java

Map

  • เหมือนพจนานุกรม คำ (key) -> คำนิยาม (value)
  • HashMap: ความซับซ้อนเฉลี่ย $O(1)$ สำหรับการดำเนินการ
public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}
การปรับแต่งโค้ดใน Java

เมธอด Hashcode

  • สิ่งที่ทำให้สิ่งเหล่านี้รวดเร็ว -> hashCode()
  • ในตัวอย่าง ArrayList เราไม่รู้ index ของชื่อผู้ใช้ที่ต้องการค้นหา
  • ด้วยเมธอด hashcode() เราสามารถแปลงออบเจ็กต์เป็น index ที่ใช้ค้นหาได้
  • ตัวอย่างเช่น pavlos.2020 -> 35189

pavlos.2020 ผ่านการประมวลผลด้วย hashcode ได้ผลลัพธ์เป็น 35189

การปรับแต่งโค้ดใน Java

การจัดทำดัชนีสมาชิก

  • HashMap และ HashSet มี array อยู่เบื้องหลัง
  • เมื่อเพิ่มสมาชิก:
    • Java เรียก hashCode() บนสมาชิกนั้นเพื่อได้ค่าจำนวนเต็ม
    • จากนั้นใช้ modulo กับค่านั้นเพื่อหาหมายเลข bucket

ตัวอย่าง:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!
การปรับแต่งโค้ดใน Java

Collision

  • เมื่อสมาชิกมากกว่าหนึ่งตัวตกอยู่ใน bucket เดียวกัน
    • เรียกว่า collision
  • ใช้ LinkedList สำหรับ bucket นั้น
  • นี่คือเหตุผลที่เราบอกว่าเป็น $O(1)$ โดยเฉลี่ย
การปรับแต่งโค้ดใน Java

ข้อควรจำ

การเลือกโครงสร้างข้อมูลก็เหมือนการเลือกเครื่องมือให้เหมาะกับงาน - ค้อน (ArrayList) เหมาะกับตะปู แต่ใช้ไม่ได้ผลกับสกรู (ซึ่ง Set อาจเหมาะกว่า)

กล่องเครื่องมือที่เปิดอยู่ มีค้อน ไขควง ประแจ และคีมวางเรียงกัน

การปรับแต่งโค้ดใน Java

มาฝึกกันเถอะ!

การปรับแต่งโค้ดใน Java

Preparing Video For Download...